Dichotomies in the Complexity of Preferred Repairs

Summary: Shows a dichotomy for globally‑optimal preferred repairs under functional dependencies: for any fixed schema repair‑checking is either in P or coNP‑complete, with tractability exactly when each relation's FDs are equivalent to a single FD or two key constraints. Provides a polynomial‑time test to distinguish the cases and a separate, different dichotomy when preferences may relate non‑conflicting facts. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1646
Venue: PODS
Year: 2015
Pagerank: 8.1725014e-05
Overall Rank: 2,746 | 81.17%
DOI: 10.1145/2745754.2745762

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Benny Kimelfeld (LogicBlox; Technion)
3. Phokion G. Kolaitis (IBM; University of California Santa Cruz)

BibTeX Citation

@inproceedings{fagin_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Dichotomies in the Complexity of Preferred Repairs}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745762},
        doi = {10.1145/2745754.2745762},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kimelfeld, Benny and Kolaitis, Phokion G.},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
5,619	An Operational Approach to Consistent Query Answering	2018	PODS	6.1483242e-05
6,664	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.8090585e-05
6,755	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	5.7830386e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-05
8,838	The Cost of Representation by Subset Repairs	2025	VLDB	5.3592132e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.093636e-05
11,811	MuSe: Multiple Deletion Semantics for Data Repair	2020	VLDB	5.093636e-05
11,969	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
4,499	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	6.6608401e-05
5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	6.0461963e-05
12,228	Spanners: A Formal Framework for Information Extraction	2013	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,838	The Cost of Representation by Subset Repairs	2025	VLDB
2	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
3	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
4	8,103	The Computation of Optimal Subset Repairs	2020	VLDB
5	5,258	Counting Database Repairs under Primary Keys Revisited	2019	PODS
6	11,524	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS
7	8,241	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS
8	185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
9	8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
10	1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS