{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:00Z","timestamp":1750306860117,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hercules Foundation and the Flemish Government"},{"name":"Fondecyt","award":["1131049, FP7-ICT-233599, FWO G082109"],"award-info":[{"award-number":["1131049, FP7-ICT-233599, FWO G082109"]}]},{"name":"ERC","award":["DIADEM, no. 246858"],"award-info":[{"award-number":["DIADEM, no. 246858"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>A great deal of research into the learning of schemas from XML data has been conducted in recent years to enable the automatic discovery of XML schemas from XML documents when no schema or only a low-quality one is available. Unfortunately, and in strong contrast to, for instance, the relational model, the automatic discovery of even the simplest of XML constraints, namely XML keys, has been left largely unexplored in this context. A major obstacle here is the unavailability of a theory on reasoning about XML keys in the presence of XML schemas, which is needed to validate the quality of candidate keys. The present article embarks on a fundamental study of such a theory and classifies the complexity of several crucial properties concerning XML keys in the presence of an XSD, like, for instance, testing for consistency, boundedness, satisfiability, universality, and equivalence. Of independent interest, novel results are obtained related to cardinality estimation of XPath result sets. A mining algorithm is then developed within the framework of levelwise search. The algorithm leverages known discovery algorithms for functional dependencies in the relational model, but incorporates the properties mentioned before to assess and refine the quality of derived keys. An experimental study on an extensive body of real-world XML data evaluating the effectiveness of the proposed algorithm is provided.<\/jats:p>","DOI":"10.1145\/2638547","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Discovering XSD Keys from XML Data"],"prefix":"10.1145","volume":"39","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"PUC Chile and University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonny","family":"Daenen","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Ugarte","sequence":"additional","affiliation":[{"name":"PUC Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan Van Den","family":"Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles (ULB)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274591"},{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_2_2_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463705"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/648315.756182"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39429-7_12"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559922"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1841909.1841911"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325964"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376750"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'89)","author":"Bitton Dina","year":"1989","unstructured":"Dina Bitton , Jeffrey Millman , and Solveig Torgersen . 1989 . A feasibility and performance study of dependency inference . In Proceedings of the International Conference on Data Engineering (ICDE'89) . 635--641. Dina Bitton, Jeffrey Millman, and Solveig Torgersen. 1989. A feasibility and performance study of dependency inference. In Proceedings of the International Conference on Data Engineering (ICDE'89). 635--641."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_17"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88282-4_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2688"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00223-2"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(03)00028-0"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDIM.2011.6093314"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021560618289"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584867"},{"key":"e_1_2_2_21_1","unstructured":"Steven Grijzenhout and Maarten Marx. 2010. University of amsterdam XML web collection. http:\/\/data.politicalmashup.nl\/sgrijzen\/xmlweb\/.  Steven Grijzenhout and Maarten Marx. 2010. University of amsterdam XML web collection. http:\/\/data.politicalmashup.nl\/sgrijzen\/xmlweb\/."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538909.1538912"},{"key":"e_1_2_2_23_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"2003","unstructured":"John E. Hopcroft , Rajeev Motwani , and Jeffrey D . Ullman . 2003 . Introduction to Automata Theory, Languages, and Computation. Addison-Wesley . John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2003. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73734"},{"volume-title":"The Design of Relational Databases","author":"Mannila Heikki","key":"e_1_2_2_26_1","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4 . 1991. The Design of Relational Databases . Addison-Wesley . Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1991. The Design of Relational Databases. Addison-Wesley."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796218281"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324185.1324188"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529282.1529414"},{"key":"e_1_2_2_33_1","volume-title":"Database Management Systems","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan and Johannes Gehrke . 2003. Database Management Systems 3 rd Ed. McGraw-Hill . Raghu Ramakrishnan and Johannes Gehrke. 2003. Database Management Systems 3rd Ed. McGraw-Hill.","edition":"3"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214044"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"volume-title":"Complexity, Logic, and Recursion Theory","author":"Emde Boas Peter Van","key":"e_1_2_2_37_1","unstructured":"Peter Van Emde Boas . 1997. The convenience of tilings . In Complexity, Logic, and Recursion Theory , Marcel Dekker , 331--363. Peter Van Emde Boas. 1997. The convenience of tilings. In Complexity, Logic, and Recursion Theory, Marcel Dekker, 331--363."},{"key":"e_1_2_2_38_1","volume-title":"XML Schema Part 1: Structures","author":"C.","unstructured":"W3 C. 2004. XML Schema Part 1: Structures 2 nd Ed. http:\/\/www.w3.org\/TR\/xmlschema-1\/#cIdentity-constraint W3C. 2004. XML Schema Part 1: Structures 2nd Ed. http:\/\/www.w3.org\/TR\/xmlschema-1\/#cIdentity-constraint","edition":"2"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0063-0"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638547","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2638547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:33Z","timestamp":1750234233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2638547"],"URL":"https:\/\/doi.org\/10.1145\/2638547","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}