Validation of streaming XML documents with abstract state machines

ABSTRACT

The exact validation of streaming XML documents can be realised by using visibly push-down automata (VPA) that are defined by Extended Document Type Definitions (EDTD). It is straightforward to represent such an automaton as an Abstract State Machine (ASM). However, creating a whole VPA is not an efficient validation approach. In this paper it is shown, how the VPA construction can be avoided by using a refined ASM that only requires knowledge of the EDTD. In a second step this approach is extended to approximate validation of streaming XML documents taking at most k updates to the document into consideration.

REFERENCES

• 1: Rajeev Alur , P. Madhusudan, Visibly pushdown languages, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007390]
• 2: E. Börger. The ASM refinement method. Formal Aspects of Computing, 15:237--257, 2003.
• 3: E. Börger and R. Stärk. Abstract State Machines. Springer-Verlag, Berlin Heidelberg New York, 2003.
• 4: Robert F. Stark , E. Borger , Joachim Schmid, Java and the Java Virtual Machine: Definition, Verification, Validation with Cdrom, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 5: Don Box , Aaron Skonnard , John Lam, Essential XML: Beyond Markup, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 6: L. M. Garshol. Definitive XML Application Development. Prentice-Hall, 2002.
• 7: Suhit Gupta , Gail Kaiser , David Neistadt , Peter Grimm, DOM-based content extraction of HTML documents, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775182]
• 8: Elliote Rusty Harold, Processing Xml with Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 9: Viraj Kumar , P. Madhusudan , Mahesh Viswanathan, Visibly pushdown automata for streaming XML, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242714]
• 10: 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]
• 11: Luc Segoufin , Victor Vianu, Validating streaming XML documents, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543622]
• 12: A. Thomo, S. Venkatesh, and Y. Y. Ye. Visibly pushdown transducers for approximate validation of streaming XML. In S. Hartmann and G. Kern-Isberner, editors, Foundations of Information and Knowledge Systems -- Proc. 5th International Symposium, FoIKS 2008, volume 4932 of LNCS, pages 219--238. Springer-Verlag, 2008.
• 13: E. Wilde. Advanced XML Technologies. CRC Press, 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.m MISCELLANEOUS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Theory

Keywords:
XML, abstract state machines, validation