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: 12100
Venue: VLDB
Year: 2020
Pagerank: 4.6020746e-05
Overall Rank: 8,014 | 44.31%
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,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05
10,213	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.1905499e-05
11,197	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1905499e-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.00067607389
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
621	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018978331
1,012	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014638349
1,037	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00014514825
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013373177
1,629	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011073148
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
2,574	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5126812e-05
3,531	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	6.9982256e-05
8,176	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	4.5634257e-05
9,218	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	4.3672293e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,045	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.6618214e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1905499e-05
6,740	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9401646e-05
1,625	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.0001109361
9,747	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2856385e-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
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05