{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T03:42:20Z","timestamp":1765165340572,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0347065","IIS-0905276"],"award-info":[{"award-number":["IIS-0347065","IIS-0905276"]}],"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":[[2011,12]]},"abstract":"<jats:p>Schema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research investigations. Since in real-life applications schema mappings can be quite complex, it is important to develop methods and tools for understanding, explaining, and refining schema mappings. A promising approach to this effect is to use \u201cgood\u201d data examples that illustrate the schema mapping at hand.<\/jats:p>\n          <jats:p>\n            We develop a foundation for the systematic investigation of data examples and obtain a number of results on both the capabilities and the limitations of data examples in explaining and understanding schema mappings. We focus on schema mappings specified by source-to-target tuple generating dependencies (s-t tgds) and investigate the following problem: which classes of s-t tgds can be \u201cuniquely characterized\u201d by a finite set of data examples? Our investigation begins by considering finite sets of positive and negative examples, which are arguably the most natural choice of data examples. However, we show that they are not powerful enough to yield interesting unique characterizations. We then consider finite sets of universal examples, where a universal example is a pair consisting of a source instance and a universal solution for that source instance. We first show that unique characterizations via universal examples is, in a precise sense, equivalent to the existence of Armstrong bases (a relaxation of the classical notion of Armstrong databases). After this, we show that every schema mapping specified by LAV s-t tgds is uniquely characterized by a finite set of universal examples with respect to the class of LAV s-t tgds. Moreover, this positive result extends to the much broader classes of\n            <jats:italic>n<\/jats:italic>\n            -modular schema mappings,\n            <jats:italic>n<\/jats:italic>\n            a positive integer. Finally, we study the unique characterizability of GAV schema mappings. It turns out that some GAV schema mappings are uniquely characterizable by a finite set of universal examples with respect to the class of GAV s-t tgds, while others are not. By unveiling a tight connection with homomorphism dualities, we establish an effective, sound, and complete criterion for determining whether or not a GAV schema mapping is uniquely characterizable by a finite set of universal examples with respect to the class of GAV s-t tgds.\n          <\/jats:p>","DOI":"10.1145\/2043652.2043656","type":"journal-article","created":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T17:49:14Z","timestamp":1324403354000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Characterizing schema mappings via data examples"],"prefix":"10.1145","volume":"36","author":[{"given":"Bogdan","family":"Alexe","sequence":"first","affiliation":[{"name":"IBM Research - Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balder TEN","family":"Cate","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz CA and IBM Research - Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wang-Chiew","family":"Tan","sequence":"additional","affiliation":[{"name":"IBM Research - Almaden and University of California, Santa Cruz, San Jose, CA and Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,12,19]]},"reference":[{"unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1989323.1989338"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/ICDE.2008.4497409"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1807085.1807120"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.14778\/1453856.1453886"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IFIP Congress. 580--583","author":"Armstrong W. W.","year":"1974","unstructured":"Armstrong , W. W. 1974 . Dependency structures of data base relationships . In Proceedings of the IFIP Congress. 580--583 . Armstrong, W. W. 1974. Dependency structures of data base relationships. In Proceedings of the IFIP Congress. 580--583."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1514894.1514903"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","volume-title":"-C","author":"Cate B.","year":"2010","unstructured":"ten Cate , B. , Kolaitis , P. G. , and Tan , W . -C . 2010 . Database constraints and homomorphism dualities. In Principles and Practice of Constraint Programming, D. Cohen, Ed., Lecture Notes in Computer Science , vol. 6308 , Springer . ten Cate, B., Kolaitis, P. G., and Tan, W.-C. 2010. Database constraints and homomorphism dualities. In Principles and Practice of Constraint Programming, D. Cohen, Ed., Lecture Notes in Computer Science, vol. 6308, Springer."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 79--90","author":"Chiticariu L.","unstructured":"Chiticariu , L. and Tan , W. C . 2006. Debugging schema mappings with routes . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 79--90 . Chiticariu, L. and Tan, W. C. 2006. Debugging schema mappings with routes. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 79--90.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","first-page":"549","article-title":"Orientations and 3-colourings of graphs","volume":"45","author":"Cot\u00e9 A.","year":"2004","unstructured":"Cot\u00e9 , A. , Chouinard-Pr\u00e9vost , V. , and Tardif , C. 2004 . Orientations and 3-colourings of graphs . Commentationes Mathematicae Universitatis Carolinae 45 , 549 -- 553 . Cot\u00e9, A., Chouinard-Pr\u00e9vost, V., and Tardif, C. 2004. Orientations and 3-colourings of graphs. Commentationes Mathematicae Universitatis Carolinae 45, 549--553.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1376916.1376938"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.4153\/CJM-1959-003-9"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science.","author":"Fagin R.","year":"1982","unstructured":"Fagin , R. 1982 a. Armstrong databases . In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. Fagin, R. 1982a. Armstrong databases. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science."},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/322344.322347"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1O16\/j.tcs.2004.10.033"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1376916.1376922"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/0020-0190(83)90005-4"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of Symposia in Applied Mathematics, M. Anshel and W. Gewirtz, Eds.","volume":"71","author":"Fagin R.","unstructured":"Fagin , R. and Vardi , M. Y . 1986. The theory of data dependencies\u2014A survey . In Proceedings of Symposia in Applied Mathematics, M. Anshel and W. Gewirtz, Eds. Vol. 34\u2014Mathematics of Information Processing. American Mathematical Society, Providence, Rhode Island, 19-- 71 . Fagin, R. and Vardi, M. Y. 1986. The theory of data dependencies\u2014A survey. In Proceedings of Symposia in Applied Mathematics, M. Anshel and W. Gewirtz, Eds. Vol. 34\u2014Mathematics of Information Processing. American Mathematical Society, Providence, Rhode Island, 19--71."},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/j.ejc.2007.11.017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1189769.1189778"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/1667053.1667055"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/1066157.1066252"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/0012-365X(92)90282-K"},{"doi-asserted-by":"crossref","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press.  Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press.","key":"e_1_2_1_24_1","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/375663.375767"},{"volume-title":"A Shorter Model Theory","author":"Hodges W.","unstructured":"Hodges , W. 1997. A Shorter Model Theory . Cambridge University Press . Hodges, W. 1997. A Shorter Model Theory. Cambridge University Press.","key":"e_1_2_1_26_1"},{"doi-asserted-by":"crossref","unstructured":"Kearns M. J. and Vazirani U. V. 1994. An Introduction to Computational Learning Theory. The MIT Press.   Kearns M. J. and Vazirani U. V. 1994. An Introduction to Computational Learning Theory. The MIT Press.","key":"e_1_2_1_27_1","DOI":"10.7551\/mitpress\/3897.001.0001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1065167.1065176"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/543613.543644"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/0022-0000(89)90002-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1016\/0095-8956(89)90039-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1137\/S0895480104445630"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1002\/(SICI)1097-0118(199610)23:2%3C151::AID-JGT6%3E3.3.CO;2-K"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/1559845.1559873"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/1060590.1060647"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/1376916.1376921"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","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\/2043652.2043656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2043652.2043656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:19Z","timestamp":1750240459000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2043652.2043656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2043652.2043656"],"URL":"https:\/\/doi.org\/10.1145\/2043652.2043656","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}