{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T02:11:55Z","timestamp":1792807915515,"version":"4.5.0"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>The presence of a schema offers many advantages in processing, translating, querying, and storage of XML data. Basic decision problems such as equivalence, inclusion, and nonemptiness of intersection of schemas form the basic building blocks for schema optimization and integration, and algorithms for static analysis of transformations. It is thereby paramount to establish the exact complexity of these problems. Most common schema languages for XML can be adequately modeled by some kind of grammar with regular expressions at right-hand sides. In this paper, we observe that, apart from the usual regular operators of union, concatenation, and Kleene-star, schema languages also allow numerical occurrence constraints and interleaving operators. Although the expressiveness of these operators remains within the regular languages, the presence or absence of these operators has a significant impact on the complexity of the basic decision problems. We present a complete overview of the complexity of the basic decision problems for DTDs, XSDs, and Relax NG with regular expressions incorporating numerical occurrence constraints and interleaving. We also discuss chain regular expressions and the complexity of the schema simplification problem incorporating the new operators.<\/jats:p>","DOI":"10.1137\/070697367","type":"journal-article","created":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T18:15:09Z","timestamp":1233339309000},"page":"2021-2043","source":"Crossref","is-referenced-by-count":26,"title":["Optimizing Schema Languages for XML: Numerical Constraints and Interleaving"],"prefix":"10.1137","volume":"38","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"key":"R1","unstructured":"S. Abiteboul, P. Buneman, and D. Suciu,\n                      Data on the Web: From Relations to Semistructured Data and XML\n                      , Morgan Kaufmann, San Francisco, 1999."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"R3","unstructured":"G. J. Bex, F. Neven, T. Schwentick, and K. Tuyls,\n                      Inference of concise DTDs from XML data\n                      , in Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), 2006, pp. 115\u2013126."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. J. Bex, F. Neven, and J. Van den Bussche,\n                      DTDs versus XML schema: A practical study\n                      , in Proceedings of the 7th International Workshop on the Web and Databases (WebDB), 2004, pp. 79\u201384.","DOI":"10.1145\/1017074.1017095"},{"key":"R5","unstructured":"A. Br\u00fcggemann-Klein, M. Murata, and D. Wood,\n                      Regular Tree and Regular Hedge Languages over Unranked Alphabets: Version 1, April 3, $2001$\n                      , Technical report HKUST-TCSC-2001-0, The Hong Kong University of Science and Technology, Hong Kong, 2001."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Br\u00fcggemann-Klein,\n                      Unambiguity of extended regular expressions in SGML document grammars\n                      , in Proceedings of the First Annual European Symposium on Algorithms (ESA), Springer, London, 1993, pp. 73\u201384.","DOI":"10.1007\/3-540-57273-2_45"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"R9","unstructured":"J. Clark and M. Murata,\n                      RELAX NG Specification\n                      , OASIS, 2001."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Cristau, C. L\u00f6ding, and W. Thomas,\n                      Deterministic automata on unranked trees\n                      , in Fundamentals of Computation Theory (FCT), Lecture Notes in Comput. Sci. 3623, M. Liskiewicz and R. Reischuk, eds., Springer, Berlin, 2005, pp. 68\u201379.","DOI":"10.1007\/11537311_7"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Dal-Zilio and D. Lugiez,\n                      XML schema, tree logic and sheaves automata\n                      , in Rewriting Techniques and Applications (RTA), Lecture Notes in Comput. Sci. 2706, R. Nieuwenhuis, ed., Springer, Berlin, 2003, pp. 246\u2013263.","DOI":"10.1007\/3-540-44881-0_18"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. Deutsch, M. F. Fernandez, and D. Suciu,\n                      Storing semistructured data with STORED\n                      , in Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, 1999, pp. 431\u2013442.","DOI":"10.1145\/304182.304220"},{"key":"R13","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , Freeman, San Francisco, 1979."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"W. Gelade,\n                      Succinctness of regular expressions with interleaving, intersection and counting\n                      , in Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Comput. Sci. 5162, Springer, Berlin, 2008, pp. 363\u2013374.","DOI":"10.1007\/978-3-540-85238-4_29"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra and M. Ogihara,\n                      The Complexity Theory Companion\n                      , Springer, Berlin, 2002.","DOI":"10.1007\/978-3-662-04880-1"},{"key":"R16","unstructured":"J. E. Hopcroft, R. Motwani, and J. D. Ullman,\n                      Introduction to Automata Theory, Languages, and Computation\n                      , 3rd ed., Addison\u2013Wesley, Reading, MA, 2007."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00109-7"},{"key":"R19","unstructured":"P. Kilpel\u00e4inen and R. Tuhkanen,\n                      Regular expressions with numerical occurrence indicators\u2014preliminary results\n                      , in Proceedings of the Eighth Symposium on Programming Languages and Software Tools (SPLST), 2003, pp. 163\u2013173."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. Kilpel\u00e4inen and R. Tuhkanen,\n                      Towards efficient implementation of XML schemacontent models\n                      , in Proceedings of the 2004 ACM Symposium on Document Engineering(DOCENG), ACM, New York, 2004, pp. 239\u2013241.","DOI":"10.1145\/1030397.1030441"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.12.003"},{"key":"R22","unstructured":"P. Kilpel\u00e4inen,\n                      Inclusion of Unambiguous $#$REs Is NP-Hard\n                      , unpublished note, University of Kuopio, Kuopio, Finland, 2004."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier,\n                      Schema-based scheduling of event processors and buffer minimization for queries on structured data streams\n                      , in Proceedings of the International Conference on Very Large Data Bases (VLDB), 2004, pp. 228\u2013239.","DOI":"10.1016\/B978-012088469-8\/50023-1"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"D. Kozen,\n                      Lower bounds for natural proof systems\n                      , in Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1977, pp. 254\u2013266.","DOI":"10.1109\/SFCS.1977.16"},{"key":"R25","unstructured":"M. Mani,\n                      Keeping chess alive\u2014Do we need 1-unambiguous content models?\n                      , talk given at Extreme Markup Languages, Montreal, 2001."},{"key":"R26","unstructured":"I. Manolescu, D. Florescu, and D. Kossmann,\n                      Answering XML queries on heterogeneous data sources\n                      , in Proceedings of the International Conference on Very Large Data Bases (VLDB), 2001, pp. 241\u2013250."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"W. Martens, F. Neven, and T. Schwentick,\n                      Complexity of decision problems for simple regular expressions\n                      , in Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS), J. Fiala, V. Koubek, and J. Kratochv\u00edl, eds., Lecture Notes in Comput. Sci. 3153, Springer, Berlin, 2004, pp. 889\u2013900.","DOI":"10.1007\/978-3-540-28629-5_70"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.005"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.021"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"A. R. Meyer and L. J. Stockmeyer,\n                      The equivalence problem for regular expressions with squaring requires exponential space\n                      , in Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, 1972, pp. 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick,\n                      On the complexity of XPath containment in the presence of disjunction, DTDs, and variables\n                      , Log. Methods Comput. Sci., 2 (2006), 3:1.","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Y. Papakonstantinou and V. Vianu,\n                      DTD inference for views of XML data\n                      , in Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), ACM Press, New York, 2000, pp. 35\u201346.","DOI":"10.1145\/335168.335173"},{"key":"R36","unstructured":"F. Reuter,\n                      An Enhanced W3C XML Schema-Based Language Binding for Object Oriented Programming Languages\n                      , manuscript, 2006."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00130-8"},{"key":"R39","unstructured":"C. M. Sperberg-McQueen and H. Thompson,\n                      XML Schema\n                      , http:\/\/www.w3.org\/XML\/ Schema (2005)."},{"key":"R40","unstructured":"C. M. Sperberg-McQueen,\n                      XML Schema $1.0$: A language for document grammars\n                      , in XML2003, 2003; available online at http:\/\/www.idealliance.org\/papers\/dx_xml03\/index.html."},{"key":"R41","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer,\n                      Word problems requiring exponential time: Preliminary report\n                      , in Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC), 1973, pp. 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"R42","unstructured":"E. van der Vlist,\n                      XML Schema\n                      , O'Reilly, Sebastopol, CA, 2002."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"P. van Emde Boas,\n                      The convenience of tilings\n                      , in Complexity, Logic, and Recursion Theory, Lect. Notes Pure Appl. Math. 187, Dekker, New York, 1997, pp. 331\u2013363.","DOI":"10.1201\/9780429187490-12"},{"key":"R44","unstructured":"G. Wang, M. Liu, J. X. Yu, B. Sun, G. Yu, J. Lv, and H. Lu,\n                      Effective schema-based XML query optimization techniques\n                      , in Proceedings of the Seventh International Database Engineering and Applications Symposium (IDEAS), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 230\u2013235."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070697367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:50Z","timestamp":1787336570000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070697367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070697367"],"URL":"https:\/\/doi.org\/10.1137\/070697367","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}