Computing Optimal Repairs for Functional Dependencies

Summary: Derives an FD-set dichotomy for optimal subset repairs: polynomial-time cases versus APX-complete cases, with support for weights and duplicates. Extends the analysis to cell-update repairs and settles the general most-probable-database dichotomy. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: hae982a80343b5e77
Venue: PODS
Year: 2018
Pagerank: 0.00010917917
Overall Rank: 1,361 | 90.86%
DOI: 10.1145/3196959.3196980

Incoming Non-self Citations Over Time

Authors

1. Ester Livshits (Technion)
2. Benny Kimelfeld (Technion)
3. Sudeepa Roy (Duke University)

BibTeX Citation

@inproceedings{livshits_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Computing Optimal Repairs for Functional Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196980},
        doi = {10.1145/3196959.3196980},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Livshits, Ester and Kimelfeld, Benny and Roy, Sudeepa},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
803	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013836858
2,443	Approximate Denial Constraints	2020	VLDB	8.4586656e-05
2,613	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2260448e-05
3,360	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3767115e-05
5,864	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.9663944e-05
6,480	OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport	2024	SIGMOD	5.7717996e-05
6,699	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.7058728e-05
6,728	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.6946342e-05
7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5387855e-05
7,463	Time Series Data Validity	2023	SIGMOD	5.5204457e-05
8,224	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	5.3747673e-05
8,280	The Computation of Optimal Subset Repairs	2020	VLDB	5.363617e-05
8,756	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.2840289e-05
9,004	The Cost of Representation by Subset Repairs	2025	VLDB	5.2389669e-05
9,305	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.1976693e-05
9,373	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.1868213e-05
9,379	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	5.1868213e-05
9,874	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	5.1176637e-05
10,618	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.9793485e-05
10,688	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.9793485e-05
10,795	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB	4.9793485e-05
11,202	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.9793485e-05
11,435	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.9793485e-05
11,603	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027958527
697	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014694048
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014114806
2,762	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.0441688e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.922611e-05
6,537	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.7535125e-05
8,194	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.379983e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
2	526	Improving Data Quality: Consistency and Accuracy	2007	VLDB
3	2,784	Interaction between Record Matching and Data Repairing	2011	SIGMOD
4	8,194	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
5	1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
6	9,004	The Cost of Representation by Subset Repairs	2025	VLDB
7	8,280	The Computation of Optimal Subset Repairs	2020	VLDB
8	2,762	Dichotomies in the Complexity of Preferred Repairs	2015	PODS
9	188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
10	8,407	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS