[FIG(quote)[ [FIGCAPTION[ [1] [CITE[The Complexity of XPath Query Evaluation]] ([TIME[2011-07-09 16:57:20 +09:00]]) ]FIGCAPTION] > In this paper, we study the precise complexity of XPath > 1.0 query processing. Even though heavily used by its incorporation > into a variety of XML-related standards, the > precise cost of evaluating an XPath query is not yet wellunderstood. > 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 complexity of > XPath query evaluation is open, and it is thus unknown > whether the query evaluation problem 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 > 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. ]FIG]