Processing XML streams with deterministic automata and stream indexes

ABSTRACT

We consider the problem of evaluating a large number of XPath expressions on a stream of XML packets. We contribute two novel techniques. The first is to use a single Deterministic Finite Automaton (DFA). The contribution here is to show that the DFA can be used effectively for this problem: in our experiments we achieve a constant throughput, independently of the number of XPath expressions. The major issue is the size of the DFA, which, in theory, can be exponential in the number of XPath expressions. We provide a series of theoretical results and experimental evaluations that show that the lazy DFA has a small number of states, for all practical purposes. These results are of general interest in XPath processing, beyond stream processing. The second technique is the Streaming IndeX (SIX), which consists of adding a small amount of binary data to each XML packet that allows the query processor to achieve significant speedups. As an application of these techniques we describe the XML Toolkit (XMLTK), a collection of command-line tools providing highly scalable XML data processing.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 3: 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
• 4: ANDIS/ISO. 1998. C++ Standard. ANDIS/ISO, Geneva, Switzerland.
• 5: Avila-Campillo, I., Green, T. J., Gupta, A., Onizuka, M., Raven, D., and Suciu, D. 2002. XMLTK: An XML toolkit for scalable XML stream processing. In Proceedings of PLANX.
• 6: Borne, K. D. n.d. NASA's astronomical data center. ADC XML resource page. Available online at http://xml.gsfc.nasa.gov/.
• 7: Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu, Adding Structure to Unstructured Data, Proceedings of the 6th International Conference on Database Theory, p.336-350, January 08-10, 1997
• 8: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 9: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 10: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, ACM SIGMOD Record, v.29 n.2, p.379-390, June 2000
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Corp., M. n.d. DIME---direct Internet message encapsulation specification index page. IETF Internet draft. Available online at http://msdn.microsoft.com/webservices/understanding/gxa/default.aspx.
• 13: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 14: Diao, Y. and Franklin, M. 2003. Query processing for high-volume XML message brokering. In Proceedings of VLDB (Berlin, Germany).
• 15: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 16: Florescu, D., Hillary, C., Kossmann, D., P.Lucas, Riccardi, F., Westmann, T., Carey, M., Sundararajan, A., and Agrawal, G. 2003. The bea/xqrl streaming xquery processor. In Proceedings of VLDB (Berlin, Germany). 997--1008.
• 17: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 18: 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
• 19: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 20: 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
• 21: Gupta, A. K., Halevy, A. Y., and Suciu, D. 2002. View selection for XML stream processing. In Proceedings of the International Workshop on the Web and Database (Web DB). 83--88.
• 22: 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]
• 23: Ashish Kumar Gupta , Dan Suciu , Alon Y. Halevy, The view selection problem for XML content based routing, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-77, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773161]
• 24: Higgins, D. G., Fuchs, R., Stoehr, P. J., and Cameron, G. N. 1992. The EMBL data library. Nucleic Acids Res. 20, 2071--2074.
• 25: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 26: 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]
• 27: V. Laurikari, NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions, Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), p.181, September 27-29, 2000
• 28: Ley, M. n.d. Computer science bibliography (dblp). Available online at http://dblp.uni- trier.de.
• 29: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, ACM SIGMOD Record, v.29 n.2, p.153-164, June 2000
• 30: Ludaescher, B., Mukhopadhyay, P., and Papakonstantinou, Y. 2002. A transducer-based XML query processor. In Proceedings of VLDB. 227--238.
• 31: 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
• 32: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 33: Benjamin Nguyen , Serge Abiteboul , Grégory Cobena , Mihaí Preda, Monitoring XML data on the Web, ACM SIGMOD Record, v.30 n.2, p.437-448, June 2001
• 34: Makoto Onizuka, Light-weight xPath processing of XML stream with deterministic automata, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956928]
• 35: 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]
• 36: Grzegorz Rozenberg , Arto Salomaa, Handbook of Formal Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 37: Arnaud Sahuguet, Everything You Ever Wanted to Know About DTDs, But Were Afraid to Ask (Extended Abstract), Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.171-183, May 18-19, 2000
• 38: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 39: Thierry-Mieg, J. and Durbin, R. 1992. Syntactic Definitions for the ACEDB Data Base Manager. Tech. rep. MRC-LMB xx.92. MRC Laboratory for Molecular Biology, Cambridge, U.K.
• 40: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
• 41: Watson, B. W. 1993. A taxonomy of finite automata construction algorithms. Computing Science report 93/43. University of Technology Eindhoven, Eindhoven, The Netherlands.
• 42: Bruce W. Watson, Implementing and using finite automata toolkits, Natural Language Engineering, v.2 n.4, p.295-302, December 1996 [doi>10.1017/S135132499700154X]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
XML processing, stream processing