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: 1647
Venue: PODS
Year: 2015
Pagerank: 7.669374e-05
Overall Rank: 3,042 | 78.84%
DOI: 10.1145/2745754.2745762

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
6,887	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	4.8937852e-05
7,066	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8445108e-05
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05
10,513	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.1945683e-05
11,616	MuSe: Multiple Deletion Semantics for Data Repair	2020	VLDB	4.1945683e-05
11,763	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.1945683e-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
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
5,398	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	5.5295577e-05
6,490	Spanners: A Formal Framework for Information Extraction	2013	PODS	5.0431719e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05
2,823	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0593894e-05
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
5,360	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5481038e-05
11,325	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1945683e-05
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05