Page 236 -

12-ch05-187-242-9780123814791
#13
3:19 Page 199
2011/6/1
HAN
5.2 Data Cube Computation Methods 199

a a a a
2 3
0 1
c 3 c 3
b 3 b 3

c 2
b 2 b 2 c 2
AC
AB
c 1
b 1 * b 1 * * * * c 1
*

* *
b 0 * b 0 * * * * c 0 * * * * * * c 0
* *
*
a a a a
B A * * * * * * C 0 1 2 3
a a a a
0 1
2 3
(a) (b)

Figure 5.4 Memory allocation and computation order for computing Example 5.4’s 1-D cuboids.
(a) The 1-D cuboids, A and B, are aggregated during the computation of the smallest 2-D
cuboid, AB. (b) The 1-D cuboid, C, is aggregated during the computation of the second
smallest 2-D cuboid, AC. The ∗’s represent chunks that, so far, have been aggregated to.

which is faster than ROLAP’s key-based addressing search strategy. For ROLAP cube
computation, instead of cubing a table directly, it can be faster to convert the table
to an array, cube the array, and then convert the result back to a table. However,
this observation works only for cubes with a relatively small number of dimensions,
because the number of cuboids to be computed is exponential to the number of
dimensions.
“What would happen if we tried to use MultiWay to compute iceberg cubes?” Remember
that the Apriori property states that if a given cell does not satisfy minimum support,
then neither will any of its descendants. Unfortunately, MultiWay’s computation starts
from the base cuboid and progresses upward toward more generalized, ancestor cuboids.
It cannot take advantage of Apriori pruning, which requires a parent node to be com-
puted before its child (i.e., more specific) nodes. For example, if the count of a cell c in,
say, AB, does not satisfy the minimum support specified in the iceberg condition, we
cannot prune away cell c, because the count of c’s ancestors in the A or B cuboids may
be greater than the minimum support, and their computation will need aggregation
involving the count of c.