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
