The Cost of Representation by Subset Repairs

Summary: Studies the "cost of representation" in subset repairs for functional dependencies: how many extra deletions are needed to satisfy sub-population representation constraints beyond minimal repairs. Proves NP-hardness, gives polynomial-time algorithms for special cases, heuristics and experiments showing practical approximations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14081
Venue: VLDB
Year: 2025
Pagerank: 4.4388652e-05
Overall Rank: 8,840 | 38.51%
DOI: 10.14778/3705829.3705860

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,019	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	4.1945683e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1945683e-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
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
791	ActiveClean: Interactive Data Cleaning For Statistical Modeling	2016	VLDB	0.00016629664
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,211	Truth Finding on the Deep Web: Is the Problem Solved?	2013	VLDB	0.00013257101
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
4,769	Automated Feature Engineering for Algorithmic Fairness	2021	VLDB	5.934329e-05
6,291	Lightweight Inspection of Data Preprocessing in Native Machine Learning Pipelines	2021	CIDR	5.1269764e-05
6,546	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.0185588e-05
6,643	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	4.9786132e-05
7,066	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8445108e-05
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
623	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018996374
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
9,369	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD	4.3481081e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1945683e-05
3,192	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD	7.4095761e-05
1,624	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011099222
2,823	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0593894e-05
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412