CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
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 75-85. Springer-Verlag, Brussels, Belgium, November 2011.
© Springer-Verlag 2011 – http://dx.doi.org/10.1007/978-3-642-24574-9

Abstract

On-Line 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 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 instance graph. We show that, although in the general case finding an r-repair is NP-complete, for real-world dimension schemas, computing such repairs can be done in polynomial time. We present algorithms for this, and discuss their computational complexity.


Updated: 2017-03-27