Database Reference
In-Depth Information
Notice that the relation
is idempotent , that is, it holds that (
→◦→
)=
. In particular,
we have that
→◦ e (
M
)= e (
M
) ,
(20.16)
e (
M
)
◦→
= e (
M
) .
(20.17)
Thus, if S 1 , S 2 , T are instances such that ( S 1 , S 2 )
∈→
and ( S 2 , T )
e (
M
),then( S 1 , T )
e (
M
). Hence, if ( S 1 , S 2 )
∈→
, then it holds that S OL e ( M ) ( S 2 )
S OL e ( M ) ( S 1 ). We use this
property in the proof.
(1) We first show that
M
admits a maximum extended recovery if and only if e (
M
a maximum recovery.
(
M be a maximum recovery of e (
M is also a
)Let
M
). We show next that
M is a recovery of e (
maximum extended recovery of
M
.Since
M
),wehavethat
◦M for every instance S of R 1 . Moreover, from (20.17) we have that
( S , S )
e (
M
)
◦M = e (
◦→◦M and, thus, ( S , S )
◦→◦M for every in-
e (
M
)
M
)
e (
M
)
stance S of R 1 . Thus, given that ( S , S )
∈→
for every instance S of R 1 , we obtain that
◦→◦M ◦→
M ) for every instance S of R 1 , which implies
( S , S )
M
M
e (
)
= e (
)
e (
M is an extended recovery of
M
that
.
M be an extended recovery of
M )
Now, let
M
. Then we have that ( S , S )
e (
M
)
e (
M ) is a recovery of e (
for every instance S of R 1 , and, hence, we have that e (
). Recall
that M is a maximum recovery of e ( M ) and, hence, we have that e ( M ) ◦M e ( M )
e (
M
M ), which implies that e (
◦M ◦→⊆ e (
M )
M
)
M
)
e (
◦→
. Therefore, given that
M )
M ) by (20.17) ,wehavethat e (
e (
M
)= e (
M
)
◦→
and e (
◦→
= e (
M
)
◦→
◦M ◦→⊆ e (
M ), which implies that e (
M )
M ). Thus,
M
)
e (
M
)
e (
e (
M
)
e (
M is an extended recovery of
we have shown that
M
, and that for every other extended
M of
M )
M ), which implies that
M
recovery
M
, it holds that e (
M
)
e (
e (
M
)
e (
is a maximum extended recovery of
M
.
M be a maximum extended recovery of
M ) is a
(
)Let
M
. Next we show that e (
maximum recovery of e (
M
).
M is an extended recovery of
M )
Given that
M
,wehavethat( S , S )
e (
M
)
e (
M ) is a recovery of e (
for every instance S of R 1 , which implies that e (
M
).Thus,by
M ) is a maximum recovery of e (
Proposition 20.21 , to prove that e (
M
), it is enough to
M ), since this fact
show that S OL e ( M ) ( S 2 )
S OL e ( M ) ( S 1 ) for every ( S 1 , S 2 )
e (
M
)
e (
M )
M ). To prove that
implies that e (
M
)
e (
e (
M
)
e (
M
).Let( S 1 , S 2 )
e (
M
)
e (
from R 2 to R 1 :
S OL e ( M ) ( S 2 )
S OL e ( M ) ( S 1 ), we make use of the following mapping
M
= { ( T , S ) | S is an instance of R 1 and ( S 1 , T ) e ( M ) }∪
{
M
( T , S )
|
( S 1 , T )
e (
M
) and S OL e ( M ) ( S )
S OL e ( M ) ( S 1 )
}
.
is an extended recovery of
We show first that
M
M
, that is, we show that for every
). First, assume that S OL e ( M ) ( S )
instance S of R 1 , it holds that ( S , S )
e (
M
)
e (
M
S OL e ( M ) ( S 1 ), and consider an arbitrary instance T such that ( S , T )
e (
M
). Notice that
( S 1 , T )
S OL e ( M ) ( S 1 ). Thus, we have that ( T , S )
and,
e (
M
) since S OL e ( M ) ( S )
∈M
Search WWH ::

Custom Search