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,655 | Explaining Query Answers with Explanation-Ready Databases | 2016 | VLDB | 8.3638668e-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 |
| 8,718 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4566012e-05 |
| 10,367 | Resilience for Regular Path Queries: Towards a Complexity Classification | 2025 | PODS | 4.1905499e-05 |
| 10,371 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS | 4.1905499e-05 |
| 10,639 | Is Integer Linear Programming All You Need for Deletion Propagation? | 2025 | VLDB | 4.1905499e-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 |
|---|---|---|---|---|
| 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 |
| 2,864 | A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies | 2012 | PODS | 7.9964194e-05 |
| 3,315 | Computing Query Probability with Incidence Algebras | 2010 | PODS | 7.2247513e-05 |
| 3,357 | Relational Lenses: A Language for Updatable Views | 2006 | PODS | 7.1738547e-05 |
| 4,973 | Maximizing Conjunctive Views in Deletion Propagation | 2011 | PODS | 5.7882537e-05 |
Previous
Page 1 / 1
Next