Minimal-change integrity maintenance using tuple deletions
From MaRDI portal
Publication:1776402
Abstract: 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 identify two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers (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. 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1696773 (Why is no real title available?)
- scientific article; zbMATH DE number 1696845 (Why is no real title available?)
- scientific article; zbMATH DE number 1696846 (Why is no real title available?)
- scientific article; zbMATH DE number 108405 (Why is no real title available?)
- scientific article; zbMATH DE number 1142327 (Why is no real title available?)
- scientific article; zbMATH DE number 1182735 (Why is no real title available?)
- scientific article; zbMATH DE number 1953144 (Why is no real title available?)
- scientific article; zbMATH DE number 1954112 (Why is no real title available?)
- scientific article; zbMATH DE number 2080463 (Why is no real title available?)
- scientific article; zbMATH DE number 754675 (Why is no real title available?)
- scientific article; zbMATH DE number 1931679 (Why is no real title available?)
- scientific article; zbMATH DE number 2085288 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- Advances in Databases and Information Systems
- Answer sets for consistent query answering in inconsistent databases
- Answering queries using views: A survey
- Complexity tailored design: a new design methodology for databases with incomplete information.
- Computable queries for relational data bases
- Datalog with non-deterministic choice computes NDB-PTIME
- Inconsistency Tolerance
- Integrity constraints for XML
- Logic Programming
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- Prioritized repairing and consistent query answering in relational databases
- Programming with non-determinism in deductive databases
- Recursive query plans for data integration
- Scalar aggregation in inconsistent databases.
Cited in
(43)- On repairing and querying inconsistent probabilistic spatio-temporal databases
- Magic Sets and their application to data integration
- Querying incomplete data over extended ER schemata
- Policy-based inconsistency management in relational databases
- On the data complexity of consistent query answering
- On the complexity of inconsistency measurement
- Extending inclusion dependencies with conditions
- Consistent query answering via ASP from different perspectives: theory and practice
- A remark on the complexity of consistent conjunctive query answering under primary key violations
- On the complexity and approximability of repair position selection problem
- Disjunctive databases for representing repairs
- On the data complexity of consistent query answering over graph databases
- Taming primary key violations to query large inconsistent data via ASP
- A framework for reasoning under uncertainty based on non-deterministic distance semantics
- Simplified forms of computerized reasoning with distance semantics
- scientific article; zbMATH DE number 7561466 (Why is no real title available?)
- Enforcement of integrity constraints by means of minimal sufficient changes
- First-order query rewriting for inconsistent databases
- An epistemic approach to model uncertainty in data-graphs
- On the complexity of sampling query feedback restricted database repair of functional dependency violations
- Inconsistency-tolerant query answering for existential rules
- Maximal state independent approximations to minimal real change
- General information spaces: measuring inconsistency, rationality postulates, and complexity
- A dichotomy in the complexity of consistent query answering for queries with two atoms
- Prioritized repairing and consistent query answering in relational databases
- From causes for database queries to repairs and model-based diagnosis and back
- Database repair via event-condition-action rules in dynamic logic
- First-order under-approximations of consistent query answers
- Distance semantics for database repair
- Why is it hard to obtain a dichotomy for consistent query answering?
- Counting and enumerating preferred database repairs
- Mining approximate interval-based temporal dependencies
- Expressive power of entity-linking frameworks
- Computing repairs under functional and inclusion dependencies via argumentation
- Probabilistic query answering over inconsistent databases
- Distance-based paraconsistent logics
- A three-valued semantics for querying and repairing inconsistent databases
- On measuring inconsistency in definite and indefinite databases with denial constraints
- Deductive databases for computing certain and consistent answers from mediated data integration systems
- Reasoning with Uncertainty by Nmatrix–Metric Semantics
- Complexity thresholds in inclusion logic
- Inconsistency Tolerance
- Magic sets for disjunctive Datalog programs
This page was built for publication: Minimal-change integrity maintenance using tuple deletions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1776402)
