Maximizing Conjunctive Views in Deletion Propagation

Summary: Dichotomy for deletion-propagation on conjunctive views without self-joins: each CQ is either solved optimally by the trivial algorithm or is APX-hard (exactly those where the trivial fails). Two constant-factor approximations for star CQs—a greedy and an LP randomized-rounding (better ratio, extensible); self-joins severely degrade approximability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1549
Venue: PODS
Year: 2011
Pagerank: 5.7938195e-05
Overall Rank: 4,971 | 65.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,797	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.1108589e-05
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-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
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05
8,721	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4608778e-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
11,632	Programmable View Update Strategies on Relations	2020	VLDB	4.1945683e-05
12,052	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
104	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00048766186
556	On the Semantics of Updates in Databases	1983	PODS	0.00020249905
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
671	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00018370973
895	Updates Of Relational Views	1983	PODS	0.00015534879
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.0001386199
5,306	On the Computation of Relational View Complements	2002	PODS	5.5769585e-05
6,267	Midas: Integrating Public Financial Data	2010	SIGMOD	5.1338991e-05
6,534	Automatic Rule Refinement for Information Extraction	2010	VLDB	5.0244622e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
9,707	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.299267e-05
4,937	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8187108e-05
9,259	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3690661e-05
10,631	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1945683e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
8,721	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4608778e-05
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
4,260	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3124474e-05