{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T01:29:49Z","timestamp":1791250189269,"version":"4.1.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1166074.1166076","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"770-813","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":130,"title":["Expressiveness and complexity of XML Schema"],"prefix":"10.1145","volume":"31","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, School for Information Technology, Diepenbeek, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, School for Information Technology, Diepenbeek, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"University of Dortmund, Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Geert Jan","family":"Bex","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, School for Information Technology, Diepenbeek, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042050"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060848"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_1_5_1","unstructured":"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\/.  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\/."},{"key":"e_1_2_1_6_1","unstructured":"Br\u00fcggemann-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.  Br\u00fcggemann-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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"e_1_2_1_8_1","unstructured":"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\/.  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\/."},{"key":"e_1_2_1_9_1","unstructured":"Clark J. 2002. Multi-format schema converter based on RELAX NG. Go online to http:\/\/www.thaiopensource.com\/relaxng\/trang.html.  Clark J. 2002. Multi-format schema converter based on RELAX NG. Go online to http:\/\/www.thaiopensource.com\/relaxng\/trang.html."},{"key":"e_1_2_1_10_1","unstructured":"Clark J. and Murata M. 2001. Relax NG specification. Go online to http:\/\/www.relaxng.org\/spec-20011203.html.  Clark J. and Murata M. 2001. Relax NG specification. Go online to http:\/\/www.relaxng.org\/spec-20011203.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988695"},{"key":"e_1_2_1_12_1","unstructured":"Cover R. 2005. The Cover Pages. Go online to http:\/\/xml.coverpages.org\/.  Cover R. 2005. The Cover Pages. Go online to http:\/\/xml.coverpages.org\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_7"},{"key":"e_1_2_1_14_1","volume-title":"Filling in the DTD gaps with schematron. O'Reilly xml.com","author":"DuCharme B.","unstructured":"DuCharme , B. 2002. Filling in the DTD gaps with schematron. O'Reilly xml.com , Sebastopol, CA . DuCharme, B. 2002. Filling in the DTD gaps with schematron. O'Reilly xml.com, Sebastopol, CA."},{"key":"e_1_2_1_15_1","unstructured":"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\/.  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\/."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Extreme Markup Languages 2004 Conference (Extreme Markup Languages","author":"Fiorello D.","year":"2004","unstructured":"Fiorello , D. , Gessa , N. , Marinelli , P. , and Vitali , F . 2004. DTD&plus;&plus; 2.0: Adding support for co-constraints . In Proceedings of the Extreme Markup Languages 2004 Conference (Extreme Markup Languages 2004 ). Fiorello, D., Gessa, N., Marinelli, P., and Vitali, F. 2004. DTD&plus;&plus; 2.0: Adding support for co-constraints. In Proceedings of the Extreme Markup Languages 2004 Conference (Extreme Markup Languages 2004)."},{"key":"e_1_2_1_17_1","unstructured":"Fokou\u00e9 A. and Schloss B. 2004. XML Schema quality checker. Go online to http:\/\/www.alphaworks.ibm.com\/tech\/xmlsqc.  Fokou\u00e9 A. and Schloss B. 2004. XML Schema quality checker. Go online to http:\/\/www.alphaworks.ibm.com\/tech\/xmlsqc."},{"key":"e_1_2_1_18_1","unstructured":"Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Boston MA.   Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Boston MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1748"},{"key":"e_1_2_1_21_1","unstructured":"Jelliffe R. 2001. The current state of the art of schema languages for XML. Presentation at XML Asia Pacific Conference Sidney Australia.  Jelliffe R. 2001. The current state of the art of schema languages for XML. Presentation at XML Asia Pacific Conference Sidney Australia."},{"key":"e_1_2_1_22_1","unstructured":"Jelliffe R. 2005. Schematron. Go online to http:\/\/xml.ascc.net\/schematron\/.  Jelliffe R. 2005. Schematron. Go online to http:\/\/xml.ascc.net\/schematron\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016376608070"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 9th International Workshop on Database Programming Languages (DBPL","author":"Koch C.","year":"2003","unstructured":"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. 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."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/362084.362140"},{"key":"e_1_2_1_26_1","volume-title":"Keeping chess alive---do we need 1-unambiguous content models? Presentation at Extreme Markup Languages Conference","author":"Mani M.","year":"2001","unstructured":"Mani , M. 2001. Keeping chess alive---do we need 1-unambiguous content models? Presentation at Extreme Markup Languages Conference 2001 . Mani, M. 2001. Keeping chess alive---do we need 1-unambiguous content models? Presentation at Extreme Markup Languages Conference 2001."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055563"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.035"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS","author":"Martens W.","year":"2004","unstructured":"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. 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."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_15"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Extreme Markup Languages 2001 Conference (Extreme Markup Languages","author":"Murata M.","year":"2001","unstructured":"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. 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."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/647852.737555"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB","author":"Sahuguet A.","year":"2000","unstructured":"Sahuguet , A. 2000 . Everything you ever wanted to know about DTDs, but were afraid to ask . In Proceedings of the International Workshop on the Web and Databases (WebDB 2000). Sahuguet, A. 2000. Everything you ever wanted to know about DTDs, but were afraid to ask. In Proceedings of the International Workshop on the Web and Databases (WebDB 2000)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604132"},{"key":"e_1_2_1_41_1","volume-title":"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","author":"Sperberg-McQueen C.","year":"2003","unstructured":"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. 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."},{"key":"e_1_2_1_42_1","unstructured":"Sperberg-McQueen C. and Thompson H. 2005. XML Schema. Go online to http:\/\/www.w3.org\/XML\/Schema.  Sperberg-McQueen C. and Thompson H. 2005. XML Schema. Go online to http:\/\/www.w3.org\/XML\/Schema."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 8th Workshop on Data Bases and Programming Languages (DBPL","author":"Suciu D.","year":"2001","unstructured":"Suciu , D. 2001 . Typechecking for semistructured data . In Proceedings of the 8th Workshop on Data Bases and Programming Languages (DBPL 2001). Springer, Berlin, Germany, 1--20. Suciu, D. 2001. Typechecking for semistructured data. In Proceedings of the 8th Workshop on Data Bases and Programming Languages (DBPL 2001). Springer, Berlin, Germany, 1--20."},{"key":"e_1_2_1_45_1","unstructured":"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\/.  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\/."},{"key":"e_1_2_1_46_1","unstructured":"van der Vlist E. 2002. XML Schema. O'Reilly Sebastopol CA.   van der Vlist E. 2002. XML Schema. O'Reilly Sebastopol CA."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Extreme Markup Languages 2003 Conference (Extreme Markup Languages","author":"Vitali F.","year":"2003","unstructured":"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 ). 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)."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1166074.1166076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:19:10Z","timestamp":1672262350000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1166074.1166076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1166074.1166076"],"URL":"https:\/\/doi.org\/10.1145\/1166074.1166076","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}