Introduction

Data Warehouses (DWs) are data repositories that integrate data from different sources, and keep historical data for analysis and decision support [10]. When generating reports, it is of central importance for these systems to compute queries that are summaries of data in a simple and efficient way. In order to do this, DWs organize data according to the multidimensional model. In the multidimensional model, dimensions reflect the perspectives upon which facts are viewed. Facts correspond to events which are usually associated to numeric values known as measures, and are referenced using the dimension elements. Dimensions are modeled as hierarchies whose nodes are called elements, where each element belongs to a category. The categories are also organized into a hierarchy called hierarchy schema.

Example 1. Consider a company that manages an online repository of research articles. The company maintains a DW to generate summaries used to analyze the download behavior of its users. The DW contains the dimensions Time and Publication. The Time dimension is structured using a hierarchy schema with a bottom category Date, which goes to the category Month, which in turn goes to the category Year. On the other hand, the Publication dimension is structured using the hierarchy schema shown in Figure 1(a), where the Article category goes to Journal, which in turn goes to Area. Also the Article category is connected to Subject category. The top category is All. Figure 1(b) shows the elements of the Publication dimension, along with the relations between elements of different categories, called rollup relations. For example, a1 and a2 are elements of category Article and b1, b2 are elements of category Journal. For each edge in the hierarchy schema, there is a rollup relation. For example, the rollup relation from the category Article to the category Journal contains the pairs or elements: (a1, b1) and (a2, b2). The fact table of the DW is shown in Figure 1(c). Each fact stored in the table represents the numbers of times an article was downloaded in a given date. As an example, article a1 was downloaded three times on January 1, 2007.

The hierarchical structure of dimensions allows users to access facts at different levels of granularity. As an example, using the aforementioned DW it is easy to compute summaries such as: number of times that each article was downloaded per month, or number of downloads broken down by area and year.

In order to compute summaries efficiently, DWs use pre-computed summaries at low level categories to derive summaries at higher level categories. Two main classes of integrity constraints, strictness and covering constraints, are used to check whether such computations, called summarizations, are correct [13,19,25]. In a consistent summarization, each fact is aggregated once and not more than once. Strictness constraints are used to require rollup relations to be strict (manyto-one) relations. If a rollup relation is required to be strict, then there cannot exist an element connected to two different elements in the rollup relation. As an example, in the Publication dimension (Figure 1(a) and (b)) the rollup relation from Article to Journal is strict. In contrast, the rollup relation from Article to Subject is not strict, because a2 is connected to two different elements in the category Subject. Covering constraints are used to require a rollup relation to connect all the elements that belongs to the category from which the rollup relation departs. As an example, in the dimension of Figure 1(b), the rollup relation from Article to Subject it is not covering since the element a1 is not connected to any element in Subject.

Example 2. The summary S Area (Area, N ) = {(c 1 , 8), (c 2 , 7)} (Figure 1) can be correctly derived from the summary S Article (Article, N ) = {(a 1 , 8), (a 2 , 7)} by summing up the number of downloads for each group of articles that go to the same area in the dimension (element a 1 goes to c 1 , and a 2 goes to c 2 ). The correctness of this derivation follows from the fact that the rollup relation from It has been shown that the dimensions that arise in real-world applications do not always have strict and covering rollup relations. The flexibility to represent rollup relations has been incorporated as a central feature of several dimension models [13,24]. In order to keep the ability to check consistency of summarizations, it is important for DW systems to know the set of strictness and covering constraints that hold. This can be achieved by allowing DW designers to formulate the constraints that must hold when the dimensions are modeled. In this paper, we study the form of inconsistency that arises when a dimension does not satisfy a set of strictness and covering constraints. Similar to the vast majority of the work on inconsistency handling in databases (cf. [4]), we address the scenario where the constraints prevail over the data and the dimension must be updated in order for it to satisfy the constraints.

