Database Reference
In-Depth Information
are guaranteed to exist when considering the extended semantics for mappings given by
tgds, and containing null values in source and target instances.
Theorem 20.42
specified by a finite set of tgds and containing
null values in source and target instances, e
(
For every mapping
M
M
)
admits a maximum recovery.
The notion of a homomorphic extension gives rise to the notion of maximum extended
recovery.
Definition 20.43 (Maximum extended recovery) Let
M
be a mapping from a schema R
1
M
a mapping from R
2
to R
1
.Then
to a schema R
2
and
M
is an
extended recovery
of
1.
M
if for every instance
S
of R
1
, it holds that (
S
,
S
)
∈
M
);
e
(
M
)
◦
e
(
M
is a
maximum extended recovery
of
M
is an extended recovery of
2.
M
if
M
,and
M
of
M
)
M
).
for every extended recovery
M
,wehave
e
(
M
)
◦
e
(
⊆
e
(
M
)
◦
e
(
At first glance, one may be tempted to think that the notions of maximum recovery and
maximum extended recovery are incomparable. However, the following theorem shows
that there is a tight connection between these two notions and, in particular, shows that
the notion of maximum extended recovery can be defined in terms of the notion of maxi-
mum recovery. It is important to notice that a mapping
M
admits a (maximum) extended
recovery only if the domain of
e
(
) is the set of all source instances. Thus, it is only
meaningful to compare the notions of (maximum) extended recovery and (maximum) re-
covery under this restriction and, therefore, the following theorem considers a mapping
M
from a schema R
1
to a schema R
2
such that D
OM
(
e
(
M
M
)) = I
NST
(R
1
).
Theorem 20.44
Let
M
be a mapping from a schema
R
1
toaschema
R
2
such that
D
OM
(
e
(
M
)) = I
NST
(R
1
)
.Then
1.
M
admits a maximum extended recovery if and only if e
(
M
)
admits a maximum recov-
ery.
2. A mapping
M
is a maximum extended recovery of
M
)
is a maxi-
M
if and only if e
(
mum recovery of e
(
M
)
.
Proof
We first introduce some notation to simplify the exposition. Consider a binary
relation
→
defined as follows:
→
=
{
(
S
1
,
S
2
)
|
there exists a homomorphism from
S
1
to
S
2
}
.
The introduction of relation
allows us to simplify the definition of the extended seman-
tics of a mapping. In fact, given a mapping
→
M
,wehavethat
e
(
M
)=
→◦M ◦→
.
