Published Articles >> Table of Contents >> Abstract

19th International Conference on Data Engineering (ICDE'03)   p. 379
XPath Query Evaluation: Improving Time and Space Efficiency
Georg Gottlob, Technische Universität Wien, Vienna, Austria
Christoph Koch, Technische Universität Wien, Vienna, Austria
Reinhard Pichler, Technische Universität Wien, Vienna, Austria

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2003.1260807
Send link to a friend

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. [11]). In this paper, 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.
Back to Top Additional Information
Citation:  Georg Gottlob, Christoph Koch, Reinhard Pichler, "XPath Query Evaluation: Improving Time and Space Efficiency," icde, p. 379,  19th International Conference on Data Engineering (ICDE'03),  2003