Skip to Main content Skip to Navigation
Journal articles

The complexity of XPath query evaluation and XML typing

Georg Gottlob 1 Christoph Koch 1 Reinhard Pichler 1 Luc Segoufin 2
2 GEMO - Integration of data and knowledge distributed over the web
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTime in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTime-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LogCFL-complete and, therefore, in the highly parallelizable complexity class NC2. The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LogSpace and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LogSpace to LogCFL, depending on the typing scheme.
Document type :
Journal articles
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-02886548
Contributor : Luc Segoufin <>
Submitted on : Wednesday, July 1, 2020 - 3:58:56 PM
Last modification on : Saturday, May 1, 2021 - 3:39:17 AM
Long-term archiving on: : Wednesday, September 23, 2020 - 4:58:26 PM

File

gkps.pdf
Files produced by the author(s)

Identifiers

Citation

Georg Gottlob, Christoph Koch, Reinhard Pichler, Luc Segoufin. The complexity of XPath query evaluation and XML typing. Journal of the ACM (JACM), Association for Computing Machinery, 2005, 52 (2), pp.284-335. ⟨10.1145/1059513.1059520⟩. ⟨hal-02886548⟩

Share

Metrics

Record views

37

Files downloads

87