Database Reference
In-Depth Information
U
i
(
x
),
•
Σ
st
contains full st-tgds that copy source relations into target relations:
U
i
(
x
)
→
W
(
x
1
,...,
x
k
,
x
k
+1
);
for 1
≤
i
≤
m
,and
W
(
x
1
,...,
x
k
,
x
k
+1
)
→
•
Σ
t
consists of the following:
- For each rule
U
i
t
+1
(
x
t
+1
)
, the full tgd
U
i
1
(
x
1
)
←
U
i
1
(
x
1
)
,...,
U
i
t
(
x
t
) in
Π
∧···∧
U
i
t
+1
(
x
t
+1
);and
- the egd
R
(
x
1
,...,
x
k
)
U
i
t
(
x
t
)
→
W
(
x
1
,...,
x
k
,
x
k
+1
)
∧
→
x
1
=
x
k
+1
(recall that
R
is one of the
intensional predicates);
the source instance
S
is populated with the facts in
S
plus the fact
W
(
c
1
,...,
c
k
,
d
),where
d
is a fresh constant that does not occur elsewhere in
S
.
•
and
S
can be constructed in polynomial time from
R
(
c
1
,...,
c
k
),
and
S
.
Since all tgds are full, we have a weakly acyclic set of tgds. In addition,
R
(
c
1
,...,
c
k
)
belongs to the evaluation of
Clearly,
M
Π
over
S
iff
S
has no solution. Indeed, assume first that
R
(
c
1
,...,
c
k
) belongs to the evaluation of
Π
over
S
. Then chasing
S
with
Π
Σ
st
∪
Σ
t
will pro-
duce the fact
R
(
c
1
,...,
c
k
). But then the egd
R
(
x
1
,...,
x
k
)
W
(
x
1
,...,
x
k
,
x
k
+1
)
x
1
=
x
k
+1
is triggered with this fact and
W
(
c
1
,...,
c
k
,
d
), which implies that the chase fails. As-
sume, on the other hand, that
S
has no solution. Since we have a weakly acyclic set of tgds,
this implies that the chase fails. The only way that this can happen is that the egd is trig-
gered with
R
(
c
1
,...,
c
k
) and
W
(
c
1
,...,
c
k
,
d
). But this implies that
R
(
c
1
,...,
c
k
) belongs
to the evaluation of
∧
→
Π
over
S
.
We conclude that there is a
provable
gap between the combined and the data complex-
ity of the problem of checking for the existence of solutions in data exchange, even for
mappings whose target dependencies consist of egds and weakly acyclic sets of tgds.
