{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T05:37:19Z","timestamp":1767850639087,"version":"3.49.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7-ICT-233599"],"award-info":[{"award-number":["FP7-ICT-233599"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            Inferring an appropriate DTD or XML Schema Definition (XSD) for a given collection of XML documents essentially reduces to learning\n            <jats:italic>deterministic<\/jats:italic>\n            regular expressions from sets of positive example words. Unfortunately, there is no algorithm capable of learning the complete class of deterministic regular expressions from positive examples only, as we will show. The regular expressions occurring in practical DTDs and XSDs, however, are such that every alphabet symbol occurs only a small number of times. As such, in practice it suffices to learn the subclass of deterministic regular expressions in which each alphabet symbol occurs at most\n            <jats:italic>k<\/jats:italic>\n            times, for some small\n            <jats:italic>k<\/jats:italic>\n            . We refer to such expressions as\n            <jats:italic>k<\/jats:italic>\n            -occurrence regular expressions (\n            <jats:italic>k<\/jats:italic>\n            -OREs for short). Motivated by this observation, we provide a probabilistic algorithm that learns\n            <jats:italic>k<\/jats:italic>\n            -OREs for increasing values of k, and selects the deterministic one that best describes the sample based on a Minimum Description Length argument. The effectiveness of the method is empirically validated both on real world and synthetic data. Furthermore, the method is shown to be conservative over the simpler classes of expressions considered in previous work.\n          <\/jats:p>","DOI":"10.1145\/1841909.1841911","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T14:38:15Z","timestamp":1286289495000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data"],"prefix":"10.1145","volume":"4","author":[{"given":"Geert Jan","family":"Bex","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wouter","family":"Gelade","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Symposium on Information Theory.","author":"Adriaans P.","unstructured":"}} Adriaans , P. and Vit\u00e1nyi , P . 2006. The power and perils of MDL . In Proceedings of the International Symposium on Information Theory. }}Adriaans, P. and Vit\u00e1nyi, P. 2006. The power and perils of MDL. In Proceedings of the International Symposium on Information Theory."},{"key":"e_1_2_1_2_1","volume-title":"Department of Computer Science","author":"Ahonen H.","unstructured":"}} Ahonen , H. 1996. Generating Grammars for structured documents using grammatical inference methods. Tech. rep. A-1996-4 , Department of Computer Science , University of Finland. }}Ahonen, H. 1996. Generating Grammars for structured documents using grammatical inference methods. Tech. rep. A-1996-4, Department of Computer Science, University of Finland."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/356914.356918"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-005-1544-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 1st Biennial Conference on Innovative Data Systems Research.","author":"Bernstein P. A.","year":"2003","unstructured":"}} Bernstein , P. A. 2003 . Applying model management to classical meta data problems . In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research. }}Bernstein, P. A. 2003. Applying model management to classical meta data problems. In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. 115--126","author":"Bex G. J.","unstructured":"}} Bex , G. J. , Neven , F. , Schwentick , T. , and Tuyls , K . 2006. Inference of concise DTDs from XML data . In Proceedings of the 32nd International Conference on Very Large Data Bases. 115--126 . }}Bex, G. J., Neven, F., Schwentick, T., and Tuyls, K. 2006. Inference of concise DTDs from XML data. In Proceedings of the 32nd International Conference on Very Large Data Bases. 115--126."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Databases. 998--1009","author":"Bex G. J.","unstructured":"}} Bex , G. J. , Neven , F. , and Vansummeren , S . 2007. Inferring XML Schema definitions from XML data . In Proceedings of the 33rd International Conference on Very Large Databases. 998--1009 . }}Bex, G. J., Neven, F., and Vansummeren, S. 2007. Inferring XML Schema definitions from XML data. In Proceedings of the 33rd International Conference on Very Large Databases. 998--1009."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367609"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168340"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2688"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 6th International Conference on Database Theory (ICDT\u201997)","volume":"1186","author":"Buneman P.","unstructured":"}} Buneman , P. , Davidson , S. B. , Fernandez , M. F. , and Suciu , D . 1997. Adding structure to unstructured data . In Proceedings of the 6th International Conference on Database Theory (ICDT\u201997) . F. N. Afrati and P. G. Kolaitis, Eds. Lecture Notes in Computer Science , vol. 1186 . Springer, 336--350. }}Buneman, P., Davidson, S. B., Fernandez, M. F., and Suciu, D. 1997. Adding structure to unstructured data. In Proceedings of the 6th International Conference on Database Theory (ICDT\u201997). F. N. Afrati and P. G. Kolaitis, Eds. Lecture Notes in Computer Science, vol. 1186. Springer, 336--350."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0172-6"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 8th International Workshop on Knowledge Representation meets Databases.","author":"Chidlovskii B.","year":"2001","unstructured":"}} Chidlovskii , B. 2001 . Schema extraction from XML: A grammatical inference approach . In Proceedings of the 8th International Workshop on Knowledge Representation meets Databases. }}Chidlovskii, B. 2001. Schema extraction from XML: A grammatical inference approach. In Proceedings of the 8th International Workshop on Knowledge Representation meets Databases."},{"key":"e_1_2_1_18_1","unstructured":"}}Clark J. Trang: Multi-format schema converter based on RELAX NG. http:\/\/www.thaiopensource.com\/relaxng\/trang.html.  }} Clark J. Trang: Multi-format schema converter based on RELAX NG. http:\/\/www.thaiopensource.com\/relaxng\/trang.html."},{"key":"e_1_2_1_19_1","unstructured":"}}Clark J. and Murata M. 2001. RELAX NG specification. OASIS.  }} Clark J. and Murata M. 2001. RELAX NG specification. OASIS."},{"key":"e_1_2_1_20_1","unstructured":"}}Cover R. 2003. The Cover Pages. http:\/\/xml.coverpages.org\/.  }} Cover R. 2003. The Cover Pages. http:\/\/xml.coverpages.org\/."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases. 1297--1300","author":"Du F.","unstructured":"}} Du , F. , Amer-Yahia , S. , and Freire , J . 2004. ShreX: Managing XML documents in relational databases . In Proceedings of the 30th International Conference on Very Large Data Bases. 1297--1300 . }}Du, F., Amer-Yahia, S., and Freire, J. 2004. ShreX: Managing XML documents in relational databases. In Proceedings of the 30th International Conference on Very Large Data Bases. 1297--1300."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30195-0_26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564089_24"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkj149"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103822.1103832"},{"key":"e_1_2_1_27_1","unstructured":"}}Fran\u00e7ois J.-M. 2006. Jahmm. http:\/\/www.run.montefiore.ulg.ac.be\/~francois\/software\/jahmm\/.  }} Fran\u00e7ois J.-M. 2006. Jahmm. http:\/\/www.run.montefiore.ulg.ac.be\/~francois\/software\/jahmm\/."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564713"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 584--589","author":"Freitag D.","year":"2000","unstructured":"}} Freitag , D. and McCallum , A. 2000 . Information extraction with HMM structures learned by stochastic optimization . In Proceedings of the 17th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 584--589 . }}Freitag, D. and McCallum, A. 2000. Information extraction with HMM structures learned by stochastic optimization. In Proceedings of the 17th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 584--589."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.57687"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021560618289"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 325--336","author":"Gelade W.","unstructured":"}} Gelade , W. and Neven , F . 2008. Succinctness of the complement and intersection of regular expressions . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 325--336 . }}Gelade, W. and Neven, F. 2008. Succinctness of the complement and intersection of regular expressions. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 325--336."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases. 436--445","author":"Goldman R.","unstructured":"}} Goldman , R. and Widom , J . 1997. DataGuides: Enabling query formulation and optimization in semistructured databases . In Proceedings of the 23rd International Conference on Very Large Data Bases. 436--445 . }}Goldman, R. and Widom, J. 1997. DataGuides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases. 436--445."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2006.166"},{"key":"e_1_2_1_37_1","unstructured":"}}Hopcroft J. and Ullman J. 2007. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.   }} Hopcroft J. and Ullman J. 2007. Introduction to Automata Theory Languages and Computation . Addison-Wesley Reading MA."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases. 228--239","author":"Koch C.","unstructured":"}} Koch , C. , Scherzinger , S. , Schweikardt , N. , and Stegmaier , B . 2004. Schema-based scheduling of event processors and buffer minimization for queries on structured data streams . In Proceedings of the 30th International Conference on Very Large Data Bases. 228--239 . }}Koch, C., Scherzinger, S., Schweikardt, N., and Stegmaier, B. 2004. Schema-based scheduling of event processors and buffer minimization for queries on structured data streams. In Proceedings of the 30th International Conference on Very Large Data Bases. 228--239."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of 27th International Conference on Very Large Data Bases. 241--250","author":"Manolescu I.","unstructured":"}} Manolescu , I. , Florescu , D. , and Kossmann , D . 2001. Answering XML queries on heterogeneous data sources . In Proceedings of 27th International Conference on Very Large Data Bases. 241--250 . }}Manolescu, I., Florescu, D., and Kossmann, D. 2001. Answering XML queries on heterogeneous data sources. In Proceedings of 27th International Conference on Very Large Data Bases. 241--250."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775223"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276331"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the International Workshop on Analogical and Inductive Inference","author":"Pitt L.","unstructured":"}} Pitt , L. 1989. Inductive inference, DFAs, and computational complexity . In Proceedings of the International Workshop on Analogical and Inductive Inference . K. P. Jantke, Ed. Lecture Notes in Computer Science, vol. 397 . Springer-Verlag , 18--44. }}Pitt, L. 1989. Inductive inference, DFAs, and computational complexity. In Proceedings of the International Workshop on Analogical and Inductive Inference. K. P. Jantke, Ed. Lecture Notes in Computer Science, vol. 397. Springer-Verlag, 18--44."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.280355"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.18626"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 3rd International Workshop on The World Wide Web and Databases","author":"Sahuguet A.","unstructured":"}} Sahuguet , A. 2000. Everything you ever wanted to know about DTDs, but were afraid to ask (Extended Abstract) . In Proceedings of the 3rd International Workshop on The World Wide Web and Databases . D. Suciu and G. Vossen, Eds. Lecture Notes in Computer Science, vol. 1997 . Springer , 171--183. }}Sahuguet, A. 2000. Everything you ever wanted to know about DTDs, but were afraid to ask (Extended Abstract). In Proceedings of the 3rd International Workshop on The World Wide Web and Databases. D. Suciu and G. Vossen, Eds. Lecture Notes in Computer Science, vol. 1997. Springer, 171--183."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00014-5"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502613"},{"key":"e_1_2_1_51_1","unstructured":"}}Thompson H. Beech D. Maloney M. and Mendelsohn N. 2001. XML Schema part 1: Structures. W3C.  }} Thompson H. Beech D. Maloney M. and Mendelsohn N. 2001. XML Schema part 1: Structures . W3C."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007653929870"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1841909.1841911","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1841909.1841911","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:57Z","timestamp":1750248537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1841909.1841911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1841909.1841911"],"URL":"https:\/\/doi.org\/10.1145\/1841909.1841911","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}