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: he390641022574b83
Venue: VLDB
Year: 2020
Pagerank: 5.363617e-05
Overall Rank: 8,280 | 44.34%
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
9,004	The Cost of Representation by Subset Repairs	2025	VLDB	5.2389669e-05
10,688	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.9793485e-05
11,712	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9793485e-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.00049349003
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025872962
526	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016886621
697	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014694048
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014114806
803	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013836858
1,043	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00012335114
1,361	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010917917
1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.7545681e-05
2,595	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	8.2422907e-05
2,613	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2260448e-05
6,537	QOCO: A Query Oriented Data Cleaning System with Oracles	2015	VLDB	5.7535125e-05
8,392	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	5.3410855e-05

Semantically Similar Papers

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