Database Reference

In-Depth Information

this instance. The second condition in
Proposition 20.21
is a desirable property for an in-

verse mapping. Intuitively, given a mapping

M

from a schema R
1
to a schema R
2
and

M
from R
2
to R
1
, mapping

M
does not lose information when bringing

a mapping

back the data exchanged by

M

, if the space of solutions of every instance of R
1
does not

M ◦M
. That is, for every instance
S
of R
1
, it should hold that

change after computing

M◦M
◦M

). In general, recov-

eries do not satisfy this condition, but
Proposition 20.21
shows that maximum recoveries

satisfy it. And not only that, it also shows that the notion of maximum recovery can be

characterized in terms of this condition.

S
OL
M
(
S
)=S
OL

(
S
) (or more succinctly,

M

=

M◦M
◦M

Example 20.22 (
Example 20.20
continued) Recall that the mapping

M

in
Example

20.20
is specified by the following st-tgd:

E
(
x
,
z
)

∧

E
(
z
,
y
)

→

F
(
x
,
y
)

∧

G
(
z
)
,

while recovery

M
4
of

M

is specified by the following tgds:

F
(
x
,
y
)

→∃

z
(
E
(
x
,
z
)

∧

E
(
z
,
y
))
,

G
(
z
)

→∃

x

∃

y
(
E
(
x
,
z
)

∧

E
(
z
,
y
))
.

Next we use
Proposition 20.21
to show that

M
4
is a maximum recovery of

M

. Given that

M
4
is a recovery of

M

,wehavethat

M ⊆M◦M
4
◦M

. Thus, given that D
OM
(

M

)=R
1
,

we conclude from
Proposition 20.21
that to prove that

M
4
is a maximum recovery of

M

,

we only need to show that

M ◦M
4
◦M ⊆M

.

Let (
S
,
T
)

∈ M ◦M
4
◦M

. To prove that (
S
,
T
)

∈ M

, we need to show that (
S
,
T
)

satisfies the st-tgd that specifies

, that is, we have to prove that for every pair of tuples

(
a
,
b
), (
b
,
c
) in
E
S
,where
a
,
b
,
c
are not necessarily distinct elements, it holds that (
a
,
c
)

M

∈

F
T
and
b

G
T
. To prove this, first notice that given that (
S
,
T
)

∈

∈M ◦M
4
◦M

,thereexist

instances
S
1
of R
1
and
T
1
of R
2
such that (
S
,
T
1
)

∈M

, (
T
1
,
S
1
)

∈M
4
and (
S
1
,
T
)

∈M

.

Thus, given that (
a
,
b
), (
b
,
c
) are elements of
E
S
, we conclude that (
a
,
c
)

F
T
1
and
b

G
T
1
.

∈

∈

Hence, from the definition of

M
4
and the fact that (
T
1
,
S
1
)

∈M
4
, we conclude that there

exist elements
d
,
e
and
f
such that:

E
S
1
.

{

(
a
,
d
)
,
(
d
,
c
)
,
(
e
,
b
)
,
(
b
,
f
)

}⊆

F
T
and
b

G
T
,whichwasto

Therefore, given that (
S
1
,
T
)

∈M

, we conclude that (
a
,
c
)

∈

∈

be shown.

On the other hand, it is claimed in
Example 20.20
that the mapping

M
1
specifiedbythe

dependency
F
(
x
,
y
)

→∃

z
(
E
(
x
,
z
)

∧

E
(
z
,
y
)) is not a maximum recovery of

M

(although

it is a recovery of

). To see why this is the case, let
S
,
T
be instances of R
1
and R
2
,

respectively, such that:

M

E
S

F
T

=

{

(1
,
2)
,
(2
,
3)

}

=

{

(1
,
3)

}

G
T

=

{

4

}

.