Query rewriting and answering under constraints in data integration systems

1 Introduction

The task of a data integration system is to combine data resid­ ing at different sources, providing the user with a unified view of them, called global schema. User queries are formulated over the global schema, and the system suitably queries the sources, providing an answer to the user, who is not obliged to have any information about the sources. The problem of data integration is a crucial issue in many application domains, e.g., re-engineering legacy systems, data warehousing, data mining, data exchange.

A central aspect of query processing is the specification of the relationship between the global schema and the sources; such a specification is given in the form of a so-called map­ ping. There are basically two approaches for specifying the mapping. The first approach, called global-as-view (GAY), requires that a view over the sources is associated with ev­ ery element of the global schema. Conversely, the second approach, called local-as-view (LAY), requires the sources to be defined as views over the global schema [Lenzerini, 2002; Duschka and Levy, 1997].

The global schema is a representation of the domain of in­ terest of the data integration system: integrity constraints are expressed on such a schema to enhance its expressiveness, thus improving its capability of representing the real world.

Since sources are in general autonomous, the data pro­ vided by the sources are likely not to satisfy the constraints on the global schema. Integrity constraints have to be taken into account during query processing; otherwise, the system may return incorrect answers to the user [Fagin et al., 2003; CaB et al., 2002].

Another significant issue is that the sources may not pro­ vide exactly the data that satisfy the corresponding portion of the global schema; in particular, they may provide either a subset or a superset of the data satisfying the mentioned por­ tion, and the mapping is to be considered sound or complete respectively. Mappings that are both sound and complete are called exact.

In this paper, we restrict our analysis to the GAY approach, which is the most used in the context of data integration. In particular, we study a relational data integration framework in which key dependencies (KDs) and inclusion dependencies (IDs) are expressed on the global schema, and the mapping is considered sound. The main contributions of this paper are the following:

1. After showing that query answering in the general case in undecidable, we provide a sound and complete query rewriting technique first for the case of IDs alone, and then for the case of KDs together with the maximal class of IDs for which the problem is decidable, called non­ key-conflicting IDs , or simply NKCIDs (Section 3).
2. Since it is likely that data retrieved at different, au­ tonomous sources violate the KDs, we introduce a novel semantics that is a "relaxation" of the sound semantics, and that allows (llinimal repairs of the data (Section 4). We then present a sound and complete query rewriting technique in the case where KDs and NKCIDs are ex­ pressed on the global schema (Section 5).
3. Finally, we present decidability and complexity results of the (decision) problem of query answering in the dif­ ferent cases (Section 6).

2 Formal framework for data integration

In this section we define a logical framework for data integra­ tion, based on the relational model with integrity constraints.

Syntax We consider to have an infinite, fixed alphabet r of constants (also called values) representing real world objects, and will take into account only databases having r as domain. We adopt the so-called unique name assumption, i.e., we as­ sume that different constants denote different objects.

Formally, a data integration system I is a triple (9, S, M), where:

1. 9 is the global schema expressed in the relational model with integrity constraints. In particular, Q = (Ill, ~I, ~ K), where ( i) Ill is a set of relations, each with an associated arity that indicates the number of its attributes. The attributes of a relation r of arity n are represented by the integers 1, ... , n. (ii) ~I is a set of inclusion dependencies (IDs), i.e. a set of as­ sertions of the form rd A] ~ r2 [B], where r1, r2 are relations in Ill, A = A1, ... , An (n 2: 0) is a se­ quence of attributes of r 1, and B = B1, ... , En is a sequence of attributes of r 2. (iii) ~K is a set of key de­ pendencies (KDs), i.e., a set of assertions of the form key(r) =A, where r is a relation in the global schema, and A = A1, ... , An is a sequence of attributes of r such that for each i E { 1, ... , n - 1} a; < ai+l· We assume, without loss of generality, that the attributes in A are the first n attributes of r. Moreover, we assume that at most one KD is specified for each relation.
2. S is the source schema, constituted by the schemas of the various sources that are part of the data integration system. We assume that the sources are relational, and that integrity constraints expressed on S are satisfied data at the sources. Hence, we do not take such con­ straints into account in our framework.
3. M is the mapping between the global and the source schema. In our framework the mapping is defined in the GAY approach, i.e., each relation in Ill is associated with a view, i.e., a query, over the sources. We indicate the mapping as a set of assertions of the form ( r, V), where r is a relation and V is the associated view over the source schema. We assume that the language used to express queries in the mapping is positive Datalog [Abiteboul et al., 1995], over the alphabet of the relation symbols in S. A Datalog query (or program) q of arity n is a col­ lection of rules of the form h(x) +- conj (x, y), where conj (x, y) is a set of atoms whose predicate symbols are either relation symbols in S or the head symbol h, and involvex = X 1 , ... ,Xn andy= Y1 , ... ,Ym. where X; and 1j are either variables or values of r. We call h(x) the head of the rule, and conj (x, y) the body.

Finally, a query over the global schema q is a formula that is intended to extract a set of tuples of elements of r. The language used to express queries over 9 is union of conjunc­ tive queries (UCQ) [Abiteboul et al., 1995], i.e., a Datalog program such that each rule head uses the same predicate of the same arity, and only relation symbols of 9 occur in each rule body.

Semantics A database instance (or simply database) C for a relational schema VB is a set of facts of the form r ( t) where r is a relation of arity n in VB and tis ann-tuple of values of the domain alphabet r . We denote as rc the set {t I r(t) E C}; moreover, given a Datalog query q, we denote as qc the evaluation of q over C, i.e., the minimal fixpoint model of q and C [Abiteboul et al., 1995].

In order to specify the semantics of a data integration sys­ tem I, we start by considering a source database for I, i.e., a database V for the source schema S. Based on V, we now specify which is the information content of the global schema Q. We call global database for I any database for Q. Formally, given a source database V for I= (Q,S,M), the semantics of I wrt V, denoted sem(I, V), is a set of global databases for I, where a global database B is in sem(I, V) if:

1. B is consistent with Q, i.e., it satisfies the IDs in ~I and the KDs in ~K. More formally: (i) B satisfies an inclu­ sion dependency ri[A] ~ r2[B] if for each tuple h in rP there exists a tuple t2 in rf such that t1[A] = t2[B], where t[A] is the projection of the tuple t over A. If B satisfies all inclusion dependencies expressed on Q we say that B is consistent with ~~; (ii) B satisfies a key dependency key ( r) = A if for each t1, t2 E r 8 with t1 =f. t2 we have ti[A] =f. t2[A]. If B satisfies all key dependencies expressed on 9 we say that B is consistent with ~K·
2. B satisfies the mapping M wrt V, i.e., it satisfies each pair (r, V) in M wrt V. In particular, we say that B satisfies the pair (r, V) wrt V, if all the tuples satisfy­ ing V in V satisfy r in B, i.e. vv ~ r 8 . Note that the above definition amounts to consider any view V as sound, which means that the data retrieved from sources satisfy the global schema, but are not necessarily com­ plete.

By simply evaluating each view over the source database V, we obtain a global database, called retrieved global database ret(I, V), that actually satisfies the sound mapping (but that is not necessarily consistent with Q).

We give now the semantics of queries. Formally, given a source database V for I we call answers to a query q of arity n w.r.t. I and V, the set ans ( q, I, V) defined as follows: ans(q,I,V) = {(c1 , ... ,cn) I foreach B E sem(I,V),(cl,····cn) E q 8 }.

In this paper, we address the query answering problem, that is the problem of computing the set ans(q,I, V). To this aim, we make use of query rewriting techniques, i.e., we ex­ ploit the mapping M to reformulate the query q into another query Qro the rewriting, that can be evaluated on the source database V . We say that Qr is a perfect rewriting of q w.r.t. I if qJ? = ans(q,I, V) for each V. Furthermore, with regard to decidability and complexity results, we will refer to the de­ cision problem associated to query answering, that is, given a data integration system I= (9, S, M), a source database V, a query q of arity n over Q and an-tuple t of values of r, to establish whether t E ans(q, I, V) .

