skip to main content
10.1145/1804669.1804698acmotherconferencesArticle/Chapter ViewAbstractPublication PagesedbtConference Proceedingsconference-collections
research-article

Data correspondence, exchange and repair

Published: 23 March 2010 Publication History

Abstract

Checking the correspondence between two or more database instances and enforcing it is a procedure widely used in practice without however having been explored from a theoretical perspective. In this paper we formally introduce the data correspondence setting and its associated computational problems: checking the existence of solutions, and verifying whether a candidate is a solution, for three distinct types of solutions. Data correspondence is a generalization of data exchange and peer data exchange, and a special case of repairing inconsistent databases. We introduce a new class of dependencies, called semi-LAV, that properly includes both LAV and full dependencies, while retaining tractability for peer data exchange, data correspondence, and database repairs. We also introduce the concept of Σ-satisfying homomorphisms. This new type of homomorphism, together with recent advances, is essential in achieving tractability, while at the same time allowing a large class of dependencies, namely the aforementioned semi-LAV ones. We also show the intractability for a series of problems in the case of weakly acyclic tuple generating dependencies. This implies that many tractability results for weakly acyclic dependencies do not carry over to data correspondence; in these new settings we need to restrict the dependencies a bit further, yielding our semi-LAV dependencies.

References

[1]
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2]
Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In ICDT, pages 31--41, 2009.
[3]
Alfred V. Aho, Catriel Beeri, and Jeffrey D. Ullman. The theory of joins in relational databases. ACM Trans. Database Syst., 4(3):297--314, 1979.
[4]
Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68--79, 1999.
[5]
Pablo Barceló. Logical foundations of relational data exchange. SIGMOD Record, 38(1):49--58, 2009.
[6]
Catriel Beeri and Moshe Y. Vardi. A proof procedure for data dependencies. J. ACM, 31(4):718--741, 1984.
[7]
Leopoldo E. Bertossi. Consistent query answering in databases. SIGMOD Record, 35(2):68--76, 2006.
[8]
Balder ten Cate and Phokion G. Kolaitis. Structural characterizations of schema-mapping languages. In ICDT, pages 63--72, 2009.
[9]
Jan Chomicki. Consistent query answering: Five easy pieces. In ICDT, pages 1--17, 2007.
[10]
Jan Chomicki and Jerzy Marcinkowski. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance, pages 119--150, 2005.
[11]
Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: Semantics and query answering. In ICDT, pages 207--224, 2003.
[12]
Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang Chiew Tan. Composing schema mappings: Second-order dependencies to the rescue. ACM Trans. Database Syst., 30(4):994--1055, 2005.
[13]
Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang Chiew Tan. Reverse data exchange: coping with nulls. In PODS, pages 23--32, 2009.
[14]
Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, and Wang Chiew Tan. Peer data exchange. ACM Trans. Database Syst., 31(4):1454--1498, 2006.
[15]
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[16]
Georg Gottlob and Alan Nash. Data exchange: computing cores in polynomial time. In PODS, pages 40--49, 2006.
[17]
Gösta Grahne and Alberto O. Mendelzon. Tableau techniques for querying information sources through global schemas. In ICDT, pages 332--347, 1999.
[18]
Phokion G. Kolaitis. Schema mappings, data exchange, and metadata management. In PODS, pages 61--75, 2005.
[19]
Maurizio Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233--246, 2002.
[20]
Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In ICDT, pages 179--193, 2007.
[21]
David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing implications of data dependencies. ACM Trans. Database Syst., 4(4):455--469, 1979.
[22]
Slawomir Staworko and Jan Chomicki. Consistent query answers in the presence of universal constraints. CoRR, abs/0809.1551, 2008.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
ICDT '10: Proceedings of the 13th International Conference on Database Theory
March 2010
260 pages
ISBN:9781605589473
DOI:10.1145/1804669
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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 2010

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

EDBT/ICDT '10
EDBT/ICDT '10: EDBT/ICDT '10 joint conference
March 23 - 25, 2010
Lausanne, Switzerland

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Exchange-RepairsJournal on Data Semantics10.1007/s13740-016-0057-45:2(77-97)Online publication date: 9-Feb-2016
  • (2015)On the Data Complexity of Consistent Query AnsweringTheory of Computing Systems10.1007/s00224-014-9586-057:4(843-891)Online publication date: 1-Nov-2015
  • (2014)Exchange-Repairs: Managing Inconsistency in Data ExchangeWeb Reasoning and Rule Systems10.1007/978-3-319-11113-1_10(140-156)Online publication date: 2014
  • (2012)Incomplete Data and Data Dependencies in Relational DatabasesSynthesis Lectures on Data Management10.2200/S00435ED1V01Y201207DTM0294:5(1-123)Online publication date: 31-Jul-2012
  • (2012)Representation systems for data exchangeProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274599(208-221)Online publication date: 26-Mar-2012
  • (2012)On the data complexity of consistent query answeringProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274580(22-33)Online publication date: 26-Mar-2012

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media