An efficient single-pass query evaluator for XML data streams

ABSTRACT

Data streams might be preferable to data stored in memory in contexts where the data is too large or volatile, or a standard approach to data processing based on data parsing and/or storing is too time or space consuming. Emerging applications such as publish-subscribe systems, data monitoring in sensor networks [6], financial and traffic monitoring, and routing of MPEG-7 [7] call for querying data streams. In many such applications, XML streams are arguably more appropriate than flat data streams, for XML data is record-like, though not precluding multiple occurrences of fields with the same name. Evaluating selection queries against XML streams is especially challenging because XML data is structured (like records) and might have unbounded size.This paper proposes an efficient single-pass evaluator of XPath queries against XML data streams unbounded (possibly infinite) in size. The evaluator is based on networks of independent deterministic pushdown transducers and it is especially suitable for implementation on devices with low-memory and simple logic as used, e.g., in mobile computing.

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: C.-Y. Chan , P. Felber , M. Garofalakis , R. Rastogi, Efficient filtering of XML documents with XPath expressions, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.354-379, December 2002 [doi>10.1007/s00778-002-0077-6]
• 3: Tim Furche, Optimizing multiple queries against XML streams, Diploma thesis, Univ. of Munich, 2003.
• 4: Georg Gottlob , Christoph Koch , Reinhard Pichler, XPath processing in a nutshell, ACM SIGMOD Record, v.32 n.1, p.12-19, March 2003 [doi>10.1145/640990.640992]
• 5: Bertram Ludäscher, Pratik Mukhopadhyay, and Yannis Papakonstantinou, A transducer-based XML query processor, Proc. of VLDB, 2002.
• 6: Fjording the Stream: An Architecture for Queries Over Streaming Sensor Data, Proceedings of the 18th International Conference on Data Engineering, p.555, February 26-March 01, 2002
• 7: José M. Martínez, MPEG-7 overview, Tech. Report N4980, ISO/IEC JTC1/SC29/WG11, 2002.
• 8: Gerome Miklau, XMLData repository, Univ. of Washington, 2003.
• 9: Dan Olteanu, Tim Furche, and François Bry, Evaluating complex queries against XML streams with polynomial combined complexity, Tech. Report PMS-FB-2003-15, Univ. of Munich, 2003, http://www.pms.informatik.unimuenchen.de/publikationen.
• 10: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 11: 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]
• 12: Dominik Schwald, Approximate streamed evaluation of XPath under memory constraints, Project thesis, Univ. of Munich, 2003.

INDEX TERMS

Keywords:
Single-Pass Query Evaluation, XML streams, XPath