An Algebra for OLAP

Abstract

OLAP (On Line Analytical Processing) comprises tools and algorithms that allow querying multidimensional (MD) databases. OLAP is based on the MD model, where data can be seen as a cube, where each cell contains one or more measures of interest, that can be aggregated along dimensions. Despite the extensive corpus of work in the field, a formally defined, reference language for OLAP is still needed, as there is no well-defined, accepted semantics, for many of the usual OLAP operations. In this paper, we address the problem, and present a set of operators that manipulate a data cube, clearly define their semantics, and prove that they can be composed, yielding a language powerful enough to express complex OLAP queries. We express these operations as a sequence of atomic transformations over a fixed MD matrix whose cells contain a sequence of measures. Each atomic transformation produces a new measure. When a sequence of transformations forms an OLAP operation, additionally, a flag is produced that indicates which cells must be considered as input for the next operation. In this way, an elegant algebra is defined. Our main contribution, with respect to other similar efforts in the field is that, for the first time, a formal proof to practical problems is given, and we believe the present work will serve as a basis to build more solid practical tools for data analysis.