Database Reference
In-Depth Information
thus, it is natural to ask what is the relationship between them and the notion of maximum
recovery. We first answer this question for the notion of inverse and the class of mappings
that are total and closed-down on the left, for which the notion of inverse is appropriate
(see
Section 20.1
).
Proposition 20.27
(1) There exists a mapping specified by a finite set of st-tgds that is
not invertible but has a maximum recovery.
(2) For every mapping
M
that is total, closed-down on the left and invertible, a mapping
M
is an inverse of
M
is a maximum recovery of
M
if and only if
M
.
Proof
(1) Let R
1
be a schema consisting of a binary relation
E
, R
2
a schema consisting
of a binary relation
F
and a unary relation
G
,and
M
=(R
1
,
R
2
,
Σ
) with
Σ
a set of st-tgds
consisting of the following dependency:
E
(
x
,
z
)
∧
E
(
z
,
y
)
→
F
(
x
,
y
)
∧
G
(
z
)
.
In
Proposition 20.16
, we show that
is not quasi-invertible. Thus, we have that this map-
ping is not invertible by
Proposition 20.14
. On the other hand, we show in
Examples 20.20
and
20.22
a maximum recovery of
M
M
. This proves that condition (1) of the proposition
holds.
(2) Let
M
a mapping from R
2
M
be a mapping from a schema R
1
to a schema R
2
and
to R
1
. Moreover, assume that
is total, closed-down on the left and invertible. Next we
prove the two directions of this part of the proposition.
(
M
M
is an inverse of
∈ M ◦M
if and only if
⇒
) If
M
, then we have that (
S
1
,
S
2
)
M
is a recovery of
S
1
⊆
S
2
. Thus, we know that
M
and, therefore, given that
M
is a
M
is a maximum recovery of
total mapping, we have from
Proposition 20.21
that
M
if
M ◦M
◦M ⊆M
M ⊆M ◦M
◦M
M
is a recovery of
(we already know that
since
∈M ◦M
◦M
. Then there exists an instance
S
of R
1
such that
M
). Assume that (
S
,
T
)
(
S
,
S
)
∈M◦M
and (
S
,
T
)
S
, fromwhich we conclude that
∈M
⊆
. Thus, we have that
S
S
OL
M
(
S
)
is closed-down on the left. Hence, given that (
S
,
T
)
⊆
M
∈M
S
OL
M
(
S
) since
,
M◦M
◦M ⊆
we have that
T
∈
S
OL
M
(
S
) and, therefore, (
S
,
T
)
∈M
. Thus, we have that
M
, which was to be shown.
(
M
is a maximum recovery of
M
is an
⇐
) Assume that
M
. In order to show that
∈ M ◦M
if and only if
S
1
⊆
inverse of
M
, we need to show that (
S
1
,
S
2
)
S
2
.First,
M
is a recovery of
assume that
S
1
⊆
S
2
. Given that
S
2
is an instance of R
1
,
M
and
M
∈M ◦M
.Thus,giventhat
is total, we know that (
S
2
,
S
2
)
M
is closed-down on the left,
∈M ◦M
. Second, assume that (
S
1
,
S
2
)
∈M ◦M
. Given that
we have that (
S
1
,
S
2
)
M
M
of
M
is a recovery of
is invertible, there exists an inverse
M
.Then
M
and, thus,
M
is a maximum recovery of
M ◦M
⊆M ◦M
.Weinfer
given that
M
,wehavethat
∈M ◦M
since (
S
1
,
S
2
)
∈M ◦M
, which implies that
S
1
⊆
M
is
that (
S
1
,
S
2
)
S
2
since
an inverse of
We now consider the second part of our question, namely what is the relationship between
the notions of quasi-inverse and maximum recovery. As shown in the following proposi-
tion, the situation is a bit more involved than for the case of the notion of inverse.
M
. This concludes the proof of the proposition.
