函数依赖是重要的元数据,用于描述数据集中列之间的关系,可以被用于很多任务中,例如范式结构标准化,数据清洗等。很多单机和并行函数依赖发现算法已经被提出。之前的单机算法在数据集较小且单机存储的时候很高效,但是缺乏并行能力;另一方面,现存的并行算法存在很大的通信开销,导致其表现不佳。为了解决这个问题,本文做了如下三方面的工作:首先是提出FD-Combine算法解决了“如何推导”的问题。现存并行算法最大问题是通信开销,我们尝试通过数据并行模式的并行来避免大量的通信开销,而数据并行模式的并行的首要问题就是”如何将部分数据上成立的函数依赖推导得到全体数据的函数依赖”,即“如何推导”的问题。为此,我们构建了BL代数系统和基础项表达,形式化了函数依赖、非函数依赖、部分函数依赖的性质与运算关系。在BL代数系统内,我们提出FD-Combine算法,在每部分数据集即数据块满足一定条件时,可以将部分函数依赖推导得到全体数据上的函数依赖。我们对比FD-Combine算法与之前非函数依赖的推导算法,得到进一步理解,并给出FD-Combine算法的不同实现方式和相应的时间复杂度。然后,改造并选择了仿射平面区组设计算法解决了“如何分割”的问题。FD-Combine算法的推导需要分割后的数据块满足一定条件,“如何分割”的问题是指,“如何使分割结果在满足FD-Combine推导条件的同时,保证分割算法的高效和分割结果的质量”。我们将原问题转化为区组设计问题,使用“数据点”的技巧使得任意有构造的区组设计都可以作为分割算法;并设计了“数据占总比”的评价指标来衡量各个区组设计产生结果的质量。由于仿射平面区组设计算法“数据占总比”接近下界、产生的块数利于并行、算法简单易于实现,我们选择了该算法作为分割算法,并分析了时间复杂度。最后,结合FD-Combine算法与仿射平面区组设计算法,我们提出了一个通用并行策略,可以实现数据并行模式的并行。使用这个策略,每个单机发现算法都可以不加修改,直接并行运行在分布式环境中。我们证明了该策略在一定条件下,p线程的加速比为((?),p)。我们利用Spark进行线程管理,对该策略在不同算法、不同数据集上做了实验,实验结果显示,“列高效”算法的加速比通常接近(?),一些情况下甚至超过p/2。例如,FastFDs使用该策略后,在letter数据集上6线程加速比为5.0,20线程加速比为10.5。实验中,在使用该策略后,当前最优的多线程HYFD算法的性能也取得了显著的提升。在lineitem数据集上,原多线程HYFD算法54线程的加速比为2.9,使用策略后54线程的加速比达到了4.9。