Expressiveness and complexity of XML Schema

ABSTRACT

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical characterizations of the Element Declarations Consistent (EDC) rule are provided. In particular, it is obtained that schemas satisfying EDC can only reason about regular properties of ancestors of nodes. Hence, with respect to expressive power, XML Schema is closer to DTDs than to tree automata. These theoretical results are complemented with an investigation of the XML Schema Definitions (XSDs) occurring in practice, revealing that the extra expressiveness of XSDs over DTDs is only used to a very limited extent. As this might be due to the complexity of the XML Schema specification and the difficulty of understanding the effect of constraints on typing and validation of schemas, a simpler formalism equivalent to XSDs is proposed. It is based on contextual patterns rather than on recursive types and it might serve as a light-weight front end for XML Schema. Next, the effect of EDC on the way XML documents can be typed is discussed. It is argued that a cleaner, more robust, larger but equally feasible class is obtained by replacing EDC with the notion of 1-pass preorder typing (1PPT): schemas that allow one to determine the type of an element of a streaming document when its opening tag is met. This notion can be defined in terms of grammars with restrained competition regular expressions and there is again an equivalent syntactical formalism based on contextual patterns. Finally, algorithms for recognition, simplification, and inclusion of schemas for the various classes are given.

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: Andrey Balmin , Yannis Papakonstantinou , Victor Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042050]
• 3: Geert Jan Bex , Wim Martens , Frank Neven , Thomas Schwentick, Expressiveness of XSDs: from practice to theory, there and back again, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060848]
• 4: Geert Jan Bex , Frank Neven , Jan Van den Bussche, DTDs versus XML schema: a practical study, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017095]
• 5: Bray, T., Paoli, J., Sperberg-McQueen, C., Maler, E., and Yergeau, F. 2004. Extensible Markup Language (XML). Tech. rep. World Wide Web Consortium. Go online to http://www.w3.org/TR/REC-xml/.
• 6: Brüggemann-Klein, A., Murata, M., and Wood, D. 2001. Regular tree and regular hedge languages over unranked alphabets: Version 1, April 3, 2001. Tech. rep. HKUST-TCSC-2001-0. The Hongkong University of Science and Technology, Hong Kong.
• 7: 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]
• 8: Buck, L., Goldfarb, C., and Prescod, P. 2000. Datatypes for DTDs (DT4DTD) 1.0. Tech. rep. World Wide Web Consortium. Go online to http://www.w3.org/TR/dt4dtd/.
• 9: Clark, J. 2002. Multi-format schema converter based on RELAX NG. Go online to http://www.thaiopensource.com/relaxng/trang.html.
• 10: Clark, J. and Murata, M. 2001. Relax NG specification. Go online to http://www.relaxng.org/spec-20011203.html.
• 11: Claudio Sacerdoti Coen , Paolo Marinelli , Fabio Vitali, Schemapath, a minimal extension to xml schema for conditional constraints, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988695]
• 12: Cover, R. 2005. The Cover Pages. Go online to http://xml.coverpages.org/.
• 13: Cristau, J., Löding, C., and Thomas, W. 2005. Deterministic automata on unranked trees. In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005). Springer, Berlin, Germany, 68--79.
• 14: DuCharme, B. 2002. Filling in the DTD gaps with schematron. O'Reilly xml.com, Sebastopol, CA.
• 15: Fernandez, M., Malhotra, A., Marsh, J., Nagy, M., and Walsh, N. 2005. XQuery 1.0 and XPath 2.0 data model. Tech. rep. World Wide Web Consortium. Go online to http://www.w3.org/TR/xpath-datamodel/.
• 16: Fiorello, D., Gessa, N., Marinelli, P., and Vitali, F. 2004. DTD++ 2.0: Adding support for co-constraints. In Proceedings of the Extreme Markup Languages 2004 Conference (Extreme Markup Languages 2004).
• 17: Fokoué, A. and Schloss, B. 2004. XML Schema quality checker. Go online to http://www.alphaworks.ibm.com/tech/xmlsqc.
• 18: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 19: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 20: Juraj Hromkoviěc , Sebastian Seibert , Thomas Wilke, Translating regular expressions into small εe-free nondeterministic finite automata, Journal of Computer and System Sciences, v.62 n.4, p.565-588, June 2001 [doi>10.1006/jcss.2001.1748]
• 21: Jelliffe, R. 2001. The current state of the art of schema languages for XML. Presentation at XML Asia Pacific Conference, Sidney, Australia.
• 22: Jelliffe, R. 2005. Schematron. Go online to http://xml.ascc.net/schematron/.
• 23: Nils Klarlund , Anders Møller , Michael I. Schwartzbach, The DSD Schema Language, Automated Software Engineering, v.9 n.3, p.285-319, August 2002 [doi>10.1023/A:1016376608070]
• 24: Koch, C. and Scherzinger, S. 2003. Attribute grammars for scalable query processing on XML streams. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL 2003). Springer, Berlin, Germany, 233--256.
• 25: Dongwon Lee , Wesley W. Chu, Comparative analysis of six XML schema languages, ACM SIGMOD Record, v.29 n.3, p.76-87, Sept. 2000 [doi>10.1145/362084.362140]
• 26: Mani, M. 2001. Keeping chess alive---do we need 1-unambiguous content models? Presentation at Extreme Markup Languages Conference 2001.
• 27: Wim Martens , Frank Neven, Frontiers of tractability for typechecking simple XML transformations, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055563]
• 28: Wim Martens , Frank Neven, On the complexity of typechecking top-down XML transformations, Theoretical Computer Science, v.336 n.1, p.153-180, 25 May 2005 [doi>10.1016/j.tcs.2004.10.035]
• 29: Martens, W., Neven, F., and Schwentick, T. 2004. Complexity of decision problems for simple regular expressions. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004). Springer, Berlin, Germany, 889--900.
• 30: Martens, W., Neven, F., and Schwentick, T. 2005. Which XML schemas admit 1-pass preorder typing? In Proceedings of the 10th International Conference on Database Theory (ICDT 2005). Springer, Berlin, Germany, 68--82.
• 31: Martens, W. and Niehren, J. 2005. Minimizing tree automata for unranked trees. In Prodeedings of the 10th International Symposium on Database Programming Languages (DBPL 2005). Springer, Berlin, Germany, 232--246.
• 32: Murata, M., Lee, D., and Mani, M. 2001. Taxonomy of XML schema languages using formal language theory. In Proceedings of the Extreme Markup Languages 2001 Conference (Extreme Markup Languages 2001), Montreal, P. Q., Canada.
• 33: Makoto Murata , Dongwon Lee , Murali Mani , Kohsuke Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology (TOIT), v.5 n.4, p.660-704, November 2005 [doi>10.1145/1111627.1111631]
• 34: Frank Neven, Automata, Logic, and XML, Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, p.2-26, September 22-25, 2002
• 35: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]
• 36: 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]
• 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: 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]
• 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: Jérôme Siméon , Philip Wadler, The essence of XML, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 15-17, 2003, New Orleans, Louisiana, USA
• 41: Sperberg-McQueen, C. 2003. XML Schema 1.0: A language for document grammars. Presentation at the Joint International Conference of the Association for Computers and the Humanities Association for Literary and Linguistic Computing (ACH/ALLC 2003). Go online to http://www.w3.org/People/cmsmcq/2003/achallc/achallc2003.html.
• 42: Sperberg-McQueen, C. and Thompson, H. 2005. XML Schema. Go online to http://www.w3.org/XML/Schema.
• 43: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 44: Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
• 45: Thompson, H., Beech, D., Maloney, M., and Mendelsohn, N. 2004. XML Schema Part 1: Structures. Tech. rep. World Wide Web Consortium. Go online to http://www.w3.org/TR/xmlschema-1/.
• 46: Eric van der Vlist, XML Schema, O'Reilly Media, Inc., 2002
• 47: Vitali, F., Amorosi, N., and Gessa, N. 2003. Datatype- and namespace-aware DTDs: A minimal extension. In Proceedings of the Extreme Markup Languages 2003 Conference (Extreme Markup Languages 2003).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

General Terms:
Algorithms, Design, Languages, Standardization, Theory

Keywords:
XML, XML Schema, validation