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)

Paper ID: 10832
Venue: VLDB
Year: 2013
Pagerank: 6.8052749e-05
Overall Rank: 4,248 | 70.86%
DOI: 10.14778/2536258.2536267

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (IBM)
2. Jan Vondrák (IBM)
3. David P. Woodruff (IBM)

BibTeX Citation

@article{kimelfeld_vldb13,
        title = {{Multi-Tuple Deletion Propagation: Approximations and Complexity}},
        author = {Kimelfeld, Benny and Vondrák, Jan and Woodruff, David P.},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {13},
        doi = {10.14778/2536258.2536267},
        url = {https://doi.org/10.14778/2536258.2536267},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,195	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.9713779e-05
3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.9695922e-05
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-05
8,598	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB	5.4049137e-05
8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.3829336e-05
10,648	Resilience for Regular Path Queries: Towards a Complexity Classification	2025	PODS	5.093636e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05

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
602	On the Semantics of Updates in Databases	1983	PODS	0.00015856828
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
620	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015703409
979	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012850156
1,075	Updates Of Relational Views	1983	PODS	0.00012294896
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
3,390	Relational Lenses: A Language for Updatable Views	2006	PODS	7.4518363e-05
4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.4528526e-05
5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	6.0461963e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
2	3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB
3	8,598	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB
4	9,845	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
5	4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS
6	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
7	620	On Propagation of Deletions and Annotations Through Views	2002	PODS
8	8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
9	4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS
10	5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS