Light-weight xPath processing of XML stream with deterministic automata

ABSTRACT

Several applications based on XML stream processing have recently emerged, such as those for air traffic control and the selective dissemination of information (SDI). Their common need is to process a large number of XPath expressions in continuous XML streams at high throughput.This paper proposes four techniques for XPath expression processing based on Deterministic Finite Automata (DFA) for two purposes: to improve the memory usage efficiency of the automata and to support the processing of branching XPath expressions. The first technique, called n-DFA, clusters the given XPath expressions into n clusters to reduce the number of DFA states. The second, called shared NFA state table, lets the Non-Deterministic Finite Automata (NFA) state set be shared among the DFA states. Our experiments show that memory usage in an 8-DFA can, with the shared NFA state table, be reduced to 1/40th that of the original 1-DFA. The optimized NFA conversion and general XPath expression processing algorithm techniques contribute to the processing of branching XPath expressions efficiently; overall performance is better than is possible with earlier approaches.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: 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
• 3: I. Avila-Campillo, T. J. Green, A. Gupta, M. Onizuka, D. Raven, and D. Suciu. XMLTK: An XML toolkit for scalable XML stream processing. In Proceedings of PLANX, 2002.
• 4: C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient filtering of XML documents with XPath expressions. In Proceedings of ICDE, 2002.
• 5: 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
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Y. Diao, P. Fischer, M. Franklin, and R. To. Yfilter: Efficient and scalable filtering of XML documents. In Proceedings of ICDE, 2002.
• 8: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 9: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 10: 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]
• 11: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 12: Z. Ives, A. Halevy, and D. Weld. Efficient evaluation of regular path expressions on streaming XML data. Technical Report UW-CSE-2000-05-02, 2000.
• 13: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 14: Mitchell P. Marcus , Mary Ann Marcinkiewicz , Beatrice Santorini, Building a large annotated corpus of English: the penn treebank, Computational Linguistics, v.19 n.2, June 1993
• 15: NAA classified advertising standards task force.http://www.naa.org/TECHNOLOGY/CLSSTDTF.
• 16: NASA's astronomical data center. ADC XML resource page. http://xml.gsfc.nasa.gov/.
• 17: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 18: João Pereira , Françoise Fabret , Hans-Arno Jacobsen , François Llirbat , Dennis Shasha, WebFilter: A High-throughput XML-based Publish and Subscribe System, Proceedings of the 27th International Conference on Very Large Data Bases, p.723-724, September 11-14, 2001
• 19: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada

INDEX TERMS

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

General Terms:
Performance

Keywords:
XPath processing, automata, selective dissemination of information, streaming XML