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,
Search WWH ::

Custom Search