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.8801067e-05
Overall Rank: 2,904 | 80.48%
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.00015699254
2,526	Stream Warehousing with DataDepot	2009	SIGMOD	8.3432541e-05
4,127	GDR: A System for Guided Data Repair	2010	SIGMOD	6.791747e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7183259e-05
4,347	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.6469984e-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.00027837289
473	Sampling Large Databases for Association Rules	1996	VLDB	0.00017673931
526	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016886621
649	Discovering Data Quality Rules	2008	VLDB	0.00015149865
1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012405065
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011156154
1,662	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9465656e-05
2,054	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1135465e-05
4,679	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4726631e-05
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-05
6,761	Propagating Functional Dependencies with Conditions	2008	VLDB	5.68869e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,887	Sequential Dependencies	2009	VLDB
2	2,677	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,843	Pattern Functional Dependencies for Data Cleaning	2020	VLDB
5	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
6	209	Dependency Inference	1987	VLDB
7	3,026	Functional Dependencies for Graphs	2016	SIGMOD
8	6,761	Propagating Functional Dependencies with Conditions	2008	VLDB
9	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB