Multi-Tuple Deletion Propagation: Approximations and Complexity
Summary: Trichotomy for multi-tuple deletion propagation on sjf-CQs: polynomial; NP-hard but approximable; or NP-hard to approximate. Extends to bounded deletions and FDs, and yields a survivor-maximization dual with a corollary on side-effect-free solutions. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Benny Kimelfeld
- 2. Jan Vondrák
- 3. David P. Woodruff
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,649 | Explaining Query Answers with Explanation-Ready Databases | 2016 | VLDB | 8.3719123e-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 |
| 8,721 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4608778e-05 |
| 10,355 | Resilience for Regular Path Queries: Towards a Complexity Classification | 2025 | PODS | 4.1945683e-05 |
| 10,359 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS | 4.1945683e-05 |
| 10,631 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 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 |
| 2,857 | A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies | 2012 | PODS | 8.0037703e-05 |
| 3,314 | Computing Query Probability with Incidence Algebras | 2010 | PODS | 7.2318581e-05 |
| 3,356 | Relational Lenses: A Language for Updatable Views | 2006 | PODS | 7.18009e-05 |
| 4,971 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7938195e-05 |
Previous
Page 1 / 1
Next