Page 226 -

3:19
2011/6/1
#3
HAN 12-ch05-187-242-9780123814791
Page 189
5.1 Data Cube Computation: Preliminary Concepts 189

all (apex cuboid)

A B C

AB AC BC

ABC (base cuboid)

Figure 5.1 Lattice of cuboids making up a 3-D data cube with the dimensions A, B, and C for some
aggregate measure, M.

A cell in the base cuboid is a base cell. A cell from a nonbase cuboid is an aggregate
cell. An aggregate cell aggregates over one or more dimensions, where each aggregated
dimension is indicated by a ∗ in the cell notation. Suppose we have an n-dimensional
data cube. Let a = (a 1 , a 2 ,..., a n , measures) be a cell from one of the cuboids making
up the data cube. We say that a is an m-dimensional cell (i.e., from an m-dimensional
cuboid) if exactly m (m ≤ n) values among {a 1 , a 2 ,..., a n } are not ∗. If m = n, then a is
a base cell; otherwise, it is an aggregate cell (i.e., where m < n).

Example 5.1 Base and aggregate cells. Consider a data cube with the dimensions month, city, and
customer group, and the measure sales. (Jan, ∗ , ∗ , 2800) and (∗, Chicago, ∗ , 1200) are
1-D cells; (Jan, ∗ , Business, 150) is a 2-D cell; and (Jan, Chicago, Business, 45) is a 3-D
cell. Here, all base cells are 3-D, whereas 1-D and 2-D cells are aggregate cells.

An ancestor–descendant relationship may exist between cells. In an n-dimensional
data cube, an i-D cell a = (a 1 , a 2 ,..., a n , measures a ) is an ancestor of a j-D cell b =
(b 1 , b 2 ,..., b n , measures b ), and b is a descendant of a, if and only if (1) i < j, and (2) for
1 ≤ k ≤ n, a k = b k whenever a k 6= ∗. In particular, cell a is called a parent of cell b, and
b is a child of a, if and only if j = i + 1.

Example 5.2 Ancestor and descendant cells. Referring to Example 5.1, 1-D cell a = (Jan, ∗ , ∗ ,
2800) and 2-D cell b = (Jan, ∗ , Business, 150) are ancestors of 3-D cell c = (Jan,
Chicago, Business, 45); c is a descendant of both a and b; b is a parent of c; and c is a
child of b.

To ensure fast OLAP, it is sometimes desirable to precompute the full cube (i.e., all
the cells of all the cuboids for a given data cube). A method of full cube computation
is given in Section 5.2.1. Full cube computation, however, is exponential to the number
n
of dimensions. That is, a data cube of n dimensions contains 2 cuboids. There are even