Page 237 -

HAN
12-ch05-187-242-9780123814791

200 Chapter 5 Data Cube Technology 2011/6/1 3:19 Page 200 #14

5.2.2 BUC: Computing Iceberg Cubes from the Apex
Cuboid Downward
BUC is an algorithm for the computation of sparse and iceberg cubes. Unlike MultiWay,
BUC constructs the cube from the apex cuboid toward the base cuboid. This allows BUC
to share data partitioning costs. This processing order also allows BUC to prune during
construction, using the Apriori property.
Figure 5.5 shows a lattice of cuboids, making up a 3-D data cube with the dimensions
A, B, and C. The apex (0-D) cuboid, representing the concept all (i.e., (∗, ∗ , ∗)), is at
the top of the lattice. This is the most aggregated or generalized level. The 3-D base
cuboid, ABC, is at the bottom of the lattice. It is the least aggregated (most detailed or
specialized) level. This representation of a lattice of cuboids, with the apex at the top
and the base at the bottom, is commonly accepted in data warehousing. It consolidates
the notions of drill-down (where we can move from a highly aggregated cell to lower,
more detailed cells) and roll-up (where we can move from detailed, low-level cells to
higher-level, more aggregated cells).
BUC stands for “Bottom-Up Construction.” However, according to the lattice con-
vention described before and used throughout this book, the BUC processing order
is actually top-down! The BUC authors view a lattice of cuboids in the reverse order,

all

A B C

AB AC BC

ABC

Figure 5.5 BUC’s exploration for a 3-D data cube computation. Note that the computation starts from
the apex cuboid.