Discovering Approximate Functional Dependencies Using Correlation Measures

Approximate functional dependencies (AFDs) are essential for schema design, data integration, and data quality assessment. However, existing discovery methods often suffer from cardinality bias, producing spurious and semantically meaningless dependencies, and their exhaustive search approach limits practicality for high-dimensional or large-scale datasets. This paper presents CAFD, a Correlation-based AFD Discovery framework that identifies statistically robust AFDs in real-world scenarios. CAFD utilizes a normalized mean-square contingency coefficient to quantify dependency strength and infer directionality, distinguishing true dependencies from symmetric correlations while mitigating cardinality bias. It employs a correlation-preserving category merging strategy to reduce dimensionality without distorting inter-attribute dependencies and integrates sampling and correlation-driven pruning to efficiently minimize search space. Extensive experiments on real-world and synthetic datasets demonstrate that CAFD consistently outperforms existing methods in accuracy and scalability, particularly in noisy, high-dimensional, and large-scale contexts.