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: 4202
Venue: SIGMOD
Year: 2009
Pagerank: 8.0104819e-05
Overall Rank: 2,872 | 80.30%
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
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
2,502	Stream Warehousing with DataDepot	2009	SIGMOD	8.4972586e-05
4,059	GDR: A System for Guided Data Repair	2010	SIGMOD	6.9330647e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,488	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.668457e-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
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
462	Sampling Large Databases for Association Rules	1996	VLDB	0.00018065337
533	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.0001705859
647	Discovering Data Quality Rules	2008	VLDB	0.00015334666
1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012529852
1,277	Extending Dependencies with Conditions	2007	VLDB	0.00011368191
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
4,584	The Power of Sampling in Knowledge Discovery	1994	PODS	6.6181342e-05
5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	6.1062071e-05
6,639	Propagating Functional Dependencies with Conditions	2008	VLDB	5.8165825e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,842	Sequential Dependencies	2009	VLDB
2	2,633	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD
3	1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
4	4,757	Pattern Functional Dependencies for Data Cleaning	2020	VLDB
5	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
6	203	Dependency Inference	1987	VLDB
7	2,973	Functional Dependencies for Graphs	2016	SIGMOD
8	6,639	Propagating Functional Dependencies with Conditions	2008	VLDB
9	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB