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,045 | Dichotomies in the Complexity of Preferred Repairs | 2015 | PODS | 7.6618214e-05 |
| 4,256 | Multi-Tuple Deletion Propagation: Approximations and Complexity | 2013 | VLDB | 6.3063725e-05 |
| 4,358 | The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries | 2016 | VLDB | 6.2499e-05 |
| 4,940 | New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins | 2020 | PODS | 5.8131196e-05 |
| 5,859 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 5.2963939e-05 |
| 7,701 | Counting and Enumerating (Preferred) Database Repairs | 2017 | PODS | 4.6690279e-05 |
| 8,718 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4566012e-05 |
| 10,639 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1905499e-05 |
| 11,771 | Dichotomies in Ontology-Mediated Querying with the Guarded Fragment | 2017 | PODS | 4.1905499e-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 |
|---|---|---|---|---|
| 555 | On the Semantics of Updates in Databases | 1983 | PODS | 0.00020229919 |
| 655 | On Propagation of Deletions and Annotations Through Views | 2002 | PODS | 0.00018593536 |
| 672 | Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins | 1985 | PODS | 0.00018353514 |
| 893 | Updates Of Relational Views | 1983 | PODS | 0.00015519479 |
| 1,119 | The Complexity of Causality and Responsibility for Query Answers and non-Answers | 2011 | VLDB | 0.00013851012 |
| 3,315 | Computing Query Probability with Incidence Algebras | 2010 | PODS | 7.2247513e-05 |
| 4,973 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7882537e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,946 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 4.8874695e-05 |
| 9,706 | Towards Update-Dependent Analysis of Query Maintenance | 2025 | PODS | 4.2951473e-05 |
| 10,639 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1905499e-05 |
| 5,748 | A Decision Procedure for Conjunctive Query Disjointness | 1989 | PODS | 5.3426438e-05 |
| 6,385 | Propagating Functional Dependencies with Conditions | 2008 | VLDB | 5.0826969e-05 |
| 893 | Updates Of Relational Views | 1983 | PODS | 0.00015519479 |
| 655 | On Propagation of Deletions and Annotations Through Views | 2002 | PODS | 0.00018593536 |
| 8,718 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4566012e-05 |
| 4,973 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7882537e-05 |
| 4,256 | Multi-Tuple Deletion Propagation: Approximations and Complexity | 2013 | VLDB | 6.3063725e-05 |