Efficient algorithms for evaluating xpath over streams

ABSTRACT

In this paper we address the problem of evaluating XPath queries over streaming XML data. We consider a practical XPath fragment called Univariate XPath, which includes the commonly used '/' and '//' axes and allows *-node tests and arbitrarily nested predicates. It is well known that this XPath fragment can be efficiently evaluated in O(|D||Q|) time in the non-streaming environment, where |D| is the document size and |Q| is the query size. However, this is not necessarily true in the streaming environment, since streaming algorithms have to satisfy stricter requirement than non-streaming algorithms, in that all data must be read sequentially in one pass. Therefore, it is not surprising that state-of-the-art stream-querying algorithms have higher time complexity than O(|D||Q|).

In this paper we revisit the XPath stream-querying problem, and show that Univariate XPath can be efficiently evaluated in O|D||Q|) time in the streaming environment. Specifically, we propose two O(|D||Q|)-time stream-querying algorithms, LQ and EQ, which are based on the lazy strategy and on the eager strategy, respectively. To the best of our knowledge, LQ and EQ are the first XPath stream-querying algorithms that achieve O(|D||Q|) time performance. Further, our algorithms achieve O(|D||Q|) time performance without trading off space performance. Instead, they have better buffering-space performance than state-of-the-art stream-querying algorithms. In particular, EQ achieves optimal buffering-space performance. Our experimental results show that our algorithms have not only good theoretical complexity but also considerable practical performance advantages over existing algorithms.

REFERENCES

• 1: S. Al--Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Srivastava, and Y. Wu. Structural joins: a primitive for efficient XML query pattern matching. ICDE Conference, 2002.
• 2: Apache. Apache Xerces2-Java XML Parser. http://xerces.apache.org/xerces2-j/.
• 3: Z. Bar-Yossef, M. Fontoura, and V. Josifovski. On the memory requirements of XPath evaluation over XML streams. Proceedings of PODS, 2004.
• 4: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, Buffering in query evaluation over XML streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065195]
• 5: C. Barton, P. Charles, D. Goyal, M. Raghavachari, M. Fontoura, and V. Josifovski. Streaming XPath processing with forward and backward axes. ICDE Conference, 2003.
• 6: S. Boag, D. Chamberlin, M. F. Ferandez, D. Florescu, J. Robie, and J. Simeon. XQuery 1.0: An XML Query Language. W3C, http://www.w3.org/TR/xquery/, 2003.
• 7: D. Brownell and D. Megginson. SAX: Simple API for XML. SAX Project Organization, http://www.saxproject.org/.
• 8: N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: optimal XML pattern matching. SIGMOD, 2002.
• 9: C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient filtering of XML documents with XPat expressions. ICDE Conference, 2002.
• 10: Y. Chen, S. B. Davidson, and Y. Zheng. An efficient XPath query processor for XML streams. ICDE, 2006.
• 11: B. Choi. What are real DTDs like? WebDB Workshop, 2002.
• 12: J. Clark. XML Transformations (XSLT) Version 1.0. W3C, http://www.w3.org/TR/xslt/, 1999.
• 13: J. Clark and S. DeRose. XML Path Language (XPath) Version 1.0. W3C, http://www.w3.org/TR/xpath/, 1999.
• 14: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 15: A. L. Diaz and D. Lovell. IBM's XML generator. http://www.alphaworks.ibm.com/tech/xmlgenerator.
• 16: M. Fernandez and et al. Galax: an implementation of XQuery. http://www.galaxquery.org/.
• 17: D. Florescu, C. Hillery, D. Kossmann, P. Lucas, F. Riccardi, T. Westmann, M. J. Carey, A. Sundararajan,and G. Agrawal. The BEA/XQRL streaming XQuery processor. VLDB Conference, 2003.
• 18: G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. VLDB Conference, 2002.
• 19: 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]
• 20: Todd J. Green , Ashish Gupta , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML streams with deterministic automata and stream indexes, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042051]
• 21: 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]
• 22: 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]
• 23: M. Kay. Saxon: the XSLT and XQuery processor. http://saxon.sourceforge.net/.
• 24: C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier. Schema-based scheduling of event processors and buffer minimization for queries on structured data streams. VLDB Conference, 2004.
• 25: B. Ludascher, P. Mukhopadhyay, and Y. Papakonstantinou. A transducer-based XML query processor. VLDB, 2002.
• 26: F. Peng and S. S. Chawathe. XSQ: A streaming XPath engine. http://www.cs.umd.edu/projects/xsq/.
• 27: Feng Peng , Sudarshan S. Chawathe, XSQ: A streaming XPath engine, ACM Transactions on Database Systems (TODS), v.30 n.2, p.577-623, June 2005 [doi>10.1145/1071610.1071617]
• 28: A. Schmidt and et al. XMark: an XML benchmark project. http://monetdb.cwi.nl/xml/.
• 29: 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]
• 30: D. Suciu. XML data repository. http://www.cs.washington.edu/research/xmldatasets/.
• 31: W3C. Section 1.2.2, XML query use cases. http://www.w3.org/TR/xquery-use-cases/, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory

Keywords:
XML, XPath, query processing, streams