Unique Solutions in Data Exchange under sts Mappings

Abstract

In classical data exchange, multiple solutions may appear and inherently cause many problems. To tackle the problem, one may use a richer language for schema mapping to have a unique solution. Therefore, in the paper, we consider a data exchange setting in which schema mapping contains a set of source-to-target dependencies and a set of targetto-source dependencies (sts mappings). Under the setting, we rst study the problem of deciding whether a data exchange setting has a unique solution with respect to a source instance. We show that the problem is as hard as Unique SAT problem and provide some restricted cases where the problem is tractable. Besides, we consider a more general problem that aims to check if a data exchange setting guarantees unique solutions for arbitrary source instances. While the problem is undecidable in general, we still can characterise some fragments where the problem is decidable and complete for some complexity class.

-

Data exchange as a theoretical problem was introduced a decade ago in [ 10 ] and has been one of the most active research topics in foundation of databases due to the need for the exchange of data in many business applications. This is the problem of transforming data structured under a source schema into data structured under a target schema. Given a source instance, the purpose of data exchange is to materialise a valid target instance (called a solution) respecting the schema mapping, speci cations that describe the relationship between data in the two heterogeneous schemas { the source and the target.

Classically, schema mappings in data exchange are written as source-to-target tuple generating dependencies (s-t tgds) to specify that if some positive patterns hold in the source, then some corresponding positive patterns must hold in the target as well. Source-to-target tuple generating dependencies are existential rules with positive conjunctive body and positive conjunctive head; the head may contain existentially quanti ed variables. Under a s-t tgds mapping, there might be more than one solution corresponding to a given source database because the target instances might contain additional facts or unknown facts. That is, the target database is actually an incomplete database, in the sense of classical database theory, namely it is a set of possible databases. This leads to a mismatch between the purpose of data exchange-materialising a valid target database and its speci cations-generating multiple valid instances.

After data is exchanged and a target instance is generated, one may want to do query answering the target data. As a consequence of incomplete database, the problem is complex and non-intuitive for general (non-positive) relational or aggregate queries, since it is basically comparable to entailment with openworld semantics (namely the computation of certain answers ), and standard relational database technologies can not be used. Anomalies caused by certain answer semantics are mentioned in [ 2,10,1,12 ], and nicely summarised by [ 14 ] thought a set of examples.

In order to solve the query answering problem, the classical data exchange framework restricts the target query language to just monotone queries (i.e., positive queries or union of conjunctive queries). It turns out that the certain answer to monotone queries over the incomplete target database are the same as the answers of the same query over a representative speci c database (one of the so called universal solutions { the core being a minimal among them) [ 10 ]. With this restriction on the query language, query answering over the target databases becomes meaningful and e cient.

To give meaning to more expressive queries (i.e queries with negation or aggregation), various interesting extensions have been proposed to restrict the uncertainty of the target instance. Extensions that are based on semantic restriction include Close World Assumption (CWA) semantics by Libkin [ 13 ] and GCWA* semantics by Hernich [ 12 ]. Regarding to restrictions on syntax, a mapping language which is more expressive than s-t tgds, namely, bidirectional tgds were considered by Arenas et. al. [ 3 ]. However, these syntax and semantic restrictions are not strong enough in general to eliminate completely the uncertainty of target instances. As a matter of fact, they can not rule out all anomalies in query answering and also do not satisfy the ultimate goal of data exchange materialising a valid target instance. Another way to deal with the problem is to use the de nability abduction approach [ 15 ] that aims at nding extensions (including t s tgds) to the initial schema mappings to guarantee the uniqueness of the materialised target instance. The results mentioned in this paper can be considered as the complexity analysis of the t s tgds extension in the approach. Contribution. In this paper, we are interested in data exchange settings where there is no ambiguity in selecting a target instance to be materialised and consequently, query answering can be done properly through the target instance. In other words, given a data exchange setting we would like to check if schema mapping rules are strong enough to guarantee the uniqueness of valid target instance. Obviously, we always get a negative answer if the language of schema mapping is s-t tgds. Therefore, in the paper, we consider both source-to-target tgds and target-to-source tgds (t-s tgds) for the mapping rules. The mapping is called sts mapping in this paper.

The mapping language was rst considered in peer data exchange [ 11 ] in which a source peer may contribute data for a target peer through s-t tgds and a target peer may use t-s tgds to restrict the data it receives. The mapping language is more expressive than the bidirectional one in [ 3 ] since it contains arbitrary t-s tgds, not only the inverses of s-t tgds.

Given a data exchange setting in which schema mapping is in sts, we study the following decision questions. 1. Does the data exchange setting have an unique solution w.r.t a speci c source instance? 2. Does the data exchange setting guarantee a unique solution for any source instance?

As an example for the rst problem, consider the source schema with two relations fEmployee(EMPid), Phone(EMPid, PhNum)g, and a target schema with one relation Contact(CONid, PhNum). Given a source database fEmployee(1), Phone(1, 123)g and the following mappings:

Employee(x) ! 9yContact (x; y)

Contact (x; y) ! Phone(x; y)

Obviously, there is only one target instance fContact(1, 123) g that together with the source instance forms a logical model of the mappings and therefore the decision procedure should give a positive answer. If we change the source database to fEmployee(1), Phone(1, 123), Phone(2, 234)g, we do not have any more a unique solution and receive a negative answer.

To illustrate for the second problem, consider the source database with two relations with the schema fEmployee(EMPid), Manager(MANid)g, and a target database with one relation with the schema Sta (STid). In order to move the data from each of the source relation to the target relation we could state the following mappings:

Employee(x) ! Sta (x)

Manager (x) ! Sta (x)

Sta (x) ! Employee(x)

These mappings guarantee that for any source instance, there is at most one solution for it under these mappings and therefore the decision procedure should give a positive answer. Note that the mapping rules do not accept every source instance, i.e source databases in which there is some manager which is not an employee have no solution.

Note that our notion of unique solution is not related to the unique-solution property mentioned in [ 9 ] about inverting schema mapping, since the latter requires distinct source instances to have distinct sets of solutions. Organisation. We start with some preliminary notions and de nitions related to unique solution. In Section 3, we present the complexity results of checking the existence of unique solution w.r.t a source instance. Next section is devoted to the problem of guarantee unique solution. As usual, at the end is conclusion and outlook.

Formal Preliminaries A schema is a nite set of predicate names with associated arities. Let R be a schema, R = fR1; :::; Rkg, an instance I over R is an union of R1I; R2I; :::; RkI such that each RiI is a nite set of tuples having the same arity as Ri. If I is an instance of schema S1 and J is an instance of schema S2, we use (I; J ) to denote an instance of schema S1 [ S2.

We consider a classical rst-order logic setting to de ne the semantics of the framework. If I is an instance and is a logic formula, we write I j= if I satis es in the rst-order logic sense. If is a set of formulas, we write I j= to mean I j= for every 2 . Given an instance I, we use Adom(I) to describe the set of all constants appearing in I.

Given a set of sentences , we use ( ) to denote the signature of , i.e. the set of all non-logical symbols in .

Dependencies. A tuple generating dependency (tgd) is a sentence of the form 8x; z('(x; z) ! 9y (x; y)), where ' and are conjunctions of atoms. For the sake of readability, we write '(x; z) ! 9y (x; y) instead of the full formula. We focus on simple tgds, i.e., tgds in which every atom does not contain occurrences of constants and repeated occurrences of variables.

A tgd is a source-to-target tgd (s-t tgd) if ' and are formulas over S and T respectively, and vice versa, a tgd is a target-to-source tgd (t-s tgd) if ' and are formulas over T and S respectively. A tgd is full if y = ;, otherwise, it is embedded. A tgd is a local-as-view (LAV) dependency if ' is an atom. A LAV dependency is complete if z = ;.

Data Exchange. A data exchange setting is a tuple M = (S; T; ), where the set is referred to schema mapping, S and T denote the source and target schemas, respectively. In the following we consider only data exchange settings M in which = st [ ts and st is a set of s-t tgds and ts is a set of t-s tgds. We also assume that all the predicates from T appear in the schema mapping, i.e. the mappings tell us some information about each target predicate.

By a solution to the data exchange setting M for a source instance I, we mean a target instance J such that (I; J ) j= . We use the notation Sol(M; I) to denote the set of all solutions to the data exchange setting M for a source instance I.

Chase. Given an instance I and a set of tgds , if the chase of I with is nite, we denote by chase (I) the result of the nite chase. Please refer to [ 10 ] for the detailed de nition of chase.

Unique solution. We now de ne some notions related to unique solution that will be used later to de ne our main problems.

De nition 1. Given a data exchange setting M and a source instance I, (M; I)

has a unique solution i there is only one J such that J is a solution of M w.r.t the source instance I.

Without a speci c source instance, we are interested in the following property of data exchange setting.

De nition 2. Given a data exchange setting M, we say that M guarantees unique solutions i for every source instance I, if there is a solution J of M w.r.t I then (M; I) has a unique solution.

3

Existence of Unique Solution In this section, we study the complexity of checking if (M; I) has a unique solution. Formally, given a data exchange setting M, the problem is de ned as follows.

Problem: ExistenceOf U niqueSolution(M) Input: source instance I Output: Is there a unique target instance J such that J 2 Sol(M; I)?

We start our complexity analysis with a general setting in which mapping rules are arbitrary tgds. As we mentioned in the introduction, by considering also t-s tgds in the mapping, our data exchange setting is similar to a peer data exchange setting [ 11 ]. Since the data complexity of existent-of-solution problem in peer data exchange setting is NP-complete, we do not expect a lower complexity for ExistenceOf U niqueSolution(M). Indeed, we show that the complexity connection between the two problems is analogous as the connection between SAT and Unique SAT [ 4 ].

Theorem 1. Unique-solution-checking problem is in NP \ co-NP for data com

plexity.

Proof. Let us start the proof with a simple observation about the unique solution of a given data exchange setting M and a source instance I. Intuitively, the observation implies the fact that the number of tuples in the unique solution is polynomially bounded by the input.

Lemma 1. If J 2 Sol(M; I) and J is unique then Adom(J )

Adom(I).

Proof. Assume that there is an element a 2 Adom(J ) and a 2= Adom(I). Let J 0 be a target instance which is the same as J but a is replaced by a0 for some new constants a0 2= Adom(I) [ Adom(J ). J 0 is isomorphic to J , therefore J 0 2 Sol(M; I). This leads to a contradiction to the fact that J is unique.

Because the schema is xed, based on the lemma, it's straightforward to see that target instances which could be the unique solution of data exchange setting M for a source instance I have at most jTj jAdom(I)jm tuples where jTj is the number of target predicates and m is the largest arity in T.

As a consequence, we have the following naive algorithm to decide the problem. 1. Verify in NP if there is a solution by guessing a target instance J using only constants in Adom(I) and checking if J 2 Sol(M; I) tu

We show the problem is complete for the class of NP \ co-NP using the following theorem.

Theorem 2. Unique-solution-checking problem is NP \ co-NP hard.

Proof. We prove the theorem by providing a reduction from Unique SAT to our problem.

Let be a propositional formula in CN F , = C1 ^ ::: ^ Cm where each Ci is a disjunction of literals among n variables fp1; :::; png.

We form M and I from as follows.

S T I = fL(:; :); C(:); P (:); V (:); T (:); F (:); N otP (:); I(:; :)g; = fA(:; :); L0(:; :); T 0(:); F 0(:); I0(:; :)g; st = fL(i; p) ! L0(i; p),

T (x) ! T 0(x), F (x) ! F 0(x), I(x; y) ! I0(x; y), P (x) ! 9yA(x; y),

C(x) ! 9yz:L0(x; y) ^ A(y; z) ^ T 0(z)g ts = fL0(i; p) ! L(i; p),

T 0(x) ! T (x), F 0(x) ! F (x), I0(x; y) ! I(x; y), A(x; y) ! V (y) ^ P (x), A(x; y) ^ A(x; z) ^ T (y) ^ F (z) ! N otP (x),

A(x; y) ^ A(x0; y) ^ I0(x; y0) ! N otP (x)g = fP (pi); P ((pi))ji = 1; ng[ fV (true); V (f alse)g[ fT (true); F (f alse)g[ fI(pi; pi); I(pi; pi))g[ fC(i)ji = 1; ng[ fL(i; p)jp 2 Ci; i = 1; n)g[ fL(i; p)j:p 2 Ci; i = 1; n)g[ fN otP ( 1)g Intuitively, ts [ st guarantees A is a correct assignment which assigns: (i) truth values to propositions in and their negations; (ii) one truth value to one literals and (iii) opposite values to opposite literals. Besides, the last dependency in st implies that A form a model of .

Now we show that is unique SAT if and only if (M; I) has a unique solution.

If is unique SAT, let M be the unique model of . We consider target instance J such that T 0J = T I ; L0J = LI ; F 0J = F I and AJ = f(p; true); (p; f alse)j Lemma 2.

Sol(M; I). p 2 M g[f(p; true); (p; f alse)jp 2= M g. Obviously J 2 Sol(M; I) because M j= then for every clause Ci, there is some literal in Ci is assigned to true. If J is not unique then there is J 0 2 Sol(M; I) such that AJ0 6= AJ . Let M 0 6= M be the interpretation in which pi 2 M 0 i (pi; true) 2 AJ0 , then for every clause Ci, there is some literal l 2 Ci, l 2 M 0 if l is positive and l 2= M 0 if l is negative. Consequently, M 0 j= . This leads to a contradiction.

The inverse direction can be proved analogously.

Since st and ts do not depend in , we can conclude the problem is NP \ co-NP hard. tu

Now, let us identify some cases where the problem can be solved by a polynomial time algorithm.

Theorem 3. Suppose we consider data exchange setting M in which dependen

cies from target to source are full tgds. Then ExistenceOf U niqueSolution(M) is tractable.

Proof. In the algorithm mentioned in the proof of Theorem 1, one does not know which could be the unique solution therefore we need to guess and check an arbitrary one. This step is not necessary in case st contains only full tgds because we know what could be the candidate for the unique solution.

st contains only full tgds. If Sol(M; I) 6= ; then J = chase st (I) 2 Proof. Since J = chase st (I), (I; J ) j= st. Assume that J 2= Sol(M; I), then (I; J ) 6j= ts. Let J 0 be a target instance such that J 0 2 Sol(M; I). Because st contains only full tgds, J is also a core of the data exchange setting ( st; S; T ). Therefore, J J 0. Besides, since (J 0; I) j= ts, (J; I) j= . This leads to a contradiction.

Assume J = chase st (I) 2 Sol(M; I) and there is another J1 2 Sol(M; I). It holds that J J1 because st contains only full tgds. Let P be a target predicate and a is a tuple such that P (a) 2 J1 n J . Consider the target instance J2 = J [ fP (a)g. Since J J2, (I; J2) j= st. Besides, since J2 J1, (J2; I) j= ts. Therefore J2 2 Sol(M; I). As a matter of fact, to verify if J is the unique of (M; I), one can use the following PTIME algorithm: { Verify if J is a solution. { If J is a solution, for each target predicate P and each tuple a, check if J2 = J [ P (a) is in Sol(M; I). If there is no such P (a then conclude J is the unique solution. tu

A similar situation happens if we require tgds. ts to contain only complete LAV

Theorem 4. If ts contains only complete LAV dependencies then the unique

solution-checking problem is tractable .

Proof. By restricting target to source dependencies to be complete LAV tgds, we also know what could be the candidate for the unique solution. Assume that we have T contains k target predicates T1; :::; Tk. W.l.o.g we can assume that ts = fTi(x) ! si (x; y)ji = 1; kg where si (x; y) is some conjunctive query over source schema S. Let ts1 = fTi(x) si (x; y)ji = 1; kg, then the following lemma holds.

Lemma 3. ts contains only complete LAV tgds. If Sol(M; I) 6= ; then J = chase ts1 (I) 2 Sol(M; I).

Proof. Since J = chase ts1 (I) 2 Sol(M; I), (I; J ) j= ts and TiJ = Isi for i = 1; k. Assume that J 2= Sol(M; I), then (I; J ) 6j= st. Let J 0 be a target instance such that J 0 2 Sol(M; I), (I; J 0) j= st then for each Ti 2 T, TiJ0 Isi . Consequently, J 0 J . Besides, since (I; J 0) j= st, together with the fact J 0 J , we can imply (I; J ) j= st. This leads to a contradiction.

Based on Lemma 3, we have an analogous polynomial algorithm as in the proof of Theorem 3. tu 4

Guaranteeing Unique Solutions In this section, we show results on complexity of deciding if a data exchange setting guarantees a unique solution for any source instance. The problem is formalised as follows.

Problem: U niqueSolutionGuarantee()

Input: a data exchange setting M

Output: Does M guarantee unique solutions?

Without any restriction in the syntax of mapping rules, we show that the problem is undecidable as follows.

Theorem 5. The problem of deciding if a data exchange setting guarantees unique solutions is undecidable.

Proof. We prove the theorem by reducing the problem of checking conjunctive query containment under a set of tgds [ 6 ] to our problem.

Assume that we have a set of tgds and two conjunctive queries q1(x) and q2(x) written over ( ), contains n dependencies i : i(x) ! 9y:'i(x; y), i = 1; n. Take the data exchange setting M = (S; T; ) in which: { S = ( ) { T = fp(:)g [ fTiji = 1; ng such that each Ti is a new predicate which has the same arity as the arity of 'i(x; y). { st = fq1(x) ^ q2(x) ! p(x)g [ f i(x) ! 9y:Ti(x; y)ji = 1; ng [ f'i(x; y) !

Ti(x; y)ji = 1; ng. { ts = fp(x) ! q1(x)g [ fTi(x; y) ! 'i(x; y)ji = 1; ng.

We prove that j= q1 q2 if and only if M guarantees unique solutions.

Assume that j= q1 q2, then j= 8x:q1(x) $ q1(x) ^ q2(x). Assume M does not guarantee unique solutions, i.e there is a source instance I, there are at least two di erent target instance J1; J2 such that both (I; J1) and (I; J2) satisfy . Based on the construction of , we have for each target predicate Ti, TTihJ1er=efoTriJe2, =pJ1'iI=. BpJe2sid=esq,1Isi=nceq1I \imq2I p.lTiehsis ,leadj=stqo1(ax)co$ntrqa1d(xic)t^ioqn2(txo)tahsewfaecllt. that J1; J2 are di erent target instances.

In case 6j= q1 q2, then 6j= 8x:q1(x) ! q2(x). Therefore, there is a source instance I which is a model of but q1I 6= q1I \ q2I . Consider the two following qd1Ii \erqe2In.tBtaasregdeto nintshtaendcees nJit1ioanndof J2, wJ1h;eJre2 aTriJe1 so=luTtiioJ1ns=of'MiI; .pJT1hi=s mq1Ie;apnJs2 M= does not guarantee unique solutions.

Note that the above reduction also yields a lower bound for the complexity of the problem where the syntax of tgds is restricted and then it is decidable to check conjunctive query containment under a set of tgds. In order to introduce decidable algorithms for these cases, let us characterise necessary and su cient conditions of a data exchange setting that guarantees unique solutions. This can be done by using the notion of Beth's de nability [ 7 ].

De nition 3 (Beth's de nability). Let be a set of sentences in FOL. A predicate P is implicitly de nable from the set of predicates P under if for every two interpretations I = hDI ; I i and J = hDJ ; J i such that they are models of , it holds that PI = PJ implies P I = P J .

Based on the correspondence between the above de nition and the de nition of a data exchange that guarantees unique solutions, we have the following lemma.

Lemma 4. A data exchange setting M guarantees unique solutions if and only if for any predicate T 2 T, T is implicitly de nable from S under .

Since Beth's de nability can be veri ed by a logical entailment, we also can reduce the problem of checking the guarantee to the problem of checking atomic query containment under a set of tgds as follows.

Theorem 6. A data exchange setting M guarantees unique solutions if and

only if for any predicate T 2 T, [ e j= 8x:T (x) $ Te(x) where e is obtained from by replacing every target predicate Pt with a new predicate with the same arity Pet and Te is a new predicate having the same arity as T .

Together with the results in deciding query containment under tgds mentioned in [ 6 ], the theorem and the reduction in the proof of Theorem 5 allow us to obtain tight bounds of U niqueSolutionGuarantee() for the following fragments of tgds.

Corollary 1. Given data exchange setting M = (S; T; ). Deciding if M guarantees unique solutions has the following complexity:

1. 2EXPTIME-complete if

2. 2EXPTIME-complete if is weakly guarded. contains only guarded tgds.

Note that, by applying Beth's and Craig's theorems about de nability in the case a data exchange setting guarantees unique solutions, one can actually constructively rewrite target predicates as views of source predicates. Consequently, given a source instance, a unique target instance can be materialised easily by using SQL to compute the views. 5

Conclusion and Outlook We have considered the problem of checking if a data exchange setting under sts mappings has a unique solution and therefore it satis es the purpose of exchanging data. We have studied two decision questions of the problem, one w.r.t a speci c source instance and one w.r.t any source instance. While the former is decidable and can be solved using a Unique SAT solver, the latter is undecidable in general and is 2EXPTIME-complete in some fragments of tgds.

Besides the results and our on-going works in combined complexity analysis of the former, there are some issues that are deserved for further investigation. First, in [ 11 ] there is a syntactical class of tgds in which the existence-of-solution of peer data exchange is tractable. Besides, the class covers the case of full tgds and complete LAVs. Therefore, it is worth to study if the existence-ofunique-solution problem is also tractable for this class. Second, more tgd-based mapping languages should be considered for a complete complexity analysis such as disjunctive tgds [ 8 ] and its guarded fragments [ 5 ]. Last but not least, in the question about guarantee unique solution we have considered only the case that solution-existence implies unique -solution-existence. It is still unknown if the problem of checking a data exchange setting under sts mappings always admitting unique solutions is decidable or undecidable.

References

1. Foto N. Afrati and Phokion G. Kolaitis. Answering aggregate queries in data exchange . In PODS, PODS '08 , pages 129 { 138 . ACM, 2008 .

2. Marcelo Arenas , Pablo Barcelo, Ronald Fagin, and Leonid Libkin . Locally consistent transformations and query answering in data exchange . In PODS, PODS '04 , pages 229 { 240 , 2004 .

3. Marcelo Arenas , Gabriel Dieguez, and Jorge Perez . Bidirectional constraints for exchanging data: Beyond monotone queries . In Proceedings of the Twenty-Fourth International Joint Conference on Arti cial Intelligence , IJCAI 2015 , Buenos Aires , Argentina, July 25-31 , 2015 , pages 2698 { 2705 , 2015 .

4. Andreas Blass and Yuri Gurevich . On the unique satis ability problem . Information and Control , 55 ( 1-3 ): 80 { 88 , 1982 .

5. Pierre Bourhis , Michael Morak , and Andreas Pieris . The impact of disjunction on query answering under guarded-based existential rules . In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Arti cial Intelligence , Beijing, China, August 3-9 , 2013 , 2013 .

6. Andrea Cal , Georg Gottlob, and Michael Kifer . Taming the in nite chase: Query answering under expressive relational constraints . J. Artif. Intell. Res. (JAIR) , 48 : 115 { 174 , 2013 .

7. William Craig . Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory . J . Symb . Log., 22 ( 3 ): 269 { 285 , 1957 .

8. Alin Deutsch , Alan Nash, and Je Remmel . The chase revisited . In PODS, PODS '08 , pages 149 { 158 , New York, NY, USA, 2008 . ACM.

9. Ronald Fagin . Inverting schema mappings . In PODS, PODS '06 , pages 50 { 59 , New York, NY, USA, 2006 . ACM.

10. Ronald Fagin , Phokion G. Kolaitis, Renee J . Miller , and Lucian Popa . Data exchange: semantics and query answering . Theor. Comput. Sci. , 336 ( 1 ): 89 { 124 , 2005 .

11. Ariel Fuxman , Phokion G. Kolaitis, Renee J . Miller , and Wang Chiew Tan . Peer data exchange . ACM Trans. Database Syst ., 31 ( 4 ): 1454 { 1498 , 2006 .

12. Andre Hernich . Answering non-monotonic queries in relational data exchange . In ICDT , pages 143 { 154 , 2010 .

13. Leonid Libkin . Data exchange and incomplete information . In PODS, PODS '06 , pages 60 { 69 , New York, NY, USA, 2006 . ACM.

14. Leonid Libkin and Cristina Sirangelo . Open and closed world assumptions in data exchange . In Proceedings of the 2009 Description Logics workshop , 2009 .

15. Nhung Ngo and Enrico Franconi . Unique solutions in data exchange . In Database and Expert Systems Applications - 25th International Conference, DEXA 2014 , Munich, Germany, September 1- 4 , 2014 . Proceedings, Part II , pages 281 { 294 , 2014 .