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.