The Computation of Optimal Subset Repairs

Summary: New tight inapproximability for optimal subset repairs: NP-hard to approximate within 17/16. Presents a (2 - 1/2^{sigma-1})-approx algorithm (sigma = number of FDs), the current best; ratio improves with many quasi-Turan clusters; validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12099
Venue: VLDB
Year: 2020
Pagerank: 4.697534e-05
Overall Rank: 7,605 | 47.10%
DOI: 10.14778/3407790.3407809

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05
10,213	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.1945683e-05
11,195	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
623	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018996374
1,012	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.0001464733
1,041	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00014482047
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013390321
1,627	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011086905
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
3,524	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	7.0087032e-05
8,166	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	4.5712945e-05
9,196	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	4.3749064e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
2,823	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0593894e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1945683e-05
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
1,624	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011099222
9,748	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2897489e-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
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05