Estimating the Confidence of Conditional Functional Dependencies

Summary: One- or two-pass, small-space estimation of CFD confidence via sampling and sketching. Works with known or discovered pattern tableaux, offering additive-error guarantees (no relative guarantees) and strong empirical accuracy with compact summaries on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb6566e2fee64b50c
Venue: SIGMOD
Year: 2009
Pagerank: 7.87641e-05
Overall Rank: 2,904 | 80.49%
DOI: 10.1145/1559845.1559895

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Lukasz Golab (AT&T)
3. Flip Korn (AT&T)
4. Andrew McGregor (University of Massachusetts Amherst)
5. Divesh Srivastava (AT&T)
6. Xi Zhang (State University of New York at Buffalo)

BibTeX Citation

@inproceedings{cormode_sigmod09,
        title = {{Estimating the Confidence of Conditional Functional Dependencies}},
        author = {Cormode, Graham and Golab, Lukasz and Korn, Flip and McGregor, Andrew and Srivastava, Divesh and Zhang, Xi},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559895},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559895},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015692059
2,525	Stream Warehousing with DataDepot	2009	SIGMOD	8.3393802e-05
4,127	GDR: A System for Guided Data Repair	2010	SIGMOD	6.7886034e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7151469e-05
4,348	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.6438522e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027827605
475	Sampling Large Databases for Association Rules	1996	VLDB	0.00017665769
526	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016879
650	Discovering Data Quality Rules	2008	VLDB	0.00015142855
1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012399252
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011150915
1,663	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.942673e-05
2,056	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1092395e-05
4,683	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4696103e-05
5,854	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9689965e-05
6,766	Propagating Functional Dependencies with Conditions	2008	VLDB	5.68609e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,888	Sequential Dependencies	2009	VLDB
2	2,672	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD
3	1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
4	4,845	Pattern Functional Dependencies for Data Cleaning	2020	VLDB
5	4,215	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
6	209	Dependency Inference	1987	VLDB
7	3,027	Functional Dependencies for Graphs	2016	SIGMOD
8	6,766	Propagating Functional Dependencies with Conditions	2008	VLDB
9	11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB