

M. CaniupÃ¡n Marileo and A. Vaisman. Repairing Dimension Hierarchies under Inconsistent Reclassification. In O. De Troyer et al., editors, Proceedings of the ER 2011 Workshops, volume 6999 of Lecture Notes in Computer Science, pages 7585. SpringerVerlag, Brussels, Belgium, November 2011.
Abstract
OnLine Analytical Processing (OLAP) dimensions are usually modelled as a hierarchical set of categories (the dimension schema), and dimension instances. The latter consist in a set of elements for each category, and relations between these elements (denoted rollup). To guarantee summarizability, a dimension is required to be strict, that is, every element of the dimension instance must have a unique ancestor in each of its ancestor categories. In practice, elements in a dimension instance are often reclassified, meaning that their rollups are changed (e.g., if the current available information is proved to be wrong). After this operation the dimension may become nonstrict. To fix this problem, we propose to compute a set of minimal rrepairs for the new nonstrict dimension. Each minimal rrepair 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 instance graph. We show that, although in the general case finding an rrepair is NPcomplete, for realworld dimension schemas, computing such repairs can be done in polynomial time. We present algorithms for this, and discuss their computational complexity.




