XPath query evaluation: improving time and space efficiency
- 6 May 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Contemporary XPath query engines evaluate queries in time exponential in the sizes of input queries, a fact that has gone unnoticed for a long time. Recently, the first main-memory evaluation algorithm for XPath 1.0 with polynomial time combined complexity, i.e., which runs in polynomial time both with respect to the size of the data and the queries, has been published (cf. [G. Gottlob, et al., (2002)]. We present several important improvements and extensions of that work, including new XPath processing algorithms with improved time and space efficiency. Moreover, we define a very large and practically relevant fragment of XPath for which a further optimized form of query evaluation is possible. Apart from its immediate relevance for XPath query processing, our work also sheds new light at those features of XPath 1.0 which are most costly relative to their practical usefulness.Keywords
This publication has 7 references indexed in Scilit:
- Containment and equivalence for an XPath fragmentPublished by Association for Computing Machinery (ACM) ,2002
- Monadic queries over tree-structured dataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Holistic twig joinsPublished by Association for Computing Machinery (ACM) ,2002
- Efficient Algorithms for Processing XPath QueriesPublished by Elsevier ,2002
- Tree Pattern Aggregation for Scalable XML Data DisseminationPublished by Elsevier ,2002
- On the Equivalence of XML PatternsPublished by Springer Nature ,2000
- Typechecking for XML transformersPublished by Association for Computing Machinery (ACM) ,2000