{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:27:45Z","timestamp":1758266865939,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["TIN2010-20967-C04-02"],"award-info":[{"award-number":["TIN2010-20967-C04-02"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0905276 and IIS-1217869"],"award-info":[{"award-number":["IIS-0905276 and IIS-1217869"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>A schema mapping is a high-level specification of the relationship between a source schema and a target schema. Recently, a line of research has emerged that aims at deriving schema mappings automatically or semi-automatically with the help of data examples, that is, pairs consisting of a source instance and a target instance that depict, in some precise sense, the intended behavior of the schema mapping. Several different uses of data examples for deriving, refining, or illustrating a schema mapping have already been proposed and studied.<\/jats:p>\n          <jats:p>In this article, we use the lens of computational learning theory to systematically investigate the problem of obtaining algorithmically a schema mapping from data examples. Our aim is to leverage the rich body of work on learning theory in order to develop a framework for exploring the power and the limitations of the various algorithmic methods for obtaining schema mappings from data examples. We focus on GAV schema mappings, that is, schema mappings specified by GAV (Global-As-View) constraints. GAV constraints are the most basic and the most widely supported language for specifying schema mappings. We present an efficient algorithm for learning GAV schema mappings using Angluin's model of exact learning with membership and equivalence queries. This is optimal, since we show that neither membership queries nor equivalence queries suffice, unless the source schema consists of unary relations only. We also obtain results concerning the learnability of schema mappings in the context of Valiant's well-known PAC (Probably-Approximately-Correct) learning model, and concerning the learnability of restricted classes of GAV schema mappings. Finally, as a byproduct of our work, we show that there is no efficient algorithm for approximating the shortest GAV schema mapping fitting a given set of examples, unless the source schema consists of unary relations only.<\/jats:p>","DOI":"10.1145\/2539032.2539035","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Learning schema mappings"],"prefix":"10.1145","volume":"38","author":[{"given":"Balder Ten","family":"Cate","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V\u00edctor","family":"Dalmau","sequence":"additional","affiliation":[{"name":"Universitat Pompeu Fabra, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz and IBM Research--Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497409"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807120"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989338"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022692615781"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992675"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_2_1_9_1","unstructured":"Anthony M. and Biggs N. 1992. An Introduction to Computational Learning Theory. Cambridge University Press.   Anthony M. and Biggs N. 1992. An Introduction to Computational Learning Theory. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1558334.1558341"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0059-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90114-1"},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Bonifati A.","key":"e_1_2_1_13_1","unstructured":"Bonifati , A. , Chang , E. Q. , Ho , T. , Lakshmanan , V. S. , and Pottinger , R . 2005. HePToX: Marrying XML and heterogeneity in your P2P databases . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . 1267--1270. Bonifati, A., Chang, E. Q., Ho, T., Lakshmanan, V. S., and Pottinger, R. 2005. HePToX: Marrying XML and heterogeneity in your P2P databases. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). 1267--1270."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274596"},{"key":"e_1_2_1_15_1","first-page":"475","volume-title":"Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP'10)","author":"Cate B.","unstructured":"ten Cate , B. , Kolaitis , P. G. , and Tan , W. C . 2010. Database constraints and homomorphism dualities . In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP'10) . 475 - 490 . ten Cate, B., Kolaitis, P. G., and Tan, W. C. 2010. Database constraints and homomorphism dualities. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP'10). 475-490."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_18_1","unstructured":"Ciucanu R. and Staworko S. 2013. Learning schemas for unordered xml. http:\/\/dbpl2013.inria.fr\/slides\/dbpl13-ciucanu-slides.pdf.  Ciucanu R. and Staworko S. 2013. Learning schemas for unordered xml. http:\/\/dbpl2013.inria.fr\/slides\/dbpl13-ciucanu-slides.pdf."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00034-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622826.1622842"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622826.1622843"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804683"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511532"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.208"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.221"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10562-3_2"},{"volume-title":"Proceedings of the 19th International Conference on Inductive Logic Programming (ILP'09)","author":"Gillis J. J. M.","key":"e_1_2_1_31_1","unstructured":"Gillis , J. J. M. and Van Den Bussche, J. 2009. Induction of relational algebra expressions . In Proceedings of the 19th International Conference on Inductive Logic Programming (ILP'09) . 25--33. Gillis, J. J. M. and Van Den Bussche, J. 2009. Induction of relational algebra expressions. In Proceedings of the 19th International Conference on Inductive Logic Programming (ILP'09). 25--33."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667055"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90294-K"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066252"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022601210986"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/234752.234755"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/647718.735908"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174647"},{"key":"e_1_2_1_40_1","unstructured":"Kearns M. J. and Vazirani U. V. 1997. An Introduction to Computational Learning Theory. The MIT Press.   Kearns M. J. and Vazirani U. V. 1997. An Introduction to Computational Learning Theory. The MIT Press."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274592"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559902"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI'85)","author":"Valiant L. G.","year":"1985","unstructured":"Valiant , L. G. 1985 . Learning disjunctions of conjunctions . In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI'85) . 560--566. Valiant, L. G. 1985. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI'85). 560--566."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375729"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2539032.2539035","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2539032.2539035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:50Z","timestamp":1750232090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2539032.2539035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2539032.2539035"],"URL":"https:\/\/doi.org\/10.1145\/2539032.2539035","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}