The complexity of XPath query evaluation and XML typing
- 1 March 2005
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 52 (2), 284-335
- https://doi.org/10.1145/1059513.1059520
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 NC 2 . 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.Keywords
This publication has 22 references indexed in Scilit:
- The complexity of acyclic conjunctive queriesJournal of the ACM, 2001
- Counting Quantifiers, Successor Relations, and Logarithmic SpaceJournal of Computer and System Sciences, 1997
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- On the relative complexity of some languages in NC1Information Processing Letters, 1989
- Problems complete for deterministic logarithmic spaceJournal of Algorithms, 1987
- Tree-size bounded alternationJournal of Computer and System Sciences, 1980
- On the Tape Complexity of Deterministic Context-Free LanguagesJournal of the ACM, 1978
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975
- Translations on a context free grammarInformation and Control, 1971
- Parenthesis GrammarsJournal of the ACM, 1967