论文部分内容阅读
函数依赖(Functional Dependency,FD)是关系型数据库中最常见的约束条件,它表示了数据库中属性之间的依赖关系。FD在数据库的分析与设计、数据库查询优化、关系模式规范化、数据集成和数据清洗等领域有着广泛的应用。但是,对于特定数据集,其FD通常是未知的,并且几乎不可能手动发现。因此,FD发现算法的研究一直是数据库领域内的热点问题。近年来,随着互联网等信息技术的快速发展,各行各业已步入大数据时代。在大规模数据场景下,典型的单机FD发现算法,如TANE、FUN、DFD、Dep-Miner、FastFDs、Fdep和HyFD等,存在着计算效率低、计算时间长以及内存开销大等问题。因此,这些单机算法可扩展性较差,无法高效地处理大规模数据。为了能够解决大规模FD发现的问题,一些研究人员提出了分布式并行的FD发现算法,如MFDM、HFDD和FDPar_Discover等。但是,这些分布式算法的列可扩展性较差,且均未考虑负载均衡问题。因此,亟需研究面向大数据的、高效可扩展的、分布式大规模FD发现算法。为解决已有工作中的不足,本文从降低计算和网络通信开销以及提升计算资源利用率的角度入手,设计了一种计算量低、数据传输量少和资源利用率高的分布式FD发现算法SmartFD。本文的主要工作内容以及贡献点如下:(1)提出了一种基于基数、方差和倾斜度的属性排序算法,该算法能够提升FD发现初期的计算资源利用率。(2)提出了一种基于划分的分布式采样方法和并行化剪枝-生成方法,上述方法可以高效地发现不成立的FD,并根据不成立的FD对候选集进行快速地剪枝和生成。(3)提出了一种基于轻量级索引的分布式验证方法。该方法利用轻量级索引,降低了验证过程中计算和内存的开销。(4)提出了一种自适应的切换策略。该策略通过对采样和验证的自适应切换来提升算法的整体效率。(5)基于Spark平台设计实现了大规模分布式FD发现算法SmartFD,并将其与当前最优的单机算法HyFD和分布式并行算法HFDD进行了性能对比。实验结果表明,SmartFD相对于目前单机最优算法HyFD可达到1.0到45.5倍的加速;相对于并行化算法HFDD可达到2.5到455.7倍的加速。在较大规模的数据集上,SmartFD相对于HyFD算法取得了超线性的加速比,且随着数据集规模的增大,HyFD和HFDD算法已无法在设定的时间内运行出结果,SmartFD算法仍能够快速地进行FD发现。本文工作所设计实现的大规模分布式函数依赖发现算法,在2018年教育部科技发展中心主办的第四届“全国高校云计算应用创新大赛”大数据技能赛全国总决赛上,以优异的算法性能获得了第一名的成绩,荣获技能赛一等奖。