Inverting schema mappings - Foundations of Data Exchange - page 282

∈M ◦M , it holds that S 2 ∈ (1) for every ( S 1 , S 2 ) D OM ( M ) , and

M ◦M ◦M (2) M = .

M is a maximum recovery of

Proof . We first prove that condition

(1) holds. For the sake of contradiction, assume that there exists ( S 1 , S 2 )

( ⇒ ) Assume that M

∈M ◦M such

M ⊆M as M = ∈M | that S 2 ∈ D OM ( M ). Then define the mapping { ( T , S ) S ∈

M is a recovery of M is a recovery of

D OM ( M ) } . Given that M ,wehavethat M .

M◦M M◦M since M ⊆M and ( S 1 , S 2 ) ∈M◦M . Thus, we obtain

Moreover,

M is assumed to be a maximum recovery of

a contradiction since M .

M is a recovery of We continue by showing that condition (2) holds. Given that M ,we

∈M◦M for every S M ⊆M◦M ◦M have that ( S , S ) ∈ D OM ( M ), which implies that .

M ◦M ◦M ⊆M

Thus, we only need to show that . By the sake of contradiction, assume

∈M◦M ◦M

that there exists ( S 1 , T 1 ) such that ( S 1 , T 1 ) ∈M . Then, there exist instances

∈M ,and( S 2 , T 1 )

S 2 and T 2 such that ( S 1 , T 2 ) ∈M , ( T 2 , S 2 ) ∈M . Note that T 1 = T 2 and

be a mapping from R 2 to R 1

S 1 = S 2 , because we are assuming that ( S 1 , T 1 ) ∈M .Let M

defined as:

=

∈M | S

M { ( T , S ) = S 2 }∪{ ( T 1 , S 2 ) } .

M is a recovery of

is a recovery of

Given that M and ( S 2 , T 1 ) ∈M ,wehavethat M M .

∈M ◦M , but given that ( S 1 , T 1 ) Now, consider the pair ( S 1 , S 2 ). We know that ( S 1 , S 2 ) ∈

where S 2 appears as the second component, we

M and ( T 1 , S 2 ) is the only tuple in M

. Thus, we conclude that

M ◦M ⊆M ◦M

. Hence, we

have that ( S 1 , S 2 ) ∈ M ◦M

M is assumed to be a maximum recovery of obtain a contradiction since M .

∈ M ◦M , then we have that S OL M ( S 2 )

( ⇐ ) We first notice that if ( S 1 , S 2 ) ⊆

S OL M ( S 1 ). To see why this is the case, let T ∈ S OL M ( S 2 ). Then given that ( S 1 , S 2 ) ∈

M ◦M ,wehavethat( S 1 , T ) ∈M ◦M ◦M M ◦M ◦M

M

,we
have that ( S 1 , T ) ∈M and, hence, T ∈ S OL M ( S 1 ). Next we use this property to prove that
if

. Thus, given that =

M satisfies (1) and (2), then M is a maximum recovery of M .

M is not a maximum recovery of

For the sake of contradiction, assume that M .

M is a recovery of M of

Then given that M , there exists a recovery M such that

M◦M ⊆M◦M . We have then that there is a tuple ( S , S ) ∈M◦M such that ( S , S )

∈

M◦M . Given that M satisfies condition (1), we have that S is an instance in D OM ( M ).

M is a recovery of ,wehavethat( S , S ) isatuplein M ◦M and, Hence, given that M

therefore, there exists an instance T of R 2 such that ( S , T ) and ( T , S ) ∈M .By

∈M

the observation in the previous paragraph, we know that S OL M ( S )

⊆ S OL M ( S ),soif

( S , T ) and ( T , S ) ∈M ,

∈M then ( S , T ) ∈M . Therefore, we conclude that ( S , T ) ∈M

which implies that ( S , S ) ∈M◦M and leads to a contradiction. This concludes the proof

of the proposition.

Next we use Proposition 20.21 to prove that the claims in Example 20.20 are indeed
correct. But before doing this, we give some intuition about the conditions in Proposi-
tion 20.21 . The first such condition tells us that if an instance S is not in the domain of
a mapping M , then a maximum recovery of M should not recover information about