{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T05:58:34Z","timestamp":1789883914018,"version":"4.0.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"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-0347065IIS-0430994"],"award-info":[{"award-number":["IIS-0347065IIS-0430994"]}],"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":[[2008,6]]},"abstract":"<jats:p>Schema mappings are high-level specifications that describe the relationship between two database schemas. Two operators on schema mappings, namely the composition operator and the inverse operator, are regarded as especially important. Progress on the study of the inverse operator was not made until very recently, as even finding the exact semantics of this operator turned out to be a fairly delicate task. Furthermore, this notion is rather restrictive, since it is rare that a schema mapping possesses an inverse.<\/jats:p>\n                  <jats:p>In this article, we introduce and study the notion of a quasi-inverse of a schema mapping. This notion is a principled relaxation of the notion of an inverse of a schema mapping; intuitively, it is obtained from the notion of an inverse by not differentiating between instances that are equivalent for data-exchange purposes. For schema mappings specified by source-to-target tuple-generating dependencies (s-t tgds), we give a necessary and sufficient combinatorial condition for the existence of a quasi-inverse, and then use this condition to obtain both positive and negative results about the existence of quasi-inverses. In particular, we show that every LAV (local-as-view) schema mapping has a quasi-inverse, but that there are schema mappings specified by full s-t tgds that have no quasi-inverse. After this, we study the language needed to express quasi-inverses of schema mappings specified by s-t tgds, and we obtain a complete characterization. We also characterize the language needed to express inverses of schema mappings, and thereby solve a problem left open in the earlier study of the inverse operator. Finally, we show that quasi-inverses can be used in many cases to recover the data that was exported by the original schema mapping when performing data exchange.<\/jats:p>","DOI":"10.1145\/1366102.1366108","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T08:09:19Z","timestamp":1214986159000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Quasi-inverses of schema mappings"],"prefix":"10.1145","volume":"33","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucian","family":"Popa","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wang-Chiew","family":"Tan","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,6,24]]},"reference":[{"key":"e_1_2_1_1_1","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_2_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220","author":"Bernstein P. A.","year":"2003","unstructured":"Bernstein , P. A. 2003 . Applying model management to classical meta-data problems . In Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220 . Bernstein, P. A. 2003. Applying model management to classical meta-data problems. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Workshop on Database Programming Languages (DBPL). 21--39","author":"Deutsch A.","unstructured":"Deutsch , A. and Tannen , V . 2001. Optimization properties for classes of conjunctive regular path queries . In Proceedings of the International Workshop on Database Programming Languages (DBPL). 21--39 . Deutsch, A. and Tannen, V. 2001. Optimization properties for classes of conjunctive regular path queries. In Proceedings of the International Workshop on Database Programming Languages (DBPL). 21--39."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292615"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055572"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265548"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Fagin R. and Nash A. 2007. The structure of inverses in schema mappings. IBM Research Report RJ10425.  Fagin R. and Nash A. 2007. The structure of inverses in schema mappings. IBM Research Report RJ10425.","DOI":"10.1145\/1265530.1265548"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583","author":"Madhavan J.","unstructured":"Madhavan , J. and Halevy , A. Y . 2003. Composing mappings among data sources . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583 . Madhavan, J. and Halevy, A. Y. 2003. Composing mappings among data sources. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583."},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","volume-title":"Generic model management: concepts and algorithms","author":"Melnik S.","unstructured":"Melnik , S. 2004. Generic model management: concepts and algorithms . Lecture Notes in Computer Science , vol. 2967 . Springer . Melnik, S. 2004. Generic model management: concepts and algorithms. Lecture Notes in Computer Science, vol. 2967. Springer."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065189"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1366102.1366108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1366102.1366108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:57:39Z","timestamp":1750240659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1366102.1366108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1366102.1366108"],"URL":"https:\/\/doi.org\/10.1145\/1366102.1366108","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}