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.000110547
Overall Rank: 1,314 | 91.20%
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 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
804	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013788292
2,451	Approximate Denial Constraints	2020	VLDB	8.4303553e-05
2,610	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2035758e-05
3,372	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3488827e-05
5,879	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.9438507e-05
6,494	OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport	2024	SIGMOD	5.7499912e-05
6,718	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.6843134e-05
6,753	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.673161e-05
7,404	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5178575e-05
7,486	Time Series Data Validity	2023	SIGMOD	5.499587e-05
8,248	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	5.354459e-05
8,301	The Computation of Optimal Subset Repairs	2020	VLDB	5.3433509e-05
8,784	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.2640635e-05
9,035	The Cost of Representation by Subset Repairs	2025	VLDB	5.2191717e-05
9,339	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.1780302e-05
9,408	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.1672232e-05
9,414	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	5.1672232e-05
9,914	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	5.0983269e-05
10,385	Budgeted Interactive Property Graph Repair with GNN	2027	SIGMOD	4.9605343e-05
10,690	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.9605343e-05
10,760	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.9605343e-05
10,866	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB	4.9605343e-05
11,269	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.9605343e-05
11,493	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.9605343e-05
11,656	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.9605343e-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.00049435337
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042804864
100	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033951027
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027867985
695	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014679058
769	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014091996
2,759	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.0269594e-05
6,006	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.9002327e-05
6,518	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.741664e-05
8,217	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.3599084e-05

Semantically Similar Papers

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