Efficiently loading and processing XML streams

ABSTRACT

XML stream applications bring the novel challenge of efficiently processing queries on sequentially accessible token-based input streams. Our Raindrop project is the first to accommodate token-based stream processing using an algebraic framework where both tokens and tuples are modeled in a uniform manner. In this paper, we illustrate how the stream loading model of our system on the fly conducts XML navigation over the input stream via concurrently constructing a minimized light-weight XML tree representation, which is called navigation-free data instance. These captured XML fragments are minimized in terms of buffer consumption. Based on the compact representation of the navigation-free data instances, we propose techniques for subsequent algebraic query evaluation, in particular, effective strategies for supporting multi-mode query operators and alternative data output semantics. The proposed stream loading model requires a much smaller buffer footprint, compared to alternative solutions in the literature such as Y-Filter. And the proposed algebra-based evaluation techniques offer effective ways to handle data recursion over XML streams, i.e., avoiding overhead from the structural join operators. Our stream loading and query evaluation techniques have been implemented as part of the Raindrop system. Experimental results based on the Raindrop system are also reported in this paper.

REFERENCES

• 1: Amélie Marian , Jérôme Siméon, Projecting XML documents, Proceedings of the 29th international conference on Very large data bases, p.213-224, September 09-12, 2003, Berlin, Germany
• 2: Yanlei Diao , Michael Franklin, Query processing for high-volume XML message brokering, Proceedings of the 29th international conference on Very large data bases, p.261-272, September 09-12, 2003, Berlin, Germany
• 3: M. Schemidt, S. Scherzinger and C. Koch. Combined Static and Dynamic Analysis for Effective Buffer Minimization in Streaming XQuery Evaluation. In Proceedings of ICDE, pages 236--245, 2007.
• 4: 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]
• 5: Zachary G. Ives , A. Y. Halevy , D. S. Weld, An XML query engine for network-bound data, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.380-402, December 2002 [doi>10.1007/s00778-002-0078-5]
• 6: Hong Su , Elke A. Rundensteiner , Murali Mani, Automaton meets algebra: a hybrid paradigm for XML stream processing, Data & Knowledge Engineering, v.59 n.3, p.576-602, December 2006 [doi>10.1016/j.datak.2005.10.008]
• 7: Bertram Ludäscher , Pratik Mukhopadhyay , Yannis Papakonstantinou, A transducer-based XML query processor, Proceedings of the 28th international conference on Very Large Data Bases, p.227-238, August 20-23, 2002, Hong Kong, China
• 8: 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]
• 9: Hong Su , Jinhui Jian , Elke A. Rundensteiner, Raindrop: a uniform and layered algebraic framework for XQueries on XML streams, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956917]
• 10: Xin Zhang , Katica Dimitrova , Ling Wang , Maged El Sayed , Brian Murphy , Bradford Pielech , Mukesh Mulchandani , Luping Ding , Elke A. Rundensteiner, Rainbow: multi-XQuery optimization using materialized XML views, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872861]
• 11: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 12: Ming Li , Murali Mani , Elke A. Rundensteiner, Semantic query optimization for processing XML streams with minimized memory footprint, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France [doi>10.1145/1416691.1416698]
• 13: N. Bruno and L. Gravano. Navigation- vs. Index-Based XML Multi-Query Processing. In Proceedings of ICDE, pages 139--150, 2003.
• 14: Z. Guo, Z. Xu, S. Zhou, A. Zhou and M. Li. Index Selection for Efficient XML Path Expression. In Proceedings of ER Workshops, page 261--272, 2003.
• 15: J. Jian, H. Su and E. A. Rundensteiner. Automaton Meets Query Algebra: Towards a Unified Model for XQuery Evaluation over XML Data Streams. In Proceedings of ER, pages 172--185, 2003.
• 16: Hong Su , Elke A. Rundensteiner , Murali Mani, Semantic query optimization in an automata-algebra combined XQuery engine over XML streams, Proceedings of the Thirtieth international conference on Very large data bases, p.1293-1296, August 31-September 03, 2004, Toronto, Canada
• 17: L. Fegaras. Efficient Processing of XML Update Streams. In Proceedings of ICDE, pages 616--625, 2008.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Special-purpose algebraic systems
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Design, Experimentation, Performance

Keywords:
XML, XQuery, query algebra, query processing, stream