Raindrop: a uniform and layered algebraic framework for XQueries on XML streams

ABSTRACT

XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data. While the automata model is naturally suited for pattern matching on tokenized XML streams, the algebraic model in contrast is a well-established technique for set-oriented processing of self-contained tuples. However, neither automata nor algebraic models are well-equipped to handle both computation paradigms.

The goal of the Raindrop project is to accommodate these two paradigms within one algebraic framework to take advantage of both. In our query model, both tokenized data and self-contained tuples are supported in a uniform manner. Query plans can be flexibly rewritten using equivalence rules to change what computation is done using tokenized data versus tuples. This paper highlights the four abstraction levels in Raindrop, namely, semantics-focused plan, stream logical plan, stream physical plan and execution plan. Various optimization techniques are provided at each level. The necessity of such a uniform and layered plan is shown by experimental study

REFERENCES

• 1: A. Schmidt, F. Waas and R. Busse et al. Xmark -- The XML-Benchmark Project. http://www.xml-benchmark.org, 2001.
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, 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.543615]
• 3: D. Barbosa, A. Mendelzon, and J. Keenleyside et al. ToXgene: a Template-Based Data Generator for XML. In Proceedings of WEBDB, pages 49--54, 2002.
• 4: D. Carney, U. Cetintemel, and M. Cherniack et al. Monitoring Streams - A New Class of Data Management Applications. In Proceedings of VLDB, pages 215--226, 2002.
• 5: Y. Diao and M. Franklin. Query Processing for High-Volume XML Message Brokering. In Proceeding of VLDB, to appear, 2003.
• 6: Leonidas Fegaras , David Maier, Towards an effective calculus for object query languages, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.47-58, May 22-25, 1995, San Jose, California, United States
• 7: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 8: 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]
• 9: J. Jian, H. Su, and E. Rundensteiner. Automaton Meets Query Algebra: Towards A Unified Model for XQuery Evaluation over XML Data Streams. In Proceedings of ER, to appear, 2003.
• 10: B. Ludascher, P. Mukhopadhyay, and Y. Papakonstantinou. A Transducer- Based XML Query Processor. In Proceedings of VLDB, pages 215--226, 2002.
• 11: 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
• 12: Mixing Querying and Navigation in MIX, Proceedings of the 18th International Conference on Data Engineering, p.245, February 26-March 01, 2002
• 13: 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]
• 14: Sourceforge. SAX 2.0. http://www.saxproject.org/, 2002.
• 15: Xin Zhang , Bradford Pielech , Elke A. Rundesnteiner, Honey, I shrunk the XQuery!: an XML algebra optimization approach, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/584931.584936]

INDEX TERMS

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

General Terms:
Management

Keywords:
XML stream, XQuery algebra, query processing