Efficient algorithms for processing XPath queries Reinhard Pichler, Christoph Koch, and Georg Gottlob   View Paper (PDF)   Return to June 2005, Volume 30, Issue 2 Abstract Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more efficiently, and propose main-memory algorithms for this problem with polynomial-time combined query evaluation complexity. Moreover, we show how the main ideas of our algorithm can be profitably integrated into existing XPath processors. Finally, we present two fragments of XPath for which linear-time query processing algorithms exist and another fragment with linear-space/quadratic-time query processing. ©2006 Association for Computing Machinery