Publicación: EFFICIENT REPAIR OF DIMENSIONS HIERARCHIES UNDER RECLASSIFICATION
Fecha
2015
Título de la revista
ISSN de la revista
Título del volumen
Editor
DATA & KNOWLEDGE ENGINEERING
Resumen
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.
Descripción
Palabras clave
UPDATES, REPAIRS, OLAP, DIMENSION HIERARCHIES, DATA WAREHOUSING
