Database Reference
In-Depth Information
class of existential queries (
Proposition 8.18
). If this was also the case in the presence of
target dependencies, then it would allow us to transfer all the results we know about query
answering under the usual semantics into the present setting. However, the next example
shows that this property fails already for the class of conjunctive queries with inequalities
under mappings with a weakly acyclic set of tgds in
Σ
t
.
Example 8.31 Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) be the mapping such that
Σ
st
consists of the
st-tgd:
P
(
x
,
y
)
→∃
∃
vR
(
u
,
v
)
,
u
and
Σ
t
consists of the tgd:
R
(
x
,
x
)
→
S
(
x
)
.
Consider source instance
S
=
{
P
(
a
,
a
)
}
. It is not hard to prove that the only CWA solu-
tion for
S
in this case is
T
=
{
R
(
⊥
1
,
⊥
2
)
}
,where
⊥
1
and
⊥
2
are distinct nulls. Notice, in
particular, that the target instance
T
=
{
R
(
⊥
,
⊥
)
,
S
(
⊥
)
}
is a CWA presolution for
S
(since
it is clearly a solution for
S
and the result of an
α
-chase), but not a CWA solution (simply
because it is not a universal solution for
S
).
Moreover, each
D
Rep
Σ
CWA
(
T
) is of the form
∈
{
R
(
b
,
c
)
}
,where
b
and
c
are distinct
cannot belong to
Rep
Σ
CWA
(
T
) because
constants. In fact, instances of the form
{
R
(
b
,
b
)
}
=
y
) then
certain
CWA
M
they violate
Σ
t
. This implies that if
Q
=
∃
x
∃
y
(
R
(
x
,
y
)
∧
x
(
Q
,
S
)=
true
. On the other hand,
certain
M
(
Q
,
S
)=
false
, since the solution
T
1
=
{
R
(
a
,
a
)
,
S
(
a
)
}
for
S
does not satisfy
Q
.
Interestingly enough, we can still recover the equivalence in one important case, namely
for unions of conjunctive queries under mappings with a weakly acyclic set of tgds. This
will allow us to transfer the good behavior of this class of queries under the usual semantics
into the present setting. The following is left as an exercise.
Proposition 8.32
Σ
t
consists of a set
of egds and a weakly acyclic set of tgds, and assume that Q is a union of conjunctive
queries over
R
t
. Then for every source instance S it is the case that certain
CWA
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
be a mapping such that
(
Q
,
S
)=
M
certain
M
(
Q
,
S
)
.
Notice that the reason why we need to restrict the statement of the proposition to map-
pings with a weakly acyclic set of tgds, is that in this way we can be sure that the existence
of solutions coincides with the existence of universal solutions, and hence, from
Theorem
8.27
, also with the existence of CWA solutions.
By combining
Proposition 8.32
and what we know about computing certain answers of
unions of conjunctive queries from
Chapter 7
, we obtain the following important corollary:
Corollary 8.33
Σ
t
consists of a set
of egds and a weakly acyclic set of tgds, and assume that Q is a union of conjunctive
queries over
R
t
. Then the data complexity of computing certain answers, i.e., computing
certain
CWA
M
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
be a mapping such that
(
Q
,
S
)
, is polynomial.
