Database Reference
In-Depth Information
graph and the simple dependency graph are the same: the only difference is that in the
dependency graph, some edges are annotated with . Another interesting class of weakly
acyclic sets of tgds includes sets of tgds without existential quantification in the right-hand
side, i.e., full tgds.
We now prove that the chase always terminates for mappings with a weakly acyclic sets
of tgds. Moreover, in this case the chase for S terminates after polynomially many steps.
Theorem 5.11
Σ t is
the union of a set of egds and a weakly acyclic set of tgds. Then there exists a polynomial p
such that the length of every chase sequence for a source instance S under
=(R s , R t ,
Σ st ,
Σ t ) be a fixed relational mapping, such that
is bounded
by p (
) .
Proof For the sake of simplicity we prove the theorem in the absence of egds. The addi-
tion of egds does not change the argument of the proof in any fundamental way.
First of all, with each node ( V , i ) in the dependency graph of
Σ t we associate its rank ,
denoted by rank( V , i ), which is the maximum number of special edges in any path in the
dependency graph G of
Σ t is weakly acyclic, the rank of each
node in G is finite. Moreover, it is clear that the maximum rank r of a node in G is bounded
by the number m of nodes in G itself. Notice that m (and, thus, r ) is a constant, since it
corresponds to the total number of attributes in the schema R t (which is assumed to be
Let us partition the nodes of G into sets N 0 , N 1 ,..., N r such that ( V , i ) belongs to N j if
and only if rank( V , i )= j ,for0
Σ t that ends in ( V , i ).Since
r . To prove the theorem, we need the following
technical result.
Claim 5.12
r, there exists a polynomial p j such that the following
holds. Let T be a target instance and T be any target instance that is obtained from T by
a sequence of chase steps using the tgds in
Fo r e a c h 0
Σ t . Then the number of distinct elements (i.e.,
constants and nulls) that occur in T at positions that are restricted to be in N j is bounded
by p j (
) .
First we show how the theorem can be proved from Claim 5.12 . It follows easily from
the proof of Proposition 5.1 that there is a polynomial p , which depends only on
such that if T is the result of any chase sequence for S under
Σ st ,then
is bounded
by p (
). Furthermore, it follows from Claim 5.12 that there exists a polynomial p ,
which depends only on
, such that the maximum number of elements that occur in the
result T of a chase sequence for T under
Σ t , at a single position, is bounded by p (
Thus, the total number of tuples that can exist in one relation in T is at most p (
) m
(since each relation symbol in R t can have arity at most m ). Thus, the total number of
tuples in T is bounded by
p (
) m . This is polynomial in
is fixed.
Furthermore, each chase step that uses a tgd adds at least one tuple. Thus, the length of
any chase sequence c for a source instance S under
)) m .
This is because c is a sequence of chase steps that are obtained by either applying an std in
Σ st to the source instance S ,oratgdin
p ( p (
is bounded by
Σ t to the facts that have already been added to the
Search WWH ::

Custom Search