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.00010912271
Overall Rank: 1,354 | 90.93%
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
100	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033951027
769	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014091996
989	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00012638176
1,490	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.0001047928
2,053	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	9.1054597e-05
2,056	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.10022e-05
2,131	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.9867472e-05
2,429	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4657925e-05
2,685	Data X-Ray: A Diagnostic Tool for Data Errors	2015	SIGMOD	8.116387e-05
2,958	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD	7.7991971e-05
4,369	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.6220109e-05
4,653	Temporal Rules Discovery for Web Data Cleaning	2016	VLDB	6.4706099e-05
4,852	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	6.3680596e-05
5,022	Descriptive and Prescriptive Data Cleaning	2014	SIGMOD	6.2989483e-05
5,488	On Repairing Structural Problems In Semi-structured Data	2013	VLDB	6.0973234e-05
6,062	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.8829004e-05
6,327	Qualitative Data Cleaning	2016	VLDB	5.7945802e-05
6,564	Finding Label and Model Errors in Perception Data With Learned Observation Assertions	2022	SIGMOD	5.7283392e-05
6,830	Benchmarking Approximate Consistent Query Answering	2021	PODS	5.6548934e-05
7,486	Time Series Data Validity	2023	SIGMOD	5.499587e-05
8,915	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2361195e-05
10,606	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.9605343e-05
11,926	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	4.9605343e-05
12,386	BART in Action: Error Generation and Empirical Evaluations of Data-Cleaning Systems	2016	SIGMOD	4.9605343e-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.00049435337
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
190	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025812169
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023188414

Semantically Similar Papers

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