Example 2.1 Consider a data integration system Io = (Qo,So,Mo), referring to the context of football teams. The global schema 90 consists of the rela­ tion predicates player(Pname, Pcountry, Pteam) and team ( Tacronym, Tname, Tleader), and the following constraints: key (player) = { Pname}, key (team) = {Tacronym}, team[Tleader] ~ player[Pname].

The source schema S0 consists of the schemas of three sources comprising the relation s1 of arity 4, and the rela­ tions s2 and s3 , both of arity 3. Finally, the mapping M 0 is defined by the two assertions

Consider the source database V 0 = { s1 (Totti ,ITA, RM, 27), s1 (Beckham, ENG, MU, 28), s2 (RM, Roma, Totti), s3 (MU, Man.Utd., Giggs)}. Then, ret(I0 , V 0 ) {player(Totti, ITA, RM), player(Beckham, ENG, MU), team(RM, Roma, Totti), team(MU,Man. Utd., Giggs)}. Notice that the facts in ret(I0 , V 0 ) together with the for­ eign key constraint team[Tleader] ~ player[Pname] im­ pose that Gi99s is a player. Since the views are sound, the semantics for the integration system has to account for all the global databases that provide the country and the team of the player. Hence, sem(I0 , V0 ) contains all database in­ stances that can be obtained by adding to ret(I0 , Vo) (among others) at least one fact of the form player ( Gigg s, a. , (J), where a. and (J are values of the domain r . Given the query q(X) +- player(X, Y, Z), we have that ans(q,I0 , V0 ) {Totti, Beckham, Giggs }. ·

3 Query rewriting

In this section we present algorithms for computing the per­ fect rewriting of a UCQ query in GAV integration systems with KDs and IDs. We first study the case in which only IDs are expressed on the global schema, then we deal with the simultaneous presence of both IDs and KDs.

Query rewriting under IDs only We start by studying query rewriting when only IDs are expressed on the global schema. To this aim, we need some preliminary definitions.

Given a conjunctive query q, we say that a variable X is unbound in q if it occurs only once in q, otherwise we say that X is bound in q. Notice that variables occurring in the head of the query are necessarily bound, since each of them must also occur in the query body. A bound term is either a bound variable or a constant.

In the following, we assume that all unbound variables in the query q are represented by the special term~-

Definition 3.1 Given an atom 9 = s(X1 , ... , Xn) and an inclusion I = r[i1, ... , ik] ~ s[j1, ... , jk], we say that I is applicable to 9 if, for each f. such that 1 :S f. :S n, if Xe -:f. ~ then there exists h such that Jh = f.. Moreover, we denote with gr(9, I) the atom s(Y1 , ... , Ym) (m is the arity of s in '1!) where for each f. such that 1 :S f. :S m, Ye = Xih if there exists h such that ih =f., otherwise Ye = ~-

Roughly speaking, an inclusion I is applicable to an atom 9 if the relation symbol of 9 corresponds to the symbol in the right-hand side of I and if all the attributes for which bound terms appear in 9 are propagated by the inclusion I. When I is applicable to 9, gr(9, I) denotes the atom obtained from 9 by using I as a rewriting rule whose direction is right-to-left.

Definition 3.2 Given an atom 91 = r(X1 , ... , Xn) and an atom 92 = r(Y1, ... , Yn), we say that 91 and 92 unify if for each i such that 1 :S i :S n, either xi = Y; or xi = ~ or Yi = ~. Moreover, if 91 and 92 unify, we denote as U (91, 92) the atom r(Z1 , ... , Zn) where, for each i, if Xi = Y; or Y; =~then Zi =Xi, otherwise Zi = Y;.

Informally, two atoms unify if they can be made equal through a substitution of each instance of the special symbol ~ with other terms.

Below we define the algorithm ID-rewrite to compute the perfect rewriting of a union of conjunctive queries Q. Infor­ mally, the algorithm computes the closure of the set of con­ junctive queries Q with respect to the following two rules: (i) if there exists a query q E Q such that body(q) contains two atoms 91 and 92 that unify, then the algorithm computes the query reduce(q, 91, 92), which is obtained from q by re­ placing 91 and 92 with U(91, 92) in the query body, and then by applying the substitution obtained in the computation of U (91, 92) to the whole query. Such a new query is then trans­ formed by the function r, which replaces with~ each variable symbol X such that there is a single occurrence of X in q. The use of r is necessary in order to guarantee that each un­ bound variable is represented by the symbol~- Such a query is then added to Q.

(ii) if there exists an inclusion I and a query q E Q con­ taining an atom 9 such that I is applicable to 9, then the algorithm adds to Q the query obtained from q by replac­ ing 9 with gr(9, I) in its body (denoted in the algorithm as q[9jgr(9, I)]). Namely, this step adds new conjunctions ob­ tained by applying inclusion dependencies as rewriting rules (applied from right to left).

The above rules correspond respectively to steps (a) and (b) of the algorithm.

Algorithm ID-rewrite(IJ!, ~I, q) Input: relational schema IJ1, inclusion dependencies ~I, union of conjunctive queries Q Output: perfect rewriting of Q Q' :=Q; repeat Qaux := Q'; for each q E Qaux do (a)foreach91,92 E body(q) do if 91 and 92 unify then Q' := Q' U { r(reduce(q, 91, 92))}; (b) for each 9 E body(q) do for each IE ~I do if I is applicable to 9 then Q' := Q' U { q[9/gr(9,I)]} until Qaux = Q'; return Q'

Termination of the algorithm is immediately implied by the fact that the number of conjunctions that can be generated by the algorithm is finite, since the maximum length of a gen­ erated conjunction is equal to the maximum length of a con­ junction in the body of the initial query Q, and the number of different atoms that can be generated by the algorithm is fi­ nite, since the alphabet of relation symbols used is finite (and corresponds to the relation symbols occurring in Q and in I:1 ), as well as the set of terms used (corresponding to the set of variable and constant names occurring in the query Q plus the symbol 0.

Henceforth, we denote as 11] D the UCQ returned by ID-rewrite(w, 1:1 , Q) . Moreover, we define the Datalog pro­ gram IIM = {VI(r, V) EM}.

Theorem 3.3 Let I = (Q, S, M) be an integration system and let Q be a UCQ query over Q. Then, II1 D U IIM is a perfect rewriting of Q w. r. t. I.

Query rewriting under KDs and IDs Now we address the problem of query rewriting in the case where KDs and IDs are defined on the global schema. Unfortunately, KDs and IDs interact reciprocally so that the (decision) problem of query answering in this setting becomes undecidable. The follow­ ing theorem is a consequence of a similar property proved in [Call eta!. , 2003] in the context of a single database.

Theorem 3.4 Consider a data integration system I = (Q,S ,M), with 9 = ('li, :EJ , :EK), where L:1 and L:K are sets of IDs and KDs respectively. Given a source database for I, a query q over 9, and a tuple t of values off, the problem of calculating ans(q, I, D) is undecidable.

Undecidability of calculating the certain answers to a query immediately implies undecidability of calculating the perfect rewriting [Call et al. , 2003]. The problem of query answering becomes decidable if we restrict the IDs to be in a particular class, so that they do not interact with KDs.

Definition 3.5 Consider a data integration system I = (Q,S, M), with 9 = ('l!, L:1 , L:K) . An ID r1[A1] ~ r2[A2] is a non-key-conflicting ID (NKCID) w.r.t. Kif either: (i) no KD is defined on r2; (ii) the KD key(r2) = K is in :EK and A2 is not a strict superset of K, i.e., A2 1; K. If all IDs in :E1 are NKCIDs w.r.t. L:K , the system I is said non-key­ conflicting (NKC).

We point out that the class of NKC IDs comprises the well­ known class of foreign key dependencies, which correspond toiDsoftheformrl[A1] ~ r2[A2] suchthatkey(r2) = A2 .

The most important feature of a NKC data integration sys­ tem is the separation between the IDs and the KDs; in such a case, in fact, we can take IDs into account as if the KDs were not expressed on 9.

Theorem 3.6 (Separation) Given a NKC data integration systemi = (Q,S,M), with9 = ('l!, :EJ , :EK), leti' = (9', S, M), with 9' = (\ll, L:1, 0), the system obtained by I by eliminating the KDs of 9 ; let D be a source database for I and I'. Moreover, let q be a query of arity n over 9 and 9', and [ann-tuple of values. We have that [ ¢ ans(q, I, D) iff Dis consistent with L:K and [ ¢ ans (q, I', D).

Proof (sketch). We say that D is consistent with L:K iff ret(I, D) is consistent with L;K. An important re­ sult, immediately derived from [Johnson and Klug, 1984], states that ans(q,I, D) is obtained by evaluating q over a (possibly infinite) database, called chase and denoted with chase(ret(I, D)). The chase is obtained by adding tuples to ret(I, D) in a way that the added tuples repair violations of IDs. The chase satisfies the IDs over 9, and it is a representa­ tive of all databases in sem(I, D) [Call et al. , 2002].

"=>"Since by hypothesis [ ¢ ans(q,I, D), there exists a global database B E sem(I, D) such that [ ¢ q 5 . Afortiori, B satisfies L:1, therefore B E sem(I', D), The claim follows immediately.

"-¢="By hypothesis, D is consistent with L:K and [ ¢ ans(q, I', D). Therefore, l ¢ qchase(ret(I',D)); note that chase(ret(I', D)) = chase(ret(I, D)). It can be shown, by induction on the number of added tuples in the construc­ tion of chase(ret(I, D)), that if I is a NKC system, and ret(I, D) satisfies L:K, also chase(ret(I, D)) satisfies L:K.

It follows that chase(ret(I, D)) is a representative for all databases in sem(I, D), and ans(q,I, D)= qchase(ret(I ,D)) . The claim follows straightforwardly. D

We now go back to query rewriting. In the case of a NKC data integration system, we can apply the same technique de­ veloped for IDs alone, provided that we take into account the KDs with suitable rules. Indeed, observe that if ret(I, D) vi­ olates L;K, any tuple is in the answer to any query. Therefore, with regard to this issue, we first introduce a unary global re­ lation val; the idea is that val stores all values occurring in D. We construct a set of rules IIval as follows: denoting with { r1 , . . . , r Nr} the set of all relations in 9,

with 1 ~ i ~ Nr and 1 ~ j ~ n ;. Then, consider a KD of the form key(r) = K ; without loss of generality, we suppose that r has arity m and K = {1 , . . . , k} (k < m). We introduce a set of m - k rules; in particular, for k + 1 ~ i ~ m:

We denote with IIKo the set of rules introduced as described above. From the results of Section 3 and from the above ob­ servation, we derive the following result.

Theorem 3.7 Consider a data integration system I = (9, S , M), and a query q of arity n over 9. Then, IIm U IIKo U II val U IIM is a perfect rewriting of q.

4 Semantics for inconsistent data sources

In the sound semantics, violations of IDs are treated "auto­ matically"because of the nature of the semantics; instead, the violation of a single KD leads to the non-interesting case in which sem(I, D) = 0.

According to a common approach in the literature on in­ consistent databases [Fagin et al., 1983; Lin and Mendelzon, 1998; Arenas et al., 1999], we now introduce the loosely­ sound semantics, opposed to the previous one (that we will call strictly-sound), in which the soundness assumption is suitably relaxed. The intuition is that in the "relaxed" seman­ tics we are allowed to delete tuples from ret(I, D) to repair violations of KDs, as long as we "minimize" such deletions; violations of IDs are treated as in the sound semantics.

Given a source database D, we define the following order­ ing » (I ,D) over the global databases for I that are consistent with 9. Given two such global databases B1 and B2, we write B1 »(:r,v ) B2, iff B1 n ret(I, D) :::> 8 2 n ret(I, D) . That is, the portion of ret(I, D) contained in the global database is greater in 8 1 than in B2 , i.e., B1 approximates the sound mapping better than B2 .

We call maximal w.r.t. (I, D) a global database B for I consistent with 9, such that there exists no global database B' consistent with 9 such that B' » (I,D) B. Based on this notion, we define the looselysound semantics sem1 as follows: sem1 (I, D) {B I B is consistent with 9 and B is maximal w.r.t. (I, D)}. Finally, we denote with ans1(q,I, D) the set of answers to queries under the loosely-sound semantics.

Example 2.1 (cont.) Consider now the source database D' obtained by adding to Do the fact s2 (RM,Roma,Beckham). Then, ret(Io, D') = ret(Io, Do) U { team(RM, Roma, Beckham)} We have now that the tuples in ret(I0 , D') violate also the KD key (team) = { Tacronym} ; hence, sem1 (Io, D') con­ tains the databases of the forms {player(Totti,ITA, RM), player(Beckham, ENG, MU), team(MU, Man. Utd., Giggs), team(RM, Roma, Totti), player( Giggs, a, /3)} and {player(Totti, ITA, RM), player(Beckham, ENG, MU), team(MU,Man.Utd., Giggs), team(RM, Roma,Beckham) , player(Giggs, a, /3)}, for each a, (3 E r .

Notice that for the query q(X) +- player(X, Y, Z) ansl(q,Io, V') = ans(q,Io, D). On the other hand, given the query q'(X, Z) +- team(X, Y, Z) we have that ans1(q',I0 ,D') {(MU,Giggs)} whereas ans(q',I0 , D)= { (MU, Giggs), (RM, Totti)}. ·

It is immediate to verify that, if sem(I, D) =f. 0, then sem1(I, D) = sem(I, D), i.e., if there exists a global database that satisfies both the constraints on g and the map­ ping assertions in M w.r.t. a source database D, then the strictly-sound and the loosely-sound semantics coincide.

5 Query rewriting in loosely-sound semantics

We now address the problem of computing answers to a query under the loosely-sound semantics. Specifically, we present a rewriting technique to compute answers to queries posed to NKC systems under the loosely-sound semantics.

Our method relies on Theorem 3.6 stating that for NKC systems it is possible to "separately" deal with inclusion and key dependencies: actually, for the first ones we exploit the algorithm ID-rewrite(w, :E1 , Q) presented in Section 3, whereas for the second ones we make use of Datalog~ un­ der stable model semantics , a well-known extension of Dat­ alog that allows for using negation in the body of program rules [Kolaitis and Papadimitriou, 1991].

More specifically, we define a Datalog~ program lilKD that allows us to compute the maximal subsets of ret(I, D) that are consistent with :EK . li1K D is obtained by taking, for each relation r E g, the rules

where: in r(x, y) the variables in X. correspond to the at­ tributes constituting the key of the relation r; y = Y1 , ... , Y m and z = Z1 , . . . , Zm.

Informally, for each relation r, li1K D contains (i) a relation rv that represents rret(I,'D); (ii) a relation r that represents a subset of rret(I,'D) that is consistent with the KD for r; (iii) an auxiliary relation f. The above rules force each stable model M of li1K D to be such that rM is a maximal subset of tuples from r ret(I,'D) that are consistent with the KD for r.

Then, we consider the Datalog~ program lilKD U liJD U liMv. where lim is obtained through ID-rewrite(w, :E1 , Q), and liMv is obtained from liM by replacing each symbol r with rv.

Theorem 5.1 Let I = (9, S, M) be a NKC system, and Q be a UCQ ofarity n over Q. Then, lilKD U lim U liMv is a perfect rewriting ofQ w.r.t. I.

6 Summary of complexity results

Strictly-sound semantics. Query answering is undecidable even if we allow a slightly more general class of IDs than the NKCIDs; let us define a !-key-conflicting (IKC) data inte­ gration system as a system such that for each ID ri[A1] ~ r2[A2], A2 can be a strict superset of key(r2 ) (if defined), but containing at most one attribute more than key(r2 ).

Theorem 6.1 The problem of query answering in I KC inte­ gration systems, under the strictly-sound semantics, is unde­ cidable.

In the strictly-sound semantics, the complexity of the deci­ sion problem of query answering is immediately derived from the rewriting of Section 3.

Theorem 6.2 The problem of query answering in NKC in­ tegration systems, under the strictly-sound semantics, is in PTIME in data complexity.

Proof. Trivial, since the perfect rewriting liw U liKD U lival U liM can be evaluated in PTIME w.r.t. D. 0

Loosely-sound semantics Since, as we already said, when sem(I, D) =f. 0 the strict semantics and the loose ones co­ incide, it is easy to see that the above properties of query answering under the strictly-sound semantics can be easily generalized.

Theorem 6.3 The problem of query answering in 1 KC inte­ gration systems, under the loosely-sound semantics, is unde­ cidable.

We now characterize the problem of query answering un­ der the loosely-sound semantics in NKC systems.

Theorem 6.4 The problem of query answering in NKC inte­ gration systems, under the loosely-sound semantics, is coNP­ complete in data complexity.

Proof (sketch). Membership in coNP follows from Theo­ rem 5.1, and from the fact that query answering in Datalog~ is coNP-complete in data complexity, while coNP-hardness can be easily proved by a reduction of the 3-COLORABILITY problem to our problem. 0

The summary of the results we have obtained is reported in the table in Figure 1, which presents the complexity of query answering for both the strictly-sound and the loosely­ sound semantics. Each row corresponds to a different class of dependencies (specified in the first two columns), while each cell of the table reports data complexity and combined complexity 1 of query answering for UCQs: for each decid­ able case, the complexity of the problem is complete w.r.t. the class reported. In the second column of the table, FK stands for "foreign key dependencies" (a well-known class of IDs) while GEN stands for "general IDs". We have marked with the symbol · the cells corresponding either to already known results or to results immediately implied by known results.

1 The results for combined complexity, which we cannot present in detail due to space limitations, hold under the assumption that the mapping is expressed in terms of UCQs.

7 Discussion and related work

In this paper we have presented techniques for query rewrit­ ing in data integration systems with integrity constraints. and analyzed the complexity of query answering. To this aim, we have exploited formalisms and methods both from the tradi­ tional database theory and from computational logic.

Several works in the literature address the problem of data integration under constraints on the global schema. In this respect, query rewriting under integrity constraints has been first studied in the LAV setting. In particular, [Duschka and Genesereth, 1997] presents a method for query rewriting un­ der functional dependencies in LAV systems, which is able to compute the perfect rewriting in the case of queries and map­ ping expressed through conjunctive queries, and "maximally contained" rewritings in the case of recursive mappings.

Then, [Gryz, 1999] analyzes query rewriting under inclu­ sion dependencies in LAV systems, and presents a method which is able to deal simultaneously with acyclic IDs and functional dependencies, based on an algorithm for comput­ ing the rewriting of a conjunctive query in a database with inclusion dependencies. The algorithm is based on a very in­ teresting idea: obtaining query rewriting by computing the rewriting of each atom in a way "almost independent" of the other atoms. This can be obtained if the body of the ini­ tial query q is preliminarly "minimized". However, we have found out that Gryz's algorithm does not actually compute the perfect rewriting, in the sense that some conjunctions of the perfect rewriting are missing. Our algorithm ID-rewrite presented in Section 3 is certainly inspired by Gryz's main in­ tuitions, but overcomes the above mentioned incompleteness through a new technique for generating the rewriting.

Complexity of query answering in GAV under IDs alone is immediately derived by the results in [Johnson and Klug, 1984]; in this work, the same problem is solved for a re­ stricted class of KDs and IDs, which, however, is significantly less general than the one treated in this paper. More recently, integration under constraints in GAV systems has been ad­ dressed in [Can et al., 2002], which presents a method for query rewriting in the presence of KDs and foreign key de­ pendencies, under a semantics analogous to our strictly-sound semantics. Thus, the method does not deal with data incon­ sistencies w.r.t. KDs. Moreover, [Fagin et al., 2003] presents an approach for dealing with integrity constraints in a GLAV setting (a generalization of LAV and GAV).

In single database settings, [Arenas et al., 1999; Greco et al., 2001] propose methods for consistent query answering in inconsistent databases, which are able to deal with universally quantified constraints. The semantics adopted in these works is different from the ones considered in the present paper.

Acknowledgments This research has been supported by the Projects INFOMIX (IST-2001-33570) and SEWASIE (IST2001-34825) funded by the EU, and by the Project D2I funded by MIUR (Ministero per I'Istruzione, I'Universita e Ia Ricerca). We thank Maurizio Lenzerini and Jarek Gryz for precious discussions about this material.