A logical framework for querying and repairing inconsistent databases
- 1 November 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 15 (6), 1389-1408
- https://doi.org/10.1109/tkde.2003.1245280
Abstract
In this paper, we address the problem of managing inconsistent databases, i.e., databases violating integrity constraints. We propose a general logic framework for computing repairs and consistent answers over inconsistent databases. A repair for a possibly inconsistent database is a minimal set of insert and delete operations which makes the database consistent, whereas a consistent answer is a set of tuples derived from the database, satisfying all integrity constraints. In our framework, different types of rules defining general integrity constraints, repair constraints (i.e., rules defining conditions on the insertion or deletion of atoms), and prioritized constraints (i.e., rules defining priorities among updates and repairs) are considered. We propose a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation). The disjunctive program can be used for two different purposes: to compute "repairs" for the database and produce consistent answers, i.e., a maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete (each preferred stable model defines a repair and each repair is derived from a preferred stable model), and more general than techniques previously proposed.Keywords
This publication has 30 references indexed in Scilit:
- Querying Inconsistent DatabasesPublished by Springer Science and Business Media LLC ,2002
- Census Data Repair: A Challenging Application of Disjunctive Logic ProgrammingLecture Notes in Computer Science, 2001
- Prioritized logic programming and its application to commonsense reasoningArtificial Intelligence, 2000
- Complexity and Expressive Power of Deterministic Semantics for DATALOG¬Information and Computation, 1999
- Minimal Founded Semantics for Disjunctive Logic ProgrammingLecture Notes in Computer Science, 1999
- Deterministic and non-deterministic stable modelsJournal of Logic and Computation, 1997
- Reasoning in inconsistent knowledge basesIEEE Transactions on Knowledge and Data Engineering, 1995
- Amalgamating knowledge basesACM Transactions on Database Systems, 1994
- Contradiction removal semantics with explicit negationLecture Notes in Computer Science, 1994
- Classical negation in logic programs and disjunctive databasesNew Generation Computing, 1991