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: 1759
Venue: PODS
Year: 2018
Pagerank: 0.00010893312
Overall Rank: 1,399 | 90.41%
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 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
2,685	Approximate Denial Constraints	2020	VLDB	8.2594662e-05
3,361	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.4872032e-05
6,352	OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport	2024	SIGMOD	5.9042757e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.8461093e-05
6,576	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.8364729e-05
6,664	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.8090585e-05
7,314	Time Series Data Validity	2023	SIGMOD	5.6471526e-05
8,058	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	5.4981306e-05
8,103	The Computation of Optimal Subset Repairs	2020	VLDB	5.4867244e-05
8,594	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.4053095e-05
8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.3829336e-05
8,838	The Cost of Representation by Subset Repairs	2025	VLDB	5.3592132e-05
9,133	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.3169677e-05
9,193	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.3058708e-05
9,199	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	5.3058708e-05
9,699	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	5.2351259e-05
10,429	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	5.093636e-05
10,502	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	5.093636e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.093636e-05
11,079	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	5.093636e-05
11,276	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
725	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014617251
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
2,746	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.1725014e-05
5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	6.0461963e-05
6,471	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.8702801e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-05

Semantically Similar Papers

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