Database Reference
In-Depth Information
R
1
(
x
,
u
,
y
)
R
2
(
x
,
u
,
v
). Then the 2
n
-tuple instance
S
producing exponen-
tially many maximal CWA-solutions is
∧
R
1
(
x
,
v
,
y
)
→
{
E
(
i
,
a
)
,
E
(
i
,
b
)
|
1
≤
i
≤
n
}
.
25. Prove
Proposition 8.29
, i.e., there exists a mapping
Σ
t
consists of a set of egds and a weakly acyclic set of tgds, and a Boolean FO query
Q
over R
t
, for which the following problem is undecidable: Given a source instance
S
,is
certain
CWA
M
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
), such that
(
Q
,
S
)=
true
?
26. Prove
Proposition 8.32
:Let
Σ
t
con-
sists of a set of egds and a weakly acyclic set of tgds, and assume that
Q
is a union
of conjunctive queries over R
t
. Then for every source instance
S
it is the case that
certain
CWA
M
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) be a mapping such that
(
Q
,
S
)=
certain
M
(
Q
,
S
).
27. (Source:
Hernich et al.
(
2011
))
Prove that there exists a mapping
Σ
t
consists of a set of
egds and a weakly acyclic set of tgds, and a Boolean conjunctive query with a single
inequality
Q
over R
t
, such that the following problem is
CO
NP-complete: Given a
source instance
S
,is
certain
CWA
M
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) such that
(
Q
,
S
)=
true
?
28. Show that for annotated mappings, we have
certain
(
M,
α)
(
Q
,
S
)=
Q
(
D
)
∈
Rep
(C
AN
S
OL
(
M,
α)
(
S
))
for arbitrary queries, and give a proof of
Proposition 8.34
.
29. (Source:
Libkin and Sirangelo
(
2011
))
Prove that there exists an annotated mapping (
|
D
)=1andanFO
query
Q
such that data complexity of finding
certain
(
M,
α)
(
Q
,
S
) is
CO
NEXPTIME-
complete.
30. (Source:
Arenas et al.
(
2011b
))
A usual assumption in data exchange is that the domain of a source instance consists
exclusively of constants. On the other hand, target instances are allowed to contain null
values, and, in fact, universal solutions require those null values in order to capture the
whole space of solutions. However, this naturally raises the question of what happens
if we need to further exchange those instances with null values? What is the right
semantics for data exchange in this case, and how is it possible to represent universal
instances for source instances with nulls?
Let
M
,
α
) with #
op
(
M
,
α
Σ
st
) be a mapping without target dependencies. Assume that
S
is
a source instance with nulls, i.e.,
S
is a naıve database over R
s
. Then a naıve database
T
over R
t
is a universal
representative
for
S
under
M
=(R
s
,
R
t
,
M
if
Rep
(
T
)=
S
∈
S
OL
M
(
S
)
.
Rep
(
S
)
Hence, analogously to the case when source instances contain no nulls, a universal
representative
T
defines the whole space of solutions for a source instance
S
.The
difference in this case is that
S
itself represents an infinite set of source instances
without nulls, and therefore
T
must represent the space of solutions for each one of
them.
Prove the following:
