Efficient evaluation of multiple queries on streaming XML data

ABSTRACT

Traditionally, XML documents are processed at where they are stored. This allows the query processor to exploit pre-computed data structures (e.g., index) to retrieve the desired data efficiently. However, this mode of processing is not suitable for many applications where the documents are frequently updated. In such situations, efficient evaluation of multiple queries over streaming XML documents becomes important. This paper introduces a new operator, mqX-scan, which efficiently evaluates multiple queries with a single pass on streaming XML data. To facilitate matching, mqX-scan utilizes templates containing paths that have been traversed to match regular path expression patterns in a pool of queries. Results of the experiments demonstrate the efficiency and scalability of the mqX-scan operator.

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: S. Abiteboul, D. Quass, J. McHugh, J. Widom and J. Wiener. The Lorel Query Language for Semistructured Data, International Journal on Digital Libraries, Vol 1(1), pp. 68--88, 1997.
• 3: D.Chamberlin, D.Florescu, J.Robie, J.Simon, M.Stefanescu. XQuery: An XML Query Language, W3C Working Draft, 2001.
• 4: S.Bressan, G.Dobbie, Z.Lacroix, M.L.Lee, Y.Li, U. Nambiar and B.Wadhwa: XOO7: Applying OO7 Benchmark to XML Query Processing Tools, 10th ACM CIKM, 2001.
• 5: S. Babu and J. Widom. Continuous Queries over Data Streams. Stanford University Tech. Report, 2001.
• 6: J.Clark and S.DeRose. XML Path Language (XPath), W3C Technical Report, 1999.
• 7: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 8: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 9: S. Cluet and J. Simeon. YATL: A functional and declarative language for XML. Working draft, 2000.
• 10: Alin Deutsch , Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for XML, Proceeding of the eighth international conference on World Wide Web, p.1155-1169, May 1999, Toronto, Canada
• 11: Z.G. Ives, A.Y. Levy and D.S. Weld. Efficient Evaluation of Regular Path Expressions on Streaming XML Data. Technical Report, University of Washington, 2000.
• 12: 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
• 13: J. Robie. The design of XQL, 1999. <http://www.texcel.no/whitepapers/xql-design.html>
• 14: SAX 1.0: The Simple API for XML. <http://www.saxproject.org/>
• 15: Apache XML Project. The Xerces Java XML parser. http://xml.apache.org/ xerces-j/index.html

INDEX TERMS

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

General Terms:
Performance

Keywords:
finite state machines, regular path expressions, streaming XML