Page 242 -

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

all

Figure 5.8 Star-Cubing: bottom-up computation with top-down expansion of shared dimensions.

A extending from AD would also be pruned because it was already computed in
ACD/A.
Shared dimensions allow us to do Apriori-like pruning if the measure of an iceberg
cube, such as count, is antimonotonic. That is, if the aggregate value on a shared dimen-
sion does not satisfy the iceberg condition, then all the cells descending from this shared
dimension cannot satisfy the iceberg condition either. These cells and their descendants
can be pruned because these descendant cells are, by definition, more specialized (i.e.,
contain more dimensions) than those in the shared dimension(s). The number of tuples
covered by the descendant cells will be less than or equal to the number of tuples covered
by the shared dimensions. Therefore, if the aggregate value on a shared dimension fails
the iceberg condition, the descendant cells cannot satisfy it either.

Example 5.6 Pruning shared dimensions. If the value in the shared dimension A is a 1 and it fails
to satisfy the iceberg condition, then the whole subtree rooted at a 1 CD/a 1 (including
a 1 C/a 1 C, a 1 D/a 1 , a 1 /a 1 ) can be pruned because they are all more specialized versions
of a 1 .

To explain how the Star-Cubing algorithm works, we need to explain a few more
concepts, namely, cuboid trees, star-nodes, and star-trees.
We use trees to represent individual cuboids. Figure 5.9 shows a fragment of the
cuboid tree of the base cuboid, ABCD. Each level in the tree represents a dimension, and
each node represents an attribute value. Each node has four fields: the attribute value,
aggregate value, pointer to possible first child, and pointer to possible first sibling. Tuples
in the cuboid are inserted one by one into the tree. A path from the root to a leaf node
represents a tuple. For example, node c 2 in the tree has an aggregate (count) value of 5,