Database Reference
In-Depth Information
M
Algorithm 8.1 C
OMPUTE
U
NIVERSAL
C
ERTAIN
A
NSWERS
(
Q
,
)
Require: A source instance
S
Ensure: If S
OL
M
(
S
)
= 0, then
CUA
is the set of universal certain answers for
Q
over
S
.Otherwise,
CUA
=
fail
1:
let
T
be the result of C
OMPUTE
C
ORE
(
under
M
M
) over
S
2:
if
T
=
fail
then
3:
CUA
:=
fail
4:
else
5:
CUA
:=
Q
naıve
(
T
)
6:
end if
Notice that this is in sharp contrast with
Theorem 7.4
which showed that even for very
simple existential FO queries (namely, conjunctive queries with inequalities) the problem
of computing certain answers could become intractable.
Theorem 8.5
also shows that the
universal certain answers semantics solves one of the main problems with the usual data
exchange semantics that we mentioned at the beginning of the chapter; namely, it permits
efficient query answering for a big and practically relevant class of queries that goes well
beyond the class of (unions of) conjunctive queries.
Since the semantics based on the set of universal solutions behaves relatively well with
respect to the complexity of computing certain answers of FO queries, it is natural to
ask whether it also avoids some of the anomalies of query answering mentioned at the
beginning of the chapter.
The simplest of the anomalies was stated in
Proposition 7.16
: there is a copying map-
ping
M
and an FO query
Q
such that
Q
is not FO-rewritable over the canonical universal
solution. The query
Q
used in the proof of that proposition was existential. We can now
state a partial positive result: for existential queries, the universal certain answers semantics
avoids those “copying” anomalies.
Corollary 8.6
Σ
st
)
be a copying mapping and Q an existential query
over
R
t
. Then for every source instance S it is the case that certain
u
M
Let
M
=(R
s
,
R
t
,
(
Q
,
S
)=
Q
(
T
)
,where
M
T is the canonical universal solution for S under
(that is, T is the “copy” of S that is
obtained by renaming each relation symbol in
R
s
into its corresponding relation symbol in
R
t
).
For the proof, we observe that universal certain answers of an existential query
Q
can be
obtained by naıve evaluation of
Q
over the core of the universal solutions. But in copying
mappings, the canonical universal solution always coincides with its core (and is just a
copy of the source).
However, the counter-intuitive behavior of the certain answers semantics in copying
mappings can still be witnessed when we leave the class of existential queries and deal with
arbitrary relational calculus queries. In fact, if certain answers to a query
Q
with respect
to a source instance
S
under a copying mapping do not coincide with the evaluation of
Q
