Database Reference
In-Depth Information
Definition 8.20 (CWA presolutions with target dependencies) Let
M
=(R s , R t ,
Σ st ,
Σ t )
be a mapping, where
Σ t consists of a set of tgds and egds. If S is a source instance, then T
is a CWA presolution for S under
M
if (i) T is a solution for S , and (ii) T is the result of
an
α
-chase sequence for S under
M
,forsome
α
:
K M
C ONST
V AR .
The reason why we impose the condition that a CWA presolution is also a solution for S
is to make sure that the result of the
α
-chase does satisfy the egds in
Σ t . We leave it as an
exercise for the reader to verify that when
Σ t = 0 this definition coincides with Definition
8.10 , which defines CWA presolutions in the absence of target dependencies.
We illustrate the concept of CWA presolution with the following example.
Example 8.21 Consider the mapping M such that the source schema consists of the
unary relation P and the target schema consists of the ternary relations E and F .Assume
that
Σ st consists of the st-tgd
σ 1 and
Σ t consists of the tgd
σ 2 ,where:
σ 1 = P ( x )
→∃
z 1
z 2
z 3
z 4 ( E ( x , z 1 , z 3 )
E ( x , z 2 , z 4 ))
σ 2 = E ( x , x 1 , y )
E ( x , x 2 , y )
F ( x , x 1 , x 2 ) .
For the source instance S =
{ P ( a )
}
the following three target instances are CWA preso-
lutions:
T 1 =
{
E ( a ,
1 ,
3 ) , E ( a ,
2 ,
4 ) , F ( a ,
1 ,
1 ) , F ( a ,
2 ,
2 )
}
T 2 =
{
E ( a ,
1 ,
3 ) , E ( a ,
2 ,
3 ) , F ( a ,
1 ,
1 ) ,
F ( a ,
2 ,
2 ) , F ( a ,
1 ,
2 ) , F ( a ,
2 ,
1 )
}
{
E ( a , b ,
3 ) , E ( a ,
2 ,
4 ) , F ( a , b , b ) , F ( a ,
2 ,
2 )
}
.
T 3 =
This is because for each 1
i
3 it is the case that T i is a solution for S that is the result
of the
α i -chase that satisfies the following (among other things that are not relevant for the
final result):
α
1 (
σ
1 , z j )=
j , for each 1
j
4.
α
2 (
σ
1 , z j )=
j , for each 1
j
3, and
α
2 (
σ
1 , z 4 )=
α
2 (
σ
1 , z 3 ).
α 3 (
σ 1 , z 1 )= b and
σ 1 , z j )=
α 3 (
j , for each 2
j
4.
Notice that, in particular, T 1 is the canonical universal solution for S .
We are finally in the position of defining CWA solutions in the presence of target depen-
dencies. As in the case without target dependencies, these are the CWA presolutions T for
S that satisfy the requirement:
(A3) Every statement that holds in T also holds in every solution T for S .
Definition 8.22 (CWA solutions with target dependencies) Let
M
=(R s , R t ,
Σ st ,
Σ st ) be
a mapping, where
Σ t consists of a set of tgds and egds. If S is a source instance, then T
is a CWA solution for S under
if (i) T is a CWA presolution for S , and (ii) T satisfies
requirement (A3) formalized above.
M
Search WWH ::




Custom Search