Example 3. Suppose that the DW administrator considers that the following constraints should be satisfied by the dimension D in Figure 2 We introduce the notion of a minimal repair of a dimension that does not satisfy a set of constraints. A minimal repair is defined as a new dimension that satisfies the constraints and is obtained by applying a minimal number of changes to the original dimension. We study the complexity of the problem of computing minimal repairs, and show that in general the problem is NP-hard. We also explore the use of Datalog programs with stable model semantics [11] to characterize minimal repairs. Logic programs act as a compact and executable logical specification of dimension repairs. The rest of the paper is organized as follows: Section 2 presents DW dimensions, and strictness and covering constraints. Next, Section 3 presents the notion of repair and describes complexity issues. Section 4 presents the logic programs to compute repairs. Finally, Sections 5 and 6 present related work and the conclusions of the paper.

Preliminaries

In this section we formalize dimensions using standard concepts from multidimensional models obtained from [9,15,17,24], with some minor modifications to facilitate presentation.

A Then D is as follows

c i ∈ C H such that (All H , c i ) ∈ր H and for every c j ∈ C, (c j , All H ) ∈ր * H . Sometimes, we will write c a ր H c b instead of (c a , c b ) ∈ր H . Example 4. The hierarchy schema H = (C H , ր H ), depicted in Figure 1(a), is as follows: C H = {Article, Journal, Subject, Area, All}; All H = All; and ր H ={ (Article, Journal), (Journal, Area), (Area, All), (Article, Subject), (Subject, All)}. A dimension D is a tuple (H D , E D , Cat D , < D ),E D = {all, a 1 , a 2 , b 1 , b 2 , c 1 , c 2 , d 1 , d 2 }; all D = all; Cat D = {all → All, a 1 → Article, a 2 → Article, b 1 → Journal, b 2 → Journal, c 1 → Area, c 2 → Area, d 1 → Subject, d 2 → Subject, }; and < D = {(a1,b1), (a2,b2), (b1,c1), (b2,c2), (c1,all),

(c2,all), (a2,d1), (a2,d2), (d1,all), (d2,all)}.

The set of rollup relations of a dimension D is defined as follows. For each pair of categories We say that the rollup relation

c i , c j ∈ C HD such that c i ր * HD c j ,R D (c i , c j ) is strict if for all elements x, y, z in E, if (x, y) ∈ R D (c i , c j ) and (x, z) ∈ R D (c i , c j ) then y = z. The rollup relation R D (c i , c j

) is covering if for all elements e ∈ E such that Cat(e) = c i , there exists an element e ′ ∈ E such that (e, e ′ ) ∈ R D (c i , c j ). A dimension is strict if all its rollup relations are strict. Otherwise, the dimension is said to be non-strict. Similarly, we use the notions of covering and non-covering dimension. Covering dimensions are also called homogeneous and non-covering dimensions are called heterogeneous.

The vast majority of research and industrial applications of DWs consider dimensions that are strict and covering [18]. For strict and covering dimensions [13] summarization operations that aggregate facts between two categories that are connected in the hierarchy schema are always correct. However, it has been shown that in some real situations dimensions fail to satisfy these conditions [14,24]. In these cases, in order to keep the ability to verify summarizability, it is useful to allow the DW administrator to specify integrity constraints to identify rollup relations that are strict or covering [14].

Let H = (C H , ր H ) be a hierarchy schema and let

D = (H D , E D , Cat D , < D ) be a dimension such that H D = H. (i) A strictness constraint over H is an expression of the form c i → c j where c i , c j ∈ C H and c i ր * H c j . The dimension D satisfies the strictness constraint c i → c j if and only if the rollup relation R D (c i , c j ) is strict. (ii) A covering constraint over H is an expression of the form c i ⇒ c j where c i , c j ∈ C H and c i ր * H c j . The dimension D satisfies the covering constraint c i ⇒ c j if and only if the rollup relation R D (c i , c j ) is covering.

We denote by Σ s (H) and Σ c (H) the set of all possible strictness constraints and covering constraints, respectively, over hierarchy schema H. We say that a dimension D satisfies a set of constraints Σ if D satisfies every constraint in Σ. Otherwise, we say that the dimension D is inconsistent with respect to Σ.

