Database Reference
In-Depth Information
P S 1 .Let S 2 be an instance of R 1 consisting only of the fact P ( t 0 ),thatis, P S 2 =
t 0
{
t 0 }
and R S 2 = 0 for all the other relations R in R 1 .Since
Σ 12 is a set of st-tgds, we have that:
S OL M ( S 2 ) .
S OL M ( S 2 )
S OL M ( S 2 ) and S 2
S 1 , which shows that ( S 1 , S 2 ) is also a wit-
Hence, S OL M ( S 1 )
.Nowlet T 1 , T 2 be the canonical universal
ness for the noninvertibility of mapping
M
solutions for S 1 and S 2 under
M
, respectively. Given that T 1
S OL M ( S 1 ),wehavethat
S OL M ( S 2 ) and, therefore, there exists a homomorphism h from T 2 to T 1 .Weuse
h to construct the desired quadratic-size witness for the noninvertibility of mapping
T 1
.
More precisely, let S 1 be an instance of R 1 defined as follows. For every R in R 2 and tuple
t
M
R T 2 , choose a st-tgd
b such that (1)
ϕ
( x )
→∃
y
ψ
( x , y ) and tuples a ,
ϕ
( x )
→∃
y
ψ
( x , y )
Σ 12 , a is a tuple of values from D OM ( S 1 ) and b is a tuple of values from
D OM ( T 1 ),(2)
is a st-tgd in
( a , b ) holds in T 1 ,and(4) R ( h ( t )) is a conjunct in
ϕ
( a ) holds in S 1 ,(3)
ψ
( a , b ). It should be noticed that such a tuple exists since ( S 1 , T 1 ) satisfies
ψ
12 and R ( h ( t ))
is a fact in T 1 (given that h is a homomorphism from T 2 to T 1 ). Then include all the con-
juncts of ϕ( a ) as facts of S 1 . Next we show that ( S 1 , S 2 ) is a witness for the noninvertibility
of
Σ
S 1
S 2
2 ).
M
and
+
is O (
Σ 12
. By definition of S 1 ,we
have that the homomorphism h mentioned above is also a homomorphism from T 2
Let T 1
be the canonical universal solution for S 1 under
M
to T 1 .
Thus, given that T 1
is a universal solution for S 1 under
is closed under target
homomorphisms (see Proposition 21.1 in Section 21.1 ), we conclude that S OL M ( S 1 )
M
and
M
S OL M ( S 2 ). Moreover, given that S 1
S 1 ,wealsohavethat S 2
S 1 and, hence, ( S 1 , S 2 ) is
. Finally, given that S 2 consists of only one fact, we
a witness for the noninvertibility of
M
T 2
have that
. Therefore, given that the number of tuples that are
included in S 1 for each fact R ( t ) in T 2 is bounded by
is bounded by
Σ 12
S 1
Σ 12
,wehavethat
is bounded
2 . Thus, it holds that
S 1
S 2
2 ), which concludes the proof of the
by
Σ 12
+
is O (
Σ 12
theorem.
M ,whether
A problem related to checking invertibility is to check, for mappings
M
and
M is an inverse of
. Somewhat surprisingly, this problem is undecidable even for the
class of mappings specified by st-tgds.
M
M =
Theorem 20.11 The problem of verifying, given mappings
M
=(R 1 , R 2 ,
Σ 12 ) and
M is an inverse of
(R 2 , R 1 ,
Σ 21 ) with
Σ 12 and
Σ 21 finite sets of st-tgds, whether
M
is
undecidable.
A fundamental, and arguably the most important, issue about any notion of inverse is the
problem of computing an inverse for a given mapping. We shall handle this problem in
Section 20.3 .
A relaxation of inverses: quasi-inverse
The notion of inverse is rather restrictive as there are many mappings that do not possess
an inverse. Thus, there is a need for weaker notions of inversion. We now briefly outline
one, known as quasi-inverses of schema mappings.
Search WWH ::

Custom Search