Database Reference
In-Depth Information
17. Give an example of a query
Q
, which is a union of conjunctive queries with at most
one negated atom or inequality per disjunct, and a mapping
M
, such that there is no
D
ATALOG
program
Π
satisfying
certain
M
(
Q
,
S
)=
certain
M
(
Π
,
S
) for every source
instance
S
.
18. (Source:
Fagin et al.
(
2005a
))
Let
Σ
t
consists of a set of egds and a
weakly acyclic set of tgds, and let
Q
be a union of conjunctive queries with at most
one inequality or negated relational atom per disjunct. Prove that
CERTAIN
M
(
Q
) can
be solved in P
TIME
.
19. (Source:
Arenas et al.
(
2011c
))
In this exercise we analyze the combined complexity of computing certain answers
to conjunctive queries with inequalities, under mappings without target dependencies.
Define
CERTAIN
(CQ
=
) as the problemof, given a mapping
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) be a mapping such that
Σ
st
), without
target dependencies, a Boolean conjunctive query with inequalities
Q
, and a source
instance
S
, determine whether
certain
M
(
Q
,
S
)=
true
. Prove that
CERTAIN
(CQ
=
)
can be solved in
CO
N
EXPTIME
, and that it is
CO
N
EXPTIME
-hard even for conjunctive
queries with two inequalities.
20. Show that there exists a Boolean conjunctive query
Q
with a single inequality and a
LAV mapping
M
=(R
s
,
R
t
,
M
M
, such that
Q
is not FO-rewritable under
, both over the canonical
universal solution and the core.
21. (Source:
Arenas et al.
(
2013
))
Consider the following statement which essentially says that small neighborhoods are
preserved in data exchange. Given a mapping
M
without target constraints, for each
number
r
≥
0 there is a number
d
≥
0 so that the following holds:
if
S
is a source instance and
a
,
b
two tuples of elements of
S
such that
N
d
(
a
)=
N
d
(
b
),
then
N
d
(
a
) =
N
d
(
b
),when
T
is the canonical universal solution for
S
.
Show that this is true if
•
M
is a L
AV
mapping. Also give an example of a G
AV
mapping
which makes the statement above false.
22. (Source:
Arenas et al.
(
2013
))
Show that there exists a mapping
Σ
st
) and an FO query
Q
such that
Q
is FO-rewritable over the canonical universal solution under
M
=(R
s
,
R
t
,
M
, but it is not rewritable
over the core.
23. Prove
Proposition 8.23
.Thatis,let
t
con-
sists of a set of tgds and egds, and
S
a source instance. Then for every target instance
T
, the following are equivalent:
M
=(R
s
,
R
t
,
Σ
st
,
Σ
st
) be a mapping, where
Σ
S
OL
CWA
M
(
S
).
(ii)
T
is a CWA-presolution and a universal solution for
S
under
(i)
T
∈
.
24. Show that
Proposition 8.26
is witnessed by the following example. The source schema
contains a binary relation
E
, and the target schema contains two ternary relations
R
1
and
R
2
. The only st-tgd is
R
(
x
,
y
)
M
z
R
1
(
x
,
z
,
z
), and the only target tgd is
→∃
z
∃
