A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies
Summary: Establishes a complexity dichotomy for deletion propagation under functional dependencies for self‑join‑free conjunctive views: a simple structural condition yields a polynomial‑time algorithm (similar to Buneman et al.). If violated, the problem is NP‑hard, constant‑factor inapproximable and deciding existence of a side‑effect‑free solution is NP‑complete, thereby generalizing prior results of Kimelfeld et al. and Cong et al. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,042 | Dichotomies in the Complexity of Preferred Repairs | 2015 | PODS | 7.669374e-05 |
| 4,260 | Multi-Tuple Deletion Propagation: Approximations and Complexity | 2013 | VLDB | 6.3124474e-05 |
| 4,361 | The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries | 2016 | VLDB | 6.2559141e-05 |
| 4,937 | New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins | 2020 | PODS | 5.8187108e-05 |
| 5,858 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 5.2997454e-05 |
| 7,702 | Counting and Enumerating (Preferred) Database Repairs | 2017 | PODS | 4.6736471e-05 |
| 8,721 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4608778e-05 |
| 10,631 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1945683e-05 |
| 11,763 | Dichotomies in Ontology-Mediated Querying with the Guarded Fragment | 2017 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 556 | On the Semantics of Updates in Databases | 1983 | PODS | 0.00020249905 |
| 655 | On Propagation of Deletions and Annotations Through Views | 2002 | PODS | 0.00018608845 |
| 671 | Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins | 1985 | PODS | 0.00018370973 |
| 895 | Updates Of Relational Views | 1983 | PODS | 0.00015534879 |
| 1,119 | The Complexity of Causality and Responsibility for Query Answers and non-Answers | 2011 | VLDB | 0.0001386199 |
| 3,314 | Computing Query Probability with Incidence Algebras | 2010 | PODS | 7.2318581e-05 |
| 4,971 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7938195e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,949 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 4.8898337e-05 |
| 9,707 | Towards Update-Dependent Analysis of Query Maintenance | 2025 | PODS | 4.299267e-05 |
| 10,631 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1945683e-05 |
| 5,735 | A Decision Procedure for Conjunctive Query Disjointness | 1989 | PODS | 5.3482653e-05 |
| 6,385 | Propagating Functional Dependencies with Conditions | 2008 | VLDB | 5.0875028e-05 |
| 895 | Updates Of Relational Views | 1983 | PODS | 0.00015534879 |
| 655 | On Propagation of Deletions and Annotations Through Views | 2002 | PODS | 0.00018608845 |
| 8,721 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4608778e-05 |
| 4,971 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7938195e-05 |
| 4,260 | Multi-Tuple Deletion Propagation: Approximations and Complexity | 2013 | VLDB | 6.3124474e-05 |