{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:27Z","timestamp":1740142767087,"version":"3.37.3"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T00:00:00Z","timestamp":1650240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872339","61472405"],"award-info":[{"award-number":["61872339","61472405"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,7,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The presence of a schema for eXtensible Markup Language (XML) documents has numerous advantages. Unfortunately, many XML documents in practice are not accompanied by a (valid) schema. Therefore, it is essential to devise algorithms to infer schemas from XML documents, where the fundamental task is learning regular expressions. In this paper, we focus on the learning of disjunctive multiplicity expressions (DMEs), a subclass of regular expressions that are particularly suitable to specify unordered models and have been used as the foundation of the schemas for unordered XML. Previous work for learning DME lacks inference algorithms that support positive and negative examples. Further, presently there has been no algorithm can learn DMEs extended with numeric occurrences. We address these challenges in the present paper and first propose a novel algorithm to learn DMEs from positive and negative examples by using genetic algorithms and parallel techniques. Then we extend DMEs to disjunctive generalized multiplicity expressions (DGMEs), which allow numeric occurrences and develop an algorithm to learn DGMEs from positive and negative examples. Finally, experimental results show that with only positive examples, our algorithm can generate a DME with an acceptable learning time, which can accept all positive examples, and when given both positive and negative examples, we can learn DMEs or DGMEs with high accuracy.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac037","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:13:14Z","timestamp":1649934794000},"page":"1733-1748","source":"Crossref","is-referenced-by-count":0,"title":["Learning Disjunctive Multiplicity Expressions and Disjunctive Generalize Multiplicity Expressions From Both Positive and Negative Examples"],"prefix":"10.1093","volume":"66","author":[{"given":"Yeting","family":"Li","sequence":"first","affiliation":[{"name":"State Key Laboratory of Computer Science , Institute of Software, Chinese Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Computer Science , Institute of Software, Chinese Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zixuan","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Computer Science , Institute of Software, Chinese Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,4,18]]},"reference":[{"key":"2023071709114531800_ref1","first-page":"1378","volume-title":"Proceedings of the 27th International Conference on Data Engineering, ICDE 2011","author":"Colazzo","year":"2011"},{"key":"2023071709114531800_ref2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.is.2018.02.007","article-title":"Schema profiling of document-oriented databases","volume":"75","author":"Gallinucci","year":"2018","journal-title":"Inform. Syst."},{"key":"2023071709114531800_ref3","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/3105960","article-title":"BonXai: combining the simplicity of DTD with the expressiveness of XML schema","volume":"42","author":"Martens","year":"2017","journal-title":"ACM Trans. Database Syst."},{"key":"2023071709114531800_ref4","doi-asserted-by":"crossref","first-page":"922","DOI":"10.14778\/2777598.2777601","article-title":"Schema management for document stores","volume":"8","author":"Wang","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"2023071709114531800_ref5","first-page":"70","volume-title":"Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Proceedings, Part II","author":"Li","year":"2019"},{"key":"2023071709114531800_ref6","first-page":"998","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases","author":"Bex","year":"2007"},{"key":"2023071709114531800_ref7","first-page":"519","volume-title":"Proceedings of the 19th International Conference on Data Engineering","author":"Wang","year":"2003"},{"key":"2023071709114531800_ref8","first-page":"31","volume-title":"Proceedings of the 14th International Symposium on Database Programming Languages, DBPL 2013","author":"Ciucanu","year":"2013"},{"year":"2015","author":"Boneva","article-title":"Shape expressions schemas","key":"2023071709114531800_ref9"},{"key":"2023071709114531800_ref10","first-page":"195","volume-title":"18th International Conference on Database Theory, ICDT 2015","author":"Staworko","year":"2015"},{"key":"2023071709114531800_ref11","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s00778-002-0076-7","article-title":"Tree pattern query minimization","volume":"11","author":"Amer-Yahia","year":"2002","journal-title":"VLDB J."},{"key":"2023071709114531800_ref12","first-page":"140","volume-title":"15th International Conference on Database Theory, ICDT 2012","author":"Staworko","year":"2012"},{"key":"2023071709114531800_ref13","first-page":"13","volume-title":"Proceedings of the 16th International Workshop on the Web and Databases, WebDB 2013","author":"Boneva","year":"2013"},{"key":"2023071709114531800_ref14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s00778-018-0532-7","article-title":"Parametric schema inference for massive JSON datasets","volume":"28","author":"Baazizi","year":"2019","journal-title":"VLDB J."},{"key":"2023071709114531800_ref15","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1841909.1841911","article-title":"Learning deterministic regular expressions for the inference of schemas from XML data","volume":"4","author":"Bex","year":"2010","journal-title":"ACM Trans. Web"},{"key":"2023071709114531800_ref16","first-page":"115","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases","author":"Bex","year":"2006"},{"key":"2023071709114531800_ref17","doi-asserted-by":"crossref","first-page":"1114","DOI":"10.1007\/s00224-014-9559-3","article-title":"Fast learning of restricted regular expressions and DTDs","volume":"57","author":"Freydenberger","year":"2015","journal-title":"Theory Comput. Syst."},{"key":"2023071709114531800_ref18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1023\/A:1021560618289","article-title":"XTRACT: learning document type descriptors from XML document collections","volume":"7","author":"Garofalakis","year":"2003","journal-title":"Data Min. Knowl. Discov."},{"key":"2023071709114531800_ref19","first-page":"586","volume-title":"Conceptual Modeling - 37th International Conference, ER 2018, Proceedings","author":"Li","year":"2018"},{"key":"2023071709114531800_ref20","first-page":"389","volume-title":"Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings, Part II","author":"Zhang","year":"2018"},{"key":"2023071709114531800_ref21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.14778\/1921071.1921078","article-title":"Update rewriting and integrity constraint maintenance in a schema evolution support system: PRISM++","volume":"4","author":"Curino","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"2023071709114531800_ref22","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/1103822.1103832","article-title":"Managing semi-structured data","volume":"3","author":"Florescu","year":"2005","journal-title":"ACM Queue"},{"key":"2023071709114531800_ref23","first-page":"434","volume-title":"Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Proceedings, Part III","author":"Li","year":"2019"},{"key":"2023071709114531800_ref24","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","article-title":"Asymptotic formulae in combinatory Analysis","volume":"s2\u201317","author":"Hardy","year":"1918","journal-title":"Proc. Lond. Math. Soc."},{"key":"2023071709114531800_ref25","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.ic.2008.12.008","article-title":"Algorithms for learning regular expressions from positive data","volume":"207","author":"Fernau","year":"2009","journal-title":"Inf. Comput."},{"key":"2023071709114531800_ref26","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/inco.1997.2695","article-title":"One-unambiguous regular languages","volume":"142","author":"Br\u00fcggemann-Klein","year":"1998","journal-title":"Inform. Comput."},{"key":"2023071709114531800_ref27","first-page":"889","volume-title":"Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22\u201327, 2004, Proceedings","author":"Martens","year":"2004"},{"key":"2023071709114531800_ref28","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jcss.2017.03.011","article-title":"Deciding definability by deterministic regular expressions","volume":"88","author":"Czerwinski","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"2023071709114531800_ref29","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00224-014-9576-2","article-title":"Deciding determinism of regular languages","volume":"57","author":"Lu","year":"2015","journal-title":"Theory Comput. Syst."},{"key":"2023071709114531800_ref30","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1137\/100814196","article-title":"Regular expressions with counting: weak versus strong determinism","volume":"41","author":"Gelade","year":"2012","journal-title":"SIAM J. Comput."},{"key":"2023071709114531800_ref31","first-page":"369","volume-title":"Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24\u201328, 2015, Proceedings, Part I","author":"Latte","year":"2015"},{"key":"2023071709114531800_ref32","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/962446.962448","article-title":"Containment and equivalence for a fragment of XPath","volume":"51","author":"Miklau","year":"2004","journal-title":"J. ACM"},{"key":"2023071709114531800_ref33","first-page":"315","article-title":"On the complexity of XPath containment in the presence of disjunction, DTDs, and variables","volume":"2","author":"Neven","year":"2006","journal-title":"Log. Methods Comput. Sci."},{"key":"2023071709114531800_ref34","first-page":"297","volume-title":"Database Theory - ICDT 2003, 9th International Conference, Siena, Italy, January 8\u201310, 2003, Proceedings","author":"Wood","year":"2003"},{"key":"2023071709114531800_ref35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1346330.1346333","article-title":"XPath satisfiability in the presence of DTDs","volume":"55","author":"Benedikt","year":"2008","journal-title":"J. ACM"},{"key":"2023071709114531800_ref36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3180281","article-title":"Minimization of tree patterns","volume":"65","author":"Czerwinski","year":"2018","journal-title":"J. ACM"},{"key":"2023071709114531800_ref37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1326554.1326556","article-title":"On the minimization of XPath queries","volume":"55","author":"Flesca","year":"2008","journal-title":"J. ACM"},{"key":"2023071709114531800_ref38","first-page":"61","volume-title":"EDBT 2008, 11th International Conference on Extending Database Technology, Nantes, France, March 25\u201329, 2008, Proceedings","author":"Kimelfeld","year":"2008"},{"key":"2023071709114531800_ref39","first-page":"13","volume-title":"Proceedings of the Fourth International Workshop on the Web and Databases, WebDB 2001","author":"Wood","year":"2001"},{"volume-title":"Proceedings of the 22nd International Conference on Data Engineering Workshops, ICDE 2006","year":"2006","author":"Hegewald","key":"2023071709114531800_ref40"},{"year":"2002","author":"Clark","article-title":"Trang: multi-format schema converter based on Relax NG","key":"2023071709114531800_ref41"},{"year":"2003","author":"Demany","article-title":"InstanceToSchema: Relax NG schema generator","key":"2023071709114531800_ref42"},{"key":"2023071709114531800_ref43","first-page":"400","volume-title":"Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings","author":"Kim","year":"2016"},{"key":"2023071709114531800_ref44","first-page":"303","volume-title":"Advanced Data Mining and Applications - 14th International Conference, ADMA 2018, Proceedings","author":"Li","year":"2018"},{"key":"2023071709114531800_ref45","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00224-014-9593-1","article-title":"Schemas for unordered XML on a DIME","volume":"57","author":"Boneva","year":"2015","journal-title":"Theory Comput. Syst."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1733\/50876263\/bxac037.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1733\/50876263\/bxac037.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T09:18:13Z","timestamp":1689585493000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/7\/1733\/6569539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,18]]},"references-count":45,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,4,18]]},"published-print":{"date-parts":[[2023,7,13]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac037","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2022,4,18]]}}}