Sampling the Repairs of Functional Dependency Violations under Hard Constraints

Summary: Samples FD repairs under hard constraints, not a single repair or only query answers. Introduces a new repair class, a randomized sampler, and constraint-aware pruning, with comparisons to prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10267
Venue: VLDB
Year: 2010
Pagerank: 0.00011129529
Overall Rank: 1,332 | 90.87%
DOI: 10.14778/1920841.1920868

Incoming Non-self Citations Over Time

Authors

1. George Beskales (University of Waterloo)
2. Ihab F. Ilyas (University of Waterloo)
3. Lukasz Golab (AT&T)

BibTeX Citation

@article{beskales_vldb10,
        title = {{Sampling the Repairs of Functional Dependency Violations under Hard Constraints}},
        author = {Beskales, George and Ilyas, Ihab F. and Golab, Lukasz},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {197--208},
        doi = {10.14778/1920841.1920868},
        url = {https://doi.org/10.14778/1920841.1920868},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
1,323	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011152602
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
2,041	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.2692538e-05
2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.1372798e-05
2,142	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	9.0975882e-05
2,398	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.631172e-05
2,759	Data X-Ray: A Diagnostic Tool for Data Errors	2015	SIGMOD	8.1577506e-05
2,981	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD	7.8960114e-05
4,488	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.668457e-05
4,598	Temporal Rules Discovery for Web Data Cleaning	2016	VLDB	6.6127851e-05
4,890	Descriptive and Prescriptive Data Cleaning	2014	SIGMOD	6.4590072e-05
4,959	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	6.4283324e-05
5,338	On Repairing Structural Problems In Semi-structured Data	2013	VLDB	6.2609275e-05
5,931	Your notebook is not crumby enough, REPLace it	2020	CIDR	6.0369708e-05
6,392	Qualitative Data Cleaning	2016	VLDB	5.8883971e-05
6,431	Finding Label and Model Errors in Perception Data With Learned Observation Assertions	2022	SIGMOD	5.8802622e-05
6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS	5.8066263e-05
7,314	Time Series Data Validity	2023	SIGMOD	5.6471526e-05
8,724	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.3766157e-05
10,322	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	5.093636e-05
11,567	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	5.093636e-05
12,042	BART in Action: Error Generation and Empirical Evaluations of Data-Cleaning Systems	2016	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00026231189
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB
2	8,838	The Cost of Representation by Subset Repairs	2025	VLDB
3	8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
4	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
5	533	Improving Data Quality: Consistency and Accuracy	2007	VLDB
6	2,041	Combining Quantitative and Logical Data Cleaning	2016	VLDB
7	9,590	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD
8	2,981	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD
9	8,241	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS
10	1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS