Database Reference

In-Depth Information

Example 20.20 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

Σ

aset

of st-tgds consisting of the following dependency:

E
(
x
,
z
)

∧

E
(
z
,
y
)

→

F
(
x
,
y
)

∧

G
(
z
)
.

(20.5)

Let

M
1
be a mapping from R
2
to R
1
specifiedbytgd:

F
(
x
,
y
)
→∃
z
(
E
(
x
,
z
)
∧
E
(
z
,
y
))
.

(20.6)

It is straightforward to prove that

M
1
is a recovery of

M

. In fact, if
S
is an instance of R
1

and
T
is the canonical universal solution for
S
under

M

, then we have that (
S
,
T
)

∈M

and

(
T
,
S
)

∈M
1
, from which we conclude that (
S
,
S
)

∈M◦M
1
. Similarly, if

M
2
is a mapping

from R
2
to R
1
specified by tgd:

G
(
z
)

→∃
x
∃
y
(
E
(
x
,
z
)

∧
E
(
z
,
y
))
,

(20.7)

then we also have that

M
2
is a recovery of

M

. On the other hand, if

M
3
is a mapping from

R
2
to R
1
specifiedbytgd:

F
(
x
,
y
)

∧

G
(
z
)

→

E
(
x
,
z
)

∧

E
(
z
,
y
)
,

(20.8)

then we have that

M
3
is not a recovery of

M

. To see why this is the case, consider an

instance
S
of R
1
such that:

E
S
=

{

(1
,
1)
,
(2
,
2)

}

.

Next we show that (
S
,
S
)

∈ M ◦M
3
. By the sake of contradiction, assume that (
S
,
S
)

∈

M ◦M
3
,andlet
T
be an instance of R
2
such that (
S
,
T
)

∈M
3
.Given

that (
S
,
T
) satisfies st-tgd
(20.5)
,wehavethat(1
,
1), (2
,
2) are elements of
F
T
and 1, 2 are

elements of
G
T
. But then given that (
T
,
S
) satisfies tgd
(20.8)
, we conclude that the tuples

(1
,
2), (2
,
1) are elements of
E
S
, which leads to a contradiction.

Finally, let

∈M

and (
T
,
S
)

M
4
be a mapping from R
2
to R
1
specified by tgds
(20.6)
and
(20.7)
.In

this case, it is possible to prove that

.Infact,nextwe

introduce some characterizations of the notion of maximum recovery that can be used to

prove this fact.

M
4
is a maximum recovery of

M

M
is an inverse of a mapping

To check whether a mapping

M

, a condition that depends

M
is

equal to the identity mapping. A similar situation holds for the case of the notion of quasi-

inverse. On the other hand, verifying whether a mapping

M
needs to be checked, namely that the composition of

only on

M

and

M

with

M
is a maximum recovery of a

M
with every other recovery of

mapping

. Given that such a test

is more complicated, it would be desirable to have an alternative condition for this notion

that depends only on the input mappings. The next proposition gives one such condition.

M

requires comparing

M

M
a

Proposition 20.21

Let

M

be a mapping from a schema
R
1
toaschema
R
2
, and

M
is a maximum recovery of

recovery of

M

.Then

M

if and only if: