COMP9318 (20T1) ASSIGNMENT 1 Solved

Q1. (40 marks)

Consider the following base cuboid Sales with four tuples and the aggregate function

SUM:

Location, Time, and Item are dimensions and Quantity is the measure. Suppose the system has built-in support for the value ALL.

1. (1)  List the tuples in the complete data cube of R in a tabular form with 4 attributes, i.e., Location, T ime, Item, SUM(Quantity)?
2. (2)  Write down an equivalent SQL statement that computes the same result (i.e., the cube). You can only use standard SQL constructs, i.e., no CUBE BY clause.
3. (3)  Consider the following ice-berg cube query:

             SELECT  Location, Time, Item, SUM(Quantity)
   

          FROM    Sales
          CUBE BY Location, Time, Item
          HAVING  COUNT(*) > 1

Draw the result of the query in a tabular form.
(4) Assume that we adopt a MOLAP architecture to store the full data cube of R, with

the following mapping functions:
1 if x = ‘Sydney’,



2 if x = ‘Melbourne’, 0 ifx=ALL.

1 if x = 2005, 

fLocation(x) =

fTime(x) = 2 if x = 2006,

0 ifx=ALL. 1

2

DUE ON 20:59 12 APR, 2020 (SUN)

1 if x = ‘PS2’,
2 if x = ‘XBox 360’, 3 if x = ‘Wii’,
0 ifx=ALL.

Draw the MOLAP cube (i.e., sparse multi-dimensional array) in a tabular form of (ArrayIndex,Value). You also need to write down the function you chose to map a multi-dimensional point to a one-dimensioinal point.

Q2. (30 marks)

fItem(x) =

Consider the given similarity matrix. You are asked to perform group average hierar- chical clustering on this dataset.

You need to show the steps and final result of the clustering algorithm. You will show the final results by drawing a dendrogram. The dendrogram should clearly show the order in which the points are merged.

Q3. (30 marks)

1 2 3 4 5 6 7

8 9

10

Data: D is a dataset of n d-dimensional points; k is the number of clusters. Initialize k centers C = [c1, c2, . . . , ck];
canStop ← false;
while canStop = false do

Initialize k empty clusters G = [g1, g2, . . . , gk]; for each data point p ∈ D do

cx ← NearestCenter(p, C); gcx .append(p);

for each group g ∈ G do
ci ← ComputeCenter(g);

return G;

Algorithm 1: k-means(D, k)

Consider the (slightly incomplete) k-means clustering algorithm as depicted in Algo- rithm 1.