Database Reference
In-Depth Information
p
2
-hard. Hint: Re-
3. Show that
the problem XML-SM-M
EMBERSHIP
is
Π
duce the validity of
Π
2
quantified Boolean formulae,
i.e.,
formulae of
the
form
∀
x
1
...
∀
x
n
∃
y
1
...
∃
y
m
ϕ
where
ϕ
is a Boolean formula over variables
x
1
,...,
x
n
,
y
1
,...,
y
m
in conjunctive normal form and quantification ranges over
true
and
false
.
4. Prove that for a given tree
T
and UNFTA
A
it can be decided in P
TIME
if
A
accepts
is UFTA(DFA), it can be done in L
OGSPACE
.
5. Prove that for a given UNFTA
T
.If
A
A
it can be decided in P
TIME
if there exists a tree
.
6. Let
D
be a nested-relational DTD. Show that for each XML tree
T
agreeing with a
D
-kind
K
there exists exactly one witnessing substitution
T
u
(see page
164
).
7. Give an example of a tree automaton
accepted by
A
L
(
K
) such that
there is more than one witnessing substitution. Can this automaton be deterministic?
8. (Source:
Bojanczyk et al.
(
2011
))
Show that for a fixed mapping
A
,an
A
-kind
K
and a tree
T
∈
M
, solution existence can be checked in L
OGSPACE
.
9. (Source:
Bojanczyk et al.
(
2011
))
A schema
has height at most
k
. Show that
for mappings with the target schema of fixed depth, solution building can be done in
E
XPTIME
, and solution existence can be tested in
S
has depth
k
if each tree conforming to
S
Σ
3
P.
10. (Source:
Bojanczyk et al.
(
2011
))
Show that the S
OL
E
XISTENCE
problem is N
EXPTIME
-hard also for mappings that do
not use = on the source side, and for mappings that use
+
but do not use . Hint:
↓
Modify the reduction in proof of
Theorem 12.28
.
11. (Source:
Amano et al.
(
2010
))
Give an example of a mapping
SM
nr
(
M ∈
↓
,
→
,
=) and a query
Q
∈
CTQ(
↓
,
=) such
that
CERTAIN
M
(
Q
) is
CO
NP-complete.
12. Generalize the P
TIME
-algorithm for certain answers so that it handles
(a) mappings in SM
nr
(
+
,
=) and queries in CTQ(
↓
,
→
↓
,
=);
(b) mappings in SM
nr
(
↓
,
=
,
=) and queries in CTQ(
↓
,
=).
13. (Source:
Amano et al.
(
2010
))
A mapping
M
is called
→
-specified
if in each target pattern,
the order of the sub-
patterns is completely specified by means of
→
;e.g.,
r
[
a
→
b
→
b
] is allowed, and
-specified mapping from SM
nr
(
r
[
a
,
b
→
b
] is not. Find a
→
↓
,
→
), and a query from
CTQ(
,
=) such that
CERTAIN
M
(
Q
) is
CO
NP-complete. Formulate and prove a
similar result for
↓
,
→
+
.
14. (Source:
David et al.
(
2010
))
Find a family
→
{T
n
}
n
>
0
of sets of XML trees such that
|T
n
|
=
n
, each tree in
T
n
has
T
n
hassizeatleast2
n
.
size
O
(
n
), but each max-description of
15. (Source:
David et al.
(
2010
))
Show that there exist a family of trees
{
S
n
}
n
>
0
with
|
S
n
|
=
O
(
n
), a mapping
M ∈
SM
nr
(
,
),anda
TQL
query
Q
such that
CERTAIN
M
(
Q
,
S
n
) has the size at least 2
n
.
↓
