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.7882537e-05
Overall Rank: 4,973 | 65.44%
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,805	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.103731e-05
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-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
7,701	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6690279e-05
8,718	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4566012e-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
11,636	Programmable View Update Strategies on Relations	2020	VLDB	4.1905499e-05
12,060	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
105	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00049082041
555	On the Semantics of Updates in Databases	1983	PODS	0.00020229919
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
672	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00018353514
893	Updates Of Relational Views	1983	PODS	0.00015519479
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00013851012
5,308	On the Computation of Relational View Complements	2002	PODS	5.5714815e-05
6,266	Midas: Integrating Public Financial Data	2010	SIGMOD	5.1288728e-05
6,527	Automatic Rule Refinement for Information Extraction	2010	VLDB	5.0200332e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
9,706	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.2951473e-05
4,940	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8131196e-05
9,263	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3648789e-05
10,639	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1905499e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
8,718	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4566012e-05
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-05
4,256	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3063725e-05