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