Database Reference
InDepth Information
The idea behind quasiinverses is to relax the notion of inverse by not differentiating
between source instances that are equivalent for dataexchange 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
specifiedbysttgd
R
(
x
,
y
)
→
∼
M
S
2
.
The quasiinverse 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 quasiinverse is defined as:
Definition 20.12 (Quasiinverse)
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 quasiinverse 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 sttgd
R
(
x
,
y
)
→
T
(
x
).It
was shown in
Example 20.4
that
does not have an inverse, as it does not satisfy the
uniquesolutions property. However, mapping
M
M
specified by tgd
T
(
x
)
→∃
zR
(
x
,
z
) is a
quasiinverse 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 quasiinverse 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
)
∈
}
.