Inverting schema mappings - Foundations of Data Exchange - page 297

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 ) admits

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