Database repairing using updates
- 1 September 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 30 (3), 722-768
- https://doi.org/10.1145/1093382.1093385
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.Keywords
This publication has 20 references indexed in Scilit:
- Minimal-change integrity maintenance using tuple deletionsInformation and Computation, 2005
- Data integration under integrity constraintsInformation Systems, 2004
- First-Order Query Rewriting for Inconsistent DatabasesLecture Notes in Computer Science, 2004
- A logical framework for querying and repairing inconsistent databasesIEEE Transactions on Knowledge and Data Engineering, 2003
- Answer sets for consistent query answering in inconsistent databasesTheory and Practice of Logic Programming, 2003
- Scalar aggregation in inconsistent databasesTheoretical Computer Science, 2003
- MERGING DATABASES UNDER CONSTRAINTSInternational Journal of Cooperative Information Systems, 1998
- The Existence of Homomorphisms to Oriented CyclesSIAM Journal on Discrete Mathematics, 1995
- Reasoning in inconsistent knowledge basesIEEE Transactions on Knowledge and Data Engineering, 1995
- A Proof Procedure for Data DependenciesJournal of the ACM, 1984