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
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
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
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
be a mapping specified by a finite set of st-tgds. Then
quasi-invertible if and only if
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
specified by a single st-tgd that has no
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
E ( x , z )
E ( z , y )
F ( x , y )
G ( z ) .
One can then show that
does not satisfy the (
M ,
M )-subset property, and thus is not
As for the case of inverses, the problem of checking, given mappings
M ,
M is a quasi-inverse of
is undecidable. In fact, it is undecidable even for
the most common mappings.
M =
Theorem 20.17 The problem of verifying, given mappings
=(R 1 , R 2 ,
Σ 12 ) and
Search WWH ::

Custom Search