=Paper=
{{Paper
|id=None
|storemode=property
|title=Logic Programs for Repairing Inconsistent Dimensions in Data Warehouses
|pdfUrl=https://ceur-ws.org/Vol-619/paper9.pdf
|volume=Vol-619
|dblpUrl=https://dblp.org/rec/conf/amw/BravoMH10
}}
==Logic Programs for Repairing Inconsistent Dimensions in Data Warehouses==
<pdf width="1500px">https://ceur-ws.org/Vol-619/paper9.pdf</pdf>
<pre>
     Logic Programs for Repairing Inconsistent
          Dimensions in Data Warehouses

       Loreto Bravo1 , Mónica Caniupán2 , and Carlos Hurtado3
                         1
                             Universidad de Concepción, Chile
                             2
                               Universidad de Bio-Bio, Chile
                              3
                                Universidad Adolfo Ibáñez


      Abstract. A Data Warehouse (DW) is a data repository that integrates
      data from multiple sources and organizes the data according to a set of
      data structures called dimensions. Each dimension provides a perspec-
      tive upon which the data can be viewed. In order to support an efficient
      processing of queries, a dimension is usually required to satisfy different
      classes of integrity constraints. In this paper, we study the problem of re-
      pairing a dimension when it fails to satisfy a set of two classes of integrity
      constraints: strictness constraints and covering constraints. We introduce
      the notion of minimal repair of a dimension in this context. A minimal
      repair is defined as a new dimension that is consistent with respect to the
      integrity constraints, which is obtained by applying a minimal amount of
      updates to the original dimension. We study the complexity of computing
      minimal repairs. Finally, we show how to characterize and compute min-
      imal repairs of a dimension using Datalog programs with stable model
      semantics.


1   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
          All                          all

                                                                          Downloads
   Area         Subject      c1    c2         d1   d2
                                                                Article       Date      N
                                                                  a1      01-01-2007 3
  Journal                    b1    b2
                                                                  a2      01-01-2007 2
                                                                  a1      02-01-2007 5
      Article                     a1     a2                       a2      02-01-2007 5
  (a) Publication dimension: (b) Publication dimension: ele-           (c) Fact table
  hierarchy schema           ments and rollup relations

                           Fig. 1. Dimension for Example 1

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.                    2
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 (many-
to-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 SArea (Area, N ) = {(c1 , 8), (c2 , 7)} (Figure 1) can be
correctly derived from the summary SArticle (Article, N ) = {(a1 , 8), (a2 , 7)} by sum-
ming up the number of downloads for each group of articles that go to the
same area in the dimension (element a1 goes to c1 , and a2 goes to c2 ). The cor-
rectness of this derivation follows from the fact that the rollup relation from
               All                       all                    all                    all


        Area         Subject   c1    c2         d1    c1    c2         d1    c1    c2         d1


      Journal                  b1    b2               b1    b2               b1    b2


          Article                   a1     a2              a1     a2              a1     a2


               (a) Dimension D                       (b) Repair D1          (c) Repair D2

Fig. 2. A Publication dimension inconsistent with respect to Article→Area and Article⇒All


Article to Area is strict and covering. Similarly, SArea can be correctly derived
from SJournal (Journal, N ) = {(b1 , 8), (b2 , 7)}. However, the summary SAll (All, N ) =
{(all, 15)} cannot be correctly derived from SSubject (Subject, N ) = {(d1 , 0), (d2 , 7)}
since such derivation would yield SAll (All, N ) = {(all, 7)}. This derivation is incor-
rect because the rollup relation from Article to Subject is not covering.               2
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: ϕ1 : Article ⇒ All,
ϕ2 : Journal ⇒ All, ϕ3 : Area ⇒ All, ϕ4 : Subject ⇒ All, which state that the rollup
relations from categories Article, Journal, Area and Subject to All are covering, and
the constraint ϕ5 : Article → Area establishing that the rollup relation from Article
to Area is strict. However, dimension D fail to satisfy constraint ϕ5 , since element
a1 goes to two different elements: c1 and c2 in the Area category. Also, D violates
ϕ1 because element a2 does not reach all. The DW administrator considers that
the constraints properly capture the semantics of the data, and therefore their
violation indicates the presence of errors. Therefore, the dimension should be
repaired (corrected) in order to resolve the inconsistency. Figure 2(b)-(c) are
two possible repairs of D. Repair D1 is obtained by deleting edge (a1 , b2 ) to
remove the violation of ϕ5 and inserting (a2 , d1 ) to remove the violation of ϕ1 .
Repair D2 is obtained by deleting edge (a1 , b1 ) and inserting (a2 , d1 ).         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 min-
imal 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 specifi-
cation of dimension repairs. The rest of the paper is organized as follows: Section
2 presents DW dimensions, and strictness and covering constraints. Next, Sec-
tion 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.


2    Preliminaries
In this section we formalize dimensions using standard concepts from multidi-
mensional models obtained from [9, 15, 17, 24], with some minor modifications to
facilitate presentation.
    A hierarchy schema H consists of a pair (CH , րH ), where (CH , րH ) is an
acyclic directed graph. Vertices in the set CH are categories and the edges րH
represent the child/parent relations between categories. The transitive and re-
flexive closure of րH is denoted by ր∗H . The set of categories CH contains a
distinguished top category denoted AllH , which is reachable from every other
category in CH and has no outgoing edges, that is, there is no category ci ∈ CH
such that (AllH , ci ) ∈րH and for every cj ∈ C, (cj , AllH ) ∈ր∗H . Sometimes, we
will write ca րH cb instead of (ca , cb ) ∈րH .
Example 4. The hierarchy schema H = (CH , րH ), depicted in Figure 1(a), is as
follows: CH = {Article, Journal, Subject, Area, All}; AllH = All; and րH ={ (Article,
Journal), (Journal, Area), (Area, All), (Article, Subject), (Subject, All)}.       2
A dimension D is a tuple (HD , ED , CatD , <D ), where HD = (CHD , րHD ) is a
hierarchy schema; ED is a set of constants, called elements; CatD : ED → CHD is
a function that defines to which category each element in ED belongs to; and the
relation <D ⊆ ED × ED represents the child/parent relations between elements
of different categories. We denote by <∗D the reflexive and transitive closure
of <D . The following conditions hold: (i) allD is the only element in category
AllHD (ii) for all pair of elements a, b ∈ ED if a <D b then CatD (a) րHD CatD (b).
Condition (ii) ensures that the child/parent relation (<D ) only connects elements
of categories that are connected in the schema.
Example 5. Let D = (HD , ED , CatD , <D ) be the dimension given in Figure 1(b).
Then D is as follows ED = {all, a1 , a2 , b1 , b2 , c1 , c2 , d1 , d2 }; allD = all; CatD =
{all 7→ All, a1 7→ Article, a2 7→ Article, b1 7→ Journal, b2 7→ Journal, c1 7→ Area, c2 7→
Area, d1 7→ Subject, d2 7→ Subject, }; and <D = {(a1 ,b1 ), (a2 ,b2 ), (b1 ,c1 ), (b2 ,c2 ), (c1 ,all),
(c2 ,all), (a2 ,d1 ), (a2 ,d2 ), (d1 ,all), (d2 ,all)}.                                            2
The set of rollup relations of a dimension D is defined as follows. For each pair
of categories ci , cj ∈ CHD such that ci ր∗HD cj , there is a rollup relation denoted
by RD (ci , cj ) that has the following set of pairs {(a, b)|CatD (a) = ci , CatD (b) =
cj and a <∗D b}.
Example 6. Dimension in Figure 1 has, for example, RD (Article, Journal) = {(a1 ,b1 ),
(a2 ,b2 )} and RD (Article, Subject) = {(a2 ,d1 ), (a2 ,d2 )}.                   2

We say that the rollup relation RD (ci , cj ) is strict if for all elements x, y, z in
E, if (x, y) ∈ RD (ci , cj ) and (x, z) ∈ RD (ci , cj ) then y = z. The rollup relation
RD (ci , cj ) is covering if for all elements e ∈ E such that Cat(e) = ci , there exists
an element e′ ∈ E such that (e, e′ ) ∈ RD (ci , cj ). 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 di-
mensions 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 = (CH , րH ) be a hierarchy schema and let D = (HD , ED , CatD , <D )
be a dimension such that HD = H.
(i) A strictness constraint over H is an expression of the form ci → cj where
ci , cj ∈ CH and ci ր∗H cj . The dimension D satisfies the strictness constraint
ci → cj if and only if the rollup relation RD (ci , cj ) is strict.
(ii) A covering constraint over H is an expression of the form ci ⇒ cj where
ci , cj ∈ CH and ci ր∗H cj . The dimension D satisfies the covering constraint
ci ⇒ cj if and only if the rollup relation RD (ci , cj ) 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 di-
mension 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
RD (Article, Area) = {(a1 , c1 ), (a1 , c2 )} is non-strict.                     2

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


3    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 incon-
sistent with respect to Σ. Figure 2(b)-(c) shows repairs of the dimension D
with respect to Σ. Repair D1 is obtained by deleting edge (a1 ,b2 ) and inserting
(a2 ,d1 ), and repair D2 is obtained by deleting (a1 ,b1 ) and inserting (a2 ,d1 ). There
are other possible repairs, for instance, a repair D3 can be obtained by deleting
edge (b1 ,c1 ) and inserting edges (b1 ,c2 ) and (a2 ,d1 ). Even though repair D3 get
rid of the inconsistencies, repairs D1 , and D2 remain closer to dimension D. 2

Given two dimensions D = (HD , ED , CatD , <D ) and D′ = (HD′ , ED′ , CatD′ , <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.

Definition 1. [Repair, Minimal Repair] Let D = (HD , ED , CatD , <D ) be a di-
mension and Σ be a set of integrity constraints over HD .
(i) A repair of D with respect to Σ is a dimension D′ = (HD′ , ED′ , CatD′ , <D′ )
such that HD′ = HD , ED′ = ED , CatD′ = CatD , 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 Σ.                          2

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.

Example 9. The distance between D and the repairs in Figure 2(b)-(c) are
dist (D, D1 ) = dist (D, D2 ) = 2. Indeed, D1 , and D2 are the minimal repairs
of D with respect to Σ.                                                     2

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. 2

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.


4    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 seman-
tics [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 DLV4
[20] and Smodels5 [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.

       Atom           Interpretation
        C(a)          element a belongs to category C in dimension D
 R(a, b, C1 , C2 ) in D, the parent of element a is b, CatD (a) = C1 and CatD (b) = C2
 R ′ (a, b, C1 , C2 ) in D′ , the parent of element a is b, CatD (a) = C1 and CatD (b) = C2
RT ′ (a, b, C1 , C2 ) transitive closure of R ′
Ins(a, b, C1 , C2 ) the child/parent relation (a, b) with CatD (a) = C1 and CatD (b) = C2 ,
                      was inserted to get D′
Del(a, b, C1 , C2 ) the child/parent relation (a, b) with CatD (a) = C1 and CatD (b) = C2 ,
                      was removed to get D′
Table 1. Predicates of the repair program Π(D, Σ) that computes a repair D′ of D
with respect to Σ

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 con-
straints, 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.
Example 10. Consider the Phone dimensions DP hone in Figure 3. Even though
the dimension is expected to be covering and strict, the dimension is not since
the strictness constraint Number → Region and the covering constraint Number ⇒
AreaCode are violated. This is, DP hone is inconsistent with respect to the set of
constraints Σc (H) ∪ Σs (H). The repair program to compute the minimal repairs
contains the following facts and rules:
Number(N1 ).          Number(N2 ).        Number(N3 ).      AreaCode(45).       AreaCode(41).
City(TCH).            City(TEM).          City(CCP).        All(all).           Region(VIII).
Region(IX).                     R(N1 ,41,Number,AreaCode). R(N3 ,45,Number,AreaCode).
R(N1 ,TCH,Number,City).         R(N2 ,TEM,Number,City).          R(N3 ,CCP,Number,City).
R(45,IX,AreaCode,Region). R(41,VIII,AreaCode,Region). R(TCH,VIII,City,Region).
R(TEM,IX,City,Region).          R(CCP,VIII,City,Region).         R(IX,all,Region,All).
R(VIII,all,Region,All).
R ′ (X, Y, number, areaCode) ← Number(X), AreaCode(Y ), choice((X, areaCode)(Y )). (1)
R ′ (X, Y, number, city) ← Number(X), City(Y ), choice((X, city)(Y )).                       (2)
R ′ (X, Y, areaCode, region) ← AreaCode(X), Region(Y ), choice((X, region)(Y )).             (3)
R ′ (X, Y, city, region) ← City(X), Region(Y ), choice((X, region)(Y )).                     (4)
R ′ (X, Y, areaCode, all) ← AreaCode(X), All(Y ), choice((X, all)(Y )).                      (5)
R ′ (X, Y, city, all) ← City(X), All(Y ), choice((X, all)(Y )).                              (6)
4
    DLV System: http://www.dbai.tuwien.ac.at/proj/dlv/
5
    Smodels System: http://www.tcs.hut.fi/Software/smodels/
                             All                                             all


                           Region                                        IX VIII


                      AreaCode City                             45 41        TCH TEM CCP


                          Number                                        N1    N2   N3


     (a) Dimension DP hone : hierar-                     (b) Dimension DP hone : elements and
     chy schema                                          rollup relations

                all                                all                                    all


             IX VIII                           IX VIII                                  IX VIII


   45 41        TCH TEM CCP           45 41        TCH TEM CCP               45 41        TCH TEM CCP


           N1   N2      N3                    N1   N2      N3                        N1   N2    N3


      (c) Repair DP1 hone               (d) Repair DP2 hone                    (e) Repair DP3 hone


      Fig. 3. Phone Dimension and repairs of it with respect to Σc (H) ∪ Σs (H)




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 6= 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 DP 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′ = (HD′ , ED′ , CatD′ , <D′ ) such that HD′ = HDP hone , ED′ = EDP hone , CatD′ =
CatDP 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 EDP hone . This new relation assigns to
each element a a new parent in every category cj such that Cat(a) րHDP hone cj .
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, cj ), (Y )) will assign a
unique value to Y in each stable model for each combination (X, cj ).
    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 three6 : M1 = {Ins(N2, 45,
Number, AreaCode), Ins(CCP, IX, City, Region), Del (CCP, VIII, City, Region)}, M2 = {
Ins(N3, 41, Number, AreaCode), Ins(N2, 45, Number, AreaCode), Del (N3, 45, Number,
AreaCode)} and M3 ={Ins(N3, TEM, Number, City), Ins(N2, 45, Number, AreaCode),
Del (N3, CCP, Number, City)}. The total weight of each best model corresponds to
the distance between each of the repairs and dimension D. Each of these models
corresponds indeed to the repairs of DP hone with respect to Σc (H) ∪ Σs (H)
shown in Figure 3(c)-(e).                                                          2

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 Ddel from
D for which the repairs of D can be computed only through reclassification of
child-parent relations of Ddel .

Example 11. Figure 4(a) shows the del-dimension Ddel 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(b)-
(c). If the del-elements are removed, these dimensions correspond to the repairs
of D with respect to Σ shown in Figure 2(b)-(c). The repair program for D with
respect to Σ contains the following facts and rules:
Article(a1 ).   Article(a2 ).   Article(del).     Journal(b1 ).       Journal(b2 ).
Journal(del).   Area(c1 ).      Area(c2 ).        Area(del).          Subject(d1 ).
Subject(del).   All(all).       All(del).         R(a1 ,b1 ,Article,Journal).
6
    To simplify the presentation we show only the Ins and Del atoms which show the
    modifications needed to restore consistency.
                   all del                              all del                              all del


        c1   c2    del        d1    del      c1   c2    del        d1    del      c1   c2    del        d1    del


        b1   b2    del                       b1   b2    del                       b1   b2    del


                  a1     a2   del                      a1     a2   del                      a1     a2   del


      (a) Dimension Ddel                                                       (c) D2 with del elements
                                          (b) D1 with del elements

                                    Fig. 4. del-Dimension for Example 11


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 6= del, Y 6= del.                                  (18)
RT ′ (X, Z, N1 , N3 ) ← RT ′ (X, Y, N1 , N2 ), R ′ (Y, Z, N2 , N3 ), X 6= del, Y 6= del, Z 6= del. (19)
 ← RT ′ (X, Y, Article, Area), RT ′ (X, Z, Article, Area), Y 6= Z.                                 (20)
 ← Article(X), not auxAll (X), X 6= del. ← Journal(X), not auxAll (X), X 6= del.                   (21)
 ← Area(X), not auxAll (X), X 6= del.           ← Subject(X), not auxAll (X), X 6= del.            (22)
auxAll (X) ← RT ′ (X, Y, Area1, All).                                                              (23)
Ins(X, Y, N1 , N2 ) ← R ′ (X, Y, N1 , N2 ), not R(X, Y, N1 , N2 ), Y 6= del.                       (24)
Del (X, Y, N1 , N2 ) ← R(X, Y, N1 , N2 ), not R( X, Y, N1 , N2 ), Y 6= 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 Ddel . Rules (14) to (17) compute a new candidate child-parent relation for the
elements in EDdel . 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).                                                                 2


5     Related Work
Letz et al. [21] motivate the importance of enforcing strictness constraints in
dimensions using constraints represented in dimensions hierarchies. In particu-
lar, 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 com-
pute 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.


6   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] ensur-
ing 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].

Acknowledgements: Loreto Bravo is funded by CONICYT grant PSD-57.
Mónica Caniupán is funded by FONDECYT grant #11070186.


References
 1. M. Arenas, L. Bertossi, and J. Chomicki. Consistent Query Answers in Inconsistent
    Databases. In PODS’99, pages 68–79, 1999.
 2. M. Arenas, L. Bertossi, and J. Chomicki. Answer Sets for Consistent Query An-
    swering in Inconsistent Databases. TPLP, 3(4-5):393–424, 2003.
 3. P. Barceló and L. Bertossi. Logic Programs for Querying Inconsistent Databases.
    In PADL 03, Springer LNCS 2562, pages 208–222, 2003.
 4. L. Bertossi. Consistent Query Answering in Databases. ACM Sigmod Record,
    35(2):68–76, 2006.
 5. L. Bertossi, L. Bravo, and M. Caniupan. Consistent Query Answering in Data
    Warehouses. In AMW’09, volume 450, 2009.
 6. M. Body, M. Miquel, Y. Bédard, and A. Tchounikine. Handling Evolutions in
    Multidimensional Structures. In ICDE’03, pages 581–591, 2003.
 7. L. Bravo and L. Bertossi. Semantically Correct Query Answers in the Presence of
    Null Values. In IIDB 06, Springer LNCS 4254, pages 336–357, 2006.
 8. F. Buccafurri, N. Leone, and P. Rullo. Enhancing Disjunctive Datalog by Con-
    straints. TKDE, 12(5):845–860, 2000.
 9. L. Cabibbo and R. Torlone. Querying Multidimensional Databases. In DBLP’98,
    pages 319–335. Springer-Verlag, 1998.
10. S. Chaudhuri and U. Dayal. An Overview of Data Warehousing and OLAP Tech-
    nology. SIGMOD Record, 26(1):65–74, 1997.
11. M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming.
    In ICLP’88, pages 1070–1080, 1988.
12. F. Giannotti, S. Greco, D. Saccà, and C. Zaniolo. Programming with Non-
    determinism in Deductive Databases. AMAI, 19(1-2):97–125, 1997.
13. C. Hurtado, C. Gutierrez, and A. Mendelzon. Capturing Summarizability with
    Integrity Constraints in OLAP. TODS, 30(3):854–886, 2005.
14. C. Hurtado and A. Mendelzon. Reasoning about Summarizability in Heterogeneous
    Multidimensional Schemas. In ICDT’01, pages 375–389, 2001.
15. C. Hurtado, A. Mendelzon, and A. Vaisman. Maintaining Data Cubes under Di-
    mension Updates. In ICDE’99, pages 346–355, 1999.
16. C. Hurtado, A. Mendelzon, and A. Vaisman. Updating OLAP Dimensions. In
    DOLAP’99, pages 60–66, 1999.
17. H. V. Jagadish, L. Lakshmanan, and D. Srivastava. What can Hierarchies do for
    Data Warehouses? In VLDB’99, pages 530–541, 1999.
