Database Reference
In-Depth Information
We now show that the notion of witness solution can be used to characterize the existence
of maximum recoveries.
Theorem 20.25
Let
M
be a mapping from a schema
R
1
to a schema
R
2
.Then
M
has
a maximum recovery if and only if every instance S
∈
D
OM
(
M
)
has a witness solution
under
M
.
M
be a maximum recovery of
Proof
(
⇒
)Let
M
,and
S
an instance in D
OM
(
M
).Then
M
is a recovery of
given that
M
, we have that there exists an instance
T
of R
2
such that
∈M
. Next we show that
T
is a witness solution for
S
under
(
S
,
T
)
∈M
and (
T
,
S
)
M
.
We already know that
T
is a solution for
S
under
M
, so we only need to show that if
T
∈
S
OL
M
(
S
), then it holds that S
OL
M
(
S
)
S
OL
M
(
S
). Thus assume that
T
∈
⊆
S
OL
M
(
S
).
Given that (
S
,
T
)
∈M
and (
S
,
T
)
,wehavethat(
S
,
T
)
∈M◦M
◦M
∈M
, (
T
,
S
)
∈M
.
M ◦M
◦M
and, therefore, (
S
,
T
)
But from
Proposition 20.21
we have that
M
=
∈M
.
S
OL
M
(
S
) and, hence,
T
is a witness solution for
S
under
We conclude that S
OL
M
(
S
)
⊆
M
.
be
(
⇐
) Assume that every
S
∈
D
OM
(
M
) has a witness solution under
M
,andlet
M
a mapping from R
2
to R
1
defined as:
{
(
T
,
S
)
|
T
is a witness solution for
S
under
M}
.
is a recovery of
By hypothesis, we have that
M
M
.Nextweuse
Proposition 20.21
to
is a maximum recovery of
show that
M
M
.
, we have that this mappings satisfies condition (1) in
Proposition
20.21
. Moreover, given that
By definition of
M
is a recovery of
M
M
,wehavethat
M ⊆M ◦M
◦M
.
is a maximum
Thus, we have from
Proposition 20.21
that if
M ◦M
◦M ⊆M
,then
M
recovery of
M
.Let(
S
,
T
)
∈M ◦M
◦M
. Then there exist instances
T
1
,
S
1
of R
2
and R
1
,
and (
S
1
,
T
)
respectively, such that (
S
,
T
1
)
∈M
, (
T
1
,
S
1
)
∈M
∈M
. Thus, by definition
,wehavethat
T
1
is a witness solution for
S
1
under
of
M
M
. Hence, given that
T
1
∈
S
OL
M
(
S
),wehavethatS
OL
M
(
S
1
)
⊆
S
OL
M
(
S
). We conclude that
T
∈
S
OL
M
(
S
) since
T
∈
S
OL
M
(
S
1
) and, thus, we have that (
S
,
T
)
∈M
, which was to be shown. This concludes
the proof of the theorem.
As a corollary of
Proposition 20.24
and
Theorem 20.25
, we obtain the desired result that
every mapping specified by a finite set of st-tgds admits a maximum recovery. It should
be noticed that this result is in sharp contrast with the nonexistence results for the notions
of inverse and quasi-inverse and the class of mappings specified by st-tgds (see
Corollary
20.5
and
Proposition 20.16
).
Theorem 20.26
Every mapping specified by a finite set of st-tgds admits a maximum
recovery.
Up to this point, we have introduced three alternative inverse operators for schema map-
pings: inverse, quasi-inverse and maximum recovery. In the previous section, we showed
that there is a tight connection between the first two operators (see
Proposition 20.14
), and,