Example 7. Let D be the publication dimension depicted in Figure 1(b). This dimension satisfies the following set Σ of strictness constraints: {Article → Journal, Article → Area, Journal → Area}. However, D does not satisfy Article → Subject, since an element of Article may reach more than one element in Subject. In contrast, dimension given in Figure 2 is inconsistent with respect to Σ since it violates the strictness constraint Article → Area. Indeed, the rollup relation

R D (Article, Area) = {(a1, c1), (a1, c2)} is non-strict.

The problem of determining if a dimension D satisfies a set of constraints can be solved in polynomial time by computing < * D .

Dimension Repairs

If a dimension D does not satisfy a set of constraints Σ, we propose to compute the minimal repairs of D, that is, dimensions over the hierarchy schema of D that satisfy Σ and that stay as close as possible to the inconsistent dimension.

Example 8. Let D be the dimension given in Figure 2, and let Σ = {Article ⇒ All, Journal ⇒ All, Area ⇒ All, Subject ⇒ All, Article → Area}. Clearly, D is inconsistent with respect to Σ.

Given two dimensions D = (H D , E D , Cat D , < D ) and D ′ = (H D ′ , E D ′ , Cat D ′ , < D ′ ), the distance between them, dist (D, D ′ ), is defined as |(< D ′ \ < D ) ∪ (< D \ < D ′ )|.

The distance dist (D, D ′ ) is the size of the symmetric difference between the child/parent relations of the two dimensions. Next, we define the notions of repair and minimal repair. (i) A repair of D with respect to Σ is a dimension

D ′ = (H D ′ , E D ′ , Cat D ′ , < D ′ ) such that H D ′ = H D , E D ′ = E D , Cat D ′ = Cat D , and D ′ satisfies Σ. (ii) A minimal repair of D with respect to Σ is a repair D ′ , such that dist (D, D ′ )

is minimal among all the repairs of D with respect to Σ.

In the notion of repair we propose, the set of elements in each category of the original dimension is preserved over all the repairs, that is deletions or additions of new elements are not allowed. It can be shown that there always exists a repair of a dimension provided that the dimension has at least one element in each category. However, there might be an exponential number of them. Thus, it becomes relevant to study the problem of finding one.

Theorem 1. Let D be a dimension, and k an integer. The problem of deciding if there exists a repair

D ′ of D such that dist (D, D ′ ) ≤ k is NP-complete.

Hardness is proven by reduction from the set covering problem. It follows then, that the problem of computing a minimal repair is NP-hard and that deciding if a dimension is a minimal repair is co-NP-complete.

Computing Repairs

Computing repairs of dimensions inconsistent with respect to a set of covering and strictness constraints can be expensive in terms of computational resources. However, we can use Datalog programs with negation under stable model semantics [11] to represent and compute the minimal repairs of a dimension. Because of space limitations, we will present here the programs with examples.

Even though Datalog programs with negation under stable models semantics can be used to express NP problems, current implementations, such as DLV 4 [20] and Smodels 5 [26], have shown to be quite efficient in practice [20]. In what follows, we will present a Datalog program with negation using predicates in Table 1 that can be used to obtain the minimal repairs of a dimension. In order to simplify the presentation, we will first discuss the case where Σ = Σ s (H) ∪ Σ c (H), that is we have to fix a dimension that, according to the constraints, should be strict and covering. Let us observe that a covering and strict dimension is such that every element will rollup to exactly one element in each parent category. The repair program relies on this observation and first computes a set of candidate dimensions that contains the same elements as the inconsistent dimension and only one rollup between every element and every parent category (note that all these candidate dimensions satisfy the covering constraints). Then, it discards the models that do not satisfy the strictness constraints.

RT ′ (X, Y, N1, N2) ← R ′ (X, Y, N1, N2). (7) RT ′ (X, Z, N1, N3) ← RT ′ (X, Y, N1, N2), R ′ (Y, Z, N2, N3). (8) ← RT ′ (X, Y, N1, N2), RT ′ (X, Z, N1, N2), Y = Z. (9) Ins(X, Y, N1, N2) ← R ′ (X, Y, N1, N2), not R(X, Y, N1, N2). (10) Del (X, Y, N1, N2) ← R(X, Y, N1, N2), not R ′ (X, Y, N1, N2). (11) ⇐ Ins(X, Y, N1, N2)[1 : 1]. (12) ⇐ Del (X, Y, N1, N2)[1 : 1]. (13)

Facts of the repair program correspond to the elements and rollup relations in D P hone . The rest of the rules in the repair program are used to compute the repairs. In general terms, the program: generates all possible dimensions

D ′ = (H D ′ , E D ′ , Cat D ′ , < D ′ ) such that H D ′ = H D P hone , E D ′ = E D P hone , Cat D ′ =

Cat D P hone and such that every element has a unique parent in every parent category (using rules (1) to ( 6)), then discards the ones that are not strict (with rules (7) to ( 9)) and finally chooses the ones that are at a minimal distance (using rules (10) to ( 13)).

More specifically, rules (1) to ( 6) populate predicate R ′ with a new covering child-parent relation for the elements in E D P hone . This new relation assigns to each element a a new parent in every category c j such that Cat(a) ր HD P hone c j . This parent is obtained by using the choice operator [12] that generates one model for each c such that Cat(c) =cj. In fact, choice((X, c j ), (Y )) will assign a unique value to Y in each stable model for each combination (X, c j ). Rules ( 7) and ( 9) compute the transitive closure of the child-parent relation of the repair. Rule ( 9) is a program constraint (a rule without head) which enforces that it is not possible to have that an element x rolls-up to two different parents in the same category. Namely, it discards all the models in which the rollup relations, captured in predicate RT ′ , are not strict. Rules (10) and (11) keep track of the insertion and deletions, respectively, that are needed to obtain the repair. The weak constraints [8], denoted by ⇐, in rules ( 12) and ( 13) are used to minimize the number of insertion and deletions needed to restore consistency. In general, a weak constraint is of the form ⇐ ϕ [weight : level ], where ϕ is a conjunction of atoms, and weight and level are integers. If ϕ is true in the model the weak constraint is violated and the weight is added up to the cost of the level. The stable models which minimize the sum of the weights of the violated weak constraints are called the best models of the program.

This program has three best models of total weight three The correctness of the program relies on the fact that in strict and covering dimensions every element contains exactly one parent in each parent category. In the general case, where the dimension is not necessarily required to be strict and covering, this does not hold anymore. However, in a minimal repair of a dimension D, the number of parents in a category for every element can be shown to be between zero and the maximum between one (1) and the number of parents for that same element in D. Thus, in the general case, in order to compute the minimal repairs, we have to be able to reduce the number of parents an element can have. This is achieved by constructing a new dimension D del from D for which the repairs of D can be computed only through reclassification of child-parent relations of D del . Example 11. Figure 4(a) shows the del-dimension D del obtained from dimension D in Figure 2(a) which is inconsistent with respect to Σ = {Article ⇒ All, Journal ⇒ All, Area ⇒ All, Subject ⇒ All, Article → Area}. From it we can compute a set of candidate repairs by reclassifying all the child/parent relations. From these candidate repairs, the only two that satisfy the constraints (ignoring the child/parent relations that involve any del-elements) are shown in Figure 4 R(a1,b2,Article,Journal). R(b1,c1,Journal,Area). R(b2,c2,Journal,Area). R(c1,all,Area,All). R(c2,all,Area,All). R(d1,all,Subject,All). R(a1,del,Article,Subject). R(a2,del,Article,Subject).

