Validating streaming XML documents

ABSTRACT

This paper investigates the on-line validation of streaming XML documents with respect to a DTD, under memory constraints. We first consider validation using constant memory, formalized by a finite-state automaton (FSA). We examine two flavors of the problem, depending on whether or not the XML document is assumed to be well-formed. The main results of the paper provide conditions on the DTDs under which validation of either flavor can be done using an FSA. For DTDs that cannot be validated by an FSA, we investigate two alternatives. The first relaxes the constant memory requirement by allowing a stack bounded in the depth of the XML document, while maintaining the deterministic, one-pass requirement. The second approach consists in refining the DTD to provide additional information that allows validation by an FSA.

REFERENCES

• 1: A. V. Aho and J. D. Ullman. Translations on a context free grammar. Information and Control, 19(19):439-475, 1971.
• 2: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 3: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 4: 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]
• 5: A. Bruggemann-Klein, M. Murata, and D. Wood. Regular tree and regular hedge languages over non-ranked alphabets. Hong Kong Univ. of Science and Technology Computer Science Center Research Report HKUST-TCSC-2001-05, 2001. Available at http://www.cs.ust.hk/tcsc/RR/2001-05.ps.gz.
• 6: 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
• 7: 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
• 8: Joost Engelfriet , Hendrik Jan Hoogeboom, Tree-Walking Pebble Automata, Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, p.72-83, January 1999
• 9: Joost Engelfriet , Hendrik Jan Hoogeboom , Jan-Pascal Van Best, Trips on trees, Acta Cybernetica, v.14 n.1, p.51-64, Feb 1999
• 10: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 11: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: Z. Ives, Alon Levy and D. Weld. Efficient Evaluation of Regular Path Expressions on Streaming XML Data. Technical Report, University of Washington, 2000.
• 13: Z. Ives, Alon Levy and D. Weld. Integrating Network-Bound XML Data. Data Engineering Bulletin, 24(2), 2001.
• 14: Ling Liu and Calton Pu and Wei Tang and Wei Han. Conquer: A continual query system for update monitoring in the WWW. In International Journal of Computer Systems, Science and Engineering, 2000.
• 15: Frank Neven , Thomas Schwentick, On the Power of Tree-Walking Automata, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.547-560, July 09-15, 2000
• 16: Benjamin Nguyen , Serge Abiteboul , Grégory Cobena , Mihaí Preda, Monitoring XML data on the Web, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.437-448, May 21-24, 2001, Santa Barbara, California, United States
• 17: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 18: Grzegorz Rozenberg , Arto Salomaa, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

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

          Nouns: XML

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Design, Languages, Theory