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
(48)- Database repair via event-condition-action rules in dynamic logic
- Consistent query answering via ASP from different perspectives: theory and practice
- scientific article; zbMATH DE number 7561466 (Why is no real title available?)
- On the data complexity of consistent query answering
- A framework for reasoning under uncertainty based on non-deterministic distance semantics
- Simplified forms of computerized reasoning with distance semantics
- Expressive power of entity-linking frameworks
- Magic Sets and their application to data integration
- A simple algorithm for consistent query answering under primary keys
- Disjunctive databases for representing repairs
- A dichotomy in the complexity of consistent query answering for queries with two atoms
- First-order query rewriting for inconsistent databases
- Consistent query answering in multi-relation databases
- Probabilistic query answering over inconsistent databases
- Why is it hard to obtain a dichotomy for consistent query answering?
- A remark on the complexity of consistent conjunctive query answering under primary key violations
- Inconsistency Tolerance
- Distance-based paraconsistent logics
- On the complexity of inconsistency measurement
- Mining approximate interval-based temporal dependencies
- Magic sets for disjunctive Datalog programs
- Prioritized repairing and consistent query answering in relational databases
- On the complexity of sampling query feedback restricted database repair of functional dependency violations
- Enforcement of integrity constraints by means of minimal sufficient changes
- Computing repairs under functional and inclusion dependencies via argumentation
- Deductive databases for computing certain and consistent answers from mediated data integration systems
- Complexity thresholds in inclusion logic
- From causes for database queries to repairs and model-based diagnosis and back
- An epistemic approach to model uncertainty in data-graphs
- On repairing and querying inconsistent probabilistic spatio-temporal databases
- Distance semantics for database repair
- On measuring inconsistency in definite and indefinite databases with denial constraints
- Reasoning with Uncertainty by Nmatrix–Metric Semantics
- General information spaces: measuring inconsistency, rationality postulates, and complexity
- Counting and enumerating preferred database repairs
- On the data complexity of consistent query answering over graph databases
- Querying incomplete data over extended ER schemata
- Extending inclusion dependencies with conditions
- A three-valued semantics for querying and repairing inconsistent databases
- Corrections to: ``On the data complexity of consistent query answering over graph databases
- Parameterized complexity classification for interval constraints
- Listing maximal H-free subgraphs
- First-order under-approximations of consistent query answers
- Inconsistency-tolerant query answering for existential rules
- Maximal state independent approximations to minimal real change
- Taming primary key violations to query large inconsistent data via ASP
- Policy-based inconsistency management in relational databases
- On the complexity and approximability of repair position selection problem
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)
