Database Reference
In-Depth Information
of evaluating queries over incomplete databases (which happen to be canonical universal
solutions). This allows us to make two important observations:
•
Returning to our initial example with copying mappings, we can see that under such
a mapping
M
, the only CWA solution for an instance
S
is a copy of
S
itself. Hence,
certain
CWA
M
(
Q
,
S
)=
Q
(
S
), as expected. This shows that the CWA semantics solves all
the query answering anomalies of our two previous semantics, at least under copying
mappings.
•
The key difference between certain answers under the OWA and under the CWA is that
the latter are always computable, for all relational calculus queries, and many more.
Recall that under the OWA, we may have FO queries for which finding certain answers
is an undecidable problem. But
Theorem8.16
states that under the CWA, certain answers
are computable for all relational calculus queries simply due to the fact that the sizes of
instances in
Rep
CWA
(
T
), for the canonical universal solution
T
, do not exceed the size
of
T
itself.
From the last remark we easily obtain that computing CWA certain answers of FO
queries is not only decidable, but it can be solved in
CO
NP.
Proposition 8.17
Let
M
Σ
st
)
be a mapping and Q an
FO
query over
R
t
.Then
the following problem can be solved in
CO
NP
: Given a source instance S, and a tuple a, is
a in certain
CWA
M
=(R
s
,
R
t
,
(
Q
,
S
)
?
Proof
Assume for the sake of simplicity that
Q
is Boolean. Otherwise we use es-
sentially the same argument. We can use the following NP algorithm to check that
certain
CWA
M
(
Q
,
S
)=
false
:
1. Compute in polynomial time the canonical universal solution
T
for
S
.
2. Guess a polynomial size instance
T
in
Rep
CWA
(
T
).
3. Check in polynomial time that
Q
does not hold in
T
.
Since a
CO
NP algorithm for checking whether
certain
CWA
M
(
Q
,
S
)=
true
is the same as
an NP algorithm for checking whether
certain
CWA
M
(
Q
,
S
)=
false
, this proves the propo-
sition.
The notions of certain answers under the CWA and the OWA are different, and in fact it
is easy to construct explicit examples. Let R
s
contain a unary predicate
U
,andR
t
contain
a unary predicate
U
. Assume that we have one st-tgd
U
(
x
)
zU
(
z
),andlet
S
be the
source instance containing only
U
(
a
). Then the only CWA solution (up to renaming of
nulls) is the instance
U
(
→∃
⊥
). However, for an arbitrary collection of nulls
⊥
1
,...,
⊥
n
,the
instance
U
(
⊥
1
)
,...,
U
(
⊥
n
) is a universal solution. Hence, if we take the Boolean query
y
(
U
(
x
)
U
(
y
)
x
=
y
),then
certain
CWA
M
Q
=
∀
x
∀
∧
→
(
Q
,
S
)=
true
while
certain
M
(
Q
,
S
)=
certain
u
M
(
Q
,
S
)=
false
.
The previous example shows that there is a mapping
M
andanFOquery
Q
such that
certain
CWA
M
(
Q
,
S
)
=
certain
M
(
Q
,
S
) for some source instance
S
. On the other hand, there
