Semantic query optimization for processing XML streams with minimized memory footprint

ABSTRACT

XQuery evaluation over XML streams requires the temporary buffering of XML elements. This paper presents a semantic query optimization solution to minimize memory footprint during XQuery evaluation by exploiting schema knowledge. We focus on one particular class of constraints, namely, the Pattern Non-Occurrence (PNO) constraints for XML streams conforming to pre-defined DTDs. PNO constraints facilitate the early release of buffered data (early buffer release) or possibly avoid to ever store the data (buffer avoidance), thus achieving a minimized memory footprint. We develop an automaton-based technique to detect PNO constraints at runtime. For a given query, optimization opportunities of early buffer release and buffer avoidance which can be triggered by runtime PNO detection are explored and the optimization decision is then encoded into the Raindrop algebraic plan. We implement our optimization technique within the Raindrop XQuery engine. Our experimental studies illustrate that the proposed techniques bring significant performance improvement in both memory and CPU usage with little overhead.

REFERENCES

• 1: S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. 1995.
• 2: Denilson Barbosa , Alberto Mendelzon , John Keenleyside , Kelly Lyons, ToXgene: a template-based data generator for XML, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564769]
• 3: Véronique Benzaken , Giuseppe Castagna , Dario Colazzo , Kim Nguyên, Type-based XML projection, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible markup language 1.0 (fourth edition). In http://www.w3.org/TR/REC-xml/, 2006.
• 5: Anne Brüggemann-Klein , Derick Wood, One-unambiguous regular languages, Information and Computation, v.142 n.2, p.182-206, May 2, 1998 [doi>10.1006/inco.1997.2695]
• 6: N. Bruno, L. Gravano, N. Koudas, and D. Srivastava. Navigation- vs. index-based xml multi-query processing. In ICDE, pages 139--150, 2003.
• 7: Yi Chen , Susan B. Davidson , Yifeng Zheng, ViteX: A Streaming XPath Processing System, Proceedings of the 21st International Conference on Data Engineering, p.1118-1119, April 05-08, 2005 [doi>10.1109/ICDE.2005.152]
• 8: Yi Chen , Susan B. Davidson , Yifeng Zheng, An Efficient XPath Query Processor for XML Streams, Proceedings of the 22nd International Conference on Data Engineering, p.79, April 03-07, 2006 [doi>10.1109/ICDE.2006.18]
• 9: P. S. Database. http://pir.georgetown.edu.
• 10: 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
• 11: 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]
• 12: Christoph Koch , Stefanie Scherzinger , Nicole Schweikardt , Bernhard Stegmaier, Schema-based scheduling of event processors and buffer minimization for queries on structured data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.228-239, August 31-September 03, 2004, Toronto, Canada
• 13: Dexter C. Kozen, Automata and Computability, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 14: Xiaogang Li , Gagan Agrawal, Efficient evaluation of XQuery over streaming data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: 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
• 16: 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
• 17: 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]
• 18: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 19: M. Schmidt, S. Scherzinger, and C. Koch. Combined static and dynamic analysis for effective buffer minimization. In ICDE, pages 236--245, 2007.
• 20: H. Su, E. A. Rundensteiner, and M. Mani. Semantic query optimization for XQuery over xml streams. In VLDB, pages 1293--1296, 2005.
• 21: 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]
• 22: W3C. XQuery 1.0 and Xpath 2.0 formal semantics. http://www.w3.org/TR/query-semantics, 2004.
• 23: Song Wang , Hong Su , Ming Li , Mingzhu Wei , Shoushen Yang , Drew Ditto , Elke A. Rundensteiner , Murali Mani, R-SOX: runtime semantic query optimization over XML streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance