ABSTRACT
Online Analytical Processing is a powerful framework for the analysis of organizational data. OLAP is often supported by a logical structure known as a data cube, a multidimen- sional data model that offers an intuitive array-based per- spective of the underlying data. Supporting efficient index- ing facilities for multi-dimensional cube queries is an issue of some complexity. In practice, the difficulty of the in- dexing problem is exacerbated by the existence of attribute hierarchies that sub-divide attributes into aggregation layers of varying granularity. In this paper, we present a hierar- chy and caching framework that supports the efficient and transparent manipulation of attribute hierarchies within a parallel ROLAP environment. Experimental results verify that, when compared to the non-hierarchical case, very little overhead is required to handle streams of arbitrary hierar- chical queries.
Categories and Subject Descriptors
H.2.7.b [Database Management]: Data Warehouse and
Repository; H.2.2.a [DatabaseManagement]: AccessMeth- ods General Terms
Algorithms Design Performance
Keywords
Hierarchies, Caching, Data Cubes, Aggregation, Indexing,
OLAP, Granularity, Materialization, Parallelization
1. INTRODUCTION
Online Analytical Processing (OLAP) has become an im- portant component of contemporary Decision Support Sys- tems (DSS). Central to OLAP is the data cube, a multidi- mensional data model that presents an intuitive cube-like
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
DOLAP’05, November 4–5, 2005, Bremen, Germany.
Copyright 2005 ACM 1595931627/
05/0011 ...$5.00.
East
West
North
South
Automotive
Household
2004
2005
East
West
North
South
2005
2004
XG27
XY53
GL75
RT57
RT91
HJ45
HY35
HK46
UJ67
JW30
NH22
Brakes
Engine
2004
2005
Interior
Appliances
Furniture
East
West
North
South
(a)
Product
(b)
(c)
Figure 1: A hierarchical Product attribute broken down from (a) category, to (b) type, to (c) product number. interface to both end users and DSS developers. In re- cent years, the academic community has become increas- ingly interested in the cube model and a number of efficient cube generation algorithms have been presented in the lit- erature[2, 16, 22].
For the most part, the focus of these algorithms has been the generation of the cube data structure itself. Methods or techniques for efficient access/querying have received rela- tively little attention. When such methods have been pre- sented, they typically assume the existence of non hierarchi- cal attributes. In practice this is rarely the case. Figure 1 provides a simple example from the automotive industry.
Here, we have three feature attributes — Product, Loca- tion, and Time — that can be viewed in terms of one or more measure attributes. In this case, each cell in the cube might be associated with an aggregated total for the measure attribute Total Sales. Note how the hierarchical Product dimension on the x-axis is broken down into increasingly finer levels of aggregation.
While it is possible to represent each of these hierarchical levels as a distinct feature attribute, doing so dramatically increases the complexity of the underlying problem. Specif- ically, the number of possible attributes or group-bys in a d-dimensional data cube is exponential on the number of dimensions. For example, a 10-dimensional cube would gen-
89
erate 2d = 1024 aggregated group-bys. By contrast, the total number of group-bys in the presence of hierarchies is given as
Q
d i=1(hi + 1) when constructed from a data cube with d attributes, where dimension i has a hierarchy of size h [20]. The same 10-dimensional data cube with three-level hierarchies on each dimension would produce over one mil- lion group-bys. Clearly this is infeasible when the original input set may already contain terabytes of data.
An alternative approach to the generation and storage of fully materialized hierarchical cubes is to produce data cubes containing hierarchies represented only at the finest level of granularity. Hierarchical roll up or drill down is then done in real time during query resolution. In order for this to be feasible, the cube architecture must support both fast indexing and hierarchy-sensitive data structures. The associated overhead should be largely transparent to the end user. In this paper we present a series of algorithms and data structures for the efficient manipulation of attribute