Fast Discovery of Functional Dependencies via Bayesian Network Learning
Published in ICDE 2026
作者 Authors: Siyi Yang, Shenglin Chen, Xi Wang, Yuhua Tang, Ruochun Jin*
摘要 Abstract: Functional dependencies (FDs) are fundamental to data quality and query optimization. However, discovering high-confidence 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 (FDσ,δs). 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× and up to 7008× speedup over baseline methods while maintaining high discovery accuracy, with an average F1 score of 0.98.