Database Reference
In-Depth Information
Σ
st
) be a relational mapping. Assume that we want to show that an
m
-
ary query
Q
over R
t
(
m
Let
M
=(R
s
,
R
t
,
≥
0) is FO-rewritable neither over the core, nor over the canonical
universal solution, under
. According to
Theorem 7.13
, for that it is enough to prove
that
Q
is not locally source-dependent under
M
M
. And in order to do this it is sufficient
0 two source instances
S
1
and
S
2
and two
m
-tuples
a
and
b
of
constants in D
OM
(
S
1
) and D
OM
(
S
2
), respectively, such that:
to construct for every
d
≥
d
(
S
2
,
b
),and
•
(
S
1
,
a
)
a
∈
certain
M
(
Q
,
S
1
) but
b
∈
certain
M
(
Q
,
S
2
).
•
Even simpler, in the case of Boolean queries
Q
, we know that
Q
is
not
FO-rewritable
(over the core or the canonical universal solution) if, for every
d
≥
0, we can find two
instances
S
1
,
S
2
such that:
•
S
1
d
S
2
,and
•
certain
M
(
Q
,
S
1
)
=
certain
M
(
Q
,
S
2
).
We now apply this methodology to prove non-rewritability results for FO-queries under
extremely simple relational mappings. We call a relational mapping
M
=(R
s
,
R
t
,
Σ
st
)
copying
if R
s
and R
t
are two copies of the same schema; that is, R
s
=
{
R
1
,...,
R
n
}
, R
t
=
{
R
1
,...,
R
n
}
,and
R
i
and
R
i
have the same arity, and
Σ
st
=
{
R
i
(
x
)
→
R
i
(
x
)
|
1
≤
i
≤
n
}.
Note that a copying mapping is both L
AV
and G
AV
. Informally, these mappings simply
“copy” the source data into the target.
We now look at the existence of FO-rewritings for the class of unions of conjunctive
queries with at most one negated relational atom per disjunct. We know, from
Theorem
7.8
, that each one of these queries admits a rewriting over an arbitrary universal solution in
D
ATALOG
C(
=)
. Some of these queries, of course, admit FO-rewritings (e.g., if no negated
atom are present). But this is not a general phenomenon, even under copying mappings.
Proposition 7.16
There exists a copying relational mapping
M
=(R
s
,
R
t
,
Σ
st
)
and a
Boolean
FO
query Q over
R
t
such that:
1. Q is the union of a conjunctive query and a conjunctive query with a single negated
atom; and
2. Q is not rewritable over the canonical universal solution, nor over the core, under
M
.
Proof
We use exactly the same mapping and query as in the proof of
Theorem 7.5
.That
is,
Σ
st
) is the relational mapping such that R
s
consists of a binary relation
E
and unary relations
A
and
B
, R
t
consists of a binary relation
G
and unary relations
P
and
M
=(R
s
,
R
t
,
