Database Reference
In-Depth Information
the following problem is undecidable: Given a source instance S, is certain
CWA
M
(
Q
,
S
)=
true
?
One would expect, as in the case of
Propositions 7.1
and
8.4
, that the previous fact
follows directly from the undecidability of the problem of existence of CWA solutions
(
Corollary 8.28
). Unfortunately, this is not the case. The reason is that the CWA semantics
is given not by the CWA solutions themselves, but by the complete instances represented
by them. Proving
Proposition 8.29
is left as an exercise for the reader.
Recall that, in the absence of target dependencies, we used the following fact to show
that the problem of computing CWA certain answers of any FO query
Q
is decidable:
certain
CWA
M
(
Q
,
S
)=
Q
(
T
)
,
for each source instance
S
with canonical universal solution
T
. Indeed, this fact states that
computing CWA certain answers of an FO query
Q
is equivalent to taking the intersection
of the evaluation of
Q
over every complete instance
D
that is represented by the canonical
universal solution under the CWA. Since there is only a finite number of such complete
instances
D
, it follows that computing CWA certain answers in this case is decidable.
But as
Proposition 8.29
states, in the presence of target dependencies the problem of
computing CWA certain answers of FO queries is no longer decidable. And, furthermore,
as the following example shows, the property that
certain
CWA
M
Σ
t
Q
(
T
), for each
source instance
S
with canonical universal solution
T
, no longer holds when
(
Q
,
S
)=
Σ
t
contains
some dependencies .
Example 8.30 (
Example 8.21
continued) Recall that
T
1
=
{
E
(
a
,
⊥
1
,
⊥
3
)
,
E
(
a
,
⊥
2
,
⊥
4
)
,
F
(
a
,
⊥
1
,
⊥
1
)
,
F
(
a
,
⊥
2
,
⊥
2
)
}
is the canonical universal solution for
S
=
. Consider the Boolean FO query
Q
that
asks whether there are at most two tuples of the form
F
(
a
,
{
P
(
a
)
}
) in a solution. Then clearly
every complete instance in
Rep
Σ
CWA
(
T
) satisfies
Q
, and, therefore,
·
,
·
Σ
t
Q
(
T
1
)=
true
.
On the other hand, it is not hard to see that
certain
CWA
M
(
Q
,
S
)=
false
. Indeed, recall
that the solution
T
2
=
{
E
(
a
,
⊥
1
,
⊥
3
)
,
E
(
a
,
⊥
2
,
⊥
3
)
,
F
(
a
,
⊥
1
,
⊥
1
)
,
F
(
a
,
⊥
2
,
⊥
2
)
,
F
(
a
,
⊥
1
,
⊥
2
)
,
F
(
a
,
⊥
2
,
⊥
1
)
}
belongs to S
OL
CWA
M
(
S
). The instance
{
E
(
a
,
a
,
c
)
,
E
(
a
,
b
,
c
)
,
F
(
a
,
a
,
a
)
,
F
(
a
,
b
,
b
)
,
F
(
a
,
a
,
b
)
,
F
(
a
,
b
,
a
)
}
belongs to
Rep
Σ
CWA
(
T
2
) and does not satisfy
Q
.
Is there any other mechanism by which we can prove decidability, in the presence of
target dependencies, of the problem of query answering under the CWA for an interesting
class of FO queries? Recall that in the case without target dependencies we were able to
prove that the CWA semantics coincides with the usual certain answers semantics for the
