Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Wednesday, July 1, 2020 - 3:58:56 PM
Last modification on : Sunday, June 26, 2022 - 12:16:39 PM
Long-term archiving on: : Wednesday, September 23, 2020 - 4:58:26 PM


Files produced by the author(s)




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⟩



Record views


Files downloads