Database Reference
In-Depth Information
that every mapping specified by these dependencies has a maximum extended recovery
even if source instances are allowed to contain nulls. The characterization of the notion of
maximum extended recovery in terms of the notion of maximum recovery was given by
Arenas et al.
(
2009a
).
Other schema mapping operators such as extract, merge, match, union and intersection
have been studied by
Melnik
(
2004
);
Bernstein and Melnik
(
2007
);
Arenas et al.
(
2010a
);
and
Perez et al.
(
2012
).
The problem of characterizing the class of mappings specified by st-tgds in terms of
their structural properties was studied by
ten Cate and Kolaitis
(
2009
). They also provided
structural characterizations of the classes of mappings specified by LAV st-tgds and GAV
st-gds, and used them to establish NP-completeness of LAV-E
QUIVALENCE
and GAV-
E
QUIVALENCE
. The problems of simplifying and refining schema mappings were consid-
ered by
Fagin et al.
(
2008a
);
Calvanese et al.
(
2011
);
Alexe et al.
(
2011
); and
Pichler et al.
(
2011
).
22.3 Exercises
1. Show that the exponential blow-up in the translation of patterns to UFTA(DFA) in
Lemma 18.2
cannot be avoided.
2. (Source:
Amano et al.
(
2009
))
Assume that schemas are given by disjunction-free DTDs (productions use concate-
nation, ?,
∗
, +, but no disjunction). Give P
TIME
algorithms for: (a) satisfiability of
⇓
-patterns; and (b) C
ONS
(
⇓
). Hint for consistency: There exists an easiest source
tree.
3. (Source:
Amano et al.
(
2009
))
Show that C
ONS
(
) is P
SPACE
-hard. Hint: Give a reduction from QSAT. Use
t
i
,
f
i
→
t
i
+1
f
i
+1
to encode universally quantified variables, and
t
i
,
f
i
⇓
→
t
i
+1
?
f
i
+1
?
for exis-
tentially quantified variables.
4. (Source:
Amano et al.
(
2009
))
Show that C
ONS
(
↓,→,→
+
,
=) is undecidable. Hint: Rotate the encoding used in
The-
orem 18.4
by 90
◦
.
5. (Source:
Amano et al.
(
2009
))
Modify the reduction above to show that C
ONS
(
,
=) is undecidable. Hint: A finite
sequence contains no repetitions iff every occurrence of an item has the same same
successor, different from itself.
6. (Source:
Amano et al.
(
2009
))
Show that C
ONS
(
↓
,
→
+
,
↓
,
↓
=) and C
ONS
(
↓
,
→
,
=) are undecidable. Hint: In the reduction
above replace = on the target side with
= on the source side and vice versa.
7. (Source:
Amano et al.
(
2009
))
Show that C
ONS
(
) is undecidable over nested-relational DTDs. Hint: Modify
again the two-register machine reduction. Encode the configurations entirely in data
values, keeping separately a list of values encoding states of the machine.
↓
,
→
,
∼
