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.