Regular expression types for XML

ABSTRACT

We propose regular expression types as a foundation for statically typed XML processing languages. Regular expression types, like most schema languages for XML, introduce regular expression notations such as repetition (*), alternation (|), etc., to describe XML documents. The novelty of our type system is a semantic presentation of subtyping, as inclusion between the sets of documents denoted by two types. We give several examples illustrating the usefulness of this form of subtyping in XML processing.The decision problem for the subtype relation reduces to the inclusion problem between tree automata, which is known to be EXPTIME-complete. To avoid this high complexity in typical cases, we develop a practical algorithm that, unlike classical algorithms based on determinization of tree automata, checks the inclusion relation by a top-down traversal of the original type expressions. The main advantage of this algorithm is that it can exploit the property that type expressions being compared often share portions of their representations. Our algorithm is a variant of Aiken and Murphy's set-inclusion constraint solver, to which are added several new implementation techniques, correctness proofs, and preliminary performance measurements on some small programs in the domain of typed XML processing.

REFERENCES

• 1: Alexander Aiken , Brian R. Murphy, Implementing regular tree expressions, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.427-447, June 1991, Cambridge, Massachusetts, United States
• 2: Roberto M. Amadio , Luca Cardelli, Subtyping recursive types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.575-631, Sept. 1993 [doi>10.1145/155183.155231]
• 3: Michael Brandt , Fritz Henglein, Coinductive axiomatization of recursive type equality and subtyping, Fundamenta Informaticae, v.33 n.4, p.309-338, April 1998
• 4: Bray, T., Paoli, J., Sperberg-McQueen, C. M., and Maler, E. 2000. Extensible markup language (XML#8482;). http://www.w3.org/XML/.
• 5: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• 6: 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
• 7: Peter Buneman , Benjamin C. Pierce, Union Types for Semistructured Data, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.184-207, September 01-03, 1999
• 8: Jiazhen Cai , Robert Paige, Using multiset discrimination to solve language processing problems without hashing, Theoretical Computer Science, v.145 n.1-2, p.189-228, July 10, 1995 [doi>10.1016/0304-3975(94)00183-J]
• 9: Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
• 10: Clark, J. 1999. XSL Transformations (XSLT). http://www.w3.org/TR/xslt.
• 11: Clark, J. 2001. TREX: Tree Regular Expressions for XML. http://www.thaiopensource.com/trex/.
• 12: Clark, J. and Murata, M. 2001. RELAX NG. http://www.relaxng.org.
• 13: Jérôme Siméon , Sophie Cluet, Using YAT to Build a Web Server, Selected papers from the International Workshop on The World Wide Web and Databases, p.118-135, March 27-28, 1998
• 14: Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. 1999. Tree automata techniques and applications (Draft book; available electronically on http://www.grappa.univ-lille3.fr/tata.)
• 15: Flemming M. Damm, Subtyping with Union Types, Intersection Types and Recursive Types, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.687-706, April 19-22, 1994
• 16: Davidson, A., Fuchs, M., Hedin, M., Jain, M., Koistinen, J., Lloyd, C., Maloney, M., and Schwarzhof, K. 1999. Schema for object-oriented XML. http://www.w3.org/TR/NOTE-SOX/.
• 17: Davies, R. 2000. Tree automata inclusion. Personal communication.
• 18: Deutsch, A., Fernandez, M., Florescu, D., Levy, A., and Suciu, D. 1998. XML-QL: A Query Language for XML. http://www.w3.org/TR/NOTE-xml-ql.
• 19: DOM. 2001. Document object model (DOM). http://www.w3.org/DOM/.
• 20: Fallside, D. C. 2001. XML Schema Part 0: Primer, W3C Recommendation. http://www.w3.org/TR/xmlschema-0/.
• 21: Mary F. Fernandez , Jérôme Siméon , Philip Wadler, A Semi-monad for Semi-structured Data, Proceedings of the 8th International Conference on Database Theory, p.263-300, January 04-06, 2001
• 22: Tim Freeman , Frank Pfenning, Refinement types for ML, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.268-277, June 24-28, 1991, Toronto, Ontario, Canada
• 23: Alain Frisch , Giuseppe Castagna , Véronique Benzaken, Semantic Subtyping, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.137-146, July 22-25, 2002
• 24: Vladimir Gapeyev , Michael Y. Levin , Benjamin C. Pierce, Recursive subtyping revealed: (functional pearl), Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.221-231, September 2000
• 25: Gilleron, R., Tison, S., and Tommasi, M. 1999. Set constraints and automata. Inf. Comput. 149, 1, 1--41.
• 26: 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
• 27: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 28: Hornung, T. 1996. Labelled trees and their recognition. In Publ. Math. Debrecen. Number 3--4 in 48. 309--316.
• 29: Hosoya, H. 2003. Regular expression pattern matching---A simpler design. Tech. Rep. 1397, RIMS, Kyoto University.
• 30: Haruo Hosoya , Benjamin Pierce, Regular expression pattern matching for XML, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 2001, London, United Kingdom
• 31: 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
• 32: Klarlund, N., Møller, A., and Schwartzbach, M. I. 2000. DSD: A schema language for XML. http://www.brics.dk/DSD/.
• 33: Gabriel M. Kuper , Jérôme Siméon, Subsumption for XML types, Proceedings of the 8th International Conference on Database Theory, p.331-345, January 04-06, 2001
• 34: Meijer, E. and Shields, M. 1999. XMλ: A functional programming language for constructing and manipulating XML documents. Manuscript.
• 35: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 36: Murata, M. 2000. Hedge automata: A formal model for XML schemata. http://www.xml.gr.jp/relax/hedge_nice.html.
• 37: Murata, M. 2001. RELAX (REgular LAnguage description for XML). http://www.xml.gr.jp/relax/.
• 38: 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]
• 39: Helmut Seidl, Deciding equivalence of finite tree automata, SIAM Journal on Computing, v.19 n.3, p.424-437, June 1990 [doi>10.1137/0219027]
• 40: Mark Shields , Erik Meijer, Type-indexed rows, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-275, January 2001, London, United Kingdom
• 41: Malcolm Wallace , Colin Runciman, Haskell and XML: generic combinators or type-based translation?, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.148-159, September 27-29, 1999, Paris, France

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Languages, Theory

Keywords:
Type systems, XML, subtyping