Database Reference
InDepth 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 sttgds 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 quasiinverse and the class of mappings specified by sttgds (see
Corollary
20.5
and
Proposition 20.16
).
Theorem 20.26
Every mapping specified by a finite set of sttgds admits a maximum
recovery.
Up to this point, we have introduced three alternative inverse operators for schema map
pings: inverse, quasiinverse 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,