Database Reference
In-Depth Information
defined as
f
(
a
1
)=
a
2
,
f
(
b
1
)=
b
2
and
⎧
⎨
f
(
c
i
)=
e
i
if 1
≤
i
≤
d
+1or2
d
+2
≤
i
≤
3
d
+2
f
(
c
i
)=
e
2
d
+1+
i
if
d
+2
≤
i
≤
2
d
+1
⎩
f
(
c
i
)=
e
i
−
2
d
−
1
if 3
d
+3
≤
i
≤
4
d
+2.
Clearly,
f
is a bijection from D
OM
(
S
1
) into D
OM
(
S
2
). Furthermore, a simple case anal-
ysis proves that for every
v
D
OM
(
S
1
) it is the case that
N
S
d
(
v
) =
N
S
d
(
f
(
v
)).This
implies that
S
1
d
S
2
. However, we prove below that
certain
M
(
Q
,
S
1
)=
true
while
certain
M
(
Q
,
S
2
)=
false
.
Let us consider first
S
1
.Let
T
1
be the canonical universal solution for
S
1
. Notice that
T
1
is
just a “copy” of
S
1
over the target; that is,
E
S
1
=
G
T
1
,
A
S
1
=
P
T
1
and
B
S
1
=
R
T
1
.Let
T
1
be an
arbitrary solution for
S
1
that does not satisfy the second disjunct
∈
∃
x
∃
y
∃
z
(
G
(
x
,
z
)
∧
G
(
z
,
y
)
∧
G
(
x
,
y
)) of
Q
. Then it must be the case that the transitive closure of
G
T
1
¬
is contained in
G
T
1
, and hence that
T
1
satisfies the first disjunct
∃
x
∃
y
(
P
(
x
)
∧
R
(
y
)
∧
G
(
x
,
y
)) of
Q
.This
R
T
1
and (
a
1
,
b
1
) belongs to the transitive closure of
G
T
1
.We
conclude that
certain
M
(
Q
,
S
1
)=
true
.
Let us consider now
S
2
. Again, the canonical universal solution
T
2
for
S
2
is a “copy”
of
S
2
over the target. Let
T
2
be the solution for
S
2
that is obtained from
T
2
by extending
the interpretation of
G
with every tuple that belongs to the transitive closure of
G
T
2
.Then
clearly
T
2
|
P
T
1
,
b
1
∈
is because
a
1
∈
G
(
x
,
y
)). Moreover, since
a
2
is the only element
in
T
2
that belongs to the interpretation of
P
,and
b
2
is the only element in
T
2
that belongs
to the interpretation of
R
,and
a
2
and
b
2
belong to different connected components of the
graph induced by
G
T
2
, it is the case that
T
2
|
=
∃
x
∃
y
∃
z
(
G
(
x
,
z
)
∧
G
(
z
,
y
)
∧¬
=
∃
x
∃
y
(
P
(
x
)
∧
R
(
y
)
∧
G
(
x
,
y
)). We conclude
that
T
2
|
=
Q
, and hence that
certain
M
(
Q
,
S
2
)=
false
.
With the help of the locality tool, we can now conclude the proof of
Proposition 7.12
,
since now we have techniques for showing non-rewritability of queries. It can be easily
shown that the query used in the proof of the previous proposition is domain-independent.
Thus, if
M
=(R
s
,
R
t
,
Σ
st
) and
ψ
nr
are, respectively, the mapping and FO-query used
in the proof of the previous proposition, we have that the following holds. The domain-
independent Boolean FO-query
ψ
nr
over R
t
is not FO-rewritable over the canonical uni-
versal solution, nor over the core, under
M
. (The reasons why we use the names
M
and
ψ
nr
will become clear below.)
Recall what we need to complete the proof of
Proposition 7.12
. Assume that
is a
domain-independent Boolean FO-query over schema R (disjoint from R
s
and R
t
), such
that for at least some instance
K
of R it is the case that
K
ϕ
.LetR
be a “copy” of
|
=
ϕ
R, that is in particular disjoint from R, R
s
and R
t
.Then
ϕ
→
ψ
nr
is not FO-rewritable
over the canonical universal solution, nor over the core, under
M
=(R
s
,
R
t
,
Σ
st
),where
ϕ
is the “translation” of
into R
and
is the relational mapping that is constructed
inside the proof of
Proposition 7.12
for R and
ϕ
M
M
.Thatis,(1)
ϕ
is obtained from
by
replacing each occurrence of the relation symbol
R
in R with its “copy”
R
in R
,(2)R
s
is
ϕ
