Database Reference
In-Depth Information
4. (Source:
Arenas et al.
(
2011c
))
Prove the following stronger version of
Theorem 5.14
. There exists a L
AV
mapping
M
Σ
t
consists of a single egd, and the problem of check-
ing for the existence of solutions under
=(R
s
,
R
t
,
Σ
st
,
Σ
t
), such that
M
is P
TIME
-complete.
5. (Source:
Kolaitis et al.
(
2006
))
Prove that there exist
fixed
source and target schemas R
s
and R
t
such that
S
OL
E
XISTENCE
restricted to mappings of the form (R
s
,
R
t
,
Σ
st
,
Σ
t
),where
Σ
t
consists
only of egds, is E
XPTIME
-hard.
6. Complete the proof of
Theorem 6.5
by proving
Claim 6.6
.
7. Prove
Lemma 6.8
stated as follows. Let
S
1
d
,
a
−−→
=
fail
.
Assume that
S
3
is an instance that satisfies the dependency
d
and such that there is a
homomorphism from
S
1
into
S
3
. Then there exists a homomorphism from
S
2
into
S
3
.
8. Prove
Proposition 6.10
, i.e., show that if
S
2
be a chase step, where
S
2
Σ
t
) is a mapping such that
Σ
t
consists only of egds, then every source instance
S
has a unique canonical universal
solution
T
(up to a renaming of nulls) under
M
=(R
s
,
R
t
,
Σ
st
,
.
9. Show that in general cores cannot be constructed as canonical solutions of a modified
mapping. That is, give an example of a schema mapping
M
M
without target constraints
M
(also without target constraints) satisfying the con-
dition that for every source
S
, the canonical universal solution for
S
under
for which there is no mapping
M
is the
M
.
10. (Source:
Gottlob and Nash
(
2008
))
Prove
Theorem 6.18
stated as follows. Let
core for
S
under
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) be a fixed relational
t
consists of a set of egds and a weakly acyclic set of tgds. There
is a polynomial-time algorithm that, for every source instance
S
, checks whether a
solution for
S
exists, and if that is the case, computes the core of the universal solutions
for
S
.
11. Give an example of a relational algebra query that is not a union of conjunctive queries
such that its certain answers cannot be computed by naıve evaluation. In fact, even a
stronger statement is true: if
Q
is a Boolean relational calculus, i.e., FO, query, and its
certain answers can be computed by naıve evaluation, then
Q
is equivalent to a union
of conjunctive queries.
12. Show that certain answers for D
ATALOG
queries can be computed in exactly the same
was as for conjunctive queries. Namely, if
Q
is a D
ATALOG
query,
S
is a source in-
stance, and
T
is a universal solution for
S
,then
certain
M
(
Q
,
S
)=
Q
naıve
(
T
).
13. Complete the proof of
Theorem 7.4
by showing that
mapping, such that
Σ
ϕ
is
satisfiable iff
certain
M
(
Q
,
S
ϕ
)=
false
.
14. (Source:
M¸dry
(
2005
))
Show that there exists a Boolean conjunctive query
Q
with two inequalities and a LAV
mapping
, such that
CERTAIN
M
(
Q
) is
CO
NP-complete.
15. (Source:
Arenas et al.
(
2011c
))
In this exercise we prove that one can efficiently compute certain answers to conjunc-
tive queries with two inequalities, by assuming some syntactic restrictions on queries.
M
