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: h04cb802c253f1e21
Venue: VLDB
Year: 2013
Pagerank: 6.6658586e-05
Overall Rank: 4,323 | 70.94%
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,222	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.8109051e-05
4,062	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.8247395e-05
4,747	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.4374568e-05
7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5387855e-05
8,761	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB	5.283642e-05
11,091	Resilience for Regular Path Queries: Towards a Complexity Classification	2025	PODS	4.9793485e-05
11,095	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9793485e-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
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
590	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015890019
619	On the Semantics of Updates in Databases	1983	PODS	0.00015518944
995	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012635689
1,088	Updates Of Relational Views	1983	PODS	0.00012091631
3,291	Computing Query Probability with Incidence Algebras	2010	PODS	7.4519264e-05
3,428	Relational Lenses: A Language for Updatable Views	2006	PODS	7.3067857e-05
4,437	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.6001218e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.922611e-05

Semantically Similar Papers

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