{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T00:59:20Z","timestamp":1770512360702,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T00:00:00Z","timestamp":1503532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MA 4938\/2-1"],"award-info":[{"award-number":["MA 4938\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Future and Emerging Technologies"},{"name":"Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX","award":["FP7-ICT-233599"],"award-info":[{"award-number":["FP7-ICT-233599"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>While the migration from DTD to XML Schema was driven by a need for increased expressivity and flexibility, the latter was also significantly more complex to use and understand. Whereas DTDs are characterized by their simplicity, XML Schema Documents are notoriously difficult. In this article, we introduce the XML specification language BonXai, which incorporates many features of XML Schema but is arguably almost as easy to use as DTDs. In brief, the latter is achieved by sacrificing the explicit use of types in favor of simple patterns expressing contexts for elements. The goal of BonXai is not to replace XML Schema but rather to provide a simpler alternative for users who want to go beyond the expressiveness and features of DTD but do not need the explicit use of types. Furthermore, XML Schema processing tools can be used as a back-end for BonXai, since BonXai can be automatically converted into XML Schema. A particularly strong point of BonXai is its solid foundation rooted in a decade of theoretical work around pattern-based schemas. We present a formal model for a core fragment of BonXai and the translation algorithms to and from a core fragment of XML Schema. We prove that BonXai and XML Schema can be converted back-and-forth on the level of tree languages and we formally study the size trade-offs between the two languages.<\/jats:p>","DOI":"10.1145\/3105960","type":"journal-article","created":{"date-parts":[[2017,8,25]],"date-time":"2017-08-25T12:00:26Z","timestamp":1503662426000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["BonXai"],"prefix":"10.1145","volume":"42","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,8,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559922"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060848"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806434"},{"key":"e_1_2_1_6_1","first-page":"182","article-title":"One-unambiguous regular languages. Info","volume":"142","author":"Br\u00fcggemann-Klein A.","year":"1998","unstructured":"A. Br\u00fcggemann-Klein and D. Wood . 1998 . One-unambiguous regular languages. Info . Comput. 142 , 2 (1998), 182 -- 206 . A. Br\u00fcggemann-Klein and D. Wood. 1998. One-unambiguous regular languages. Info. Comput. 142, 2 (1998), 182--206.","journal-title":"Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_8_1","unstructured":"Russel Butek and Shannon Kendrick. 2011. Web services hints and tips: Avoid anonymous types. Retrieved from http:\/\/www.ibm.com\/developerworks\/webservices\/library\/ws-avoid-anonymous-types\/ws-avoid-anonymous-types-pdf.pdf.  Russel Butek and Shannon Kendrick. 2011. Web services hints and tips: Avoid anonymous types. Retrieved from http:\/\/www.ibm.com\/developerworks\/webservices\/library\/ws-avoid-anonymous-types\/ws-avoid-anonymous-types-pdf.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22321-1_12"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988695"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Foundations of Software Science and Computation (FOSSACS\u201913)","author":"Czerwi\u0144ski W.","unstructured":"W. Czerwi\u0144ski , C. David , K. Losemann , and W. Martens . 2013. Deciding definability by deterministic regular expressions . In Proceedings of the International Conference on Foundations of Software Science and Computation (FOSSACS\u201913) . 289--304. W. Czerwi\u0144ski, C. David, K. Losemann, and W. Martens. 2013. Deciding definability by deterministic regular expressions. In Proceedings of the International Conference on Foundations of Software Science and Computation (FOSSACS\u201913). 289--304."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201913)","author":"Czerwi\u0144ski W.","unstructured":"W. Czerwi\u0144ski , W. Martens , and T. Masopust . 2013. Efficient separability of regular languages by subsequences and suffixes . In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201913) . 150--161. W. Czerwi\u0144ski, W. Martens, and T. Masopust. 2013. Efficient separability of regular languages by subsequences and suffixes. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201913). 150--161."},{"key":"e_1_2_1_13_1","volume-title":"Document Structure Description (DSD).","author":"DSD.","year":"2002","unstructured":"DSD. 2002. Document Structure Description (DSD). Retrieved from http:\/\/www.brics.dk\/DSD\/ ( 2002 ). DSD. 2002. Document Structure Description (DSD). Retrieved from http:\/\/www.brics.dk\/DSD\/ (2002)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"key":"e_1_2_1_15_1","unstructured":"Davide Fiorello Nicola Gessa Paolo Marinelli and Fabio Vitali. 2004. DTD++ 2.0: Adding support for co-constraints. In Extreme Markup Languages.  Davide Fiorello Nicola Gessa Paolo Marinelli and Fabio Vitali. 2004. DTD++ 2.0: Adding support for co-constraints. In Extreme Markup Languages."},{"key":"e_1_2_1_16_1","unstructured":"S. Gao C. M. Sperberg-McQueen H. Thompson N. Mendelsohn D. Beech and M. Maloney. 2012. W3C XML Schema Definition Language (XSD) 1.1 Part 1: Structures. Retrieved from http:\/\/www.w3.org\/TR\/2012\/REC-xmlschema11-1-20120405\/ (April 2012).  S. Gao C. M. Sperberg-McQueen H. Thompson N. Mendelsohn D. Beech and M. Maloney. 2012. W3C XML Schema Definition Language (XSD) 1.1 Part 1: Structures. Retrieved from http:\/\/www.w3.org\/TR\/2012\/REC-xmlschema11-1-20120405\/ (April 2012)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.008"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT\u201915)","author":"Hofman P.","unstructured":"P. Hofman and W. Martens . 2015. Separability by short subsequences and subwords . In Proceedings of the International Conference on Database Theory (ICDT\u201915) . 230--246. P. Hofman and W. Martens. 2015. Separability by short subsequences and subwords. In Proceedings of the International Conference on Database Theory (ICDT\u201915). 230--246."},{"key":"e_1_2_1_19_1","volume-title":"jEdit Programmer\u2019s Text Editor","unstructured":"JEdit. jEdit Programmer\u2019s Text Editor . Retrieved from www.jedit.org. JEdit. jEdit Programmer\u2019s Text Editor. Retrieved from www.jedit.org."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265552"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_56"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"W. Martens V. Mattick M. Niewerth S. Agarwal N. Douib O. Garbe D. G\u00fcnther D. Oliana J. Kroniger F. L\u00fccke T. Melikoglu K. Nordmann G. \u00d6zen T. Schlitt L. Schmidt J. Westhoff and D. Wolff. 2015. Design of the BonXai Schema Language (draft 2015). Retrieved from http:\/\/www.bonxai.org\/downloads\/bonxai-design.pdf.  W. Martens V. Mattick M. Niewerth S. Agarwal N. Douib O. Garbe D. G\u00fcnther D. Oliana J. Kroniger F. L\u00fccke T. Melikoglu K. Nordmann G. \u00d6zen T. Schlitt L. Schmidt J. Westhoff and D. Wolff. 2015. Design of the BonXai Schema Language (draft 2015). Retrieved from http:\/\/www.bonxai.org\/downloads\/bonxai-design.pdf.","DOI":"10.1145\/2745754.2745774"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367556"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745774"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Wim Martens Frank Neven Matthias Niewerth and Thomas Schwentick. 2017. BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema (data set). Retrieved from http:\/\/bonxai.org\/downloads.html.  Wim Martens Frank Neven Matthias Niewerth and Thomas Schwentick. 2017. BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema (data set). Retrieved from http:\/\/bonxai.org\/downloads.html.","DOI":"10.1145\/3105960"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324185.1324188"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.021"},{"key":"e_1_2_1_29_1","volume-title":"An Introduction to XML and Web Technologies","author":"M\u00f8ller Anders","unstructured":"Anders M\u00f8ller and Michael Schwartzbach . 2006. An Introduction to XML and Web Technologies . Addison-Wesley . Anders M\u00f8ller and Michael Schwartzbach. 2006. An Introduction to XML and Web Technologies. Addison-Wesley."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_1_31_1","unstructured":"D. Peterson S. Gao A. Malhotra C. M. Sperberg-McQueen H. Thompson and P. V. Biron. 2012. W3C XML Schema Definition Language (XSD) 1.1 Part 2: Datatypes. Retrieved from http:\/\/www.w3.org\/TR\/2012\/REC-xmlschema11-2-20120405\/.  D. Peterson S. Gao A. Malhotra C. M. Sperberg-McQueen H. Thompson and P. V. Biron. 2012. W3C XML Schema Definition Language (XSD) 1.1 Part 2: Datatypes. Retrieved from http:\/\/www.w3.org\/TR\/2012\/REC-xmlschema11-2-20120405\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_64"},{"key":"e_1_2_1_33_1","volume-title":"Relax NG Specification.","author":"NG.","year":"2001","unstructured":"Relax NG. 2001. Relax NG Specification. Retrieved from http:\/\/www.relaxng.org\/spec-20011203.html ( 2001 ). RelaxNG. 2001. Relax NG Specification. Retrieved from http:\/\/www.relaxng.org\/spec-20011203.html (2001)."},{"key":"e_1_2_1_34_1","unstructured":"Schematron. 1999. Schematron.\n   Retrieved from http:\/\/www.schematron.com\/ (\n  1999\n  ).  Schematron. 1999. Schematron. Retrieved from http:\/\/www.schematron.com\/ (1999)."},{"key":"e_1_2_1_35_1","unstructured":"C. M. Sperberg-McQueen and H. Thompson. 2005. XML Schema. Retrieved from http:\/\/www.w3.org\/XML\/Schema.  C. M. Sperberg-McQueen and H. Thompson. 2005. XML Schema. Retrieved from http:\/\/www.w3.org\/XML\/Schema."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105960","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:04Z","timestamp":1750217404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105960"}},"subtitle":["Combining the Simplicity of DTD with the Expressiveness of XML Schema"],"short-title":[],"issued":{"date-parts":[[2017,8,24]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3105960"],"URL":"https:\/\/doi.org\/10.1145\/3105960","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,24]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}