Attribute Value Reordering For Efficient Hybrid OLAP

Our paper Attribute Value Reordering For Efficient Hybrid OLAP was accepted by Information Sciences a few days ago. It should appear next year I imagine but I make the preprint available now. It is an extended version of an earlier paper presented at DOLAP. In this case, the journal version is considerably extended and well worth the read.

It shows a very mathematical approach to multidimensional databases (OLAP) linking some OLAP problems to graph theory (an equivalent to graph isomorphism is shown) and there are some probabilistic results there as well.

There are also other, less mathematical, novel results like the concept of the normalizaiton of a data cube which is quite distinct from the normalization of a relational database.

The normalization of a data cube is the ordering of the attribute values. For large multidimensional arrays where dense and sparse chunks are stored differently, proper normalization can lead to improved storage efficiency. We show that it is NP-hard to compute an optimal normalization even for 1×3 chunks, although we find an exact algorithm for 1×2 chunks. When dimensions are nearly statistically independent, we show that dimension-wise attribute frequency sorting is an optimal normalization and takes time O(d n log(n)) for data cubes of size n^d. When dimensions are not independent, we propose and evaluate a several heuristics. The hybrid OLAP (HOLAP) storage mechanism is already 19%-30% more efficient than ROLAP, but normalization can improve it further by 9%-13% for a total gain of 29%-44% over ROLAP