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: heee10f11d0cb12af
Venue: VLDB
Year: 2010
Pagerank: 0.00010942213
Overall Rank: 1,348 | 90.95%
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
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033676943
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014108234
1,044	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00012329478
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010513265
2,054	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	9.1158071e-05
2,057	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.1086574e-05
2,127	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.9990594e-05
2,424	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.483813e-05
2,687	Data X-Ray: A Diagnostic Tool for Data Errors	2015	SIGMOD	8.1271333e-05
2,967	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD	7.8016942e-05
4,348	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.6438522e-05
4,652	Temporal Rules Discovery for Web Data Cleaning	2016	VLDB	6.4828106e-05
4,829	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	6.3887613e-05
5,000	Descriptive and Prescriptive Data Cleaning	2014	SIGMOD	6.3194405e-05
5,469	On Repairing Structural Problems In Semi-structured Data	2013	VLDB	6.1175518e-05
6,048	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9024167e-05
6,384	Qualitative Data Cleaning	2016	VLDB	5.8039496e-05
6,554	Finding Label and Model Errors in Perception Data With Learned Observation Assertions	2022	SIGMOD	5.7473435e-05
6,814	Benchmarking Approximate Consistent Query Answering	2021	PODS	5.6736541e-05
7,467	Time Series Data Validity	2023	SIGMOD	5.5178324e-05
8,895	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2534908e-05
10,540	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.9769913e-05
11,882	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	4.9769913e-05
12,343	BART in Action: Error Generation and Empirical Evaluations of Data-Cleaning Systems	2016	SIGMOD	4.9769913e-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.00049326063
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035960573
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025861123
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023251151

Semantically Similar Papers

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