Data Exchange is an old problem that was rstly studied from a theoretical point of view only in 2003. Since then many approaches were considered when it came to the language describing the relationship between the source and the target schema. These approaches focus on what it makes a target instance a \good" solution for data-exchange. In this paper we propose the inference-based semantics that solves many certain-answer anomalies existing in current data-exchange semantics. We show that in case of mappings represented by source-to-target tgds and safe target egds we may compute in polynomial time a target table (universal representative) able to exactly represent the inference-based semantics. We show that the new semantics agrees with the other semantics when it comes to UCQ queries. Finally we show that one may use the universal representative to compute certain-answers in tractable time for large class of non-UCQ queries even for a subclass of UCQ:.
The data-exchange problem is that of transforming a database existing under a source schema into another database under a di erent target schema. This database transformation is based on mappings that describe the relationship between the source and the target database. A mapping M can be viewed as a, possibly in nite, set of pairs (I; J ), where I is a source instance and J a target instance. In this case, J is called a data-exchange solution for I and M . The mapping between the source and the target database is usually speci ed in some logic formalism. The most widely accepted mapping language is the one based on sets of tuple-generating dependencies (tgds) and equality-generating dependencies (egds).
It is very common to query the target solutions. This takes us to the
problem of querying incomplete databases [
Based on the interpretation of the mapping language there may be
several semantics in data exchange. The rst semantics was introduced in [
To better understand the type of anomalies we may encounter under these semantics, consider the next simple example. A company has in the source schema a binary relation P representing the relationship between projects and employees. After some reorganization it was realized that each projects nancing should be provided by one or more cost-centers, each employee belonging to one of these cost-centers. With this the company creates the target schema with two binary relations P C and CE representing the project to cost-center and cost-center to employee relationship respectively. In the case of the unidirectional semantics the process can be speci ed by tgd
1 : 8p 8e P (p; e) ! 9cc P C(p; cc) ^ CE(cc; e): Let source I be P I = f(p1; e1); (p1; e2); (p2; e3)g, stating that there are two employees e1 and e2 working on project p1 and only employee e3 working on project p2. Consider query: Q:=8p 8cc P C(p; cc) ^ CE(cc; \e3\) ! p = \p2\ (Is e3 involved only in project p2?). Let instance J be P CJ = f(p1; cc1); (p2; cc1)g and CEJ = f(cc1; e1); (cc1; e2); (cc1; e3)g. Because J is part of all aforementioned unidirectional semantics, the certain answer for the given query will be un-intuitively false. Naturally one may expect this answer to be true, as there is no indication from the source that employee e3 is involved in project p1.
Motivated by certain answer anomalies in the current data-exchange semantics, in this paper we propose a new data-exchange semantics based on logical inference for mappings represented by sets of s-t tgds and safe target egds. This semantics eliminates most anomalies related to certain-answers and keeps the same certain answers with the other semantics for union of conjunctive queries. We will also show that under this settings for any source instance one may compute a target table representation that may be queries to obtain certain-answers for any FO query. Finally we will review some complexity results regarding the certain-answers under this new semantics and present large classes of FO queries for which certain-answers can be computed in polynomial time. More details, examples and proofs can be found in the full version of this paper.
This section reviews the basic technical preliminaries and de nitions. More
information on relational database theory can be obtained from [
A nite mapping f , where f (ai) = bi, for i 2 f1; : : : ; ng, will be represented as fa1=b1; a2=b2; : : : ; an=bng. When it is clear from the context f , it will be also viewed as the following formula a1 = b1 ^ a2 = b2 ^ : : : ^ an = bn. For a mapping f and set A, with f jA will denote the mapping f restricted to values from A. By abusing the notation, a vector x = (x1; x2; : : : ; xn) will be often viewed as the set fx1; x2; : : : ; xng, thus we may have set operations like xi 2 x or x \ y. Databases. A schema S is a nite set fS1; S2; : : : ; Sng of relational symbols, each symbol Si having a xed arity arity(Si). Let Cons, Nulls and Vars be three countably in nite sets of constants, nulls and variables such that there are no common elements between any two of these sets. Elements from Cons are symbolized by lower case (possibly subscripted) characters from the beginning of the alphabet (e.g. a, b1). Elements from Vars are represented by lower case (possibly subscripted) characters from the end of the alphabet (e.g. z, x2). Each element from the countable set Nulls is represented with, possible subscripted, symbol ? (e.g. ?i). A nave table T of S is an interpretation that assigns to each relational symbol Si a nite set SiT (Cons [ Nulls)arity(Si), sometimes we also view Si as a relation between elements of Cons [ Nulls. The set dom(T ) means all elements that occur in T , clearly dom(T ) Cons [ Nulls. A nave table T is called an instance if dom(T ) Cons. In contrast to general nave tables, which are identi ed by capitalized characters from the end of the alphabet (e.g. T , V ), instances are represented by capitalized characters from the middle of the alphabet (e.g. I, J ). The set of all instances over schema S is denoted Inst(S). A valuation v is a mapping over the set Cons [ Nulls such that v(a) = a, for all a 2 Cons, and v(?) 2 Cons, for all ? 2 Nulls. Valuations are extended to tuples and nave tables as follows. For each tuple t = (t1; t2; : : : ; tn), let v(t):=(v(t1); v(t2); : : : ; v(tn)); and for a nave table T over schema S, de ne v(T ) as Rv(T ):=fv(t) : t 2 RT g, for all R 2 S. The interpretation of a nave table T is given by Rep(T ):=fv(T ) : v valuationg.
Schema mappings. A data-exchange schema mapping is a triple M = (S; T; ), where S and T are two disjoint schemas named the source and target schema respectively; is a set of formulae expressing the relationship between the source and the target database. Most commonly, is represented by a set of sourceto-target tuple-generating dependencies (s-t tgds) and target equality-generating dependencies (egds). Where a source-to-target tuple-generating dependency is a FO sentence of the form: 8x (8y (x; y) ! 9z (x; z)), where x, y and z are vectors of variables from Vars; (x; y) (often referred to as the body of the tgd) is a conjunction of atoms over the source schema; and (x; z) (often referred to as the head of the tgd) is a conjunction of atoms over the target schema. An equalitygenerating dependency is a FO sentence of the form: 8x ( (x) ! x = y), where (x) is a conjunction of atoms over the target schema and x,y are variables from the vector x. A source instance I 2 Inst(S) and a target instance J 2 Inst(T) are said to satisfy a s-t tgd , denoted (I; J ) j= ; if I [ J is a model of in the model-theoretic sense. Similarly, a target instance J satis es an egd , denoted J j= , if J is a model for in the model-theoretic sense. This is extended to a set of s-t tgds and egds by stipulating that (I; J ) j= , for all s-t tgd 2 and J j= , for all egd 2 . A position in is a pair (R; i), where R is a relational symbol and 1 i arity(R). A position (R; i) is said to be a ected in if it holds an existentially quanti ed variable somewhere in . With a ( ) is denoted the set of all a ected positions in . When the schemata are known or not relevant in the context, we usually interchange the notion of schema mapping and the set of dependencies that de nes it.
A data-exchange semantics O associates for a schema mapping M = (S; T; )
and a source instance I a possible in nite set of target instances J(I; M )KO. We
refer to each element of J(I; M )KO as a solution for I and M under semantics O.
Queries. CQ, UCQ, UCQ: and UCQ6= denote the classes of conjunctive queries,
union of conjunctive queries, union of conjunctive queries with negation and
union of conjunctive queries with unequalities, respectively. For complete de
nitions of these classes, please refer to [
As mentioned in the introduction, there are many semantics considered in dataexchange. In this section we brie y review the most prominent of these semantics. In Section 3.4 we introduce a new semantics for mappings speci ed by sets of s-t tgds and egds that addresses many of certain-answers anomalies occurring under the current semantics. In the nal part of this section we will review the semantics based on bidirectional constraints. 3.1
The OWA-Semantics is the rst semantics considered in data exchange [
J(I; )Kowa := fJ 2 Inst(T) : I [ J j= g: (1) 3.2
To outcome the counter-intuitive behavior under the OWA-semantics Libkin [
The GCWA semantics was inspired from Minker's [
Example 1. Consider source instance with binary relation DeptC for departments and names of consultant employees working in that department and ternary relation DeptF T E for departments and full-time employees (name and id) from the given department. Suppose the company hires all the consultants as full-time employees, thus the target schema will be the ternary relation DeptEmp with the same structure as DeptF T E. The exchange mapping is represented as:
Consider source instance with consultants \john" and \adam" part of the \hr" department and full-time employee \adam" with employee id 1 part of \hr". Let target query be: Is there exactly one employee named adam in hr department?. Under the CGWA -semantics the query will return the counter-intuitive answer true, even if based on the source instance and given mapping one would expect the answer to be false, because beside full-time employee \adam" there maybe a consultant named \adam" in the \hr" department. 3.4
In order to avoid the certain-answer anomalies presented in this section and in the introduction, we present a new closed-world semantics for mappings speci ed by a set of s-t tgds and egds.
Let : (x; y) ! 9z (x; z) be a s-t tgd and I a source instance. A set of facts J 0 is said to be inferred from I and with function f denoted with I !f J 0 if f ( (x; y)) inferred from I and
I and f ( (x; z)) = J 0. Tuple t 2 J 0 is said to be strongly with function f if t 2 f jx( (x; z)), otherwise we say that t is weakly inferred. Intuitively a tuple t is strongly inferred from I and with f if t does not depend on the assignment given by f to existential variables from . Let be a set of s-t tgds, I a source instance and J a target instance. A function that assigns for each a set of functions ff1; f2; : : : ; fng such 2 that I !fi Ji J is called an inference strategy for I and J with . Note that the function that allocates the empty set for each 2 is an inference strategy for any I and . Given an inference strategy and 2 , a tuple t 2 J is said to be: strongly inferred with strategy for if there exist f 2 ( ) such that t is strongly inferred from I and with f ; not inferred with strategy for if there is no f 2 ( ) with I !f J 0 3 t; weakly inferred with strategy for otherwise. A tuple t is said to be inferred with strategy for I, and J if there exists 2 such that t is strongly or weakly inferred with for . With this we are now ready to introduce the inferred-based semantics.
De nition 1. Given a source instance I and a set of s-t tgds and egds the inference-based semantics for I and , denoted with J(I; )Kinf , is the set of all target instances J for which there exists an inference strategy such that: 1. Every tuple t 2 J is inferred with for I, and J ; 2. For every : ! 2 and every function f with f ( ) I there exists f 0 2 ( ) such that f 0 is an extension of f ; 3. For every : and J ; = SI!gJg;g2 ( ) Jg, there is no function ! 2 f with f ( ) 2 J ; and f ( ) 6 I, where f ( ) contains at least one weakly inferred tuple with strategy for . 4. (I; J ) j= in the model-theoretic sense.
Intuitively the rst rule from the de nition states that all tuples in the target
instance needs to be inferred from the source instance and the mapping, this is
taking care of the tuples not inferred present under OWA-semantics. This also
allows the same nulls to be matched to di erent constant as long as there exists
an inference for each of these. This takes care of the query anomalies present
under CWA-semantics. The second condition makes sure that all possible source
triggers are red. With this all tuples that can be inferred will be present in at
least in one instance in the semantics, this solves the anomaly presented in
Example 1 for GCWA . The third condition ensures that the assignment of nulls
does not contradict with the inference strategy used, thus taking care of the
query anomaly from the introduction. The last condition is needed in order to
guarantee that the instances from the semantics are models for the egds. Need
to mention here that by renouncing to Condition 3 from the previous de
nition we obtain the semantics de ned in [
Theorem 1. For a xed set of s-t tgds the solution-existence problem can be
solved in polynomial time and the solution-check is an NP-complete problem
under inference-based semantics.
Arenas et al. in [
J(I; $)K$:=fJ 2 Inst(T) : I [ J j= $g: (2)
This approach did solve most of the anomalies related to the other semantics.
Unfortunately, this is achieved at a high cost, as even the most common
dataexchange problems became non-tractable. For example, testing if the semantics
is empty is an NP-hard problem [
Another issue with bidirectional semantics is that there are simple unidirectional mappings for which neither of the presented closed-world semantics are not expressible using bidirectional constraints without changing the target schema, as shown in the example below.
Example 2. Consider source schema with two binary relations P F T E, for projects and the full-time employees assigned on the project, and P T , that contains the tasks associated with each project. Let target schema consist of a binary relation P E, for projects and employee assigned to that project, and binary relation T M , for employee and the task they manage. Consider source instance I, with P F T EI = f(hr; adam)g and P T I = f(hr; comp)g, stating that full-time employee `adam` works on the `hr` project and the 'hr' project consists of one task `comp'. Consider the following mapping stating that each full-time employee working on a project is also an employee working on the project ( 1) and that for each project task there exists an employee working on that project that manages that task ( 2).
1 : P F T E(pid; eid) ! P E(pid; eid) 2 : P T (pid; tid) ! 9eid P E(pid; eid); T M (eid; tid):
It is easy to observe that for any set $ of bidirectional constraints there is no possibility to di erentiate between the tuples from relation P E as being inferred from P F T E or P T source relation. Thus, for J1 = fP E(hr; adam)g, J2 = J1 [ fT M (adam; comp)g and J3 = J1 [ fP E(hr; sal); T M (sal; comp)g, we have that either J1 2 J(I; $)K$ or J2 2= J(I; $)K$ or J3 2= J(I; $)K$, where \sal" is a consultant not a full-time employee. On the other hand, we have that J1 2= J(I; )K and J2; J3 2 J(I; )K , for any semantics 2 fcwa; gcwa ; infg. 4
As mentioned in the introduction, data exchange transforms a database existing under a source schema into another database under the target schema. This means that for a given semantics it would be preferable to be able to materialize one or more table representations on a target. The materialized table(s) could later be used to obtain answers for di erent queries over the target database. In this section we will introduce a new type of table capable of representing all solutions for the inference-based semantics. Thus this new table can be used to obtain the certain answers for any FO query.
De nition 2. Let Nulls be partitioned in two in nite sets Nullso and Nullsc. A semi-nave table is a nave table T for which each null is identi ed as being either from Nullso or Nullsnc. The semi-nave table T has the following interpretation: Rep(T ):= J = v( [ vi(T )) : v valuation over Nullsc; vi valuation over Nullso i 1
The nulls from Nullso are called open and denoted ?o (possibly subscripted). The ones from Nullsc are called closed and denoted ?c (possibly subscripted). Example 3. Let T be the semi-nave table with RT = f(a; ?o1; ?c1; ?c2)g. We have I1; I2; I3 2 Rep(T ), where RI1 = f(a; a; b; c)g, RI2 = f(a; a; b; c); (a; b; b; c)g and RI3 = f(a; a; b; a); (a; b; b; a); (a; c; b; a)g. For RI4 = f(a; a; b; c); (a; a; b; d)g, we have that I4 2= Rep(T ), because closed null ?c2 was valued to both c and d.
To a semi-nave table T we add a global condition ' , denoted (T; ' ), as a conjunction 1 ^ 2 ^ : : : ^ n where each conjunct i, 1 i n, is a disjunction of unequalities over the elements from dom(T ). Given v a valuation over Nullsc and v1; v2; : : : ; vn valuations over Nullso, for some integer n, we say that (v; fv1; v2; : : : ; vng) satis es x 6= y, denoted (v; fv1; v2; : : : ; vng) j= (x 6= y), i : { v(x) 6= a, when x 2 Nullsc and y = a 2 Cons; { vi(x) 6= a, for all i n, when x 2 Nullso and y = a 2 Cons; { v(x) 6= vi(y), for all i n, when x 2 Nullsc and y 2 Nullso; { v(x) 6= v(y), when x; y 2 Nullsc; and { vi(x) 6= vj (y), for all i; j n, when x; y 2 Nullso.
The previous notion is naturally extended to a disjunction of unequalities and to the conjunctive formula ' where each conjunct represents a disjunction of unequalities. This is denoted (v; fv1; v2; : : : ; vng) j= ' . With this we can de ne: n Rep(T; ' ):= J = v( [ vi(T )) : n an integer, v valuation over Nullsc; i 1
vi valuation over Nullso and (v; fv1; : : : ; vng) j= ' Example 4. Consider (T; ' ), where T is the same as in Example 3 and global condition ' :=(?o1 6= a _ ?c2 6= ?o1). It can be veri ed that I1; I2 2 Rep(T; ' ) and I3 2= Rep(T; ' ) because the tuple R(a; a; b; a) in I3 was obtained from valuations v = f?c1=b; ?c2=ag and v1 = f?o1=ag and (v; fv1g) 6j= ' .
For the next result, let's de ne the notion of safe egds. For a set of s-t tgds and egds we say that it contains safe egds if each variable that occurs more than once in the body of an egd it occurs only in positions di erent than a ( ).
The following result shows that for any set of s-t tgds and safe egds there exists an exact representation for the inference-based semantics. Theorem 2. Let be a set of s-t tgds and safe egds. Then one may compute in polynomial time (for a xed ) (T; ' ) such that J(I; )Kinf = Rep(T; ' ).
The pair (T; ' ) from the previous theorem is called universal representative for I and . In Theorem 2 the universal representative is computed using a 3-step chase algorithm (for a detailed description please check the full version of the paper).
Example 5. Consider = f 1; 2; 3g, where: Let instance I be SI = f(a; b); (c; d)g and RI = f(a)g. In this case a universal representative for I and is the pair (T; ' ), where KT = f(a; ?c1); (c; ?o1)g, V T = f(?c1; b); (?o1; d)g, U T = f(a; ?c1)g and ' :=(?c1 6= ?o1). 5
If in the previous section we showed how we can compute universal representatives for inference-based semantics. in this section we will focus on when and how these representatives can be used to compute certain answers for di erent query classes and check the complexities of such evaluations. Let us rst start by de ning the certain-answer evaluation problem.
Problem Evalinf ( ,Q) Input: I 2 Inst(S) and t 2 (dom(I))arity(t).
Question: Is t 2 certinf (Q; (I; ))?
The following theorem ensures that for any mapping of s-t tgds and safe egds the OWA and inference-based semantics agrees on UCQ certain-answers for any source instance.
Theorem 3. Let be a set of s-t tgds and safe egds . Then for any source instance I and q 2 UCQ we have certowa(Q; (I; )) = certinf (Q; (I; )) and one may use the universal representative for I and to compute certinf (Q; (I; )) in polynomial time (for a xed ).
The following negative result shows that not all queries are tractable under inference-based semantics.
Theorem 4. There exists a set of s-t tgds and safe egds and there exists a query Q 2 CQ: such that the problem Evalinf ( ,Q) is coNP-complete.
From this it follows that for tractable query evaluation under inference-based semantics we need to restrict either the set or the query class used or both. In the last part of this section we will present such restrictions that ensure tractability for certain answers evaluation under inference-based semantics. Proposition 1. Let be a set of full s-t tgds and safe egds. Then for any FO query Q the Evalinf ( ,Q) is tractable and one may use the universal representative to compute it.
With UCQ6=;n is denoted the set of UCQ6= queries with at most n unequalities per disjunct.
Theorem 5. Let be a set of s-t tgds and safe egds. Then for any UCQ6=;1 query Q the Evalinf ( ,Q) problem is tractable and one may use only the universal representative to evaluate the query. And the Evalinf ( ,Q) for q 2 UCQ6=;2 is coNP-complete.
In [
Next we will present a subclass of CQ: that has tractable query evaluation properties for a restricted class of s-t tgds and safe egds. Let CQ:;1 denote the subclass of CQ: such that each query of this class has exactly one positive atom. Theorem 7. Let be a set of s-t tgds and safe egds, such that for all s-t tgds each existentally quanti ed variable occurs in only one atom and each egd does not equate two variables both occurring in a ected positions. Then for any CQ:;1 query the Evalinf ( ; Q) problem is polynomial and can be decided using a universal representative.
Intuitively, the restrictions on the mapping language from the previous theorem ensure that the universal representative does not have any global condition and it contains only open nulls. 6
In this paper we introduced the inference-based semantics for data exchange. We showed that the inference-based semantics solves most of the certain-answers anomalies existing in the existing semantics and that one may compute a universal representative that exactly represents the semantics. For the certain answer semantics it remained an open problem if one can evaluate certain-answers for any CQ:;1 queries in polynomial time for any and not only for the restricted class of dependencies presented here. As further work we intend to increase the language for this semantics to included target tgds too.