Data Cube Computation & Data Generalization

1Why compute cubes efficiently?

• Data cube computation is an essential task in warehouse implementation.
• Pre-computing all or part of a cube greatly reduces response time and improves OLAP performance.
• The challenge: it can need substantial computation time and storage space.

2Cube materialization: cells and cuboids

A data cube is a lattice of cuboids, and each cuboid is a group-by. For dimensions A, B, C:

                 all            ← apex cuboid (0-D): most generalized, ONE value
           A      B      C      ← 1-D cuboids
          AB     AC     BC      ← 2-D cuboids
                ABC             ← base cuboid (3-D): least generalized

• Drill down: move from the apex down toward the base.
• Roll up: move from the base up toward the apex.

Base cells vs aggregate cells

• A cell in the base cuboid is a base cell. A cell in any non-base cuboid is an aggregate cell.
• In an aggregate cell, each aggregated dimension is written as *.
• A cell a = (a₁, …, aₙ, measures) is an m-dimensional cell if exactly m values are not "*".
• m = n → base cell
• m < n → aggregate cell

Ancestors and descendants

An i-D cell a is an ancestor of a j-D cell b (and b is a descendant of a) if and only if:

1. i < j, and
2. a and b agree on every dimension where a is not "*".

If additionally j = i + 1, then a is the parent and b is the child.

Example: (Jan, *, *) is an ancestor of (Jan, Toronto, Business) and the parent of (Jan, Toronto, *).

3Full cube vs iceberg cube

Full cube

Pre-computing all cells of all cuboids gives the fastest OLAP, but:

• It's exponential in the number of dimensions: n dimensions → 2ⁿ cuboids. With concept hierarchies there are even more:

• Each cuboid's size depends on the cardinality of its dimensions.
• So the full cube can need huge, excessive memory.

Iceberg cube

• Cube cells are usually sparse. A customer buys only a few items, so most cells are empty or have tiny values.
• Instead, materialize only cells whose measure passes a minimum threshold (the iceberg condition), e.g. count ≥ 10 or sales ≥ $100.

4MultiWay array aggregation

Data structures: ROLAP stores cuboids in relational tables. MOLAP uses multidimensional arrays. Two methods for computing full cubes are covered: MultiWay (array-based) and BUC.

The chunked array

• Take a 3-D array for A, B, C, partitioned into small memory-based chunks.
• Each dimension is split into 4 equal partitions, giving 4 × 4 × 4 = 64 chunks (chunk 1 = a0b0c0, chunk 2 = a1b0c0, …, chunk 64 = a3b3c3).
• Cardinalities A = 40, B = 400, C = 4000 → partition sizes 10, 100, 1000.

Cuboids to compute for the full cube:

• ABC: the base cuboid, already given as the 3-D array. Everything else is computed from it, directly or indirectly.
• AB, AC, BC: 2-D cuboids
• A, B, C: 1-D cuboids
• all: the apex, group-by (); one value, e.g. the total count

Simultaneous aggregation

The key idea is that when a base cell is read, all the aggregate cells it belongs to are updated at the same time. Then the array is scanned once, not once per cuboid.

5BUC — Bottom-Up Computation

• BUC builds the cube from the apex cuboid toward the base cuboid, the opposite direction to MultiWay.
• The usual lattice drawing puts the apex (all) at the top and the base (ABC) at the bottom.

BUC's exploration order for a 3-D cube (Figure 8-4):

all → A → AB → ABC → AC → B → BC → C

It partitions on A, then recursively on B within each A partition, and so on, depth-first. BUC's strength: iceberg pruning. If a partition fails the minimum support, none of its descendants can pass, so BUC stops exploring that branch.

6Star attributes, star-nodes and star-trees

• If the single-dimension aggregate for an attribute value p fails the iceberg condition, there's no point treating p separately.
• Replace p with *. Then p is a star-node; values that pass are non-star-nodes.
• A cuboid tree compressed this way is a star-tree. A star-table lists the star-nodes.

7Attribute-oriented induction (AOI)

Data generalization replaces low-level values (numeric age) with higher-level concepts (young, middle-aged, senior), so large data can be described concisely at multiple levels of abstraction.

The AOI idea

1. Collect the task-relevant data with a database query.
2. Generalize by looking at the number of distinct values of each attribute: either attribute removal or attribute generalization.
3. Aggregate by merging identical generalized tuples and accumulating their counts.
4. Present the result as charts, cross-tabs or rules.

The two rules

Worked example: "Science Students" at Big University

use Big_University_DB
mine characteristics as "Science_Students"
in relevance to name, gender, major, birth_place, birth_date,
                residence, phone#, gpa
from student
where status in "graduate"

Step 1: initial (working) relation. Data focusing collects the task-relevant tuples.

Step 2: prepare for generalization. Decide each attribute:

Step 3: derive the prime relation P. Insert the generalized tuples and merge identical ones, keeping a count:

Step 4: presentation. The user interacts by drilling, pivoting and mapping into rules, and controls how it is visualised, e.g. as a cross-tab:

8Quick revision sheet