Page 245 -

HAN
12-ch05-187-242-9780123814791

208 Chapter 5 Data Cube Technology 2011/6/1 3:19 Page 208 #22

traversal order. The remaining four trees are BCD, ACD/A, ABD/AB, and ABC/ABC.
They are the child trees of the base star-tree, and correspond to the level of 3-D cuboids
above the base cuboid in Figure 5.8. The subscripts in them correspond to the same
subscripts in the base tree—they denote the step or order in which they are created
during the tree traversal. For example, when the algorithm is at step 1, the BCD child
tree root is created. At step 2, the ACD/A child tree root is created. At step 3, the ABD/AB
tree root and the b∗ node in BCD are created.
When the algorithm has reached step 5, the trees in memory are exactly as shown
in Figure 5.11. Because depth-first traversal has reached a leaf at this point, it starts
backtracking. Before traversing back, the algorithm notices that all possible nodes in the
base dimension (ABC) have been visited. This means the ABC/ABC tree is complete, so
the count is output and the tree is destroyed. Similarly, upon moving back from d∗ to
c∗ and seeing that c∗ has no siblings, the count in ABD/AB is also output and the tree
is destroyed.
When the algorithm is at b∗ during the backtraversal, it notices that there exists a
sibling in b 1 . Therefore, it will keep ACD/A in memory and perform a depth-first search

root:5 1 BCD:5 1 a CD/a :3 2 a b*D/a b*:1 3 a b*c*/a b*c*:1 4
1
1
1
1
1
1
:3 a :2 b*:1 c*:1 d*:1
a 1 2 2 3 4 5
b*:1 3 b 1 :2 b*:2 c*:1 4 d*:1 5
c*:1 4 c*:2 c 3 :2 d*:1 5

d*:1 5 d*:2 d :2
4
Base Tree BCD–Tree ACD/A–Tree ABD/AB–Tree ABC/ABC–Tree

Figure 5.11 Aggregation stage one: processing the leftmost branch of the base tree.

root:5 1 BCD:5 1 a CD/a :3 2 a b D/a b :2 6 a b c*/a b c*:2 7
1
1 1
1 1
1 1
1 1
1
a :3 2 a :2 b*:1 3 b :2 6 c*:3 7 d*:2 8
2
1
1
x b :2 6 b*:2
1
c*:1 4 c*:2 7 d*:3 8
c*:2 7 c 3 :2 d*:1 5 d*:2 8
d*:2 8 d :2
4
Base Tree BCD–Tree ACD/A–Tree ABD/AB–Tree ABC/ABC–Tree
Figure 5.12 Aggregation stage two: processing the second branch of the base tree.