Database Reference
In-Depth Information
M
but has no
universal solutions. This immediately turns our attention to the problem of the existence of
universal solutions. We prove in the next section that for arbitrary relational mappings this
problem is undecidable. After that we return to the good class of mappings, and show that
universal solutions behave well for them.
and a source instance S , such that S has at least one solution under
M
6.2 Existence of universal solutions
The fact that there are source instances that have solutions but not universal solutions was
already implicit in Example 5.4 .
Example 6.4 ( Example 5.4 continued) Consider again the mapping in which
Σ st consists
of the st-tgd E ( x , y )
G ( x , y ) and
Σ t =
{ θ 1 ,
θ 2 }
,where:
θ 1 := G ( x , y )
→∃
zL ( y , z ) ,
θ 2 := L ( x , y )
→∃
zG ( y , z ) .
Let S =
{
E ( a , b )
}
be a source instance. Then clearly T =
{
G ( a , b ) , L ( b , a )
}
is a solution
for S . We prove next that S does not have universal solutions.
Assume for the sake of contradiction that there is a universal solution T for S . Then, due
to the presence of
θ 1 and
θ 2 , there must be an infinite sequence of the form
G ( a , b ) , L ( b , v 1 ) , G ( v 1 , v 2 ) , L ( v 2 , v 3 ) , G ( v 3 , v 4 ) ,...
of facts in T . But since T is finite and satisfies
θ 1 and
θ 2 , it must be the case that:
v 2 i 1 = a or v 2 i = b ,forsome i
1, or
i < j ,or
v 2 i 1 = v 2 j 1 ,forsome1
v 2 i = v 2 j ,forsome1
i < j .
We show that each of these cases leads to a contradiction.
Assume first that v 2 i 1 = a ,forsome i
1. Consider the instance
T := { G ( a , b ) , L ( b , c 1 ) , G ( c 1 , c 2 ) , L ( c 2 , c 3 ) , G ( c 3 , c 4 ) ,...,
L ( c j 1 , c j ) , G ( c j , c j 1 )
}
,
where all the c 's are distinct constants not appearing in T and 2 i < j . Clearly T
S OL M ( S ), and since T is universal there is a homomorphism h from T into T .Butthen
it is easy to see that h ( v )= c for each 1
2 j , which implies that h ( v 2 i 1 )= c 2 i 1 .
However, this is a contradiction since h ( v 2 i 1 )= h ( a )= a and c 2 i 1
= a . The remaining
cases, that is, when either v 2 i = b ,forsome i
1, or v 2 i = v 2 j or v 2 i 1 = v 2 j 1 ,forsome
1
i < j , are similar and are left as an exercise to the reader.
The previous example immediately raises the question of whether the existence of uni-
versal solutions problem, as defined below, is a decidable problem.
Search WWH ::




Custom Search