article

Database repairing using updates

Author:

Jef WijsenAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 30, Issue 3

Pages 722 - 768

https://doi.org/10.1145/1093382.1093385

Published: 01 September 2005 Publication History

Abstract

Repairing a database means bringing the database in accordance with a given set of integrity constraints by applying some minimal change. If a database can be repaired in more than one way, then the consistent answer to a query is defined as the intersection of the query answers on all repaired versions of the database.Earlier approaches have confined the repair work to deletions and insertions of entire tuples. We propose a theoretical framework that also covers updates as a repair primitive. Update-based repairing is interesting in that it allows rectifying an error within a tuple without deleting the tuple, thereby preserving consistent values in the tuple. Another novel idea is the construct of nucleus: a single database that yields consistent answers to a class of queries, without the need for query rewriting. We show the construction of nuclei for full dependencies and conjunctive queries. Consistent query answering and constructing nuclei is generally intractable under update-based repairing. Nevertheless, we also show some tractable cases of practical interest.

References

[1]

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.]]

Digital Library

[2]

Arenas, M., Bertossi, L. E., and Chomicki, J. 1999. Consistent query answers in inconsistent databases. In Proceedings of the 18th ACM Symposium on Principles of Database Systems. ACM Press, 68--79.]]

Digital Library

[3]

Arenas, M., Bertossi, L. E., and Chomicki, J. 2003a. Answer sets for consistent query answering in inconsistent databases. Theory and Practice of Logic Programming 3, 3--4, 393--424.]]

Digital Library

[4]

Arenas, M., Bertossi, L. E., Chomicki, J., He, X., Raghavan, V., and Spinrad, J. 2003b. Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 296, 3, 405--434.]]

Digital Library

[5]

Arenas, M., Bertossi, L. E., and Kifer, M. 2000. Applications of Annotated Predicate Calculus to Querying Inconsistent Databases. In Proceedings of the 1st International Conference on Computational Logic (CL 2000). LNAI, vol. 1861. Springer, 926--941.]]

Digital Library

[6]

Arieli, O. 2000. An algorithmic approach to recover inconsistent knowledge-bases. In Proceedings of the European Workshop on Logics in Artificial Intelligence (JELIA 2000). LNCS, vol. 1919. Springer, 148--162.]]

Digital Library

[7]

Arieli, O., Denecker, M., Nuffelen, B. V., and Bruynooghe, M. 2002. Repairing inconsistent databases: A model-theoretic approach and abductive reasoning. In Paraconsistent Computational Logic. Datalogiske Skrifter, vol. 95. Roskilde University, Roskilde, Denmark, 51--65.]]

[8]

Arieli, O., Denecker, M., Nuffelen, B. V., and Bruynooghe, M. 2004. Database repair by signed formulae. In Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2004). LNCS, vol. 2942. Springer, 14--30.]]

[9]

Beeri, C. and Vardi, M. Y. 1984. A proof procedure for data dependencies. J. ACM 31, 4 (Oct.), 718--741.]]

Digital Library

[10]

Bertossi, L. E. and Chomicki, J. 2003. Query answering in inconsistent databases. In Logics for Emerging Applications of Databases, J. Chomicki, R. van der Meyden, and G. Saake, Eds. Springer, Chapter 2, 43--83.]]

[11]

Bertossi, L. E. and Schwind, C. 2002. Analytic tableaux and database repairs: Foundations. In Proceedings of the 2nd International Symposium on Foundations on Information and Knowledge Systems (FoIKS 2002). LNCS, vol. 2284. Springer, 32--48.]]

Digital Library

[12]

Bertossi, L. E. and Schwind, C. 2004. Database repairs and analytic tableaux. Annals of Mathematics and Artificial Intelligence 40, 1--2, 5--35.]]

Digital Library

[13]

Bravo, L. and Bertossi, L. E. 2003. Logic programs for consistently querying data integration systems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 10--15.]]

[14]

Bravo, L. and Bertossi, L. E. 2004. Consistent query answering under inclusion dependencies. In CASCON. IBM, 202--216.]]

Digital Library

[15]

Bry, F. 1997. Query answering in information systems with integrity constraints. In First IFIP WG 11.5 Working Conference on Integrity and Internal Control in Information Systems: Increasing the Confidence in Information Systems, Zurich, Switzerland, December 4--5, 1997. Chapman Hall, 113--130.]]

Digital Library

[16]

Calì, A., Calvanese, D., Giacomo, G. D., and Lenzerini, M. 2004. Data integration under integrity constraints. Inf. Syst. 29, 2, 147--163.]]

Digital Library

[17]

Calì, A., Lembo, D., and Rosati, R. 2003a. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems. ACM, 260--271.]]

Digital Library

[18]

Calì, A., Lembo, D., and Rosati, R. 2003b. Query rewriting and answering under constraints in data integration systems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 16--21.]]

[19]

Celle, A. and Bertossi, L. E. 2000. Querying inconsistent databases: Algorithms and implementation. In Proceedings of the 1st International Conference on Computational Logic (CL 2000). LNAI, vol. 1861. Springer, 942--956.]]

Digital Library

[20]

Chomicki, J. and Marcinkowski, J. 2005a. Minimal-change integrity maintenance using tuple deletions. Inf. Comput. 197, 1-2, 90--121.]]

[21]

Chomicki, J. and Marcinkowski, J. 2005b. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance. LNCS, vol. 3300. Springer, 119--150.]]

Digital Library

[22]

Chomicki, J., Marcinkowski, J., and Staworko, S. 2004a. Computing consistent query answers using conflict hypergraphs. In Proceedings of the 13th ACM Conference on Information and Knowledge Management (CIKM '04). ACM, 417--426.]]

Digital Library

[23]

Chomicki, J., Marcinkowski, J., and Staworko, S. 2004b. Hippo: A system for computing consistent answers to a class of SQL queries. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT 2004). LNCS, vol. 2992. Springer, 841--844.]]

[24]

de Amo, S., Carnielli, W. A., and Marcos, J. 2002. A logical framework for integrating inconsistent information in multiple databases. In Proceedings of the 2nd International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2002). LNCS, vol. 2284. Springer, 67--84.]]

Digital Library

[25]

Fagin, R., Kolaitis, P. G., Miller, R. J., and Popa, L. 2002. Data exchange: Semantics and query answering. In Proceedings of the 9th International Conference on Database Theory (ICDT 2003). LNCS, vol. 2572. Springer, 207--224.]]

Digital Library

[26]

Fagin, R., Kolaitis, P. G., and Popa, L. 2003. Data exchange: Getting to the core. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems. ACM, 90--101. A journal version will appear in ACM Trans. Database Syst.]]

Digital Library

[27]

Franconi, E., Palma, A. L., Leone, N., Perri, S., and Scarcello, F. 2001. Census data repair: A challenging application of disjunctive logic programming. In Proceedings of the 8th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2001). LNCS, vol. 2250. Springer, 561--578.]]

Digital Library

[28]

Fuxman, A. D. and Miller, R. J. 2005. First-order rewriting for inconsistent databases. In Proceedings of the 10th International Conference on Database Theory (ICDT 2005). LNCS, vol. 3363. Springer, 337--351.]]

Digital Library

[29]

Grant, J. and Subrahmanian, V. S. 1995. Reasoning in inconsistent knowledge bases. IEEE Trans. Knowl. Data Eng. 7, 1, 177--189.]]

Digital Library

[30]

Greco, G., Greco, S., and Zumpano, E. 2003a. A logical framework for querying and repairing inconsistent databases. IEEE Trans. Knowl. Data Eng. 25, 6, 1389--1408.]]

Digital Library

[31]

Greco, S., Sirangelo, C., Trubitsyna, I., and Zumpano, E. 2003b. Preferred repairs for inconsistent databases. In 7th International Database Engineering and Applications Symposium (IDEAS 2003). IEEE Computer Society, 202--211.]]

[32]

Hell, P. and Zhu, X. 1995. The existence of homomorphisms to oriented cycles. SIAM J. Discrete Math. 8, 2, 208--222.]]

Digital Library

[33]

Lembo, D., Lenzerini, M., and Rosati, R. 2002. Source inconsistency and incompleteness in data integration. In Proceedings of the 9th International Workshop on Knowledge Representation Meets Databases (KRDB 2002). Number 54 in CEUR Workshop Proceedings. Technical University of Aachen (RWTH).]]

[34]

Lin, J. and Mendelzon, A. O. 1998. Merging databases under constraints. Int. J. Cooperative Inf. Syst. 7, 1, 55--76.]]

[35]

Nair, M. 1982a. A new method in elementary prime number theory. J. London Math. Soc. 25, 385--391.]]

[36]

Nair, M. 1982b. On Chebyshev-type inequalities for primes. Amer. Math. Monthly 89, 126--129.]]

[37]

Plotkin, G. D. 1969. A note on inductive generalization. In Machine Intelligence 5, B. Meltzer and D. Michie, Eds. Edinburgh University Press, Edinburgh, 153--163.]]

[38]

Sciore, E. 1983. Inclusion dependencies and the universal instance. In Proceedings of the 2nd ACM Symposium on Principles of Database Systems. ACM, 48--57.]]

Digital Library

[39]

Wijsen, J. 2002. Condensed representation of database repairs for consistent query answering. In Proceedings of the 9th International Conference on Database Theory (ICDT 2003). LNCS, vol. 2572. Springer, 378--393.]]

Digital Library

[40]

Wijsen, J. 2004. Making more out of an inconsistent database. In Proceedings of the 8th East European Conference on Advances in Databases and Information Systems (ADBIS 2004). LNCS, vol. 3255. Springer, 291--305.]]

Cited By

Pachera ABonifati AMauri A(2025)User-Centric Property Graph RepairsProceedings of the ACM on Management of Data10.1145/37097353:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709735
Laurent DSpyratos N(2025)Consistent query answering in multi-relation databasesInformation and Computation10.1016/j.ic.2025.105279303(105279)Online publication date: Mar-2025
https://doi.org/10.1016/j.ic.2025.105279
Akasiadis CNentidis ACharalambidis AArtikis A(2024)Detecting and Fixing Inconsistency of Large Knowledge GraphsProceedings of the 13th Hellenic Conference on Artificial Intelligence10.1145/3688671.3688766(1-8)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3688671.3688766
Show More Cited By

Index Terms

Database repairing using updates
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Consistent query answering under primary keys: a characterization of tractable queries
ICDT '09: Proceedings of the 12th International Conference on Database Theory

This article deals with consistent query answering to conjunctive queries under primary key constraints. The repairs of an inconsistent database db are obtained by selecting a maximum number of tuples from db without ever selecting two tuples that agree ...
First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys
PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query ...
Consistent Query Answering for Primary Keys on Path Queries
PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database. For a Boolean query q, the problem CERTAINTY(q) takes a database as ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 30, Issue 3

September 2005

226 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1093382

Issue’s Table of Contents

Copyright © 2005 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 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: 01 September 2005

Published in TODS Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

169
Total Citations
View Citations
1,672
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pachera ABonifati AMauri A(2025)User-Centric Property Graph RepairsProceedings of the ACM on Management of Data10.1145/37097353:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709735
Laurent DSpyratos N(2025)Consistent query answering in multi-relation databasesInformation and Computation10.1016/j.ic.2025.105279303(105279)Online publication date: Mar-2025
https://doi.org/10.1016/j.ic.2025.105279
Akasiadis CNentidis ACharalambidis AArtikis A(2024)Detecting and Fixing Inconsistency of Large Knowledge GraphsProceedings of the 13th Hellenic Conference on Artificial Intelligence10.1145/3688671.3688766(1-8)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3688671.3688766
Koutris POuyang XWijsen J(2024)Consistent Query Answering for Primary Keys on Rooted Tree QueriesProceedings of the ACM on Management of Data10.1145/36511392:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651139
Sun YSong SYuan X(2024)From Minimum Change to Maximum Density: On Determining Near-Optimal S-RepairIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.329440136:2(627-639)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3294401
Pachera ABonifati AMauri A(2024)Towards User-Centric Graph Repairs2024 IEEE 40th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW61823.2024.00057(375-376)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDEW61823.2024.00057
Li WZhang AZong CZhu RQiu T(2024)Optimal Update Repair with Maximum Likelihood and Minimum CostDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_20(299-314)Online publication date: 1-Oct-2024
https://doi.org/10.1007/978-981-97-5552-3_20
Huang RWang JSong SLin XZhu XPei J(2023)Efficiently Cleaning Structured Event Logs: A Graph Repair ApproachACM Transactions on Database Systems10.1145/357128148:1(1-44)Online publication date: 13-Mar-2023
https://dl.acm.org/doi/10.1145/3571281
Bertossi L(2023)Attribution-Scores in Data Management and Explainable Machine LearningAdvances in Databases and Information Systems10.1007/978-3-031-42914-9_2(16-33)Online publication date: 4-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-42914-9_2
Peng JShen DTang NLiu TKou YNie TCui HYu G(2022)Self-Supervised and Interpretable Data Cleaning with Sequence Generative Adversarial NetworksProceedings of the VLDB Endowment10.14778/3570690.357069416:3(433-446)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.14778/3570690.3570694
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents