Database Reference
In-Depth Information
is an interesting class of queries for which the semantics based on CWA coincides with the
usual semantics. This is the class of existential queries.
Proposition 8.18
Σ
st
)
be a mapping and Q an existential query over
R
t
. Then for every source instance S, certain
CWA
Let
M
=(R
s
,
R
t
,
(
Q
,
S
)=
certain
M
(
Q
,
S
)
.
M
Proof
For the sake of simplicity, assume that
Q
is Boolean. For arbitrary queries we use
exactly the same argument. Clearly, every instance in
Rep
CWA
(
T
),where
T
is a CWA
solution for
S
under
M
, is also a solution for
S
. Thus,
certain
M
(
Q
,
S
)=
true
implies
certain
CWA
M
(
Q
,
S
)=
true
. Next we prove the opposite direction.
certain
CWA
M
(
Q
,
S
)=
true
but
certain
M
(
Q
,
S
)=
false
. Then there exists a solution
T
for
S
where
Q
does not
hold. But it is easy to see then that
Q
neither holds in the solution
T
for
S
that is obtained
from
T
by simultaneously replacing each null in D
OM
(
T
) with a distinct constant that
appears neither in
T
nor in
Q
.Let
T
can
be the canonical universal solution for
S
under
Assume,
for
the
sake of
contradiction,
that
M
.
T
.Let
T
1
be the homomorphic image
By definition, there is a homomorphism
h
:
T
can
→
of
T
can
under
h
.Then
T
1
∈
Rep
CWA
(
T
can
).Furthermore,
Q
does not hold in
T
1
. In fact, since
Q
is an existential query it is also monotone. This implies that if
T
1
|
=
Q
then
T
|
=
Q
,
which would be a contradiction. Hence, there is an instance in
Rep
CWA
(
T
can
) over which
Q
does not hold. We conclude that
certain
CWA
M
(
Q
,
S
)=
false
, which is a contradiction.
By combining
Proposition 8.18
and results on query answering under the usual certain
answers semantics from
Chapter 7
, we obtain the following:
M
=(R
s
,
R
t
,
Corollary 8.19
Σ
st
)
be a mapping and Q a union of conjunctive
queries over
R
t
. Then the following problem can be solved in polynomial time: Given a
source instance S, compute certain
CWA
M
1. Let
(
Q
,
S
)
.
2. There exists a mapping
Σ
st
)
and a Boolean conjunctive query Q with
inequalities over
R
t
, such that the following problem is
CO
NP
-complete: Given a source
instance S, is certain
CWA
M
M
=(R
s
,
R
t
,
(
Q
,
S
)=
true
?
That is, the CWA semantics shares with the usual certain answers semantics the problem
of intractability of query answering for nonpositive queries.
Summary
We can summarize the query answering behavior of the semantics based on CWA certain
answers as follows:
•
The semantics eliminates the anomalies of the usual certain answers semantics, at least
under copying mappings.
•
Computing CWA certain answers of arbitrary relational calculus queries is a decidable
problem that belongs to the class
CO
NP.
•
Computing CWA certain answers of (unions of) conjunctive queries can be done in poly-
nomial time, but extending this class with inequalities immediately leads to intractability.
