The essence of XML

ABSTRACT

The World-Wide Web Consortium (W3C) promotes XML and related standards, including XML Schema, XQuery, and XPath. This paper describes a formalization of XML Schema. A formal semantics based on these ideas is part of the official XQuery and XPath specification, one of the first uses of formal methods by a standards body. XML Schema features both named and structural types, with structure based on tree grammars. While structural types and matching have been studied in other work (notably XDuce, Relax NG, and a previous formalization of XML Schema), this is the first work to study the relation between named types and structural types, and the relation between matching and validation.

REFERENCES

• 1: Martin Abadi , Luca Cardelli, A Theory of Objects, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Tim Bray, Jean Paoli, and C. M. Sperberg-McQueen. Extensible Markup Language (XML) 1.0. W3C Recommendation, February 1998.
• 4: Allen Brown , Matthew Fuchs , Jonathan Robie , Philip Wadler, MSL — a model for W3C XML schema, Proceedings of the 10th international conference on World Wide Web, p.191-200, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371982]
• 5: James Clarke. XSL Transformations (XSLT) version 1.0. W3C Recommendation, November 1999.
• 6: James Clarke. TREX --- Tree Regular Expressions for XML. Thai Open Source Software Center, February 2001.
• 7: James Clarke and Murata Makoto. RELAX NG specification. Oasis, December 2001.
• 8: 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
• 9: H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications, 1997.
• 10: Carl A. Gunter , John C. Mitchell, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
• 11: Haruo Hosoya , Benjamin C. Pierce, XDuce: A Typed XML Processing Language (Preliminary Report), Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.226-244, May 18-19, 2000
• 12: Michael Kay. XSL Transformations (XSLT) version 2.0. W3C Working Draft, April 2002.
• 13: Murata Makoto. Document description and processing languages -- regular language description for XML (relax), October 2000.
• 14: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]
• 15: Peter Neumann. Risks to the public from the use of computers. phACM Software Engineering Notes 10(3), July 1985.
• 16: 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]
• 17: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 18: John C. Reynolds, Syntactic control of interference, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-46, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512766]
• 19: John C. Reynolds. The essence of Algol. In J. W. de Bakker and J. C. van Vliet, editors, Algorithmic Languages. North-Holland, Amsterdam, 1981, pages 345-372.
• 20: Grzegorz Rozenberg , Arto Salomaa, Handbook of Formal Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 21: Jérôme Siméon , Philip Wadler, The Essence of XML (Preliminary Version), Proceedings of the 6th International Symposium on Functional and Logic Programming, p.21-46, September 15-17, 2002
• 22: Henri S. Thompson, David Beech, Murray Maloney, and N. Mendelsohn. XML Schema part 1: Structures. W3C Recommendation, May 2001.
• 23: XPath 2.0. W3C Working Draft, November 2002.
• 24: XQuery 1.0: An XML Query Language. W3C Working Draft, November 2002.
• 25: XQuery 1.0 Formal Semantics. W3C Working Draft, November 2002.
• 26: XQuery Formal Semantics FS Issue-0141 -- FS Issue-0151.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

General Terms:
Languages, Standardization, Theory

Keywords:
XML, XML schema, XPath, XQuery, validation