

The term "data cube" is not used consistently in the data warehousing research literature. We will use the following rather general definition. A data set is conceptually modeled as a multidimensional hyperrectangle, or data cube for short. The d functional attributes that describe a data item in the set are the dimensions. Some of them are hierarchical, e.g., yearquartermonthday for the time dimension (sometimes multiple hierarchies for an attribute exist, e.g., weekday is another hierarchy for the time dimension). A dtuple of dimension values defines a cell of the data cube, similar to a multidimensional array. Cells contain the values of additional attributes, the measure attributes. For simplicity and without loss of generality, we will further on assume that the cube has only a single measure attribute.
Note that we do not advocate any particular implementation for data cubes. Possible solutions were examined elsewhere, e.g., in Goil & Choudhary (1997), Roussopoulos, Kotidis, & Roussopoulos (1997), and Sarawagi & Stonebraker (1994). The model is also not restricted to a certain OLAP architecture like Multidimensional OLAP (MOLAP) or Relational OLAP (ROLAP) (for a discussion of ROLAP and MOLAP, see Pendse & Creeth, 2001). However, our discussion will mainly focus on MOLAP techniques.
A simple example is a sales data cube with dimensions product, time (date of sale), and location (place of sale), and the measure attribute amount (value of sales transaction). Hence for each product, time, and location, the corresponding amount of sales is stored. Figure 1 shows a possible instance with dimension hierarchies indicated (ALL represents the whole domain of an attribute). If there is no sales transaction for a certain combination of dimension values, the corresponding cell is empty. In the figure empty cells contain the value 0.
Figure 1: Data Cube Example
As summarized in Chaudhuri & Dayal (1997), dominant aggregate query types on data cubes are rollup/drilldown (increases, respectively decreases, level of aggregation along one or more attribute hierarchies) and sliceanddice (selects attributes and cells of interest).
These queries are typically range queries or sequences of related range queries (e.g., hierarchical range queries as discussed in Koudas, Muthukrishnan, & Srivastava, 2000). Hence, we are mainly concerned with support for aggregate range queries which select a hyperrectangular region of the data cube and return an aggregate, e.g., SUM or COUNT, of the measure values of the selected cells. A formal definition is given below.
Let A denote a ddimensional data cube such that dimension i (1 ≤ i ≤ d) has N_{i} cells. Without loss of generality, let the domain of dimension i be {0,1,…, N_{i} 1}. A cell c = [c_{l},…, c_{d}], where each c_{i} is an element of the domain of the corresponding dimension, contains the measure value A[c]. With e:f we denote a hyperrectangular region of the data cube, more precisely the set of all cells c that satisfy e_{i} ≤ c_{i} ≤ f_{i} for all 1 ≤ i ≤ d. Cell e is the anchor and cell f the endpoint of the region. The anchor and endpoint of the entire data cube hence are [0,…, 0] and [N_{1}  1,…, N_{d} 1], respectively. The term op(A[e] : A[f]) denotes the result of applying the aggregate operator op to the measure values in region e : f, i.e., it defines an aggregate range query. For example, SUM(A[e] : A[f]) is a range sum. The range sum SUM(A[0,…, 0] : A[f]) will be referred to as a prefix sum.
The term original cube denotes a data cube which is obtained as the straightforward projection of a data set to the ddimensional space defined by the cube's dimensions. If any of the cube's cells contain values which are aggregates of multiple cells of an original cube (e.g., subtotals), it will be referred to as a preaggregated cube.

