Database Reference
In-Depth Information
8. (Source:
Amano et al.
(
2009
))
Show that C
ONS
(
, ,
=) is N
EXPTIME
-hard over nested-relational DTDs. Hint: Use
the proof of hardness of solution existence and enforce that all data values in the
source tree are different.
9. (Source:
Amano et al.
(
2009
))
Show that A
B
C
ONS
◦
(
↓
p
2
-hard. Hint: Recall the reduction used in the proof of
↓
,
) is
Π
Theorem 11.7
.
10. (Source:
Bojanczyk et al.
(
2011
))
Give a formal definition of the class
Π
2
E
XP
in terms of Turing machines and prove
that 2
n
-
UNIVERSALITY
is hard for this class (see page
242
).
11. (Source:
Bojanczyk et al.
(
2011
))
Modifying the reduction from the proof of
Theorem 18.9
, show that A
B
C
ONS
is
Π
2
E
XP
-hard for SM
nr
(
) andSM
nr
(
,
=),andN
EXPTIME
-hard for SM
nr
(
↓
, ,
∼
↓
, ,
→
↓
, ,
=).
12. (Source:
Fagin et al.
(
2005b
))
Let
M
12
and
M
23
be the mappings in
Example 19.2
,and
σ
13
be the following FO
dependency:
∀
n
∃
y
∀
c
(
Takes
(
n
,
c
)
→
Enrolled
(
y
,
c
))
.
Show that
σ
13
defines the composition of
M
12
and
M
23
.
13. (Source:
Fagin et al.
(
2005b
))
Let
M
12
=(R
1
,
R
2
,
Σ
12
) and
M
23
=(R
2
,
R
3
,
Σ
23
),where
Σ
12
and
Σ
23
are finite sets
of st-tgds. Prove that C
OMPOSITION
(
M
12
,
M
23
) is in NP.
14. (Source:
Fagin et al.
(
2005b
))
Show that for each SO tgd
from a schema R
s
to a schema R
t
there exists a poly-
nomial
p
, with the following property. Assume that
S
is an instance of R
s
,
T
is an
instance of R
t
,
U
is a set such that D
OM
(
S
)
σ
∪
D
OM
(
T
)
⊆
U
⊆
C
ONST
∪
V
AR
and
|
U
|≥
p
(
S
+
T
).Then(
S
,
T
)
|
=
σ
if and only if (
S
,
T
) satisfies
σ
with witnessing
valuations whose domain and range is
U
.
15. (Source:
Fagin et al.
(
2005b
))
Let
M
23
be the mappings in
Example 19.2
. Use the composition algorithm
for SO tgds to calculate an SO tgd
M
12
and
σ
13
defining the composition of
M
12
with
M
23
.
16. (Source:
Arenas et al.
(
2009a
))
An SO tgd
is said to be
equality-free
if it does not contain any atomic formula of the
form
t
1
=
t
2
,where
t
1
and
t
2
are terms built from some variables and function symbols.
Show that if a mapping
σ
M
M
is defined by an equality-free SO tgd, then
is closed
under target homomorphisms.
17. (Source:
Fagin et al.
(
2005b
))
Here you will show that equalities in SO tgds are strictly necessary for the purposes
of composition. More precisely, let R
1
be a schema consisting of a unary predicate
Employee
, R
2
a schema consisting of a binary predicate
Manager
and R
3
a schema
