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: he17c79c7775913f5
Venue: PODS
Year: 2011
Pagerank: 6.6001218e-05
Overall Rank: 4,437 | 70.17%
DOI: 10.1145/1989284.1989308

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (IBM)
2. Jan Vondrák (IBM)
3. Ryan Williams (IBM)

BibTeX Citation

@inproceedings{kimelfeld_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Maximizing Conjunctive Views in Deletion Propagation}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989308},
        doi = {10.1145/1989284.1989308},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Vondrák, Jan and Williams, Ryan},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,504	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.3782213e-05
4,062	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.8247395e-05
4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.6658586e-05
4,747	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.4374568e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.922611e-05
7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5387855e-05
8,194	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.379983e-05
8,761	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB	5.283642e-05
10,987	GDPView: An Interactive Interface that Unifies Variants of Deletion Propagation (DP)	2026	VLDB	4.9793485e-05
11,095	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9793485e-05
12,128	Programmable View Update Strategies on Relations	2020	VLDB	4.9793485e-05
12,541	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	4.9793485e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027958527
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
590	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015890019
619	On the Semantics of Updates in Databases	1983	PODS	0.00015518944
995	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012635689
1,088	Updates Of Relational Views	1983	PODS	0.00012091631
4,823	Automatic Rule Refinement for Information Extraction	2010	VLDB	6.3937168e-05
5,494	On the Computation of Relational View Complements	2002	PODS	6.1072994e-05
6,483	Midas: Integrating Public Financial Data	2010	SIGMOD	5.7700543e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,028	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
2	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
3	4,747	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS
4	9,585	Materializing Views with Minimal Size To Answer Queries	2003	PODS
5	8,761	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB
6	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
7	590	On Propagation of Deletions and Annotations Through Views	2002	PODS
8	7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
9	5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
10	4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB