{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T14:23:30Z","timestamp":1775831010889,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1.07E+13"],"award-info":[{"award-number":["1.07E+13"]}],"id":[{"id":"10.13039\/501100002850","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":[[2009,12]]},"abstract":"<jats:p>\n            A schema mapping is a specification that describes how data from a source schema is to be mapped to a target schema. Once the data has been transferred from the source to the target, a natural question is whether one can undo the process and recover the initial data, or at least part of it. In fact, it would be desirable to find a\n            <jats:italic>reverse<\/jats:italic>\n            schema mapping from target to source that specifies how to bring the exchanged data back.\n          <\/jats:p>\n          <jats:p>In this article, we introduce the notion of a recovery of a schema mapping: it is a reverse mapping, M\u2032 for a mapping M, that recovers sound data with respect to M. We further introduce an order relation on recoveries. This allows us to choose mappings that recover the maximum amount of sound information. We call such mappings maximum recoveries. We study maximum recoveries in detail, providing a necessary and sufficient condition for their existence. In particular, we prove that maximum recoveries exist for the class of mappings specified by FO-to-CQ source-to-target dependencies. This class subsumes the class of source-to-target tuple-generating dependencies used in previous work on data exchange. For the class of mappings specified by FO-to-CQ dependencies, we provide an exponential-time algorithm for computing maximum recoveries, and a simplified version for full dependencies that works in quadratic time. We also characterize the language needed to express maximum recoveries, and we include a detailed comparison with the notion of inverse (and quasi-inverse) mapping previously proposed in the data exchange literature. In particular, we show that maximum recoveries strictly generalize inverses. We finally study the complexity of some decision problems related to the notions of recovery and maximum recovery.<\/jats:p>","DOI":"10.1145\/1620585.1620589","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T20:53:14Z","timestamp":1260305594000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["The recovery of a schema mapping"],"prefix":"10.1145","volume":"34","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}]},{"given":"Jorge","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Oxford University, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2009,12,14]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353403"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055592"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376920"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).","author":"Bernstein P.","year":"2003","unstructured":"Bernstein , P. 2003 . Applying model management to classical meta data problems . In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR). Bernstein, P. 2003. Applying model management to classical meta data problems. In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247482"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265549"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT), 225--241","author":"Deutsch A.","unstructured":"Deutsch , A. and Tannen , V . 2003. Reformulation of XML queries and constraints . In Proceedings of the 9th International Conference on Database Theory (ICDT), 225--241 . Deutsch, A. and Tannen, V. 2003. Reformulation of XML queries and constraints. In Proceedings of the 9th International Conference on Database Theory (ICDT), 225--241."},{"key":"e_1_2_2_9_1","volume-title":"-I","author":"Du D.-Z.","year":"2000","unstructured":"Du , D.-Z. and Ko , K . -I . 2000 . Theory of Computational Complexity. Wiley-Interscience . Du, D.-Z. and Ko, K.-I. 2000. Theory of Computational Complexity. Wiley-Interscience."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263674"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292615"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366108"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142358"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/369275.369284"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_2_20_1","unstructured":"Hernich A. and Schweikardt N. 2009. Logic and data exchange: Which solutions are \u201cgood\u201d solutions&quest; Logic and the foundations of game and decision theory (LOFT 8). G. Bonanno B. L\u00f6we and W. van der Hoek 29 1 Texts in Logic and Games Amsterdam University Press. To appear.  Hernich A. and Schweikardt N. 2009. Logic and data exchange: Which solutions are \u201cgood\u201d solutions&quest; Logic and the foundations of game and decision theory (LOFT 8). G. Bonanno B. L\u00f6we and W. van der Hoek 29 1 Texts in Logic and Games Amsterdam University Press. To appear."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142357"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the 22th International Conference on Very Large Data Bases (VLDB), 251--262","author":"Levy A. Y.","unstructured":"Levy , A. Y. , Rajaraman , A. , and Ordille , J. J . 1996. Querying heterogeneous information sources using source descriptions . In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB), 251--262 . Levy, A. Y., Rajaraman, A., and Ordille, J. J. 1996. Querying heterogeneous information sources using source descriptions. In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB), 251--262."},{"key":"e_1_2_2_26_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory , 1 st edition. Springer-Verlag . Libkin, L. 2004. Elements of Finite Model Theory, 1st edition. Springer-Verlag.","edition":"1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142360"},{"key":"e_1_2_2_28_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_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066177"},{"key":"e_1_2_2_30_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1993. Computational Complexity . Addison Wesley . Papadimitriou, C. H. 1993. Computational Complexity. Addison Wesley."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767146"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1620585.1620589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1620585.1620589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:01Z","timestamp":1750249081000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1620585.1620589"}},"subtitle":["Bringing exchanged data back"],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1620585.1620589"],"URL":"https:\/\/doi.org\/10.1145\/1620585.1620589","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}