Fast Discovery of Functional Dependencies via Bayesian Network Learning

Functional dependencies (FDs) are fundamental to data quality and query optimization. However, discovering highconfidence FDs from large-scale, noisy real-life datasets remains challenging, especially for those with low-support which can be early pruned. In view of this challenge, we propose BSFD, a scalable and parallel framework that leverages Bayesian network (BN) structure learning to guide the discovery of meaningful FDs with low support and high confidence $\left(\text{FD}_{\sigma, \delta} \mathrm{s}\right)$. We establish a numerical equivalence between FDs and parent-child relationships in BNs, which lays the statistical foundation of our approach. We have also proposed a stratified sampling strategy with a theoretical bound on structure correctness relative to the sampling ratio, which enables efficient BN learning with structural accuracy preserved. As for large datasets, BSFD vertically partitions the input relation into multiple smaller sub-tables using BN-derived correlated attribute sets, which significantly reduces the search space. Experiments on real-life and synthetic datasets demonstrate that BSFD achieves on average $490 \times$ and up to 7008× speedup over baseline methods while maintaining high discovery accuracy, with an average $F_{1}$ score of 0.98.