Database Reference
In-Depth Information
The idea behind quasi-inverses is to relax the notion of inverse by not differentiating
between source instances that are equivalent for data-exchange purposes. More precisely,
let
be a mapping from a schema R
1
to a schema R
2
. Instances
S
1
and
S
2
of R
1
are
data-
exchange equivalent
with respect to
M
M
, denoted by
S
1
∼
M
S
2
,ifS
OL
M
(
S
1
)=S
OL
M
(
S
2
).
For instance, for the mapping
T
(
x
),wehavethatif
S
1
is
an instance consisting of the fact
R
(1
,
2) and
S
2
is an instance consisting of the fact
R
(1
,
3),
then
S
1
M
specifiedbyst-tgd
R
(
x
,
y
)
→
∼
M
S
2
.
The quasi-inverse of a mapping
M
is then obtained by not differentiating between
source instances
S
1
and
S
2
such that
S
1
∼
M
S
2
. Formally, given a schema R and a mapping
N
from R to R, the mapping
N
[
∼
M
,
∼
M
] is defined as:
there exist
S
1
,
S
2
∈
{
(
S
1
,
S
2
)
∈
I
NST
(R)
×
I
NST
(R)
|
I
NST
(R) such that
S
1
∼
M
S
1
,
S
2
∼
M
S
2
and (
S
1
,
S
2
)
∈N }
,
and then the notion of quasi-inverse is defined as:
Definition 20.12 (Quasi-inverse)
Let
M
be a mapping from a schema R
1
to a
M
a mapping from R
2
to R
1
.Then
M
is a quasi-inverse of
schema R
2
,and
M
if
M ◦M
)[
(
∼
M
,
∼
M
]=Id
R
1
[
∼
M
,
∼
M
].
Example 20.13 Let R
1
be a schema consisting of a binary relation
R
, R
2
a schema con-
sisting of a unary relation
T
,and
M
a mapping specified by st-tgd
R
(
x
,
y
)
→
T
(
x
).It
was shown in
Example 20.4
that
does not have an inverse, as it does not satisfy the
unique-solutions property. However, mapping
M
M
specified by tgd
T
(
x
)
→∃
zR
(
x
,
z
) is a
quasi-inverse of
M
. To see why this is the case, consider first the inclusion:
Id
R
1
[
∼
M
,∼
M
]
⊆
(
M ◦M
)[
∼
M
,∼
M
]
.
(20.1)
∼
M
], then there exist instances
S
1
,
S
2
of R
1
such that
S
1
∼
M
S
1
,
If (
S
1
,
S
2
)
∈
Id
R
1
[
∼
M
,
S
2
∼
M
S
2
and (
S
1
,
S
2
)
Id
R
1
. Thus, we have that
S
1
⊆
S
2
.Let
T
1
be the canonical universal
∈
solution for
S
1
under
. Then we have that (
S
1
,
T
1
)
, and also that (
T
1
,
S
2
)
∈M
by
M
∈M
M
, and given that
S
1
⊆
S
2
. Hence, we conclude that (
S
1
,
S
2
)
the definitions of
M
and
∈
∼
M
] since
S
1
∼
M
S
1
and
S
2
∼
M
S
2
. Thus, we have shown that inclusion
(20.1)
holds, and it only remains to prove that the
following inclusion holds to show that
M◦M
), which implies that (
S
1
,
S
2
)
M◦M
)[
∈
∼
M
,
(
(
M
is a quasi-inverse of
M
:
M ◦M
)[
(
∼
M
,
∼
M
]
⊆
Id
R
1
[
∼
M
,
∼
M
]
.
(20.2)
M ◦M
)[
∼
M
], then there exist instances
S
1
,
S
2
of R
1
such that
S
1
∼
M
If (
S
1
,
S
2
)
∈
(
∼
M
,
S
1
,
S
2
∼
M
S
2
and (
S
1
,
S
2
)
M ◦M
). Thus, we have that there exists an instance
T
of
∈
(
R
2
such that (
S
1
,
T
)
and (
T
,
S
2
)
∈M
, from which we conclude that:
∈M
R
S
1
R
S
2
{
a
|
(
a
,
b
)
∈
}⊆{
a
|
(
a
,
b
)
∈
}
.
(20.3)
Let
S
2
be an instance of R
1
defined as:
R
S
2
=
R
S
2
R
S
1
{
a
|
(
a
,
b
)
∈
}×{
d
|
(
c
,
d
)
∈
}
.
