Efficient Algorithms for Repairing Inconsistent Dimensions in Data Warehouses

Abstract—Dimensions in Data Warehouses (DWs) are usually modeled as a hierarchical set of categories called the dimension schema. To guarantee summarizability, this is, the capability of using pre-computed answers at lower levels to compute answers at higher levels, a dimension is required to be strict and covering, meaning that every element of the dimension must be connected to a unique ancestor in each of its ancestor categories. In practice, rollup relations of dimensions need to be reclassified to correct errors or to adapt the data to changes. After these operations the dimension may become non-strict. A minimal r-repair is a new dimension that is strict and covering, is obtained from the original dimension through a minimum number of changes, and keeps the set of reclassifications. In the general case finding an r-repair for a dimension is NP-complete. We present efficient polynomial time algorithms to compute a single r-repair for dimensions that contain one conflicting level and become inconsistent after one reclassification of elements. I