Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early works, but little attention has been paid to more general queries. A few semantics proposals for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings. The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-of too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is coNP-complete when the dependencies are weakly-acyclic.
Data exchange is the problem of transferring data from a source schema to a target schema, where the transfer process is usually described via so-called schema mappings, specifying how the data should be moved and restructured. Furthermore, the target schema may have its own constraints to be satisfied. Schema mappings and target constraints are usually encoded via standard database dependencies. Thus, given an instance over the source schema S, the goal is to materialize an instance over the target schema T, called solution, in such a way that and together satisfy the dependencies.
By now, the certain answers semantics is the most accepted one for answering queries. The
certain answers to a query is the set of all tuples that are answers to the query in every solution
of the data exchange setting [
In this example, we assume that the set of target dependencies Σ is empty. The above schema mapping states that all orders in the source schema must be copied to the AllOrd relation, and all the paid orders must be copied to the Paid relation. Assume the source instance is as follows: = {Ord(1, yes), Ord(2, no)}, and assume we want to pose the query over the target schema asking for all the unpaid orders. This can be written as the following FO query:
() = AllOrd() ∧ ¬Paid().
One would expect the answer to be {2}, since the schema mapping above is simply copying
to the target schema, and hence = {AllOrd(1), AllOrd(2), Paid(1)} should be the only
candidate solution. However, under the classical notion of solution of [
The issue above arises because the classical notion of solution is too permissive, in that it allows the existence of facts in a solution that have no support from the source (e.g., Paid(2) in the solution ′ of Example 1 above).
Some eforts exist in the literature that provide alternative notions of solutions for which
certain answers to general queries become more meaningful. Prime examples are the works
of [
Example 2. Consider the data exchange setting = ⟨S, T, Σ , Σ ⟩, where S stores employees of a company in the unary relation Emp. For some employees, the city they live in is known, and it is stored in the binary relation KnownC. The target schema T contains the binary relation EmpC, storing employees and the cities they live in, and the binary relation SameC, storing pairs of employees living in the same city. The sets Σ = { 1, 2} and Σ = { 3, } are as follows (for simplicity, we omit the universal quantifiers): 1 = 2 =
Emp() → ∃ EmpC(, ), 3 KnownC(, ) → EmpC(, ), = EmpC(, ), EmpC(′, ) → SameC(, ′), = EmpC(, ), EmpC(, ) → = .
The above setting copies employees from the source to the target. The TGD 1 states that every copied employee must have some city associated, whereas 2 states that when the city of an employee is known, this should be copied as well. Moreover, the target schema requires that employees living in the same city should be stored in relation SameC ( 3), and each employee must live in only one city ( ). Assume the source instance is
= {Emp(john), Emp(mary), KnownC(john, miami)}, and assume our query asks for all pairs of employees living in diferent cities. This can be written as:
(, ′) = ∃∃′ EmpC(, ) ∧ EmpC(′, ′) ∧ ¬SameC(, ′).
One would expect that the set of certain answers to is empty, since it is not certain that john and mary live in diferent cities. However, no CWA-solution admits mary and john to live in the same city, and thus (john, mary) is a certain answer under the CWA-solution-based semantics. □
The approach of [
Other semantics have been proposed in [
In this paper, we propose a new notion of data exchange solution, dubbed supported solution, which allows us to deal with general queries, but at the same time is suitable for practical applications. That is, we show that certain answers under supported solutions naturally generalize certain answers under classical solutions, when focusing on positive queries. Moreover, such solutions do not make any assumption on how values associated to existential variables compare to other values, hence solving issues like the ones of Example 2.
As expected, there is a price to pay to get meaningful answers over general queries: we show that certain answering is undecidable for general settings, but becomes coNP-complete when we focus on weakly-acyclic dependencies.
Basics. We consider pairwise disjoint countably infinite sets Const, Var, Null of constants, variables, and labeled nulls. Nulls are denoted by the symbol ⊥, possibly subscripted. A term is a constant, a variable, or a null. We additionally assume the existence of countably infinite set Rel of relations, disjoint from the previous ones. A relation has an arity, denoted (), which is a non-negative integer. We also use / to say that is a relation of arity . A schema is a set of relations. A position is an expression of the form [], where is a relation and ∈ {1, . . . , ()}.
An atom (over a schema S) is of the form (t), where is an -ary relation (of S) and t is a tuple of terms of length . We use t[] to denote the -th term in t, for ∈ {1, . . . , }. An atom without variables is a fact. An instance (over a schema S) is a finite set of facts (over S). A database is an instance without nulls. For a set of atoms , dom() is the set of all terms in , whereas var() is the set dom() ∩ Var. A homomorphism from a set of atoms to a set of atoms is a function ℎ : dom() → dom() that is the identity on Const, and such that for each atom (t) = (1, . . . , ) ∈ , (ℎ(t)) = (ℎ(1), . . . , ℎ()) ∈ . Dependencies. A tuple-generating dependency (TGD) (over a schema S) is a first-order formula of the form ∀x, y (x, y) → ∃z (y, z), where x, y, z are disjoint tuples of variables, and and are conjunctions of atoms (over S) without nulls, and over the variables in x, y and y, z respectively. The body of , denoted body( ), is (x, y), whereas the head of , denoted head( ), is (y, z). We use exvar( ) to denote the tuple z and fr( ) to denote the tuple y, also called the frontier of . An equality-generating dependency (EGD) (over a schema S) is a first-order formula of the form ∀x (x) → = , where x is a tuple of variables, a conjunction of atoms (over S) without nulls, and over x, and , ∈ x. The body of , denoted body( ), is (x), and the head of , denoted head( ), is the equality = . For clarity, we will omit the universal quantifiers in front of dependencies and replace the conjunction symbol ∧ with a comma. Moreover, with a slight abuse of notation, we sometimes treat a conjunction of atoms as the set of its atoms. Consider an instance . We say that satisfies a TGD if for every homomorphism ℎ from body( ) to , there is an extension ℎ′ of ℎ such that ℎ′ is a homomorphism from head( ) to . We say that satisfies an EGD = (x) → = , if for every homomorphism ℎ from body( ) to , ℎ() = ℎ(). satisfies a set of TGDs and EGDs Σ if satisfies every TGD and EGD in Σ .
Queries. A query (x), with free variables x, is a first-order (FO) formula (x) with free variables x. The arity of (x), denoted (), is the number |x|. The output of (x) over an instance , denoted (), is the set {t ∈ dom()|x| | |= (t)}, where |= is FO entailment.1 A query is Boolean if it has arity 0, in which case its output over an instance is either the empty set or the empty tuple ⟨⟩. A conjunctive query (CQ) is a query of the form (x) = ∃y (x, y), where (x, y) is a conjunction of atoms over x and y. A union of conjunctive queries (UCQ) is a query of the form (x) = ⋁︀
=1 (x), where each (x) is a CQ. We also refer to UCQs as positive queries.
Data Exchange Settings. A data exchange setting (or simply setting) is a tuple of the form = ⟨S, T, Σ , Σ ⟩, where S, T are disjoint schemas, called source and target schema, respectively; Σ is a finite set of TGDs, called the source-to-target TGDs of , such that for each TGD ∈ Σ , body( ) is over S and head( ) is over T; Σ is a finite set of TGDs and EGDs over T, called the target dependencies of . We say is TGD-only if Σ contains only TGDs.
A source (resp., target) instance of is an instance over S (resp., T). We assume that source
instances are databases, i.e., they do not contain nulls. Given a source instance of , a solution
of w.r.t. is a target instance of such that ∪ satisfies Σ and satisfies Σ [
Given a data exchange setting = ⟨S, T, Σ , Σ ⟩, a source instance of and a query 1We assume active domain semantics, i.e., quantifiers range over the terms in the given instance. over T, the certain answers to over w.r.t. is the set cert (, ) = ⋂︀∈sol(,) ( ).
To distinguish between the notion of solution (resp., certain answers) above and the one defined in Section 3, we will refer to the former as classical.
A universal solution of w.r.t. is a solution ∈ sol(, ) such that, for every ′ ∈ sol(, ),
there is a homomorphism from to ′ [
The goal of this section is to introduce a new notion of solution for data exchange that we call supported. As already discussed, the main issue we want to solve w.r.t. classical solutions is that such solutions are too permissive, i.e., they allow for the presence of facts that are not a certain consequence of the source instance and the dependencies. Consider again Example 1. The (classical) solution ′ in Example 1 is not supported, since from the source instance and the dependencies, we cannot conclude that the fact Paid(2) should occur in the target. On the other hand, the solution = {AllOrd(1), AllOrd(2), Paid(1)} is supported: it contains precisely the facts supported by and the dependencies, and no more than that. Similarly, considering Example 2, the instance = {EmpC(john, miami), EmpC(mary, chicago), SameC(john, mary)} is a solution, but it is not supported, since from the source and the dependencies we cannot certainly conclude that john and mary live in the same city. We now formalize the above intuitions.
Consider a TGD and a mapping ℎ from the variables of to Const. We say that a TGD ′ is a ground version of (via ℎ) if ′ = ℎ(body( )) → ℎ(head( )).
Definition 1 (ex-choice). An ex-choice is a function , that given as input a TGD = (x, y) → ∃z (y, z) and a tuple t ∈ Const|y|, returns a set (, t) of pairs of the form (, ), one for each existential variable ∈ exvar( ), where is a constant of Const.
Note that if does not contain existential variables, (, t) is the empty set.
Intuitively, given a TGD, an ex-choice specifies a valuation for the existential variables of the TGD which depends on a given valuation of its frontier variables.
We now define when a ground version of a TGD indeed assigns existential variables according to an ex-choice.
Definition 2 (Coherence). Consider a TGD = (x, y) → ∃z (y, z), an ex-choice and a ground version ′ of via some mapping ℎ. We say that ′ is coherent with if for each existential variable ∈ exvar( ), (, ℎ()) ∈ (, ℎ (y)).
For a set Σ of TGDs and EGDs, and an ex-choice , Σ denotes the set of dependencies obtained from Σ , where each TGD in Σ is replaced with all ground versions of that are coherent with . Note that the set Σ can be infinite. We now present our notion of solution. Definition 3 (Supported Solution). Consider a setting = ⟨S, T, Σ , Σ ⟩ and a source instance of . A target instance of is a supported solution of w.r.t. if there exists an ex-choice such that ∪ satisfies Σ and satisfies Σ such that ∪ ′ satisfies Σ and ′ satisfies Σ
. supported solutions of w.r.t. .
Note that a supported solution contains no nulls. We use ssol(, ) to denote the set of all {(, chicago)}. Then, Σ is Example 3. Consider the data exchange setting and the source instance of Example 2. The target instance = {EmpC(john, miami), EmpC(mary, chicago)} is a supported solution of w.r.t. . Indeed, consider the ex-choice such that ( 1, john) = {(, miami)}, and ( 1, mary) =
, and there is no other target instance ′ ⊊ of {Emp( ) → EmpC(, {KnownC(, ) → EmpC(, ) | ,
∈ Const}∪ ) | ∈ Const ∧ (, ) ∈ ( 1, )}, whereas Σ is the set containing the EGD of Example 2, and the set of TGDs
supported certain answers.
{EmpC(, ), EmpC( ′, ) → SameC(, ′) | , ′, ∈ Const}.
Clearly, ∪ satisfies Σ , and satisfies Σ , and any other strict subset ′ of is such that ∪ ′ does not satisfy Σ . Another supported solution is {EmpC(john, miami), EmpC(mary, miami),
With the notion of supported solution in place, it is now straightforward to define the tuples scert (, ) = ⋂︀
∈ssol(,) ( ).
Definition 4 (Supported Certain Answers). Consider a data exchange setting , a source instance of and a query over T. The supported certain answers to over w.r.t. is the set of Example 1. It is not dificult to see that the only supported solution of Example 4. Consider the data exchange setting , the source instance , and the query of w.r.t. is the instance and the query of Example 2. Then, one can verify that scert (, ) = ∅. = {AllOrd(1), AllOrd(2), Paid(1)}. Thus, the supported certain answers to over w.r.t. are scert (, ) = ( ) = {2}. Consider now the data exchange setting , the source instance ,
We now start establishing some important results regarding supported solutions and supported certain answers. The following theorem states that supported solutions are a refined subset of the classical ones, but whether a supported solution exists is still tightly related to the existence of a classical one. (1) ssol(, ) ⊆ sol(, ), and (2) ssol(, ) = ∅ if sol(, ) = ∅.
Theorem 2. Consider a data exchange setting . For every source instance of , its holds that
Regarding certain answers, we show that supported solutions indeed enjoy an important property: supported certain answers and classical certain answers coincide, when focusing on positive queries. Note that this does not necessarily follow from Theorem 2. source instance of , scert (, ) = cert (, ).
Theorem 3. Consider a setting = ⟨S, T, Σ , Σ ⟩ and a positive query over T. For every □ □ □
From the above, we conclude that for positive queries, certain query answering can be performed as done in the classical setting, and thus all important results from that setting, like query answering via universal solutions, carry over.
Corollary 1. Consider a setting = ⟨S, T, Σ , Σ ⟩ and a positive query over T. If is a (classical) universal solution of w.r.t. , then scert (, ) = ( )↓.
Proof. It follows from Theorem 1 and Theorem 3. □
We now move to the complexity analysis of the two most important data exchange tasks: deciding whether a supported solution exists, and computing the supported certain answers to a query.
In data exchange, it is usually assumed that a setting does not change over time, and a given query is much smaller than a given source instance. Thus, for understanding the complexity of a data exchange problem, it is customary to assume that and are fixed, and only is considered in the complexity analysis, i.e., we consider the data complexity of the problem. Hence, the problems we are going to discuss will always be parametrized via a setting , and a query (for query answering tasks). The first problem we consider is deciding whether a supported solution exists; is a fixed data exchange setting.
INPUT : A source instance of .
QUESTION : Is ssol(, ) ̸= ∅? The above problem is very important in data exchange, as one of the main goals is to actually construct a target instance that can be exploited for query answering purposes. Hence, knowing in advance whether at least a supported solution exists is of paramount importance.
Thanks to Item 2 of Theorem 2, all the complexity results for checking the existence of a classical solution can be directly transfered to our problem.
Theorem 4. There exists a data exchange setting such that EXISTS-SSOL() is undecidable.
Despite the negative result above, we also inherit positive results from the literature, when
focusing on some of the most important data exchange scenarios, known as weakly-acyclic.
Such settings only allow target TGDs to belong to the language of weakly-acyclic TGDs, which
have been first introduced in the seminal paper [
Theorem 5. For every weakly-acyclic data exchange setting , EXISTS-SSOL() is in PTIME.
We now move to the second crucial task: computing supported certain answers. Since this problem outputs a set, it is standard to focus on its decision version. For a fixed data exchange setting and a fixed query , we consider the following decision problem:
PROBLEM : SCERT(, ) INPUT : A source instance of and a tuple t ∈ Const().
QUESTION : Is t ∈ scert (, )?
One can easily show that the above problem is logspace equivalent to the one of computing the supported certain answers.
We start by studying the problem in its full generality, and show that there is a price to pay for query answering with general queries.
Theorem 6. There exists a data exchange setting = ⟨S, T, Σ , Σ ⟩, with Σ having only TGDs, and a query over T, such that SCERT(, ) is undecidable.
Although the complexity result above tells us that computing supported certain answers might be infeasible in some settings, we can show that for weakly-acyclic settings, the complexity is more manageable.
Theorem 7. For every weakly-acyclic setting and every query , SCERT(, ) is in coNP, and there exists a weakly-acyclic setting that is TGD-only and a query such that SCERT(, ) is coNP-hard.
We point out that the above result is in contrast with all the data exchange semantics discussed
in the introduction, for which computing certain answers is undecidable, even for weakly-acyclic
settings [
We conclude this section by recalling that for positive queries, supported certain answers
coincide with the classical ones (Theorem 3), and computing (classical) certain answers for
weakly-acyclic settings, under positive queries, is tractable [
For future work, it would be interesting to see if the good complexity guarantees we obtain
for weakly-acyclic dependencies are preserved when considering more complex acyclicity
conditions (e.g., see [