Abstract
Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. In this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to query answering in the context of data exchange. These issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem. We give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. A universal solution has no more and no less data than required for data exchange and it represents the entire space of possible solutions. We then identify fairly general, and practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently.We adopt the notion of “certain answers” in indefinite databases for the semantics for query answering in data exchange. We investigate the computational complexity of computing the certain answers in this context and also study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution.
Research carried out while these authors were visiting scientists at the IBM Almaden Research Center. Kolaitis was also partially supported by NSF Grant IIS-9907419. Miller was also partially supported by a research grant from NSERC.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul, S. Cluet, and T. Milo. Correspondence and Translation for Heterogeneous Data. In ICDT, pages 351–363, 1997.
S. Abiteboul and O. M. Duschka. Complexity of Answering Queries Using Materialized Views. In PODS, pages 254–263, 1998.
S. Abiteboul and O. M. Duschka. Complexity of Answering Queries Using Materialized Views. Unpublished full version of [2], 2000.
C. Beeri and M.Y. Vardi. A Proof Procedure for Data Dependencies. JACM, 31(4):718–741, 1984.
A. Calì, D. Calvanese, G. D. Giacomo, and M. Lenzerini. Data Integration under Integrity Constraints. In CAiSE, pages 262–279, 2002.
M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion Dependencies and their Interaction with Functional Dependencies. JCSS, 28(1):29–59, 1984.
S. S. Cosmadakis and P. C. Kanellakis. Functional and Inclusion Dependencies: A Graph Theoretic Approach. In Advances in Computing Research, volume 3, pages 163–184. 1986.
R. Fagin. Horn Clauses and Database Dependencies. JACM, 29(4):952–985, Oct. 1982.
R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. IBM Research Report, Nov. 2002.
M. Friedman, A. Y. Levy, and T. D. Millstein. Navigational Plans For Data Integration. In AAAI, pages 67–73, 1999.
A. Halevy. Answering Queries UsingViews:A Survey. VLDB Journal, pages 270–294, 2001.
R. Hull and M. Yoshikawa. ILOG: Declarative Creation and Manipulation of Object Identifiers. In VLDB, pages 455–468, 1990.
M. Lenzerini. Data Integration: A Theoretical Perspective. In PODS, pages 233–246, 2002.
A.Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering Queries Using Views. In PODS, pages 95–104, May 1995.
D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing Implications of Data Dependencies. ACM TODS, 4(4):455–469, Dec. 1979.
D. Maier, J. D. Ullman, and M.Y. Vardi. On the Foundations of the Universal Relation Model. ACM TODS, 9(2):283–308, June 1984.
J. A. Makowsky. Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples. JCSS, 34(2/3):266–292, April/June 1987.
R. J. Miller, L.M. Haas, and M. Hernández. Schema Map** as Query Discovery. In VLDB, pages 77–88, 2000.
L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating Web Data. In VLDB, pages 598–609, 2002.
N. C. Shu, B. C. Housel, and V. Y. Lum. CONVERT: A High Level Translation Definition Language for Data Conversion. Communications of the ACM, 18(10):557–567, 1975.
N. C. Shu, B. C. Housel, R. W. Taylor, S. P. Ghosh, and V. Y. Lum. EXPRESS: A Data EXtraction, Processing, amd REStructuring System. TODS, 2(2):134–174, 1977.
R. van der Meyden. The Complexity of Querying Indefinite Data about Linearly Ordered Domains. JCSS, 54:113–135, 1997.
R. van der Meyden. Logical Approaches to Incomplete Information:A Survey. In Logics for Databases and Information Systems, pages 307–356. Kluwer, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L. (2003). Data Exchange: Semantics and Query Answering. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds) Database Theory — ICDT 2003. ICDT 2003. Lecture Notes in Computer Science, vol 2572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36285-1_14
Download citation
DOI: https://doi.org/10.1007/3-540-36285-1_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00323-6
Online ISBN: 978-3-540-36285-2
eBook Packages: Springer Book Archive