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: 12593
Venue: VLDB
Year: 2021
Pagerank: 5.3829336e-05
Overall Rank: 8,700 | 40.32%
DOI: 10.14778/3425879.3425892

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (Duke University)
2. Shouzhuo Sun (Duke University)
3. Shweta Patwa (Duke University)
4. Debmalya Panigrahi (Duke University)
5. Sudeepa Roy (Duke University)

BibTeX Citation

@article{hu_vldb21,
        title = {{Aggregated Deletion Propagation for Counting Conjunctive Query Answers}},
        author = {Hu, Xiao and Sun, Shouzhuo and Patwa, Shweta and Panigrahi, Debmalya and Roy, Sudeepa},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {2},
        pages = {228--240},
        doi = {10.14778/3425879.3425892},
        url = {https://doi.org/10.14778/3425879.3425892},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,576	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.8364729e-05
7,269	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.6595955e-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
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
191	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.00026096009
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
663	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015174751
1,096	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012189583
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
2,195	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.9713779e-05
2,914	Reverse Data Management	2011	VLDB	7.9667467e-05
3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.9695922e-05
4,248	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.8052749e-05
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-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	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	8,598	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB
3	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
4	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
5	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
6	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
7	636	Answering Conjunctive Queries under Updates	2017	PODS
8	5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
9	4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS
10	4,248	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB