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.00010912749
Overall Rank: 1,362 | 90.85%
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
804	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013830311
2,445	Approximate Denial Constraints	2020	VLDB	8.4546614e-05
2,614	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2221507e-05
3,360	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3732195e-05
5,866	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.96357e-05
6,482	OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport	2024	SIGMOD	5.7690673e-05
6,703	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.7031717e-05
6,734	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.6919385e-05
7,385	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5361635e-05
7,467	Time Series Data Validity	2023	SIGMOD	5.5178324e-05
8,230	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	5.372223e-05
8,286	The Computation of Optimal Subset Repairs	2020	VLDB	5.361078e-05
8,764	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.2815275e-05
9,014	The Cost of Representation by Subset Repairs	2025	VLDB	5.2364868e-05
9,314	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.1952088e-05
9,382	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.1843659e-05
9,388	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	5.1843659e-05
9,881	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	5.115241e-05
10,629	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.9769913e-05
10,699	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.9769913e-05
10,805	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB	4.9769913e-05
11,211	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.9769913e-05
11,441	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.9769913e-05
11,609	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.9769913e-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.00049326063
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042926566
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033676943
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027945388
697	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014687805
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014108234
2,763	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.0404242e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.9198073e-05
6,539	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.7507888e-05
8,202	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.3774362e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,737	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,202	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,014	The Cost of Representation by Subset Repairs	2025	VLDB
7	8,286	The Computation of Optimal Subset Repairs	2020	VLDB
8	2,763	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,414	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS