Database Reference

In-Depth Information

,wehavethat
S
2
∼
M
S
2
, from which we conclude

that
S
2
∼
M
S
2
. Furthermore, from the definition of instance
S
2
and inclusion
(20.3)
,we

have that
S
1
⊆

By definition of the mapping

M

S
2
. Hence, we conclude that (
S
1
,
S
2
)

∈

Id
R
1
, which implies that (
S
1
,
S
2
)

∈

∼
M
] since
S
1
∼
M
S
1
and
S
2
∼
M
S
2
. Thus, we have shown that inclusion
(20.2)

holds, which proves that

Id
R
1
[

∼
M
,

M
is a quasi-inverse of

M

.

We have seen that quasi-inverses may exist when inverses do not exist. But is it the case

that the notion of quasi-inverse strictly generalizes the notion of inverse? If we focus on

the class of mapping for which the notion of inverse is appropriate (see
Section 20.1
), then

the answer is positive.

Proposition 20.14

There exists a mapping specified by a finite set of st-tgds that is not

invertible but has a quasi-inverse.

•
For every mapping
M
that is total, closed-down on the left and invertible, a mapping

M
is an inverse of
M
if and only if
M
is a quasi-inverse of
M
.

•

When do quasi-inverses exist? We previously used the subset property to characterize

invertibility (see
Theorem 20.7
). It turns out that a relaxation of this property obtained by

not differentiating between source instances that are equivalent for data-exchange purposes

characterizes quasi-invertibility. Formally, a mapping

M

from a schema R
1
to a schema

R
2
is said to satisfy the (

∼
M
,

∼
M
)
-subset property
if for every pair
S
1
,
S
2
of instances of

S
OL
M
(
S
2
), then there exist instances
S
1
,
S
2
of R
1
such that
S
1
∼
M
S
1
,

R
1
,ifS
OL
M
(
S
1
)

⊆

S
2
∼
M
S
2
and
S
2
⊆

S
1
.

Theorem 20.15

Let

M

be a mapping specified by a finite set of st-tgds. Then

M

is

quasi-invertible if and only if

M

satisfies the
(

∼
M
,

∼
M
)
-subset property.

Still, not every mapping specified by st-tgds has a quasi-inverse. In fact, a rather strong

negative statement is true.

Proposition 20.16

There exists a mapping

M

specified by a single st-tgd that has no

quasi-inverse.

The mapping is quite simple. The source schema R
1
consists of a binary relation
E
,the

target schema R
2
consists of a binary relation
F
and a unary relation
G
, and there is a single

st-tgd

E
(
x
,
z
)

∧
E
(
z
,
y
)

→
F
(
x
,
y
)

∧
G
(
z
)
.

(20.4)

One can then show that

M

does not satisfy the (

∼
M
,

∼
M
)-subset property, and thus is not

quasi-invertible.

As for the case of inverses, the problem of checking, given mappings

M
,

M

and

M
is a quasi-inverse of

whether

M

is undecidable. In fact, it is undecidable even for

the most common mappings.

M
=

Theorem 20.17
The problem of verifying, given mappings

M

=(R
1
,
R
2
,

Σ
12
)
and