Publicación: EFFICIENT ALGORITHMS FOR REPAIRING INCONSISTENT DIMENSIONS IN DATA WAREHOUSES
Fecha
2013
Título de la revista
ISSN de la revista
Título del volumen
Editor
PROCEEDINGS- INTERNATIONAL CONFERENCE OF THE CHILEAN COMPUTER SCIENCE SOCIETY
Resumen
DIMENSIONS IN DATA WAREHOUSES (DWS) ARE USUALLYMODELED AS A HIERARCHICAL SET OF CATEGORIES CALLED THE DIMENSIONSCHEMA. TO GUARANTEE SUMMARIZABILITY, THIS IS, THE CAPABILITY OFUSING PRE-COMPUTED ANSWERS AT LOWER LEVELS TO COMPUTE ANSWERSAT HIGHER LEVELS, A DIMENSION IS REQUIRED TO BE STRICT AND COVERING,MEANING THAT EVERY ELEMENT OF THE DIMENSION MUST BE CONNECTEDTO A UNIQUE ANCESTOR IN EACH OF ITS ANCESTOR CATEGORIES. IN PRACTICE,ROLLUP RELATIONS OF DIMENSIONS NEED TO BE RECLASSI?ED TO CORRECTERRORS OR TO ADAPT THE DATA TO CHANGES. AFTER THESE OPERATIONS THEDIMENSION MAY BECOME NON-STRICT. A MINIMAL R-REPAIR IS A NEWDIMENSION THAT IS STRICT AND COVERING, IS OBTAINED FROM THE ORIGINALDIMENSION THROUGH A MINIMUM NUMBER OF CHANGES, AND KEEPSTHE SET OF RECLASSI?CATIONS. IN THE GENERAL CASE ?NDING AN R-REPAIRFOR A DIMENSION IS NP-COMPLETE. WE PRESENT EF?CIENT POLYNOMIALTIME ALGORITHMS TO COMPUTE A SINGLE R-REPAIR FOR DIMENSIONS THATCONTAIN ONE CON?ICTING LEVEL AND BECOME INCONSISTENT AFTER ONERECLASSI?CATION OF ELEMENTS.
