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: hd3b28343c7a4c0aa
Venue: PODS
Year: 2012
Pagerank: 5.9002327e-05
Overall Rank: 6,006 | 59.75%
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,314	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.000110547
2,759	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.0269594e-05
4,085	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.7989526e-05
4,341	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.6408734e-05
4,714	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4395938e-05
4,769	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.4131333e-05
7,404	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5178575e-05
8,217	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.3599084e-05
8,788	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB	5.263678e-05
12,316	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.9605343e-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
581	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016042765
593	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015833398
620	On the Semantics of Updates in Databases	1983	PODS	0.00015460693
1,000	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012588668
1,093	Updates Of Relational Views	1983	PODS	0.0001204652
3,301	Computing Query Probability with Incidence Algebras	2010	PODS	7.4238397e-05
4,460	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.5757194e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,164	Tree-Width and Functional Dependencies in Databases	2008	PODS
2	10,072	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
3	8,788	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB
4	6,887	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS
5	6,783	Propagating Functional Dependencies with Conditions	2008	VLDB
6	1,093	Updates Of Relational Views	1983	PODS
7	593	On Propagation of Deletions and Annotations Through Views	2002	PODS
8	7,404	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
9	4,460	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS
10	4,341	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB