Logic Programs for Consistently Querying Data Integration Systems

1 Introduction

For several reasons a database may become inconsistent wrt certain integrity constraints (ICs). In such a situation, possi­ bly most of the data is still consistent. In [Arenas et al. , 1999] consistent data in a single relational database is characterized as the data that is invariant under all minimal restorations of consistency, i.e. true in all repaired versions of the original instance (the repairs). In that paper and others [Arenas et al., 2000; Greco et al., 2001], some mechanisms have been devel­ oped for retrieving consistent answer when queries are posed to such an inconsistent database.

When independent data sources are integrated, inconsisten­ cies wrt to global ICs are likely to occur, specially when the sources are virtually integrated by means of a mediator, be­ cause the data sources are kept completely independent. The mediator provides a global schema as an interface, and is re­ sponsible for generating query plans to answer global queries by retrieving data sets from the sources and combining them into a final answer set for the user.

"Local-as-view" (LAY) is a common paradigm for data in­ tegration that describes each data source as a set of views over the global schema. Another one, "global-as-view" (GAY), defines every global relation as a view of the set of relations in the sources ([Lenzerini, 2002] is a good survey). Query answering is harder in LAY [Abiteboul et al., 1998]. On the other side, the LAY approach allows more flexibility when new sources are integrated into an existing system. However, the flexibility to add new sources, without having to consider the other sources in the system, makes inconsistencies wrt global ICs more likely.

Example 1 Consider the LAV based global integration sys­ tem ®1 with a global relation R(X, Y) and two source rela­ tions vi= {V1(a, b) , V1 (c, d)} andv2 = {V2 (a, c), V2 (d, e)}

Leopoldo Bertossi

Carleton University School of Computer Science Ottawa, Canada bertossi@ scs.carleton.ca

that are described by the view definitions V1 (X, Y) +- R(X, Y); V2(X, Y) +- R(X, Y) . The global functional depen­ dency ( FD) R : X -+ Y is violated through the pair of tuples {(a, b), (a, c) }. o

In a virtual integration system, the mediator should solve po­ tential inconsistencies when the query plan is generated. In [Bertossi et al., 2002], under the LAY approach, a methodol­ ogy for generating query plans to compute answers to limited forms of queries that are consistent wrt an also restricted class of universal ICs was presented. The limitation comes from a first step where a query transformation for consistent query answering (CQA) is performed [Arenas et al., 1999]. Next, query plans are generated for the transformed query. How­ ever, [Bertossi et al., 2002] provides the right semantics for CQA in mediated integrated systems (see Section 2).

Example 2 (example 1 continued) If we pose to the global system the query Q : Ans(X , Y) +- R(X, Y), we obtain the answers { Ans(a, b), Ans(c, d), Ans(a, c), Ans(d, e)}. However, only the tuples Ans( c, d), Ans( d, e) should be re­ turned as consistent answers wrt the FD R : X -+ Y. 0

In this paper, under the LAY approach and assuming that sources are open (or incomplete) [Abiteboul et al., 1998], we solve the problem of retrieving consistent answers to global queries. We consider arbitrary universal ICs and referential ICs, in consequence all the ICs that are used in database praxis [Abiteboul et al., 1995]. View definitions are conjunc­ tive queries, and global queries are expressed in Datalog and its extensions with negation. The methodology can be sum­ marized as follows. First, in Section 3, the minimal legal global instances of a mediated system are specified by means of logic programs with a stable model, or answer sets, seman­ tics. Next, in Section 4, the repairs of the minimal global in­ stances are specified as the stable models of disjunctive logic programs. Those programs contain annotation constants, like those used to specify repairs of single relational databases for CQA [Barcelo et al., 2002]. Finally, in Section 5, consistent answers to queries are obtained by running a query program in combination with the previous two specification programs.

2 Preliminaries

2.1 Global schemas and view definitions

A global schema R is modeled by a finite set of relations {R1 , R2, ... , Rn} over a fixed domain U. With these relation symbols and the elements of U treated as constants, a first­ order language .C(R) can be defined. This language can be extended with new defined predicates and built-ins. In partic­ ular, we will extend the global schema with a local schema S, i.e. a finite set of new view predicates V1, V2 , ... ,that will be used to describe the relations in the local sources.

Each view, denoted by, say a new predicate V, is defined by means of conjunctive query [Abiteboul et at., 1995], i.e. an .C(n U S)-formula of the form 'Pv: V(t) <- body(cpv ), where lis a tuple containing variables and/or constants, and body( 'Pv) is a conjunction of n-atoms.

A database instance D over schema n can be considered as a first-order structure with domain U, where the extensions of the relations Ri are finite. (The extensions of built-in pred­ icates may be infinite, but fixed.) A global integrity constraint (IC) is an .C(R)-sentence '¢. An instanceD satisfies '¢, de­ notedD f= '¢,if'¢ is true in D.

Given a database instance D over schema n, and a view definition 'Pv , 'Pv (D) denotes the extension of V obtained by applying the definition 'Pv to D. If the view already has an extension v (corresponding to the contents of a data source), it is possible that v is incomplete and stores only some of the tuples in cp v (D); and we say the view extension v is open wrt D [Abiteboul et al., 1998]. Most mechanisms for deriving query plans assume that sources are open, e.g. [Duschka et al., 2000].

A sourceS is a pair (cp, v), where cp is the view definition, and v is an extension for cp. An open global system (!) is a finite set of open sources. The global schema n consists of the relation names that do not have a definition in the global system. The underlying domain U for n is a proper superset of the "active" domain. The latter consists of all the constants appearing in the view extensions Vi of the sources, and in their definitions. A global system (!) defines a set of legal global instances [Lenzerini, 2002].

Definition 1 Given an open global system (!) = { ( cp1, v1), . . . , (cpn, vn) }, the set of legal global instances is Linst(®) = {D instance over n I Vi~ 'Pi(D), i = 1, . .. ,n}. 0

Example 3 (example 2 continued) Let us denote by cp1 , 'P2 the view definitions ofVl, V2, resp. in ®1. D = {R(a, b), R( c, d), R( a, c), R( d, e)} is a legal global instance, because v1 = {V1(a , b), V1(c, d)}~ <p1(D) = {V1(a, b) , V1(c, d), V1 (a, c), V1(d, e)} andv2 = {V2(a, c), V2(d, e)}~ cp2(D) = {V2(a, b), V2(c, d) , V2(a, c), V2(d, e)}. Supersets of D are also legal instances. 0

The semantics of query answers in mediated integration sys­ tems is given by the notion of certain answer. In this paper we will consider queries expressed in Datalog and its exten­ sions with negation.

Definition 2 [Abiteboul et al., 1998] Given an open global system (!) and a query Q(X) to the system, a tuple i is a certain answer to Q in (!) if for every global instance D E Linst(®), it holds D f= Q[~. We denote with Certain~S ( Q) the set of certain answers to Q in®. 0

The inverse-rules algorithm [Duschka et al., 2000] for gen­ erating query plans under the LAY approach assumes that sources are open and each source relation V is defined as a conjunctive view over the global schema: V(X) <- P1(X1) , ... , Pn(Xn), with X~ Ui Xi.

Then,forj = l , . .. n, P1(Xj) <- V(X) isaninverserule for P1. The tuple X1 is transformed to obtain the tuple Xj as follows: if X E X1 is a constant or is a variable appearing in X, then X is unchanged in Xj . Otherwise, X is a variable xi that does not appear in x, and it is replaced by the term fi(X), where fi is a fresh Skolem function. We denote the set of inverse rules of the collection V of source descriptions in(!) by v-1.

Example 4 Consider the mediated data integration system ® 3 with global schema n = {P, R}. The set V of local view definitions consists of V1 (X, Z) <- P(X, Y), R(Y, Z), and V2(X, Y) <- P(X, Y). The set v- 1 consists of the rules P(X, f(X, Z)) <- V1(X, Z); R(f(X, Z), Z) <­ V1(X, Z); and P(X, Y) <- V2(X, Y). o

The inverse rules are then used to answer queries expressed in terms of the global relations, that now have definitions in terms of the sources. The answers obtained with the in­ verse rule algorithm are maximally contained in the queries [Duschka et al., 2000], and coincide with the certain answers [Abiteboul et al., 1998] .

2.2 Global systems and consistency

We assume that we have a set of global integrity constraints IC that is consistent as a set of logical sentences, and generic, in the sense that it does not entail any ground database literal. ICs used in database praxis are always generic.

Definition 3 [Bertossi et al., 2002] (a) Given a global sys­ tem, ®, an instanceD is minimal if D E Linst(®) and is minimal wrt set inclusion, i.e. there is no other instance in Linst(®) that is a proper subset of D (as a set of atoms). We denote by Mininst ( (!)) the set of minimal legal global in­ stances of(!) wrt set inclusion. (b) A global system (!) is consistent wrt IC, ifforall DE Mininst(®), D f= IC. 0

Example 5 (example 4 continued) Assume that (!) 3 has the sourcecontentsv1 = {V1(a,b)}, v2 = {V2(a,c)}, resp. and that U = {a , b, c, u}. Then, the elements of Mininst(® 3 ) are of the form Dz = {P(a, z), R(z, b), P(a, c)} for some z E U. The global FD P(X, Y): X --+ Y is violated exactly in those minimal legal instances D z for which z =1- c. Thus, ®3 is inconsistent. 0

Definition 4 The ground tuple a is a minimal answer to a query Q posed to(!) if for every DE Mininst(®), a E Q(D), where Q(D) is the answer set for Q in D. The set of minimal answers is denoted by MinimallS ( Q). 0

Clearly Certain~S(Q) ~ Minimal~S(Q) . For monotone queries [Abiteboul et at., 1995], the two notions coincide [Bertossi et al., 2002] . Nevertheless, in Example 5 the query Ans(X, Y) <- ·P(X, Y) has (b, a) as a minimal answer, but not as a certain answer, because there are legal instances that contain P(b, a). Since consistency was defined wrt minimal global instances, the notion of minimal answer is particularly relevant.

Given a database instance D, we denote by L.(D) the set of ground formulas { P(a) I p En and D F P(a)}.

Definition 5 [Arenas et al. , 1999] (a) Let D , D' be database instances over the same schema and domain. The distance, 6. (D , D'), between D and D' is the symmetric difference 6.(D, D') = (I:( D) \ L:(D')) U (I:(D') \ I:( D)). (b) For database instances D , D', D", we define D' :::; D D" if 6. (D , D') ~ 6.(D, D") . o

Definition 6 (based on [Arenas et al., 1999]) Let <!) be a global system and I C a set of globaliCs. A repair of<!) wrt IC is a global database instance D', such that D' f= IC and D' is :S:D-minimalfor some D E Mininst (<B) . 0

Thus, a repair of a global system is a global database instance that minimally differs from a minimal legal global database instance. If <!) is already consistent, then the repairs are the elements of Mininst ( <!)) . In Definition 6 we are not requir­ ing that a repair respects the property of the sources of being open, i.e. that the extension of each view in the repair con­ tains the corresponding view extension in the source. Thus, it may be the case that a repair - still a global instance - does not belong to Linst(<B). If we do not allow this, a global sys­ tem might not be repairable. Repairs are used as an auxiliary concept to define the notion of consistent answer.

Example 6 (example I continued) The only element in Mininst(<B1 ) is Do = {R(a, b), R(c, d), R(a, c), R(d, e)}, that does not satisfy IC. Then, ® 1 is inconsistent. The re­ pairs are the global instances that minimally differ from Do andsatisfytheFD, namelyD6 = {R(a,b) , R(c, d),R(d,e)} and D5 = {R(a, c) , R(c, d), R(d,e)}. Notice that they do not belong to Linst(<B1 ) . 0

Definition 7 [Bertossi et al., 2002] (a) Given a global sys­ tem® , a set of global integrity constraints IC, and a global first-order query Q(X), we say that a (ground) tuple tis a consistent answer to Q wrt IC iff for every repair D of®, D f= Q[~. (b) We denote by Consise5(Q) thesetofconsis­ tent answers to Q in <B. 0

Example 7 (example 6 continued) For the query Q1 (X): ::JY R(X, Y), a is a consistent answer. Q2 (X, Y): R(X, Y) has ( c, d), ( d, e) as consistent answers. 0

If<!) is consistent wrt IC, then Consise5 ( Q) = Minimale5 ( Q). Furthermore, if the ICs are generic, then for any <!) it holds Consise5 (Q) ~ Minimale5 ( Q) [Bertossi et al., 2002] . Notice also that the notion of consistent answer can be ap­ plied to queries written in Datalog or its extensions with built­ ins and stratified negation.

3 Specification of Legal Instances

The specification of the class M ininst( <!)) for system <!) is given using normal logic programs, whose rules are inspired by the inverse-rules algorithm. They use auxiliary predi­ cates instead of function symbols, but their functionality is enforced using the choice predicate [Giannotti et al., 1991].

Definition 8 Given an open global system ®, the program, II(<!)), contains the following clauses:

1. Fact dom(a) for every constant a E U; and the fact V(a) whenever V(a) E vdor some source extension Vi in <B.
2. For every view (source) predicate V in the system with

The predicate Fi(X , Xi) is replacing the Skolem function f i (X) = Xi introduced in Section 2.1, and, through the choice predicate, it assigns values in the domain to the vari­ ables in the head of the rule that are not in X. There is a new Skolem predicate for each pair formed by a description rule as in item 2. above and a different existentially quanti­ fied variable in it. The predicate choice((X) , (Xi)) ensures that for every (tuple of) value(s) for X, only one (tuple of) value(s) for xi is non deterministically chosen between the constants of the active domain.

Example 8 (examples 4 and 5 continued) Program II(<!) 3 ) contains the following rules:

I . dom(a). dom(b) . dom(c). dom(u) . V1(a , b). V2(a, c). 2. P(X, Z) ,_ V1(X, Y), F1(X, Y, Z). R(Z, Y) ,_ V1(X, Y) , F1(X, Y , Z) . P(X, Y) ,_ V2(X, Y). 3. F1(X,Y,Z) ,_ V1(X,Y),dom(Z), choice((X, Y), (Z)). 0

For every program II with the choice operator, there is its stable version, SV(II), whose stable models correspond to the so-called choice models of I1 [Giannotti et al., 1991]. The program SV(II) is obtained as follows : (a) Each choice rule r: H ,_ B, choice{( X) , (Y)) in I1 is replaced by the rule H ,_ B ,chosenr(X, Y) . (b) For each rule as in (a), the following rules are added

The rules defined in (b) ensure that, for every tuple X where B is satisfied, the predicate chosenr (X, Y) satisfies the func­ tional dependency X --+ Y. In (a) the choice operator is re­ placed by the new predicate chosenr that forces the expected functional dependency.

Example 9 (example 8 continued) Program SV(II(<B3)) contains the following rules:

1. dom(a) . dom(b) . dom(c). dom(u). V1(a, b) . V2(a, c).
2. P(X, Z) ,_ VI(X, Y), F1(X, Y, Z) . R(Z, Y) ,_ V1 (X, Y), F1 (X, Y, Z). P(X, Y) ,_ V2(X, Y).
3. F1(X,Y,Z) ,_ V1(X,Y),dom(Z), chosen1(X,Y,Z) . 4. chosen 1(X,Y,Z) ,_ V1(X,Y),dom(Z), not diffChoice1 (X, Y , Z). diffChoice 1 (X, Y, Z) ,_ chosen 1 (X, Y, Z'), dom(Z), Z' =1- Z .

Its stable models are:

• M 1 = {dom(a), dom(b), dom(c), dom(u), V1(a, b) , V2(a, c), P(a, c), diffChoice 1 (a, b, a), chosen 1 (a , b, b) , diffChoice1 (a, b, c),
• diffChoice1 (a , b, u), F1 (a , b, a), R(a, b), P(a, a)}

diffChoice1 (a, b, u) , F1 (a, b, b) , R(b, b), P(a, b)} M2 = {dom(a),dom(b),dom(c),dom(u), V1(a,b), V2(a, c), P(a, c), chosen 1 (a, b, a) , diffChoice1 (a, b, b), diffChoice1 (a, b, c),

• M 3 = {dom(a),dom(b),dom(c) , dom(u), V1(a,b) , V2(a, c), P(a, c), diffChoice1 (a, b, a) , diffChoice1 (a , b, b) , chosen1 (a , b, c),

diffChoice1 (a , b, u), F1 (a, b, c), R(c, b)} M 4 = {domd(a), domd(b), domd(c), domd(u) , V1(a, b) , V2(a, c), P(a, c) , diffChoice1 (a, b, a) , diffChoice1 (a , b, b), diffChoice1 (a , b, c),

chosen1 (a, b, u) , F1 (a, b, u), R( u, b), P(a, u)}. D

Definition 9 The instance associated to a stable model M of IT(®) is DM = {P(a) I PER and P(a) EM}. D

Example 10 (example 9 continued) DMl' DM 2 , DM 3 , DM. are the elements of Mininst(Q53 ), namely {P(a, b), R(b, b), P(a,c)} , {P(a,a) , R(a, b), P(a,c)} , {P(a, c) , R(c, b)}, {P(a, u) , R(u, b) , P(a, c)}, respectively. D

Theorem 1 If M is a stable model of program SV(IT(®)), then D M E M ininst( Q5 ). Furthermore, the minimal legal instances obtained in this way are all the minimal legal in­ stances of® . D

The program IT( Q5) (or its stable version) can be used to com­ pute MinimalC!5(Q), where Q is a query expressed as a, say Datalognot program IT(Q). This can be done by running the combined program under the skeptical or cautious stable sta­ ble model semantics, that sanctions as true wrt the program whatis true in all choice (resp. stable) models. If the query Q is monotone, e.g. a Datalog query, then in the same way CertainC!5 ( Q) can be computed.

4 Specification of Repairs of a Global System

In [Barcelo et al., 2002] repairs of single relational databases are specified using disjunctive logic programs with stable model semantics. The approach works for arbitrary universal and referential ICs in the sense that the repairs of the database correspond to the stable models of the program. We briefly explain these programs, because they will be used to specify repairs of integration systems.

First, the database predicates in the program are expanded with an extra argument to be filled with one of a set of new an­ notation constants. An atom in (outside) the original database is annotated with td (fd). Annotations ta and fa are consid­ ered advisory values, to solve conflicts between the database and the ICs. If an atom gets the derived annotation fa. it means an advise to make it false, i.e. to delete it from the database. Similarly, an atom that gets the annotation ta must be inserted into the database.

Example 11 Consider the integrity constraint lfx(P(x) ---+ R(x)), and the inconsistent database instance r = {P(a)}. The logic program should have the effect of repairing the database. Single, local repair steps are obtained by deriv­ ing the annotations ta or fa. This is done when each IC is considered in isolation, but there may be interacting !Cs, and the repair process may take several steps and should stabilize at some point. In order to achieve this, we use annotations t*, f*. The latter, for example, groups together the annotations fd and fa for the same atom (rules I . and 4. below). These derived annotations are used to give a feedback to the bodies of the rules that produce the local, single repair steps, so that a propagation of changes is triggered (rule 2. below). The annotations t** and f** are just used to read off the literals that are inside (resp. outside) a repair. This is achieved by means of rules 6. below, that are used to interpret the models as database repairs. The following is the program:

• I . P(x, f*) +--- P(x , fa)· P(x , t *) +--- P(x , ta) · P(x, t*) +--- P(x, td)· (similarly for R)

2. P(x, fa) V R(x, ta) +--- P(x , t*), R(x , f*) .

3. P(a, td) +---.

1. P(x, f*) +--- not P(x, td) · R(x, f*) +--- not R(x, td)·

5. +--- P(x, ta) , P(x, fa)· +--- R(x , ta) , R(x, fa)·

6. P(x, t **) +--- P(x , ta)· P(x, f**) +--- P(x, fa)·

P(x, t**) +--- P(x , td) , not P(x, fa)·

P(x, f**) +--- not P(x, td), not P(x, ta)· (similarly for R)

Only rules 2. depend on the JCs. They say how to repair them when violations are found. Rules 3. contain the database atoms. Rules 4. capture the CWA. Rules 5. are denial pro­ gram constraints to discard models that contain an atom an­ notated with both ta and fa. The program has two stable models: {P(a, td) , P(a, t*) , R(a, f*) , R(a, ta) , P(a, t**) , R(a, t*), R(a, t**)}, and {P(a, td), P(a, t*),P(a, f*), R(a, f*), P(a,f**), R(a,f**), P(a, fa)}, thefirstone say­ ing (look at underlined atoms) that R(a) is inserted into the database; the second one, that P(a) is deleted. 0

The next definition combines into one program the specifica­ tion of the minimal legal instances and their repairs.

Definition 10 The repair program, IT(® , IC), of Q5 wrt IC contains the following clauses:

1. Facts as in 1. in Definition 8.
2. Each of the rules 2. in Definition 8 is replaced by PJCXj, td) +--- V(X) , 1\x,E(XA X) F;(X , Xi)·
3. Exactly the same rules as in 3. in Definition 8.
4. For every predicate P E R, the clauses

P(X, t*) +--- P(X, td), dom(X). 1

P(X, t*) +--- P(X, ta), dom(X).

P(J{, f*) +--- P(X, fa), dom(XJ.

P(X, f*) +--- dom(X), not P(X, td)·

1. For every first-order global universaliC of the form

V(Q1(:ih)V·· ·VQncYn) +--- P1(x1)/\ · ··1\Pm(Xm)/\cp) , where P;, Qj E R, and cp is a conjunction of built-in atoms, the clause

where X is the tuple of all variables appearing in database atoms in the rule.

6. For every referential 1C of the form Vx(P(x) ---+ -:3yQ(x', y)), with x' ~ x, the clauses

P(X, fa) V Q(X', null , ta) +--- P(X, t*) , not aux (X'), _ _ not Q(_X', null, td), doJn(X) .

aux(X') +--- Q(X', Y, td), not Q(X', Y, fa),dom(X', Y). aux(X') +--- Q(X', Y, ta), dom(X', Y) .

7. For every predicate P E R, the interpretation clauses:

P(a, f**) +--- P(a, fa) ·

P(a, f**) +--- not P(a, td), not P(a, ta)·

1 If X = (X1 , . . . , Xn), we abbreviate dom(Xl) 1\ · · · 1\ dom(Xn) with dom(X).

Rules 6. repair referential ICs by deletion of tuples or inser­ tion of null values that are not propagated through other ICs [Barcelo et al., 2003]. For this purpose, we consider that the new constant null tf. U, in particular dom(null) is not a fact. The choice models of program II(lB, !C) that do not contain a pair of literals of the form { P(a, ta), P(a, fa)} are called coherent models.

Definition 11 The instance associated to a choice model M of II(lB, IC) is DM = {P(a) I P(a, t**) EM}. D

Theorem 2 If M is a coherent choice model II(lB, !C), then D M is a repair of lB wrt I C. Furthermore, the repairs ob­ tained in this way are all the repairs of lB. D

5 Consistent Answers

Now, we can obtain the answers to queries posed to a system (!)that are consistent wrt to !C. We do the following:

1. We start with a query Q that is expressed as a stratified Datalog program, II( Q), whose extensional predicates are el­ ements of the global schema R. Each positive occurrence of those predicates, say P(£), is replaced by P(f, t**); and each negative occurrence, say not P(£), by P(l, f**). This pro­ gram has a query predicate Ans that collects the answers to Q. In particular, first order queries can be expressed as strati­ fied Datalog programs [Abiteboul et al., 1995].
2. Program II(Q) is appended to the program SV(II(lB, !C)), the stable version of the repair program.
3. The consistent answers to Q are the ground Ans atoms in the intersection of all stable models of II( Q)USV(II(lB, !C)).

Example 12 (example 9 cont.) Consider the global symme­ try integrity constraint sim : 't/x't/y(R(x, y) --> R(y, x)) on l53. We want the consistent answers to the query Q : P(x, y). First, the query is written as the query program clause Ans(X, Y) +-- P(X, Y, t**). This query program, II(Q), is run with SV(II( lB3, sim)), which on its turn has five stable models with the following associated repairs: (a) DM'i = { P(a, b), R(b, b), P(a, c)}, the repair of the al­ ready consistent minimal instances D M, in Example 10; (b) DM; = { P(a, a), P(a, c)} and DM; = { R(a, b), R(b, a), P(a, a), P(a, c) }, the repairs of the inconsistent instance DM 2 ; (c) DM~ = { P(a, c)} and DM5 = { R(c, b), R(b, c), P(a, c)}, the repairs of instance DM 3 ; and (d) DM6 = { P(a, u), P(a, c)} and DM'i = { R(u, b), R(b, u), P(a, u), P(a, c)}, the repairs of DM 4 ·

The corresponding stable models ofii(Q) U SV(II( lB3, sim)) are: (a)~= M~ U {Ans(a, b), Ans(a, c)}; (b) M; = M2 U {Ans(a, a), Ans(a, c)}; M; = M3 U {Ans(a, a), Ans(a, c)}; (c) M: = M4 U {Ans(a, c)}; ~ = M5 U {Ans(a, c)}; (d) M;; = M6 U {Ans(a, u), Ans(a, c)}; M; = M7 U {Ans(a, u), Ans(a, c)}. Ans(a, c) is the only query atom in all stable models, then the tuple (a, c) is the only consistent answer to the query. D

If (!) is consistent, then the consistent answers to Q computed with this method coincide with the minimal answers to Q, and then to the certain answers if Q is monotone. If we are inter­ ested in just the minimal answers to Q, without considering consistency issues, then they can be computed as above, but using II((!)) introduced in Definition 8 instead of II((!), !C) .

6 Conclusions

We have presented the most general approach so far to spec­ ifying, by means of disjunctive logic programs with a sta­ ble model semantics, the database repairs of a mediated in­ tegration system with open sources under the LAV approach. Then, consistent answers to queries posed to such a system are computed by running a query program together with the specification of database repairs under the skeptical or cau­ tious stable model semantics. The specification of the repairs is achieved by first specifying the class of minimal global le­ gal instances of the integration system. To the best of our knowledge, this is also the first specification, under the LAY paradigm, of such global instances in a logic programming formalism. This specification is inspired by the inverse rules algorithms, where auxiliary functions are replaced by auxil­ iary predicates that are forced to be functional by means of the non deterministic choice operator.

The methodology works for conjunctive view definitions, but can be extended to disjunctive views using the corre­ sponding extension of the inverse rules algorithm [Duschka, 1997]. Wrt the ICs and queries it can handle, the approach works for arbitrary universal and referential integrity con­ strains and queries expressed as Datalognot programs. In consequence, the current approach to consistent query an­ swering (CQA) subsumes and extends the methodologies pre­ sented in [Bertossi et al., 2002] for integration systems, and the one in [Barcelo et al., 2002] for stand alone relational databases.

For reasons of space, we just mention a few optimiza­ tions of the specification programs and their execution. The materialization of the CWA present in II(lB, !C) can be avoided by program transformation. Classes of common ICs can be identified for which SV(II(lB, !C)) becomes head-cycle-free, and in consequence, can be transformed into a non disjunctive program [Ben-Eliyahu et al., 1994; Barcelo et al., 2003]. The program for CQA can be split [Lif­ schitz et al., 1994] into the program that specifies minimal legal instances, the program that specifies their repairs and the query program. The first is non stratified, but its models can be computed bottom-up as fixpoints of an iterative op­ erator [Giannotti et al., 2001]; and the second one is locally stratified [Przymusinski, 1991]. Finally, if the query program is stratified, e.g. if the original query is first-order, then the consistent answers can be eventually computed by a bottom­ up evaluation mechanism.

For CQA we have successfully experimented with DLV [Eiter et al., 2000]. The current implementations of the dis­ junctive stable models semantics would be much more effec­ tive in database applications if it were possible to evaluate open queries in a form that is guided by the query rather than based on, first, massive grounding of the whole program and, second, considering what can be found in every (completely constructed) stable model of the program.

Wrt related papers, query answering in mediated integra­ tion systems under the assumption that certain global ICs hold has been treated in [Gryz, 1999; Duschka et al., 2000; Grant et al., 2002; Cali et al., 2002]. However, in CQA, we do not assume that global ICs hold. Logic programming specifications of repairs of single relational databases have been presented in [Arenas et al., 2000; Greco et al., 2001; Barcelo et al., 2002].

[Lembo et al., 2002] considers integration systems under the GAY approach that do not satisfy global key dependen­ cies. There, legal instances are allowed to be more flexible, allowing their computed views to accommodate the satisfac­ tion of the ICs. In this sense, the notion of repair is implicit; and the legal instances are the repairs we have considered here. View definitions are expressed as Datalog queries; and the queries to the global system are conjunctive. The "re­ pairs" of the global system are specified by normal programs under stable model semantics.

In [Bertossi et al., 2002], CQA in possibly inconsistent integration systems under the LAY approach is considered. There, the notion of repair of a minimal legal instance is in­ troduced. The algorithm for CQA is based on a query trans­ formation mechanism [Arenas et al., 1999] applied to first­ order queries. The resulting query may contain negation, and is run on top of an extension of the inverse algorithm to the case of stratified Datalog" 0 t queries. This approach is limited by the restrictions of the query transformation methodology.

Acknowledgments

Work funded by DIPUC, MECESUP, CONICYT, Carleton University Start-Up Grant 9364-01, NSERC Grant 25027902. L. Bertossi is Faculty Fellow of the IBM Center for Ad­ vanced Studies, Toronto Lab. We are grateful to Pablo Bar­ celo, Alvaro Cortes, Ariel Fuxman, Nicola Leone, and Al­ berto Mendelzon for useful conversations.