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: 12406
Venue: VLDB
Year: 2021
Pagerank: 4.4566012e-05
Overall Rank: 8,718 | 39.41%
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.0033542e-05
7,024	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8530001e-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

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
213	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0003371037
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
943	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015140995
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00013851012
1,376	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012315734
2,655	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.3638668e-05
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-05
3,224	Reverse Data Management	2011	VLDB	7.3523336e-05
4,256	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3063725e-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
4,973	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7882537e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
10,639	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1905499e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
4,055	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4906839e-05
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-05
4,973	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7882537e-05
4,256	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3063725e-05