Computation of Sparse Data Cubes with Constraints

For a data cube there are always constraints between dimensions or between attributes in a dimension, such as functional dependencies. We introduce the problem that when there are functional dependencies, how to use them to speed up the computation of sparse data cubes. A new algorithm CFD is presented to satisfy this demand. CFD determines the order of dimensions by considering their cardinalities and functional dependencies between them together. It makes dimensions with functional dependencies adjacent and their codes satisfy monotonic mapping, thus reduces the number of partitions for such dimensions. It also combines partitioning from bottom to up and aggregate computation from top to bottom to speed up the computation further. In addition CFD can efficiently compute a data cube with hierarchies from the smallest granularity to the coarsest one, and at most one attribute in a dimension takes part in the computation each time. The experiments have shown that the performance of CFD has a significant improvement.