Query processing of streamed XML data

ABSTRACT

We are addressing the efficient processing of continuous XML streams, in which the server broadcasts XML data to multiple clients concurrently through a multicast data stream, while each client is fully responsible for processing the stream. In our framework, a server may disseminate XML fragments from multiple documents in the same stream, can repeat or replace fragments, and can introduce new fragments or delete invalid ones. A client uses a light-weight database based on our proposed XML algebra to cache stream data and to evaluate XML queries against these data. The synchronization between clients and servers is achieved through annotations and punctuations transmitted along with the data streams. We are presenting a framework for processing XML queries in XQuery form over continuous XML streams. Our framework is based on a novel XML algebra and a new algebraic optimization framework based on query decorrelation, which is essential for non-blocking stream processing.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 3: C. Beeri and Y. Tzaban. SAL: An Algebra for Semistructured Data and XML. In ACM SIGMOD Workshop on The Web and Databases (WebDB'99), Philadelphia, Pennsylvania, pages 37--42, June 1999.
• 4: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 5: Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994 [doi>10.1145/181550.181564]
• 6: D. Chamberlin, D. Florescu, J. Robie, J. Simeon, and M. Stefanescu. XQuery: A Query Language for XML. Available at http://www.w3.org/TR/xquery/, 2000.
• 7: Vassilis Christophides , Sophie Cluet , Jérǒme Simèon, On wrapping query languages and efficient XML integration, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.141-152, May 15-18, 2000, Dallas, Texas, United States
• 8: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 9: Sophie Cluet , Guido Moerkotte, Nested Queries in Object Bases, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.226-242, August 30-September 01, 1993
• 10: Leonidas Fegaras , Ramez Elmasri, Query Engines for Web-Accessible XML Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.251-260, September 11-14, 2001
• 11: Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000 [doi>10.1145/377674.377676]
• 12: Mary F. Fernandez , Jérôme Siméon , Philip Wadler, An Algebra for XML Query, Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, p.11-45, December 13-15, 2000
• 13: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 14: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 15: Z. Ives, A. Levy, and D. Weld. Efficient Evaluation of Regular Path Expressions on Streaming XML Data. Technical report, University of Washington, 2000. Technical Report UW-CSE-2000-05-02.
• 16: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• 17: World Wide Web Consortium (W3C). Extensible Markup Language (XML). http://www.w3.org/XML/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

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

General Terms:
Languages, Performance

Keywords:
XML, databases, query optimization, query processing