Recovering Exchanged Data
Pages 105 - 116
Abstract
The inversion of data exchange mappings is one of the thorniest issues in data exchange. In this paper we study inverse data exchange from a novel perspective. Previous work has dealt with the static problem of finding a target-to-source mapping that captures the "inverse" of a source-to-target data exchange mapping. As we will show this approach has some drawbacks when it come actually applying the inverse mapping in order to recover a source instance from a materialized target instance. More specifically (1): As is well known, the inverse mappings have to be expressed in a much more powerful language than the mappings they invert. (2): There are simple cases where a source instance computed by the inverse mapping misses sound information that one may easily obtain when the particular target instance is available. (3): In some cases the inverse mapping can introduce unsound information in the recovered source instance.
To overcome these drawbacks we focus on the dynamic problem of recovering the source instance using the source-to-target mapping as well as a given target instance. Similarly to the problem of finding "good" target instances in forward data exchange, we look for "good" source instances to restore, i.e. to materialize. For this we introduce a new semantics to capture instance based recovery. We then show that given a target instance and a source-to-target mapping expressed as set of tuple generating dependencies, there are chase-based algorithms to compute a representative finite set of source instances that can be used to get certain answers to any union of conjunctive source queries. We also show that the instance based source recovery problem unfortunately is coNP-complete. We therefore present a polynomial time algorithm that computes a "small" set of source instances that can be used to get sound certain answers to any union of conjunctive source queries. This algorithm is then extended to extract more sound information for the case when only conjunctive source queries are allowed.
References
[1]
S. Abiteboul and O. M. Duschka. Complexity of answering queries using materialized views. In PODS, pages 254--263, 1998.
[2]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[3]
M. Arenas, R. Fagin, and A. Nash. Composition with target constraints. In ICDT, pages 129--142, 2010.
[4]
M. Arenas, R. Fagin, and A. Nash. Composition with target constraints. Logical Methods in Computer Science, 7(3), 2011.
[5]
M. Arenas, J. P erez, J. L. Reutter, and C. Riveros. Composition and inversion of schema mappings. SIGMOD Record, 38(3):17--28, 2009.
[6]
M. Arenas, J. P erez, J. L. Reutter, and C. Riveros. Inverting schema mappings: Bridging the gap between theory and practice. PVLDB, 2(1):1018--1029, 2009.
[7]
M. Arenas, J. P erez, J. L. Reutter, and C. Riveros. Query language-based inverses of schema mappings: semantics, computation, and closure properties. VLDB J., 21(6):823--842, 2012.
[8]
M. Arenas, J. P erez, and C. Riveros. The recovery of a schema mapping: Bringing exchanged data back. ACM Trans. Database Syst., 34(4), 2009.
[9]
C. Beeri and M. Y. Vardi. A proof procedure for data dependencies. J. ACM, 31(4):718--741, 1984.
[10]
P. A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003.
[11]
A. Deutsch, A. Nash, and J. B. Remmel. The chase revisited. In PODS, pages 149--158, 2008.
[12]
R. Fagin. Inverting schema mappings. ACM Trans. Database Syst., 32(4), 2007.
[13]
R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: semantics and query answering. Theor. Comput. Sci., 336(1):89--124, 2005.
[14]
R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Composing schema mappings: Second-order dependencies to the rescue. ACM Trans. Database Syst., 30(4):994--1055, 2005.
[15]
R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Quasi-inverses of schema mappings. ACM Trans. Database Syst., 33(2), 2008.
[16]
R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Reverse data exchange: Coping with nulls. ACM Trans. Database Syst., 36(2):11, 2011.
[17]
R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Schema mapping evolution through composition and inversion. In Z. Bellahsene, A. Bonifati, and E. Rahm, editors, Schema Matching and Mapping, Data-Centric Systems and Applications, pages 191--222. Springer, 2011.
[18]
G. Grahne and A. Onet. Representation systems for data exchange. In ICDT, pages 208--221, 2012.
[19]
P. Hell and J. Nesetril. Graphs And Homomorphisms. Oxford University Press, 2004.
[20]
L. Libkin. Data exchange and incomplete information. In PODS, pages 60--69, 2006.
[21]
L. Libkin. Incomplete information and certain answers in general data models. In PODS, pages 59--70, 2011.
[22]
A. Nash, P. A. Bernstein, and S. Melnik. Composition of mappings given by embedded dependencies. ACM Trans. Database Syst., 32(1):4, 2007.
[23]
C. H. Papadimitriou. Computational complexity. Addison-Wesley, 1994.
Recommendations
Anatomy of the Chase
A lot of research activity has recently taken place around the chase procedure, due to its usefulness in data integration, data exchange, query optimization, peer data exchange and data correspondence, to mention a few. As the chase has been investigated ...
Quasi-inverses of schema mappings
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 ...
Inverting schema mappings
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsA schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). Although the notion of an inverse of a schema mapping is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2015
358 pages
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 May 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SIGMOD/PODS'15
Sponsor:
SIGMOD/PODS'15: International Conference on Management of Data
May 31 - June 4, 2015
Victoria, Melbourne, Australia
Acceptance Rates
PODS '15 Paper Acceptance Rate 25 of 80 submissions, 31%;
Overall Acceptance Rate 642 of 2,707 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 189Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in