Database Reference
In-Depth Information
following result about the complexity of existence of CWA solutions under
M
. The input
to this problem is a source
S
; the question is whether S
OL
CWA
M
(
S
)
= 0.
Corollary 8.28
1. There is a mapping
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
such that the existence of
CWA
solutions under
M
problem is undecidable.
2. Let
Σ
t
consists of a set of egds and a weakly
acyclic set of tgds. Then the existence of
CWA
solutions under
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
be a mapping, where
M
problem can be
solved in polynomial time.
Query answering under CWA and target dependencies
Recall that in the absence of target dependencies we defined the set of CWA certain answers
of target query
Q
for source instance
S
under mapping
M
=(R
s
,
R
t
,
Σ
st
) as:
(
Q
,
S
)=
certain
CWA
M
S
OL
CWA
M
{
Q
(
T
)
|
T
∈
(
S
)
}
,
Q
(
T
)=
{
where
. Recall also that in the absence of target
dependencies,
Rep
CWA
(
T
) was defined as the set of complete instances represented by
T
under the CWA; that is, those complete instances that were homomorphic images of
T
.
Notice, in particular, that in this case if
T
was a solution then each instance
T
represented
by
T
was also a solution.
But is the latter fact also true in the presence of target dependencies? The answer
is negative, as shown by the following example. Consider an incomplete instance
T
=
{
Q
(
D
)
|
D
∈
Rep
CWA
(
T
)
}
R
(
x
). Then clearly
T
satisfies the tgd. But, on the other
hand, its homomorphic image
T
=
{
P
(
a
,
a
)
}
does not satisfy it. Thus, in order to be se-
mantically sound, we need to redefine the notion of
Rep
CWA
(
T
) when there is a set of egds
and tgds
P
(
⊥
1
,
⊥
2
)
}
and a tgd
P
(
x
,
x
)
→
Σ
t
that needs to be satisfied. In particular, we define the set of instances repre-
sented by
T
with respect to
Σ
t
under the CWA, denoted by
Rep
Σ
CWA
(
T
), as the one that
consists of each complete instance that is a homomorphic image of
T
and satisfies
Σ
t
.
In the same way, we define
Σ
t
Q
(
T
) :=
Rep
Σ
CWA
(
T
)
{
Q
(
D
)
|
D
∈
}
,
and the set of CWA certain answers of target query
Q
for source instance
S
under mapping
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) as:
(
Q
,
S
)=
certain
CWA
M
S
OL
CWA
M
{
Σ
t
Q
(
T
)
|
T
∈
(
S
)
}
.
We will see later some examples of the application of this semantics.
Our first observation is that the problem of computing CWA certain answers of FO
queries is undecidable in the presence of target dependencies, even for mappings with a
weakly acyclic set of tgds. Recall that, on the other hand, for mappings without target
dependencies the problem is decidable.
Proposition 8.29
There exists a mapping
Σ
t
consists of a
set of egds and a weakly acyclic set of tgds, and a Boolean
FO
query Q over
R
t
,forwhich
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
, such that
