On the memory requirements of XPath evaluation over XML streams

ABSTRACT

The important challenge of evaluating XPath queries over XML streams has sparked much interest in the past two years, A number of algorithms have been proposed, supporting wider fragments of the query language, and exhibiting better performance and memory utilization. Nevertheless, all the algorithms known to date use a prohibitively large amount of memory for certain types of queries. A natural question then is whether this memory bottleneck is inherent or just an artifact of the proposed algorithms.In this paper we initiate the first systematic and theoretical study of lower bounds on the amount of memory required to evaluate XPath queries over XML streams. We present a general lower bound technique, which given a query, specifies the minimum amount of memory that any algorithm evaluating the query on a stream would need to incur. The lower bounds are stated in terms of new graph-theoretic properties of queries. The proof is based on tools from communication complexity.We then exploit insights learned from the lower bounds to obtain a new algorithm for XPath evaluation on streams. The algorithm uses space close to the optimum. Our algorithm deviates from the standard paradigm of using automata or transducers, thereby avoiding the need to store large transition tables.

REFERENCES

• 1: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 2: Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543642]
• 3: I. Avila-Campillo, T. J. Green, A. Gupta, M. Onizuka, D. Raven, and D. Suciu. XMLTK: An XML toolkit for scalable XML stream processing. In Proc. 1st Workshop on Programming Languages for XML (PLAN-X), 2002.
• 4: S. Boag, D. Chamberlin, M. F. Fernández, D. Florescu, J. Robie, and J. Siméosn. XQuery 1.0: An XML Query Language. W3C, http://www.w3.org/TR/xquery, 2003.
• 5: T. Bray, J. Paoli, and C. M. Sperbeg-McQueen. Extensible Markup Language (XML) 1.0. W3C, http://www.w3.org/TR/1998/REC-xml-19980210, 1998.
• 6: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 7: B. Choi, M. Mahoui, and D. Wood. On the optimality of holistic algorithms for twig queries. In Proc. 14th DEXA, pages 28--37, 2003.
• 8: B. Choi, M. Mahoui, and D. Wood. The optimality of holistic algorithms for XPath. http://www.cis.upenn.edu/~kkchoi/xpath.pdf, 2003.
• 9: J. Clark. XSL Transformations (XSLT) Version 1.0. W3C, http://www.w3.org/TR/xslt, 1999.
• 10: J. Clark and S. DeRose. XML Path Language (XPath), Version 1.0. W3C, http://www.w3.org/TR/xpath, 1999.
• 11: YFilter: Efficient and Scalable Filtering of XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.341, February 26-March 01, 2002
• 12: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 13: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 14: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 15: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 16: Z. Ives, A. Levy, and D. Weld. Efficient evaluation of regular path expressions on streaming XML data. Technical report, University of Washington, 2000.
• 17: Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005 [doi>10.1007/s00778-004-0123-7]
• 18: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 19: D. Olteanu, T. Kiesling, and F. Bry. An evaluation of regular path expressions with qualifiers against XML streams. In Proc. 19th ICDE, pages 702--704, 2003.
• 20: Feng Peng , Sudarshan S. Chawathe, XPath queries on streaming data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872810]
• 21: Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773170]
• 22: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 23: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]