Database Reference
In-Depth Information
over the canonical universal solution
T
for
S
(that is, over the “copy” of
S
that is obtained
by renaming each relation symbol in R
s
into its corresponding relation symbol in R
t
), we
may have an anomaly. The following example shows that the universal certain answers
semantics presents this kind of counter-intuitive behavior, even for simple FO queries.
Example 8.7 Consider the copying mapping
M
=(R
s
,
R
t
,
Σ
st
) such that
Σ
st
consists of
the following st-tgd:
P
(
x
,
y
)
.
P
(
x
,
y
)
→
Let
S
=
be a source instance and
Q
be the Boolean FO query that asks whether
the interpretation of the target relation
P
contains exactly one tuple. That is,
{
P
(
a
,
b
)
}
y
P
(
x
,
y
)
y
=
y
1
)
.
y
1
(
P
(
x
1
,
y
1
)
Q
:=
∃
x
∃
∧∀
x
1
∀
→
x
=
x
1
∧
P
(
a
,
b
)
Clearly, the query
Q
holds over the canonical universal solution
T
=
{
}
for
S
. On the other hand,
certain
u
M
under
M
(
Q
,
S
)=
false
, since it is easy to see that the
target instance
T
=
P
(
a
,
b
)
,
P
(
{
⊥
1
,
⊥
2
)
}
,where
⊥
1
,
⊥
2
are distinct null values, is also a
,and
Q
does not hold in
T
.
universal solution for
S
under
M
Summary
We have seen the following behavior of the universal solution semantics:
•
Computing universal certain answers for arbitrary relational calculus queries is an unde-
cidable problem, even in the absence of target dependencies.
•
There is a large and practically relevant class of FO queries (namely, the class of exis-
tential queries), for which query answering under the universal solution semantics can
be efficiently solved. Moreover, some of the query answering anomalies disappear for
queries in this class.
•
However, the new semantics continues to exhibit counter-intuitive behavior when ap-
plied to arbitrary FO queries, even in the simplest copying mappings.
In the next section we study a different semantics, based on the idea of a closed-world
assumption, that solves all the query answering anomalies we have seen so far and presents
good decidability properties for query answering.
8.2 Closed-world semantics
Both the usual and the universal certain answers semantics are based on the
open-world
assumption
,or
OWA
. Under this assumption, solutions in S
OL
M
(
S
) are open to adding
new facts. That is, if
T
is a solution, then all extensions of
T
are solutions as well. Under
the universal solution semantics, if
T
is a universal solution, then all its extensions which
are universal must be accounted for when one computes query answers.
All the query answering anomalies we have seen so far arise because of this openness:
one can see that in all the examples, we exploit this fact in an essential way. But if we look,
