The Computation of Optimal Subset Repairs

Summary: Studies optimal subset repairs for inconsistent databases, establishing a tighter 17/16 inapproximability threshold. Provides the best known (2−1/2^(σ−1))-approximation for σ FDs, with improved ratios on quasi-Turán clusters and empirical validation. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12287
Venue: VLDB
Year: 2020
Pagerank: 5.4867244e-05
Overall Rank: 8,103 | 44.41%
DOI: 10.14778/3407790.3407809

Incoming Non-self Citations Over Time

Authors

1. Dongjing Miao (Harbin Engineering University)
2. Zhipeng Cai (Georgia State University)
3. Jianzhong Li (Harbin Engineering University)
4. Xiangyu Gao (Harbin Engineering University)
5. Xianmin Liu (Harbin Engineering University)

BibTeX Citation

@article{miao_vldb20,
        title = {{The Computation of Optimal Subset Repairs}},
        author = {Miao, Dongjing and Cai, Zhipeng and Li, Jianzhong and Gao, Xiangyu and Liu, Xianmin},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {2061--2074},
        doi = {10.14778/3407790.3407809},
        url = {https://doi.org/10.14778/3407790.3407809},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,838	The Cost of Representation by Subset Repairs	2025	VLDB	5.3592132e-05
10,502	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	5.093636e-05
11,397	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00026231189
533	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.0001705859
725	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014617251
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
1,323	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011152602
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.9625097e-05
2,551	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	8.4290374e-05
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
6,471	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.8702801e-05
8,228	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	5.4621278e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
2	10,372	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD
3	6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS
4	1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
5	9,921	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS
6	185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
7	8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
8	8,241	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS
9	8,838	The Cost of Representation by Subset Repairs	2025	VLDB
10	1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS