Minimal-change integrity maintenance using tuple deletions

By Jan Chomicki, Jerzy Marcinkowski. Information and Computation, 2002

391 citations recorded by the source corpus.

We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We focus on two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers [in: ACM Symposium on Principles of Database Systems (PODS), 1999, 68] (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable cases. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/b3c1b47b0612c354be4e2fe23d39439ada6231c0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

HoloClean: Holistic Data Repairs with Probabilistic Inference (2017, methodology): “In the current implementation we limit these constraints to: (i) denial constraints [13] that specify various business logic and integrity constraints, and (ii) matching dependencies [7, 16, 24] to specify lookups to available external dictionaries or labeled (clean) data.”
On approximating optimum repairs for functional dependency violations (2009, background): “The complexity of consistent query answering has been studied for different classes of integrity constraints [7, 3, 5, 12], and practical implementations have been proposed that compute consistent answers, for some restricted classes of first-order queries and constraints, using query rewriting [19,”
Improving Data Quality: Consistency and Accuracy (2007, background): “…on two topics introduced in [2]: repair is to ﬁnd another database that is consistent and minimally differs from the original database ( e.g., [2, 5, 25, 9, 10, 14]); and consistent query answer is to ﬁnd an answer to a given query in every repair of the original database ( e.g., [2, 10, 24, 34]).”
Conditional Functional Dependencies for Data Cleaning (2007, background): “There has also been recent work on constraint repair [2, 5, 7, 19], which speci-CC”
Guided data repair (2011, background): “Most of the existing data repair approaches (e.g., [2, 6, 7, 16]) focus on providing fully automated solutions using diﬀerent heuristics to select updates that would introduce minimal changes to the data, which could be risky especially for critical data.”
Trends in Cleaning Relational Data: Consistency and Deduplication (2015, background): “There exist multiple theoretic studies [17, 2, 24] and surveys [44, 8] on studying the complexity of data repairing parameterized by different classes of ICs, such as FDs, CFDs, and DCs, and different repairing operations, such as value updating, and tuple deleting.”
On the decidability and complexity of query answering over inconsistent and incomplete databases (2003, background): “In [10] the authors establish complexity results for query answering under such a semantics in the presence of denial constraints, a generalization of key dependencies and functional dependencies, while in [9] also inclusion dependencies are considered.”