Abstract
A common technique for speeding up OLAP query processing is to materialize (pre-compute) some aggregate views, called cube views, and use them for the derivation of other cube views. The derivations are inferred from the dimension hierarchies, and are usually represented as a relation between cube views called cube dependence relation, also called summarizability relation for a single dimension hierarchy. In this paper, we study the problem of computing the summarizability relation of dimension schemas that model structural irregularities of dimensions by means of integrity constraints. We study the intrinsic complexity of the problem, and present an algorithm which uses deep structural properties of dimension hierarchies and constraints to solve the problem. Finally, we give an extension of the algorithm to compute the dependence relation for the multidimensional case.