[Back]

G. Gottlob, C. Koch, R. Pichler:
"The Complexity of XPath Query Evaluation";
Talk: ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, San Diego, USA (invited); 06-09-2003 - 06-11-2003; in: "Proceedings of the 22^nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems", F. Neven (ed.); ACM Press, (2003), ISBN: 1-58113-670-6; 179 - 190.

In this paper, we study the precise complexity of XPath 1.0 query processing. Evan though heavily used by it´s incorporation into a variety of XML-related standards, the precise cost of evaluating an XPath query is not yet well-understood. The first polynomial-time algorithm for XPath processing (with respect to combined complexity) was proposed only recently, and even to this day all major XPath engines take time exponential in the size of the input queries. From the standpoint of theory, the precise complextiy of XPath query evaluation is open, and it is thus unknown whether the query evaluationproblem can be parallelized.
In this work, we show that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, but that the combined complexity isPTIME-hard. Subsequently, we study the sources of this hardness and identify a large and pratically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therfore, in the highly parallelizable complexity class NC₂.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404375