R ′ (X, Y ′ , Z, Journal) ← R(X, Y, Z, Journal), Journal(Y ′ ), choice((X, Y, Journal)(Y ′ )). (14) R ′ (X, Y ′ , Z, Area) ← R(X, Y, Z, Area), Area(Y ′ ), choice((X, Y, Area)(Y ′ )). (15) R ′ (X, Y ′ , Z, Subject) ← R(X, Y, Z, Subject), Subject(Y ′ ), choice((X, Y, Subject)(Y ′ )). (16) R ′ (X, Y ′ , Z, All) ← R(X, Y, Z, All), All(Y ′ ), choice((X, Y, All)(Y ′ )). (17) RT ′ (X, Y, N1, N2) ← R ′ (X, Y, N1, N2), X = del, Y = del. (18) RT ′ (X, Z, N1, N3) ← RT ′ (X, Y, N1, N2), R ′ (Y, Z, N2, N3), X = del, Y = del, Z = del. (19) ← RT ′ (X, Y, Article, Area), RT ′ (X, Z, Article, Area), Y = Z. (20) ← Article(X), not aux All (X), X = del. ← Journal(X), not aux All (X), X = del. (21) ← Area(X), not aux All (X), X = del. ← Subject(X), not aux All (X), X = del. (22) aux All (X) ← RT ′ (X, Y, Area1, All). (23) Ins(X, Y, N1, N2) ← R ′ (X, Y, N1, N2), not R(X, Y, N1, N2), Y = del. (24) Del (X, Y, N1, N2) ← R(X, Y, N1, N2), not R ( X, Y, N1, N2), Y = del. (25) ⇐ Ins(X, Y, N1, N2).[1 : 1] ⇐ Del(X, Y, N1, N2).[1 : 1]. (26)

The facts of the repair program correspond to the elements and rollup relations in D del . Rules ( 14) to (17) compute a new candidate child-parent relation for the elements in E D del . Then, the consistency of each candidate repair with respect to strictness (rules (18) to (20)) and covering (rules ( 21) to ( 23)) constraints is checked ignoring every child/parent relation with a del-element. Next, rules (24) and ( 26) chooses the ones that are at a minimal distance. Finally, the repairs are obtained from the consistent candidate repairs by removing every del-element.

The best models of this program correspond to the repairs of D as shown in Figure 2(b)-(c).

Related Work

Letz et al. [21] motivate the importance of enforcing strictness constraints in dimensions using constraints represented in dimensions hierarchies. In particular, the constraints are used to keep dimensions strict upon successive update operations. Pedersen et al. [23] present a method to model non-strict dimensions as strict dimensions when the OLAP implementation requires the dimensions to be strict. In our setting, in contrast, the objective is to clean errors that turn a dimension inconsistent with respect to a set of constraints. The problem of repairing relational databases with respect to a set of integrity constraints (e.g. functional dependencies and inclusion dependencies) has been extensively studied (see [4] for a survey). Even though there are several ways to represent a data warehouse using relations (e.g. star schema or snowflake schema [10,18]) it is not possible to use the relational repair techniques to compute DW's repairs. This is because, it is either not possible to represent the required strictness and covering constraints with the relational constraints, or the minimal relational repairs obtained by tuple deletions, insertions or updates do not coincide with the minimal repairs of DWs. Indeed, they might result in the removal of more roll-up relations than needed or in discarding repairs that are minimal in the DWs sense, but not in the relational case.

Logic programs have been used to specify the repairs of relational databases with respect to relational integrity constraints (e.g. functional dependencies, foreign key constraints) [2,3,7]. As far as we know, this paper is the first work on the application of logic programs to restore consistency of DWs.

Conclusions

In this paper we propose logic programs to compute repairs of dimensions, which are obtained by performing insertions and deletions of edges between dimension elements. We do not consider the insertion or elimination of dimension elements, options that might be helpful to restore consistency of dimensions. We leave this analysis for future work.

Since an enterprise data warehouses can contain terabytes of data [10] ensuring that the dimensions satisfy the required integrity constraints can be vital for an efficient computation of reports and summaries. Therefore, it is important to develop tools to allow the designer of a DW to check integrity constraints and to help in the process of repairing inconsistencies with respect to them. We believe that such tools would be particularly useful in the creation and cleaning stage of DWs and when the dimensions are updated and adapted due to changes in data sources or modifications to the business rules [6,15,16,22].

We have explored a novel line of research which is the application of logic programming to support data cleaning tasks in data warehousing. An interested idea for future research is to compute consistent answers to queries over DWs, following the framework proposed in [1,4], where repairs are used as auxiliary concepts to characterize consistent answers to queries. A preliminary analysis in this direction is presented in [5].