Aggregated Deletion Propagation for Counting Conjunctive Query Answers

Summary: Aggregated Deletion Propagation: minimize input deletions to remove a target number of counting CQ outputs (no self-joins). Full complexity map: poly-time solvability criteria and a decision procedure; NP-hard structure; pragmatic heuristic with experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12405
Venue: VLDB
Year: 2021
Pagerank: 4.4608778e-05
Overall Rank: 8,721 | 39.33%
DOI: 10.14778/3425879.3425892

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,565	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.0081626e-05
7,022	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8576599e-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

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
214	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0003363692
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
942	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015155714
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.0001386199
1,371	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012323502
2,649	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.3719123e-05
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
3,218	Reverse Data Management	2011	VLDB	7.3592173e-05
4,260	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3124474e-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
4,971	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7938195e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
10,631	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1945683e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05
7,162	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8132423e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
4,971	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7938195e-05
4,260	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3124474e-05