Database Reference
In-Depth Information
hence, (
T
,
S
)
). Therefore, given that (
S
,
T
)
) and (
T
,
S
)
),we
∈
e
(
M
∈
e
(
M
∈
e
(
M
). Second, assume that S
OL
e
(
M
)
(
S
)
conclude that (
S
,
S
)
∈
e
(
M
)
◦
e
(
M
⊆
S
OL
e
(
M
)
(
S
1
).
Then there exists an instance
T
such that (
S
,
T
)
) and (
S
1
,
T
)
/
∈
e
(
M
∈
e
(
M
).Bydefini-
,wehavethat(
T
,
S
)
and, thus, (
T
,
S
)
). Thus, we also conclude
tion of
M
∈M
∈
e
(
M
) in this case.
We are now ready to prove that for every (
S
1
,
S
2
)
that (
S
,
S
)
∈
e
(
M
)
◦
e
(
M
M
), it holds that
∈
e
(
M
)
◦
e
(
M
). Given that
M
is a max-
⊆
S
OL
e
(
M
)
(
S
1
).Let(
S
1
,
S
2
)
∈
M
◦
S
OL
e
(
M
)
(
S
2
)
e
(
)
e
(
is an extended recovery of
M
M
M
imum extended recovery of
and
,wehavethat
M
)
) and, therefore, (
S
1
,
S
2
)
). Thus, given
e
(
M
)
◦
e
(
⊆
e
(
M
)
◦
e
(
M
∈
e
(
M
)
◦
e
(
M
)=
e
(
that
e
(
by
(20.17)
, we conclude that there exist instances
T
of R
2
and
S
2
of R
1
such that (
S
1
,
T
)
∈
e
(
M
), (
T
,
S
2
)
∈M
M
)
◦
e
(
M
M
)
◦M
◦→
and (
S
2
,
S
2
)
∈→
. Hence,
,wehavethatS
OL
e
(
M
)
(
S
2
)
by definition of
M
⊆
S
OL
e
(
M
)
(
S
1
) (since (
S
1
,
T
)
∈
e
(
M
)).
S
OL
e
(
M
)
(
S
2
) since (
S
2
,
S
2
)
But we also have that S
OL
e
(
M
)
(
S
2
)
⊆
∈→
, and, therefore, we
conclude that S
OL
e
(
M
)
(
S
2
)
⊆
S
OL
e
(
M
)
(
S
1
), which was to be shown.
(2) Up to this point, we have shown that
M
admits a maximum extended recovery
if and only if
e
(
M
) admits a maximum recovery. In fact, we conclude from the preceding
proof that:
M
,then
M
is a maximum extended recovery of
•
if
e
(
M
) has a maximum recovery
M
,and
M
,then
e
(
M
) is a maximum recovery of
•
if
M
has a maximum extended recovery
e
(
M
).
M
is a
Next we prove the second part of the proposition, that is, we prove that a mapping
M
) is a maximum recovery of
e
(
maximum extended recovery of
).
It should be noticed that the “only if” direction corresponds to the second item above and,
thus, we only need to show that if
e
(
M
if and only if
e
(
M
M
) is a maximum recovery of
e
(
M
is a
M
),then
maximum extended recovery of
M
.
M
) is a maximum recovery of
e
(
M
) is
Assume that
e
(
M
). Then we have that
e
(
M
is an extended recovery of
M
be an
a recovery of
e
(
M
) and, thus,
M
.Nowlet
M
) is a recovery of
e
(
extended recovery of
M
.Thenwehavethat
e
(
M
) and, hence,
M
)
M
) since
e
(
M
) is a maximum recovery of
e
(
e
(
M
)
◦
e
(
⊆
e
(
M
)
◦
e
(
M
). Therefore,
M
is an extended recovery of
M
we conclude that
M
, and for every extended recovery
M
)
M
), which means that
M
is a maximum
M
M
◦
⊆
M
◦
of
, it holds that
e
(
)
e
(
e
(
)
e
(
M
extended recovery of
. This completes the proof of the proposition.
From
Theorems 20.42
and
20.44
, we obtain as a corollary that every mapping specified by
a finite set of tgds and containing nulls in the source has a maximum extended recovery.
M
Corollary 20.45
is a mapping specified by a finite set of tgds and containing null
values in source and target instances, then
If
M
admits a maximum extended recovery.
Finally, another conclusion that can be drawn from
Theorem 20.44
is that the machinery
