Database Reference
InDepth Information
∈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