proof of Proposition 5.6 , since in Section 6.2 ( Theorem 6.7 ) we will prove a more general
Example 5.7 ( Example 4.1 continued)
It is clear that there is a unique successful chase
sequence for S under
, and that its result is T shownonpage 39 . Thus, from Proposition
5.6 , T is a solution for S .
But the chase as a tool for data exchange has one drawback: nothing can be concluded
about the existence of solutions in the case when the chase does not terminate. Thus, we
now concentrate on conditions that guarantee chase termination.
5.4 Weak acyclicity of target constraints
As we have seen, the main problem with the application of the chase is nontermination.
This happens, for instance, when the set of tgds permits an infinite sequence of null creation
during the chase (as in the second case of Example 5.4 ). So a natural idea is to restrict target
constraints to make such an infinite sequence of null creation impossible.
We now do precisely this, and restrict the shape of tgds to prevent such behavior, and
obtain a meaningful class of mappings for which the chase is not only guaranteed to termi-
nate, but does it in polynomially many steps.
We first provide some intuition behind the restriction. Recall Example 5.4 ,inwhich
we had a single target tgd
zL ( y , z ). In that example, the tgd was fired to
create new tuples in relation L based on tuples in relation G , and once it was done, the chase
terminated. However, when we extended the set of constraints with the tgd
θ 1 = G ( x , y )
θ 2 = L ( x , y )
zG ( y , z ), we entered a cycle: each fact in G created a fact in L , which then created a fact
in G , which created a fact in L , and so on.
Thus, we need to avoid cycles. To enforce this syntactically, note that in our example,
θ 1 says that L depends on G ,and
θ 2 says that G depends on L . So, we break cycles of this
kind. Formally, we do it as follows.
follows. The nodes (positions) of the graph are all pairs ( R , i ),where R is a relation symbol
in R t of arity n and 1
is a set of tgds over R t . We construct the simple dependency graph of
n . Then we add edges as follows. For every tgd
( x , y )
, and for every variable x mentioned in x that occurs in the i th position
(attribute) of relation R in
( x , z )) in
, add an edge from ( R , i ) to ( T , j ) if the variable that occurs in
the j th position of relation T in
x itself, or
an existentially quantified variable z (that corresponds to the introduction of a new
Definition 5.8 (Acyclicity) We say that a set
of tgds is acyclic if its simple dependency
graph has no cycles.