A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies

Summary: Establishes a complexity dichotomy for deletion propagation under functional dependencies for self‑join‑free conjunctive views: a simple structural condition yields a polynomial‑time algorithm (similar to Buneman et al.). If violated, the problem is NP‑hard, constant‑factor inapproximable and deciding existence of a side‑effect‑free solution is NP‑complete, thereby generalizing prior results of Kimelfeld et al. and Cong et al. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1576
Venue: PODS
Year: 2012
Pagerank: 6.0461963e-05
Overall Rank: 5,905 | 59.49%
DOI: 10.1145/2213556.2213584

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (IBM)

BibTeX Citation

@inproceedings{kimelfeld_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213584},
        doi = {10.1145/2213556.2213584},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
2,746	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.1725014e-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,781	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.5116536e-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
11,969	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.4528526e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
2	9,845	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
3	8,598	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB
4	6,731	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS
5	6,639	Propagating Functional Dependencies with Conditions	2008	VLDB
6	1,075	Updates Of Relational Views	1983	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	4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS
10	4,248	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB