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 )
}
.     Search WWH ::

Custom Search