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: 1548
Venue: PODS
Year: 2011
Pagerank: 6.4528526e-05
Overall Rank: 4,901 | 66.38%
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 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,570	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.4061164e-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
5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	6.0461963e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-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
8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.3829336e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05
11,827	Programmable View Update Strategies on Relations	2020	VLDB	5.093636e-05
12,250	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	5.093636e-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.0010828372
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
602	On the Semantics of Updates in Databases	1983	PODS	0.00015856828
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
979	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012850156
1,075	Updates Of Relational Views	1983	PODS	0.00012294896
4,752	Automatic Rule Refinement for Information Extraction	2010	VLDB	6.5235308e-05
5,392	On the Computation of Relational View Complements	2002	PODS	6.2339252e-05
6,394	Midas: Integrating Public Financial Data	2010	SIGMOD	5.8877829e-05

Semantically Similar Papers

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