p ( p ( x )) m . This completes the
target. Hence we can take p ( x ) to be the polynomial
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
. 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
. Second, there may be values that are copied by a chase step from a position
in N i , with j
= 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 =0 p i (
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
= j , is bounded by the polynomial q (
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
). 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
Σ 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
) 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.
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.