Database Reference
In-Depth Information
16.2 Bibliographic comments
There are multiple references on XML; its theoretical foundations, including the model
based on unranked trees that we use here, are surveyed, for instance, in the papers by
Vianu
(
2001
);
Libkin
(
2006b
);
Neven
(
2002
);
Klarlund et al.
(
2003
), and
Gou and Chirkova
(
2007
). For basic information on tree automata, their decision problems and their complex-
ity, see the surveys by
Comon et al.
(
2007
)and
Schwentick
(
2007
). Testing emptiness for
UNFTAs with transitions represented by NFAs was shown to be polynomial by
Neven
(
2002
). L
OGSPACE
data complexity of testing if a given tree is accepted by an UNFTA
was given by
Gottlob et al.
(
2005
).
Tree patterns as they are presented here were introduced by
Arenas and Libkin
(
2008
),
and further extended with horizontal axes and data comparison by
Amano et al.
(
2009
).
The patterns were introduced originally to represent conjunctive queries (
Gottlob et al.
,
2006
;
Bj orklund et al.
,
2011
,
2008
). It should be noted however that to have the full ex-
pressive power of CQs one should allow DAG patterns, as it is done by
Bj orklund et al.
(
2008
).
David
(
2008
) considers a different kind of semantics based on injective homo-
morphisms. Expressing injective patterns as CQs requires inequality on node variables.
Satisfiability and evaluation of tree patterns is essentially folklore as it appeared in many
incarnations in the literature on tree patterns and XPath satisfiability (
Amer-Yahia et al.
,
2002
;
Benedikt et al.
,
2008
;
Bj orklund et al.
,
2008
;
Hidders
,
2003
). The presented proof is
by
Amano et al.
(
2009
).
Systematic investigation into XML data exchange was initiated by
Arenas and Libkin
(
2008
), who considered mappings based on restricted patterns disallowing horizontal nav-
igation and data comparisons. Those features were added by
Amano et al.
(
2009
). Nested-
relational DTDs were considered by
Abiteboul et al.
(
2006
), and by
Arenas and Libkin
(
2004
,
2008
). Empirical studies on their usage are reported by
Bex et al.
(
2004
).
The algorithms testing existence and materializing solutions were obtained by
Bojanczyk et al.
(
2011
).
The query answering problem for child-based XML mappings was already considered
by
Arenas and Libkin
(
2008
),whogaveadetailedcomplexity analysis. The influence
of sibling order and data comparisons was studied by
Amano et al.
(
2010
). Semantics
of certain answers for XML-to-XML queries was originally introduced by
David et al.
(
2010
). Other studies of certain answers and incompleteness in XML include the papers
by
Abiteboul et al.
(
2006
),
Barcel´oetal.
(
2010
), and
Gheerbrant et al.
(
2012
).
Algorithms for translating XML data exchange tasks into relational are given by
Chirkova et al.
(
2012
).
16.3 Exercises
1. Give an example of a DTD such that the smallest tree it admits is exponential.
2. Prove that the pattern satisfiability problem is NP-complete even for a fixed DTD.
Hint: Use equalities and constants in the pattern.
