Database Reference
In-Depth Information
p
(
p
(
x
))
m
. This completes the
target. Hence we can take
p
(
x
) to be the polynomial
M·
proof of
Theorem 5.11
assuming
Claim 5.12
.
To finish the proof of
Theorem 5.11
we prove
Claim 5.12
. We do this by induction on
j
.
Base case: We consider positions (
V
,
A
) in
N
0
. These are positions for which no incoming
path has a special edge. This means that no new values are created in those positions, and,
thus, that the number of elements in each (
V
,
A
)
∈
N
0
is at most
T
. Since this is true for
each (
V
,
A
) in
N
0
, we can take
p
0
(
x
)=
x
.
Inductive case: There are three different ways by which an element may appear in
T
at a
position in
N
j
. First, there may be values that were already there in
T
, of which there are
at most
. Second, there may be values that are copied by a chase step from a position
in
N
i
, with
j
T
=
i
. And third, there may be elements that are generated as new values (i.e.,
nulls) during a chase step.
We first count the number of distinct elements that can be copied to positions in
N
j
from
positions in
N
i
with
i
=
j
. This means that there exists a nonspecial edge from a position
in
N
i
to a position in
N
j
. Notice first that this can only happen if
i
<
j
. Indeed, assume
otherwise. Then there exists a nonspecial edge from a position (
V
,
A
) in
N
i
to a position
(
U
,
B
) in
N
j
with
i
>
j
. But then there is a path in
G
ending at (
U
,
B
) that has
i
special
edges. This contradicts the fact that rank(
U
,
B
)=
j
<
i
. We can conclude then that the
number of distinct elements that can be copied to positions in
N
j
from positions in
N
i
, with
i
1
i
=0
p
i
(
j
−
).
Let us count now the number of new values (i.e., nulls) that can be generated at positions
in
N
j
by the chase steps. This can only be done by using a special edge going from a
position in
N
i
, with
i
<
j
, to a position in
N
j
. We know that the number of distinct values
that appear at positions belonging to the
N
i
's such that
i
<
j
is bounded by the polynomial
q
(
=
j
, is bounded by the polynomial
q
(
T
)=
T
∑
j
−
1
i
=0
p
i
(
).Let(
V
,
A
) be a position in
N
j
,andlet
e
be the maximum number
of special edges that enter a node in
G
(we know that
e
is a constant, as it only depends
on
T
)=
T
∑
). Then for every choice of
e
values in
j
−
1
i
=0
N
i
(one value for each special edge that
can enter a position) and for every dependency in
M
Σ
t
there is at most one new value that
can be generated at position (
V
,
A
). Thus, the maximum number of new values that can be
generated during a chase step in (
V
,
A
) is at most
)
e
. We conclude that the
maximum number of distinct values that can be generated at a position in
N
j
is at most
q
(
M·
q
(
T
2
)
e
, which is polynomial, since
and
e
are fixed.
Putting this all together, we can define the polynomial
p
i
(
x
) as
x
+
q
(
x
)+
q
(
x
).This
finishes the proof of the claim and the theorem.
T
)=
M
·
q
(
T
M
The theorem above shows that the class of mappings with a weakly acyclic set of tgds is
well behaved with respect to data exchange. Indeed, as an immediate corollary to
Proposi-
tion 5.6
(which states that the result of the chase is always a solution) and
Theorem 5.11
,
we obtain that the problem of existence of solutions for mappings with a weakly acyclic
set of tgds is tractable. But not only that, we also see that for every source instance that has
solution, a particular solution can be materialized in polynomial time.
