Database Reference
In-Depth Information
Claim 6.6
can be easily proved by induction on
n
, and is left as an exercise for the reader.
Using
Claim 6.6
and
Theorem 6.7
in
Section 6.3
(showing that the result of a successful
chase sequence for a source instance is always a universal solution) we conclude that if
A
halts on the empty input then
S
(
A
) has a universal solution under
M
. Indeed, let
c
be a halting computation of
A
.Then
Claim 6.6
implies that
T
(
A
,
c
) is the result of a
finite chase sequence for
S
(
A
) under
M
. By inspecting the tgds in
Σ
t
, it is easy to see
that
T
(
,
c
) violates none of them, and hence this chase sequence is successful. Using
Theorem 6.7
we conclude that
T
(
A ,
c
) is a universal solution for
S
(
A
) under
M
.
We now prove the opposite direction; that is, if
S
(
A
A
) has a universal solution under
M
halts on the empty input. Assume, for the sake of contradiction, that
T
is a
universal solution for
S
(
A
) under
M
,but
A
does not halt on the empty input. Let
n
be
the largest integer such that there are pairwise distinct values
u
0
,
u
1
,...,
u
n
that satisfy the
following:
u
0
= 0and(
u
i
,
u
i
+1
)
,then
A
Steps
T
, for each 0
∈
≤
i
≤
n
−
1. Since
A
does not halt
on the empty input there is a computation
c
=(
c
0
,
c
1
,...,
c
n
) of
A
such that
c
n
is not final.
From
Claim 6.6
, there is a finite chase sequence for
S
(
,
c
).
It can be proved (by repeatedly applying
Lemma 6.8
in
Section 6.3
) that there is a homo-
morphism
h
:
T
(
A
) under
M
with result
T
(
A
→
T
. Recall that
Steps
T
(
A ,
c
)
=
A
,
c
)
{
(
u
j
,
u
j
+1
)
|
0
≤
j
≤
n
}
.Butthen
Steps
T
, for each 0
it must be the case that (
h
(
u
j
)
,
h
(
u
j
+1
))
∈
≤
j
≤
n
. Notice that by the
choice of
n
, it must be the case that
h
(
u
k
)=
h
(
u
),forsome0
≤
k
<
≤
n
+1.
,
c
) to a target instance
T
by adding the following tuples:
We now extend
T
(
A
•
(
u
n
+1
,
u
n
+1
) to
Steps
.
•
(
u
n
+1
,
v
p
,
v
p
) to
Positions
, for each 0
≤
p
,
p
≤
n
+2.
•
(
u
n
+1
,
q
,
v
p
) to
Config
, for each 0
≤
p
≤
n
+2and
q
∈
Q
.
•
≤
p
≤
n
+2and
a
∈
A
.
•
(
u
n
+1
,
v
p
,
v
p
) to
LeftCopy
and
RightCopy
, for each 0
≤
p
≤
n
+2.
•
(
u
n
+1
,
a
,
v
p
) to
Symbols
, for each 0
(
u
n
+1
,
v
p
) to
End
, for each 0
≤
p
≤
n
+2.
Σ
t
,that
T
violates none of them, and hence
T
is a solution for
S
(
A
) under
M
.Since
T
is a universal solution for
S
(
A
) under
M
,
there is a homomorphism
h
:
T
→
T
.
We next prove the following property:
h
(
h
(
u
j
)) =
u
j
for each 0
It is not hard to see, by inspecting the tgds in
n
+ 1. The
proof is by induction on
j
.For
j
= 0 this is trivial, since
u
0
is the constant 0 and ho-
momorphisms preserve constants. Assuming the statement holds for 0
,...,
j
, we prove
it for
j
+ 1. Since
h
:
T
(
≤
j
≤
Steps
T
(
A ,
c
)
,
A
,
c
)
→
T
is a homomorphism and (
u
j
,
u
j
+1
)
∈
Steps
T
.Since
h
:
T
→
T
is also a homomorphism, we get
we have (
h
(
u
j
)
,
h
(
u
j
+1
))
∈
h
(
h
(
u
j
))
,
h
(
h
(
u
j
+1
))
∈
Steps
T
. By the induction hypothesis, we know
h
(
h
(
u
j
)) =
u
j
.
Furthermore, the only tuple of the form (
u
j
,
) in
Steps
T
is (
u
j
,
u
j
+1
).Thisimpliesthat
h
(
h
(
u
j
+1
)) =
u
j
+1
, which finishes the inductive proof.
Recall that
u
0
,
u
1
,...,
u
n
+1
are pairwise distinct elements. Thus, since
h
(
h
(
u
j
)) =
u
j
,
for each 0
·
n
+1, it must be the case that
h
(
u
0
)
,
h
(
u
1
)
,...,
h
(
u
n
+1
) are also pairwise
distinct elements. But this is a contradiction since we stated above that for some 1
≤
j
≤
≤
k
<
