Database Reference
In-Depth Information
Thus, the existence of solutions problem is undecidable over arbitrary relational map-
pings given by st-tgds. This suggests that we should further restrict the class of depen-
dencies allowed in mappings, in such a way that checking the existence of solutions is
a decidable (ideally, tractable) problem. Before presenting such a class, we describe the
main algorithmic tool used in data exchange for checking the existence of solutions and
for building them - the well-known chase procedure.
5.3 The chase
The chase was originally designed for reasoning about the implication problem for data
dependencies. In data exchange, the chase is used as a tool for constructing a solution for a
given source instance. In fact, it constructs a solution with very good properties, as we will
see in the next chapter.
The basic idea behind the chase can be described as follows. It starts with a source
instance S , and then triggers every dependency in
t , as long as this process is appli-
cable. In doing so, the chase may fail (if firing an egd forces two constants to be equal) or
it may never terminate (for instance, in some cases when the set of tgds is cyclic ). Notice
that, in a way, we already applied the chase procedure in the proof of Proposition 5.1 .
Before defining it formally, we illustrate it with an example.
Σ
Σ
st
Example 5.4 Let
M
=(R s , R t ,
Σ
st ,
Σ
t ) be a mapping such that:
the source schema consists of a binary relation E ;
the target schema consists of binary relations G and L ;
Σ st consists of the st-tgd
ϕ
= E ( x , y )
G ( x , y );
Σ
t consists of the tgd
θ
1 = G ( x , y )
→∃
zL ( y , z ).
Let S be the source instance E ( a , b ). The chase procedure starts with the empty target T
and keeps firing rules while some of the constraints are violated. This is done as follows.
1. We start with S =
{
E ( a , b )
}
and T 0 = 0. Then ( S , T 0 ) violates the st-tgd
ϕ
. The chase
procedure uses this constraint to populate the target with the fact G ( a , b ).
2. Now T 1 =
{
G ( a , b )
}
and ( S , T 1 )
|
=
ϕ
.However,( S , T 1 )
|
=
θ 1 , since the relation L is still
empty. This triggers the application of
θ 1 , which results in adding a fact L ( b ,
) to the
target, where
is a fresh null value.
3. Now T 2 =
, and no dependency is violated. Thus, the chase success-
fully terminates ,and T 2 is a solution for S .
{
G ( a , b ) , L ( b ,
)
}
Σ t contains
We now modify target constraints and assume that
θ 1 and a new tgd
θ 2 =
L ( x , y )
zG ( y , z ). The beginning of the chase procedure is the same as before, but it does
not stop at step 3 as before, since ( S , T 2 )
→∃
|
=
θ 2 . The chase continues as follows.
4. A fact G (
,
1 ) is added to the target to satisfy
θ 2 .Hereagain
1 is a new null value.
5. Now T 3 =
{
G ( a , b ) , G (
,
1 ) , L ( b ,
)
}
violates
θ 1 .Sowehavetoaddanewfact
L (
1 ,
2 ),where
2 is a fresh null value.
Search WWH ::




Custom Search