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