Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of a mapping between the source and the target schemas, and answering queries over target instances. A schema mapping is a condition, often expressed in a fragment of first-order logic, that relates instances of source and target schemas. Most commonly it is a conjunction of sentences of the form
(1) where ϕ and ψ are both conjunctions of atomic formulae. For example, if we have a source database S(·, ·) that lists employees and their salaries, and a target database T (·, ·) that lists people and their children, then a natural mapping is ∀x∀y (S(x, y) → ∃z T (x, z)).
The study of both data exchange and schema mappings has been actively
pursued recently (see, e.g., recent surveys [
Theoretical foundations of data exchange were developed in [
This semantics implies that for the same source instance one can have many
different target solutions. In fact this semantics of data exchange follows the so
called open world assumption (OWA), as target solutions may contain arbitrary
facts, some of which are not directly implied by the source data and the schema
mapping. An alternative approach, developed in [
If a query Q is posed against target instances, then it must be answered in a way that is consistent with the source. A common approach is to look for certain answers: certainM (Q, S) = \{Q(T ) | T is a solution}. (2) A desirable feature in data exchange is to find a particular solution to be materialized in the target, which allows to answer queries over the target (with certain answer semantics), with no access to source data. In other words, we want a specific target instance T0 so that certainM (Q, S) = Q′(T0), for some query Q . ′
Data exchange literature identified two particularly nice solutions, called the
canonical solution [
While this looks reasonable, the definition of query answering is actually underspecified. We know well how to answer queries on complete databases; in contrast, databases arising in data exchange are often incomplete as they contain null values (for example, it is common for target schemas to have attributes that do not correspond to any attributes in the source schema; these are populated with nulls). Thus, the notions of query answering over incomplete databases are essential in data exchange, and have to be incorporated into the algorithms for answering queries in data exchange.
Let us briefly recall the standard approach to query answering over databases
with incomplete information [
The answers to a query Q over R are defined as
That is, 2Q(R) contains answers independent of the interpretation of nulls. One
easy case of finding such answers is known: if Q is a union of conjunctive queries,
then 2Q(R), under both closed and open world assumptions, is obtained by a
straightforward evaluation of Q on R and then discarding tuples that contain
nulls (elements of V ). This is referred to as naive evaluation. Clearly, naive
evaluation is done in PTIME; adding negation to queries (e.g., going to the full
FO) makes the problem coNP-complete under the closed world assumption [
The theory of incomplete information explains why the OWA works well for
answering unions of conjunctive queries in data exchange. In fact the canonical
solution in data exchange, viewed as an open-world incomplete database, turns
out to represent the set of all data exchange solutions under the OWA (property
already referred to as universality in [
However, going beyond unions of conjunctive queries poses problems. They
appear even in the simplest mappings of the form ∀x¯ R(x¯) → R′(x¯) that copy
contents of each relation R into a new relation R′. Under the OWA, even FO
query answering in data exchange is undecidable, and for every Boolean query,
either its certain answers are false for all instances, or the certain answers for its
negation are false for all instances [
The reason behind such anomalies is that our intuition tells us that the mapping ∀x¯ R(x¯) → R′(x¯) forces R′ to be a copy of R; however, under the OWA semantics, R′ is allowed to be an arbitrary extension of R. It seems natural then ′ to adopt the CWA that would not permit adding arbitrary facts to R and would only put there what the constraints dictate – that is, a copy of R.
This approach was developed in [
When the definition of certainM (Q, S) is applied to CWA-solutions, a proper notion of query answers Q(T ) has to be adopted for CWA-solutions T . The most natural semantics is 2Q(T ), where T is viewed as a closed-world incomplete database. This approach naturally leads to a new semantics of query answering: a tuple t is in certainM (Q, S) under the CWA if, for every CWA-solution T and every R ∈ Rep(T ), this tuple is in Q(R). That is,
certainCMWA(Q, S) = \{Q(R) | R ∈ Rep(T ), T is a CWA-solution.}
It was shown in [
Extensions of this approach to mappings that involve constraints over target
schemas were developed in [
But fully open or fully closed mappings, being two extreme cases, are bound to have their shortcomings. Consider again the example of a source database S(·, ·) that lists employees and their salaries, and a target database T (·, ·) that lists people and their children. The mapping is given by ∀x∀y (S(x, y) → ∃z T (x, z)). Under the CWA, if we assume that each employee has one salary, in the target each employee will have exactly one value for the ‘child’ attribute. This example indicates that it is natural to declare some target attributes as open, and some as closed. In the above example, we would formulate the mapping as ∀x∀y (S(x, y) → ∃z T (xcl, zop)), saying that only employees from the source are moved to the target, but the number of values of the ‘child’ attribute are arbitrary.
Such mixed mappings were studied in [13]. Data exchange solutions under
mixed mappings are incomplete databases where domain elements are annotated
as either open (op) or closed (cl ). Such an approach for databases with nulls was
used back in the 80s, see [
Annotated data exchange solutions have been defined along the lines of CWAsolutions. Each tuple put in the target still needs to be justified by some source data and the schema mapping. The tuple annotation (determined by the schema mapping) will then give either and open-world or closed-world semantics to the tuple attributes. The restriction that all facts true in the target must be implied by the source and the schema mapping is enforced only limited to closed attributes.
A particular annotated solution, the annotated canonical solution, has the
usual property that it represents the semantics of all the solutions. That is, if Tc
is the annotated canonical solution, RepA(Tc) contains precisely all the instances
R that are in RepA(T ) for some annotated solution T . When annotation is
removed from Tc, this is the usual canonical solution of [
The semantics of query answering is standard: for an annotated schema mapping Mα a tuple t is certainMα (Q, S) if, for every annotated solution T and every R ∈ RepA(T ), this tuple is in Q(R). Since the semantics of the annotated canonical solution Tc captures the semantics of all solutions, the usual equation certainMα (Q, S) = 2Q(Tc) holds also under annotated mappings. Thus the complexity of computing certain answers for arbitrary FO queries, must range from coNP-complete (in the case of all ‘closed’ annotation) to undecidable (in the case of all ‘open’ annotation).
In particular it was shown that for query answering, there is a complexity trichotomy that depends on the number of target attributes declared as open per each atom in a rule in the mapping. If the number is 0 (i.e., we are under the CWA), then the complexity is in general coNP-complete. If the number is 2 or greater, then, as for the OWA, the problem is undecidable. But if the number is 1, the problem is decidable, albeit with a high complexity: coNEXPTIMEcomplete. Note that this means that each atom in a rule has at most one open annotation; the rule itself (or the mapping) can have arbitrarily many open annotations. We prohibit atoms such as T (xop, yop) but can have, for example, T1(xop, ycl) ∧ T1(yop, zcl) ∧ T2(xop, zcl).
In the case of unions of conjunctive queries, all the cases collapse and the usual naive evaluation over the canonical solution produces the answer in polynomial time.
Finally, [13] considered the issue of composing schema mappings, and showed
that the OWA approach of [
Acknowledgments Supported by EPSRC grants E005039 and F028288, and the FET-Open Project FoX (grant agreement 233599). 13. L. Libkin and C. Sirangelo. Data exchange and schema mappings in open and closed worlds In PODS’08, pages 139–148. 14. R. Reiter. On closed world databases. In Logic and Databases, Plenum Press, 1978, pages 55–76.