Ronald Fagin
Phokion G. Kolaitis
Abstract
An inverse of a schema mapping M is intended to undo what M does, thus providing a way to perform reverse data exchange. In recent years, three different formalizations of this concept have been introduced and studied, namely the notions of an inverse of a schema mapping, a quasi-inverse of a schema mapping, and a maximum recovery of a schema mapping. The study of these notions has been carried out in the context in which source instances are restricted to consist entirely of constants, while target instances may contain both constants and labeled nulls. This restriction on source instances is crucial for obtaining some of the main technical results about these three notions, but, at the same time, limits their usefulness, since reverse data exchange naturally leads to source instances that may contain both constants and labeled nulls.
We develop a new framework for reverse data exchange that supports source instances that may contain nulls, and we thereby overcome the semantic mismatch between source and target instances of the previous formalizations. The development of this new framework requires a careful reformulation of all the important notions, including the notions of the identity schema mapping, inverse, and maximum recovery. To this effect, we introduce the notions of extended identity schema mapping, extended inverse, and maximum extended recovery, by making systematic use of the homomorphism relation on instances. We give results concerning the existence of extended inverses and of maximum extended recoveries, and results concerning their applications to reverse data exchange and query answering. Moreover, we show that maximum extended recoveries can be used to capture in a quantitative way, the amount of information loss embodied in a schema mapping specified by source-to-target tuple-generating dependencies.
- Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley. Google Scholar
Digital Library
- Afrati, F., Li, C., and Pavlaki, V. 2008. Data exchange: Query answering on incomplete data sources. In Proceedings of the International ICST Conference on Scalable Information Systems (InfoScale). Google ScholarDigital Library
- Arenas, M., Pérez, J., Reutter, J. L., and Riveros, C. 2009a. Composition and inversion of schema mappings. SIGMOD Record 38, 3, 17--28. Google ScholarDigital Library
- Arenas, M., Pérez, J., Reutter, J. L., and Riveros, C. 2009b. Inverting schema mappings: Bridging the gap between theory and practice. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 1018--1029. Google ScholarDigital Library
- Arenas, M., Pérez, J., Reutter, J. L., and Riveros, C. 2010. Foundations of schema mapping management. In Proceedings of ACM Symposium on Principles of Database Systems (PODS). 227--238. Google ScholarDigital Library
- Arenas, M., Pérez, J., and Riveros, C. 2009. The recovery of a schema mapping: Bringing exchanged data back. ACM Trans. Data. Syst. 34, 4. Google ScholarDigital Library
- Beeri, C. and Vardi, M. Y. 1984. A proof procedure for data dependencies. J. ACM 31, 4, 718--741. Google ScholarDigital Library
- 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.Google Scholar
- Bernstein, P. A., Green, T. J., Melnik, S., and Nash, A. 2008. Implementing mapping composition. VLDB J. 17, 2, 333--353. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Fagin, R. 2007. Inverting schema mappings. ACM Trans. Data. Syst. 32, 4. Google ScholarDigital Library
- Fagin, R., Kolaitis, P. G., Miller, R. J., and Popa, L. 2005a. Data exchange: Semantics and query answering. Theor. Comput. Sci. 336, 1, 89--124. Google ScholarDigital Library
- Fagin, R., Kolaitis, P. G., Popa, L., and Tan, W.-C. 2005b. Composing schema mappings: Second-order dependencies to the rescue. ACM Trans. Data. Syst. 30, 4, 994--1055. Google ScholarDigital Library
- Fagin, R., Kolaitis, P. G., Popa, L., and Tan, W. C. 2008. Quasi-inverses of schema mappings. ACM Trans. Data. Syst. 33, 2. Google ScholarDigital Library
- Fagin, R., Kolaitis, P. G., Popa, L., and Tan, W.-C. 2009. Reverse data exchange: Coping with nulls. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 23--32. Google ScholarDigital Library
- Fagin, R., Kolaitis, P. G., Popa, L., and Tan, W.-C. 2011. Schema mapping evolution through composition and inversion. In Schema Matching and Mapping, Z. Bellahsene and A. Bonifati and E. Rahm, Ed. Springer, 191--222.Google Scholar
- Fagin, R. and Nash, A. 2010. The structure of inverses in schema mappings. J. ACM 57, 6. Google ScholarDigital Library
- Fuxman, A., Hernández, M. A., Ho, C. T. H., Miller, R. J., Papotti, P., and Popa, L. 2006. Nested mappings: Schema mapping reloaded. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 67--78. Google ScholarDigital Library
- Imieliński, T. and Lipski, Jr., W. 1983. Incomplete information and dependencies in relational databases. In Proceedings of the ACM Symposium on Management of Data (SIGMOD). 178--184. Google ScholarDigital Library
- Imieliński, T. and Lipski, Jr., W. 1984. Incomplete information in relational databases. J. ACM 31, 4, 761--791. Google ScholarDigital Library
- Lenzerini, M. 2002. Data integration: A theoretical perspective. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 233--246. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Melnik, S. 2004. Generic Model Management: Concepts and Algorithms. Lecture Notes in Computer Science, vol. 2967, Springer. Google ScholarDigital Library
- Nash, A., Bernstein, P. A., and Melnik, S. 2005. Composition of mappings given by embedded dependencies. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 172--183. Google ScholarDigital Library
- Popa, L., Velegrakis, Y., Miller, R. J., Hernández, M. A., and Fagin, R. 2002. Translating Web data. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609. Google ScholarDigital Library
Index Terms
- Reverse data exchange: Coping with nulls
Recommendations
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
A 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 ...
The recovery of a schema mapping: Bringing exchanged data back
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 ...
Comments