18. R. Kimball and M. Ross. The Data Warehouse Toolkit: The Complete Guide to
    Dimensional Modeling. John Wiley & Sons, Inc., 2002.
19. H. Lenz and A. Shoshani. Summarizability in OLAP and Statistical Data Bases.
    In SSDBM’97, pages 132–143, 1997.
20. N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, C. Koch, C.Mateis, S. Perri,
    and F. Scarcello. The DLV System for Knowledge Representation and Reasoning.
    TOCL, 7(3):499–562, 2006.
21. C. Letz, E. Henn, and G. Vossen. Consistency in Data Warehouse Dimensions. In
    IDEAS’02, pages 224–232, 2002.
22. A. Mendelzon and A. Vaisman. Temporal Queries in OLAP. In VLDB’00, pages
    242–253, 2000.
23. T. Pedersen, C. Jensen, and C. Dyreson. Extending Practical Pre-Aggregation in
    On-Line Analytical Processing. In VLDB’99, pages 663–674, 1999.
24. T. Pedersen, C. Jensen, and C. Dyreson. A Foundation for Capturing and Querying
    Complex Multidimensional Data. Inf. Syst., 26(5):383–423, 2001.
25. M. Rafanelli and A.Shoshani. STORM: a Statistical Object Representation Model.
    In SSDBM’90, pages 14–29, 1990.
26. T. Syrjänen and I. Niemelä. LPNMR’01, chapter The Smodels System, pages
    434–438. Springer LNCS 2173. 2001.

</pre>