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.85486e-05
Overall Rank: 2,914 | 80.47%
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
602	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015670535
2,534	Stream Warehousing with DataDepot	2009	SIGMOD	8.3120592e-05
4,128	GDR: A System for Guided Data Repair	2010	SIGMOD	6.7763091e-05
4,245	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.6958006e-05
4,369	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	6.6220109e-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.00027775994
477	Sampling Large Databases for Association Rules	1996	VLDB	0.00017624579
527	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016859013
653	Discovering Data Quality Rules	2008	VLDB	0.00015102328
1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012373297
1,297	Extending Dependencies with Conditions	2007	VLDB	0.00011118907
1,670	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9124313e-05
2,063	Space Efficient Mining of Multigraph Streams	2005	PODS	9.0815237e-05
4,692	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4492362e-05
5,864	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9498215e-05
6,783	Propagating Functional Dependencies with Conditions	2008	VLDB	5.6675149e-05

Semantically Similar Papers

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