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.6618214e-05
Overall Rank: 3,045 | 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.00035692958
2,574	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5126812e-05
6,886	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	4.8904572e-05
7,062	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8398632e-05
7,701	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6690279e-05
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05
10,522	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.1905499e-05
11,620	MuSe: Multiple Deletion Semantics for Data Repair	2020	VLDB	4.1905499e-05
11,771	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.1905499e-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.0007528369
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-05
5,406	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	5.5239588e-05
6,487	Spanners: A Formal Framework for Information Extraction	2013	PODS	5.0383288e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
8,014	The Computation of Optimal Subset Repairs	2020	VLDB	4.6020746e-05
5,370	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5427744e-05
11,327	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1905499e-05
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
7,701	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6690279e-05