Database Reference
In-Depth Information
the disjoint union of R and R
s
,(3)R
t
is the disjoint union of R
and R
t
,and(4)
Σ
st
consists
Σ
st
plus a set of copying st-tgds from R into R
.
of the st-tgds in
ϕ
→
ψ
nr
is not FO-rewritable over the canonical universal solution, nor
over the core, we need to show, of course, that it is not locally source-dependent. In the
present case, for each
d
To prove that
0 we construct source instances
S
1
and
S
2
such that:
≥
The restriction of both
S
1
and
S
2
to schema R corresponds to the instance
K
,and
•
the restriction of
S
i
,for
i
= 1or
i
= 2, to R
s
corresponds to the instance
S
i
used in the
proof of
Proposition 7.16
.
•
It is easy to see that
S
1
d
S
2
. This is because
S
i
,for
i
= 1or
i
= 2, essentially consists
of the disjoint union of
S
i
and
K
, and we know from the proof of
Proposition 7.16
that
S
1
d
S
2
. We show below that
certain
M
(
ϕ
→
ψ
nr
,
S
1
)
ϕ
→
ψ
nr
,
S
2
).
=
certain
M
(
Let us consider first
S
1
. Consider an arbitrary solution
T
1
for
S
1
under
M
. Then the
restriction
T
1
of
T
1
to the relation symbols in R
t
is a solution for
S
1
under
M
.Butthen,
since
certain
M
(
ψ
nr
,
S
1
)=
true
, it must be the case that
T
1
|
=
ψ
nr
.Since
ψ
nr
is domain-
independent, it follows that
T
1
|
ϕ
→
ψ
nr
,
S
1
)=
true
.
=
ψ
nr
. We conclude that
certain
M
(
Let us consider now
S
2
.Since
certain
M
(
ψ
nr
,
S
2
)=
false
, there exists a solution
T
2
for
ψ
nr
. Consider now the instance
T
2
of schema R
t
that consists
of the disjoint union of
T
2
(over schema R
t
) and a “copy” of
K
(over schema R
). Clearly,
T
2
is a solution for
S
2
under
M
such that
T
2
|
S
2
under
=
. The restriction of
T
2
to the relation symbols in R
t
(which
M
ψ
nr
is domain-independent, we also have
T
2
|
is
T
2
) does not satisfy
ψ
nr
. But since
=
ψ
nr
.
Furthermore, the restriction of
T
2
to R is a “copy” of
K
, which satisfies
ϕ
.Since
ϕ
is
a domain-independent query over R, it must be the case that
T
2
|
=
ϕ
. We conclude that
T
2
|
ϕ
→
ψ
nr
,
S
2
)=
false
. This completes the proof
of
Proposition 7.12
from the previous section.
=
ϕ
∧¬
ψ
nr
, and hence that
certain
M
(
