Database Reference
In-Depth Information
S
1
S
2
a
1
a
2
b
2
c
4
d
+2
c
1
e
2
d
+1
e
1
e
4
d
+2
e
2
d
+2
e
2
d
+3
e
2
d
e
2
e
4
d
+1
c
2
d
+2
c
2
d
+1
b
1
Figure 7.1 Instances
S
1
and
S
2
of
Proposition 7.16
.
R
,and
Σ
st
consists of the st-tgds:
E
(
x
,
y
)
→
G
(
x
,
y
)
A
(
x
)
P
(
x
)
B
(
x
)
→
R
(
x
)
.
→
Clearly,
M
is copying. The query
Q
over R
t
is defined as:
∃
x
∃
y
(
P
(
x
)
∧
R
(
y
)
∧
G
(
x
,
y
))
∨∃
x
∃
y
∃
z
(
G
(
x
,
z
)
∧
G
(
z
,
y
)
∧¬
G
(
x
,
y
))
.
This is the union of a conjunctive query and a conjunctive query with a single negated
relational atom. We prove next that
Q
is rewritable neither over the canonical universal
solution nor over the core under
.
Assume otherwise. We prove below that
Q
is not locally source-dependent under
M
,
which directly contradicts
Theorem 7.15
. Recall that for this we need to construct, for
every
d
M
≥
0, two source instances
S
1
and
S
2
such that
S
1
d
S
2
but
certain
M
(
Q
,
S
1
)
=
certain
M
(
Q
,
S
2
).
Define source instances
S
1
and
S
2
as shown in
Figure 7.1
:
E
S
1
is a cycle of length 4
d
+4
with elements
a
1
,
b
1
,
c
1
,
c
2
,...,
c
4
d
+2
,
E
S
2
is the disjoint union of two cycles of length 2
d
+
d
, the first one with elements
a
2
,
e
1
,...,
e
2
d
+1
,
and the second one with elements
b
2
,
e
2
d
+2
,...,
e
4
d
+2
,
A
S
1
=
,
A
S
2
=
,
B
S
1
=
and
B
S
2
=
{
a
1
}
{
a
2
}
{
b
1
}
{
b
2
}
.Let
f
:D
OM
(
S
1
)
→
D
OM
(
S
2
) be
