Database Reference
In-Depth Information
bounds for query answering over a big class of FO queries, but unfortunately does not
solve some of the simplest anomalies.
The second semantics is based on the notion of a
closed-world assumption
that forbids
data exchange solutions to be enlarged with facts that are not implied by the source instance
and the mapping. That is, “good” solutions are those that populate targets with only as
much information as needed to satisfy constraints of mappings. The third semantics is less
rigid than the closed-world semantics: it explicitly specifies which attributes are interpreted
under the closed-world, and which under the open-world assumptions. These semantics do
solve many of the anomalies that appear in data exchange, but unfortunately shares the
usual certain answers semantics problems related to intractability of query answering.
Again, it is fair to say that there is no single semantics that solves all the problems in
data exchange. But by presenting at least three alternatives to the usual certain answers
semantics, we give the reader a few options to choose the semantics that achieves the right
balance between the desired expressiveness of queries in data exchange and the efficiency
of query evaluation.
8.1 Universal solutions semantics
The first alternative semantics that we present takes the view that universal solutions are
the preferred ones in data exchange, and equates “good” in
(8.1)
with being universal.
Thus, for a given query
Q
, it looks for tuples present in the answer to
Q
on every
universal
solution, as opposed to every solution. Formally, this semantics is defined as follows.
M
Definition 8.1 (Universal certain answers) Let
be a mapping,
Q
a query over R
t
and
S
a source instance. We define the set of
universal certain answers of Q with respect to S
under
M
(or simply the universal certain answers of
Q
with respect to
S
,if
M
is clear
from the context), as:
(
Q
,
S
)=
certain
u
M
{
Q
(
T
)
|
T
is a universal solution for
S
}
.
Since computing certain answers for a union of conjunctive queries can be done by
posing the query over an arbitrary universal solution, we conclude the following:
Proposition 8.2
If
is a mapping and Q is a union of conjunctive queries over
R
t
,then
certain
M
(
Q
,
S
)=
certain
u
M
(
Q
,
S
)
for every source instance S.
M
However,
Proposition 8.2
does not even extend to conjunctive queries with inequalities,
as shown in the following example.
Example 8.3 Consider the mapping
M
=(R
s
,
R
t
,
Σ
st
) such that
Σ
st
consists of the fol-
lowing st-tgd:
R
(
x
,
y
)
→∃
zP
(
x
,
y
,
z
)
.
That is,
R
is a binary relation symbol in R
s
and
P
is a ternary relation symbol in R
t
.
Let
S
be the source instance
{
R
(
a
,
b
)
}
. Then the universal certain answer of the query
