Reverse data exchange: coping with nulls

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, thus overcoming 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.

REFERENCES

• 1: S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
• 2: Marcelo Arenas , Jorge Pérez , Cristian Riveros, The recovery of a schema mapping: bringing exchanged data back, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376920]
• 3: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 4: P.A. Bernstein. Applying Model Management to Classical Meta-Data Problems. In CIDR, pages 209--220, 2003.
• 5: Philip A. Bernstein , Todd J. Green , Sergey Melnik , Alan Nash, Implementing mapping composition, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.2, p.333-353, March 2008 [doi>10.1007/s00778-007-0059-9]
• 6: Alin Deutsch , Val Tannen, Optimization Properties for Classes of Conjunctive Regular Path Queries, Revised Papers from the 8th International Workshop on Database Programming Languages, p.21-39, September 08-10, 2001
• 7: Ronald Fagin, Inverting schema mappings, ACM Transactions on Database Systems (TODS), v.32 n.4, p.25-es, November 2007 [doi>10.1145/1292609.1292615]
• 8: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 9: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Composing schema mappings: Second-order dependencies to the rescue, ACM Transactions on Database Systems (TODS), v.30 n.4, p.994-1055, December 2005 [doi>10.1145/1114244.1114249]
• 10: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Quasi-inverses of schema mappings, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-52, June 2008 [doi>10.1145/1366102.1366108]
• 11: Ariel Fuxman , Mauricio A. Hernandez , Howard Ho , Renee J. Miller , Paolo Papotti , Lucian Popa, Nested mappings: schema mapping reloaded, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: Jayant Madhavan , Alon Y. Halevy, Composing mappings among data sources, Proceedings of the 29th international conference on Very large data bases, p.572-583, September 09-12, 2003, Berlin, Germany
• 13: Sergey Melnik, Generic Model Management: Concepts And Algorithms (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 14: Alan Nash , Philip A. Bernstein , Sergey Melnik, Composition of mappings given by embedded dependencies, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065189]
• 15: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases
          Subjects: Data translation**

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Theory

Keywords:
chase, data exchange, data integration, inverse, maximum recovery, model management, quasi-inverse, schema mapping