Efficient repair of dimension hierarchies under inconsistent reclassification

摘要

On-Line Analytical Processing (OLAP) dimensions are usually modeled as a set of elements connected by a hierarchical relationship. To ensure summarizability, a dimension is required to be strict, that is, every element of the dimension must have a unique ancestor in each of its ancestor categories. In practice, elements in a dimension are often reclassified, meaning that their rollups are changed. After this operation the dimension may become non-strict. To fix this problem, we propose to compute a set of minimal r-repairs for the new non-strict dimension. Each minimal r-repair is a strict dimension that keeps the result of the reclassification, and is obtained by performing a minimum number of insertions and deletions to the dimension graph. We show that, although in the general case finding an r-repair is NP-complete, for real-world hierarchy schemas, computing such repairs can be done in polynomial time. Further, we propose efficient heuristic-based algorithms for computing r-repairs, and discuss their computational complexity. We also perform experiments over synthetic and real-world dimensions to show the plausibility of our approach.