分布式大数据函数依赖发现

计算机研究与发展ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔＤＯＩ：１０．７５４４／ｉｓｓｎｌｏｏＯ一１２３９．２０１５．２０１４０２２９５２（２）：２８２—２９４，２０１５分布式大数据函数依赖发现李卫榜李战?怀陈群姜西安涛刘海龙７１００７２）潘巍（西北工业大学计算机科学学院（ｗｂｌｉ２００３＠１６３．ｃｏｍ）ＦｕｎｃｔｉｏｎａｌＤｅｐｅｎｄｅｎｃｉｅｓＤｉｓｃｏＶｅｒｉｎｇｉｎＤｉｓｔｒｉｂｕｔｅｄＢｉｇＤａｔａＬｉＷｅｉｂａｎｇ，ＬｉＺｈａｎｈｕａｉ，ＣｈｅｎＱｕｎ，ＪｉａｎｇＴａｏ，ＬｉｕＨａｉｌｏｎｇ，ａｎｄＰａｎＮｏｒｆ＾叫ｅｓ￡Ｐｒ扎ＰｏＺｙ￡ｅｃ矗ｎｉｃ口ＺＷｅｉ（ＣｏＺＺ已班ｏ，Ｃｏｍ户群蛔，Ｓｃ妇ｎｃｅ，Ａｂｓｔｒ眦ｔＤｉｓｃｏｖｅｒｉｎｇＵｈｉ口８ｒ５ｉ缈，Ｘｉ’Ⅻ７１００７２）（ＦＤｓ）ｆｒｏｍｒｅｌａｔｉｏｎａｌｄａｔａｂａｓｅｓｉｓａｎｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓａｉｍｐｏｒｔａｎｔｄａｔａｂａｓｅａｎａｌｙｓｉｓｔｅｃｈｎｉｑｕｅ，ｗｈｉｃｈｈａｓｓｅｍａｎｔｉｃｓａｎａｌｙｓｉｓ，ｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｓｓｉｚｅｏｎｌｙ．ｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａｔｉｏｎｓｉｎｋｎｏｗｌｅｄｇｅｄｉｓｃｏＶｅｒｙ，ｄａｔａｂａｓｅＥｘｉｓｔｉｎｇｆｕｎｃｔｉｏｎａｌｓｕｉｔａｂｌｅｔｏｄａｔａｑｕａｌｉｔｙａｓｓｅｓｓｍｅｎｔａｎｄｄａｔａｂａｓｅｄｅｓｉｇｎ．ａｒｅｄｅｐｅｎｄｅｎｃｉｅｓｏｆｓｍａｎｄａｔａｍａｉｎｌｙａｐｐｌｉｅｄｉｎｃｅｎｔｒａｌｉｚｅｄｄａｔａ，ａｎｄｉｓｆａｒｍｏｒｅｃｈａｌｌｅｎｇｉｎｇＩｎｔｏａｒｅｔｈｅｃａｓｅＨｏｗｅｖｅｒ，ｅｓｐｅｃｉａｌｌｙｉｔｄｉｓｃｏｖｅｒｆｕｎｃｔｉｏｎａｌｗｅｐｒｏｐｏｓｅｅｘｅｃｕｔｅｓｅｔａｄｅｐｅｎｄｅｎｃｉｅｓｉｎｄｉｓｔｒｉｂｕｔｅｄｄｅｐｅｎｄｅｎｃｉｅｓｄａｔａｂａｓｅｓ，ｗｉｔｈｂｉｇｄａｔａ．ｔｈｉｓｐａｐｅｒ，ｎｏｖｅｌｆｕｎｃｔｉｏｎａｌｄｉｓｃｏｖｅｒｉｎｇａｐｐｒｏａｃｈｉｎｄｉｓｔｒｉｂｕｔｅｄｂｉｇｄａｔａ．ＦｉｒｓｔｌｙｗｅｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓｄｉｓｃｏＶｅｒｉｎｇｏｎｔｏａｌｇｏｒｉｔｈｍｉｎｐａｒａｌｌｅｌｉｎｅａｃｈｎｏｄｅ，ｔｈｅｎｐｒｕｎｅｔｈｅｃａｎｄｉｄａｔｅｔｈｅｒｅｓｕｌｔｓｏｆｄｉｓｃｏｖｅｒｙ．Ｓｅｃｏｎｄｌｙｗｅｇｒｏｕｐｔｈｅｃａｎｄｉｄａｔｅｓｅｔｏｆｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓｂａｓｅｄｏｆｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓａｃｃｏｒｄｉｎｇｅｘｅｃｕｔｅｔｈｅｆｅａｔｕｒｅｓｏｆｃａｎｄｉｄａｔｅｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓ’１ｅｆｔｈａｎｄｓｉｄｅ，ａｎｄｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｂａｓｅｄｅｖｅｎｔｕａｎｙ．ｓｈｉｐｍｅｎｔｏｎｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓｄｅｐｅｎｄｅｎｃｙｅａｃｈｃａｎｄｉｄａｔｅｓｅｔｉｎｐａｒａｌｌｅｌ，ａｎｄｇｅｔａＵｔｈｅｆｕｎｃｔｉｏｎａｌｔｏＷｅａｎｄａｎａｌｙｚｅｔｈｅｎｕｍｂｅｒｏｆｃａｎｄｉｄａｔｅｆｕｎｃｔｉｏｎｓｗｉｔｈｒｅｇａｒｄｌｏａｄｂａｌａｎｃｅａｒｅｄｉｆｆｅｒｅｎｔｇｒｏｕｐｓ，ａｎｄｄａｔａｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓ．ｄｉｓｃｏｖｅｒｉｎｇｔａｋｅｎｄａｔａｓｅｔｓｉｎｔｏａｃｃｏｕｎｔｗｈｅｎｔｈａｔｄｉｓｃｏｖｅｒｉｎｇｃｏｍｐａｒｅｄＥｘｐｅｒｉｍｅｎｔｓｏｎｒｅａｌ—ｗｏｒｌｄｂｉｇｄｅｍｏｎｓｔｒａｔｅｗｉｔｈｐｒｅＶｉｏｕｓｍｅｔｈｏｄｓ，ｏｕｒａｐｐｒｏａｃｈｉｓｍｏｒｅｅｆｆｅｃｔｉｖｅｉｎｅｆｆｉｃｉｅｎｃｙ．Ｋｅｙｗｏｒｄｓｄｉｓｃｏｖｅｒｉｎｇｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓ；ｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓ；ｂｉｇｄａｔａ；ｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ摘要在关系数据库中，函数依赖发现是一种十分重要的数据库分析技术，在知识发现、数据库语义分析、数据质量评估以及数据库设计等领域有着广泛的应用．现有的函数依赖发现算法主要针对集中式数据，通常仅适用于数据规模比较小的情况．在大数据背景下，分布式环境函数依赖发现更富有挑战性．提出了一种分布式环境下大数据的函数依赖发现算法，其基本思想是首先在各个节点利用本地数据并行进行函数依赖发现，基于以上发现的结果对函数依赖候选集进行剪枝，然后进一步利用函数依赖的左部（１ｅｆｔｈａｎｄｓｉｄｅ，ＬＨＳ）的特征，对函数依赖候选集进行分组，针对每一组候选函数依赖并行执行分布式环境发现算法，最终得到所有函数依赖．对不同分组情况下所能检测的候选函数依赖数量进行了分析，在算法的执行过程中，综合考虑了数据迁移量和负载均衡的问题．在真实的大数据集上的实验表明，提出的检测算法在检测效率方面与已有方法相比有明显的提升．关键词函数依赖发现；函数依赖；大数据；知识发现；并行计算中图法分类号ＴＰ３１１．１３收稿日期：２０１４—１１一０６；修回日期：２０１４—１２一０８基金项目：国家“九七三”重点基础研究发展计划基金项目（２０１２ｃＢ３１６２０３）；国家自然科学基金项目（６１４７２３２１，６１０３３００７）；国家“八六三”高技术研究发展计划基金项目（２０１２ＡＡ０１１００４）；西北工业大学基础研究基金项目（３１０２０１４ＪＳＪｏ００５，３１０２０１４ＪＳＪ００１３）万方数据李卫榜等：分布式大数据函数依赖发现规则发现是数据挖掘中的一项重要任务．关系数据库中，函数依赖发现在知识发现、数据库语义分析、数据质量评估以及数据库设计等领域有着广泛的应用．大数据背景下数据有着４Ｖ特征，即数据量巨大（ｖ０１ｕｍｅ）、数据类型繁多（ｖａｒｉｅｔｙ）、数据更新速度快（ｖｅｌｏｃｉｔｙ）和价值密度低（ｖａｌｕｅ）等特点［１。２］．这些特点使得传统的函数依赖发现算法很难适合大数据环境．函数依赖（ｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｙ，ＦＤ）是关系数据库中两个属性集合的属性值之间的约束关系表示．例如学生信息表中，学号可以决定学生姓名，这里：“学号决定学生姓名”就是一个函数依赖．通常情况下，关系数据库Ｒ上的实例，一的函数依赖可以表示成形如：Ｘ—ｙ的形式，其中Ｘ，ｙＥｕ，Ｕ为ｒ的属性集合．函数依赖ｘ—ｙ成立的条件为：对所有的元组对≠。，￡，∈ｒ（Ｕ），如果满足ｆ。［Ｘ］一￡ｉ［Ｘ］，则必有￡ｉ［ｙ］一￡，［ｙ］．从数据中发现函数依赖有着十分重要的意义．例如，从一个包含化合物信息的数据库中发现某些化合物函数依赖于特定的结构属性，则对于化工合成来说，有着十分重要的应用价值［３］．由于函数依赖有着重要的应用价值，很多学者对集中式环境下关系数据中发现函数依赖的问题进行了相关研究，并提出了多种函数依赖发现算法［３。１１Ｉ．现有的函数依赖发现算法主要针对小规模、集中式分布的数据，不适合分布式环境和大数据的情况．在分布式环境下数据分布在不同的节点，节点间通过网络进行连接．由于每个节点仅包含部分数据，在单个节点执行传统的函数依赖发现算法所得到的函数依赖仅满足局部数据，未必满足整体数据．例１．图１是一个分布式数据库的示例：谢ＺＢＣ１口ｌ６１Ｃ１２ｄ１６ｌＣ２ｌ耐０口Ｃ３口２６２Ｃｌ４口１６２Ｃ２４口ｌ６２Ｃ２５口２６１Ｃｌ５口２６１Ｃ１６ｄ２６ｌＣ２６口２６ｌＣ２（砷ｎ，ｄｌｓｔｎｂｕｔｅｄａｔＪｌ（ｂ）咆，ｄＩｓｔｎｂｕｔｅｄａｔ眈（ｃ，，ｌ＋，２Ｆｉｇ．１Ａｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅ．图１一个分布式数据库在该分布式数据库中，原始数据如图１（ｃ）所示，原始数据分别分布在ｓ。和ｓｚ两个节点上，如图１（ａ）（ｂ）所示．数据库实例ｒ。和ｒ。均包含４个属性，分别为ｉｄ，Ａ，Ｂ，Ｃ．从图１不难看出，对ｒ，来说，任意元组对￡；和≠ｉ，如果满足￡，［Ａ］一≠，［Ａ］，则必定存万方数据在￡，［Ｂ］一巧［Ｂ］．如对￡，［Ａ］一￡：［Ａ］＝口，，存在￡，［Ｂ］一￡。［Ｂ］一６。，反之亦然，根据函数依赖的定义，ｒ，上存在函数依赖Ａ—Ｂ，Ｂ—Ａ．同理，ｒ。上同样存在函数依赖Ａ—Ｂ，Ｂ—Ａ．说明函数依赖Ａ—Ｂ，Ｂ—Ａ在分布式环境的局部数据上成立，但是对于全局数据，如图１（ｃ）所示，存在￡，［Ａ］一￡。［Ａ］一口。，但是￡，［Ｂ］＝易。，ｆ。［Ｂ］＝６：，≠。［Ｂ］≠屯［Ｂ］，因此函数依赖Ａ—Ｂ在全局数据上不成立．由此可见，分布式环境下，在各个分布式节点上成立的函数依赖在集中式环境下未必成立，因此现有的集中式环境下的函数依赖发现算法对分布式环境并不适用．从本例不难看出，分布式环境下进行函数依赖发现需要进行数据迁移，无法直接使用现有的函数依赖发现算法．关于函数依赖发现的现有研究比较多，主要针对集中式环境下函数依赖的发现，其中比较典型的有ＴＡＮＥ［３］，ＦＵＮ［４１和Ｆａｓｔｆｄｓ［５３等．分布式环境下，数据分布在不同的节点，上述的函数依赖发现算法无法直接使用．此外，由于已有的算法复杂度与数据规模呈指数级关联，因此在大数据背景下现有的检测算法效率比较低．本文研究了分布式环境下大数据函数依赖发现的相关问题，提出了一种分布式环境下大数据的函数依赖发现算法，其基本思想是首先在各个节点利用本地数据并行执行函数依赖发现算法，基于以上发现的结果对函数依赖候选集进行剪枝，然后进一步利用函数依赖的左部（１ｅｆｔｈａｎｄｓｉｄｅ，ＬＨｓ）的特征，对函数依赖候选集进行分组，针对每一组候选函数依赖并行执行分布式环境发现算法，最终得到所有函数依赖．在算法的执行过程中，综合考虑了数据迁移量和负载均衡的问题．通过对数据迁移量和负载均衡的权衡和折衷，可以在尽量减少数据迁移量的基础上，有效提高算法的函数依赖发现效率．本文的主要工作及贡献如下：１）给出了适合分布式环境的候选函数依赖搜索策略和函数依赖发现的剪枝策略，分析并论证了候选函数依赖剪枝的特点；２）研究了分布式环境下函数依赖发现，分别给出了集中式发现算法和并行发现算法；３）分析了基于散列进行数据重分布及并行函数依赖发现的问题，给出了候选函数依赖的分组策略；４）基于真实数据集和人工数据集通过实验验证了本文提出的分布式环境下函数依赖发现算法，并进行了对比分析．２８４本文使用真实及人工大数据集基于ＨａｄＯｏｐ和Ｈａｍａ平台对提出的分布式环境函数依赖发现方法进行了实验验证．实验结果表明，本文的方法在数据规模和分片数量方面扩展性良好，在减少响应时间方面效果明显．１相关工作１．１函数依赖发现现有的函数依赖发现算法主要是针对集中式环境进行函数依赖发现，根据发现方法的不同总体上来说可以分成两种：自顶向下的发现算法和自底向上的发现算法［６］．这两种方法的不同之处在于：自顶向下的发现算法从函数依赖的最短的左端到最长的左端，逐层生成候选函数依赖，然后对生成的候选函数依赖进行验证，从中发现函数依赖；自底向上的发现算法与之不同，先通过元组的比较得到一致集合（ａｇｒｅｅ—ｓｅｔｓ）或差异集合（ｄｉｆｆｅｒｅｎｃｅ—ｓｅｔｓ），然后生成候选函数依赖，最后在一致集合和差异集合上验证生成的候选函数依赖是否满足．自顶向下的函数依赖发现算法中，以研州Ｅ［３］，ＦＵＮＬ４］和ＦＩ）＿Ｍｉｎｅ［７３等为代表．ＴＡＮＥ方法和ＦＵＮ方法根据元组的属性值将元组划分成不同的集合，然后在不同的划分上对候选函数依赖进行检测．通过逐层发现的方法，在每一层对候选函数依赖进行验证，生成符合条件的函数依赖，然后根据发现的结果生成下一层的候选函数依赖．ＴＡＮＥ方法和ＦＵＮ方法的主要区别在于剪枝策略的不同．ＦＤ—Ｍｉｎｅ方法考虑函数依赖Ａｒｍｓｔｒｏｎｇ公理系统得到候选函数依赖剪枝策略，在逐层发现过程中对候选函数依赖进行剪枝．与自顶向下的方法不同，自底向上的函数依赖发现算法不对候选函数依赖在整个数据库元组上进行验证，而是基于元组间比较得到一致集合和差异集合，对生成的候选函数依赖进行验证．比较典型的方法有ＦａｓｔＦＤｓ［５１和Ｄｅｐ—Ｍｉｎｅｒ［８］等．ＦａｓｔＦＤｓ和Ｄｅｐ—Ｍｉｎｅｒ首先从初始数据库中得到一个划分，根据该划分计算出一致集合和差异集合，根据得到的一致集合和差异集合可以发现最小的函数依赖覆盖．ＦａｓｔＦＤｓ和Ｄｅｐ—Ｍｉｎｅｒ的主要区别在于Ｄｅｐ—Ｍｉｎｅｒ使用了一种逐层搜索的方法，而ＦａｓｔＦＤｓ方法采用的是一种深度优先的搜索策略．文献［１２］研究了分布式数据库函数依赖挖掘方法，给出了一个分布式数据库函数依赖挖掘框架，首万方数据计算机研究与发展２０１５，５２（２）先在各个节点进行函数依赖发现，然后根据发现的结果对候选函数依赖集合进行剪枝，最后将各个节点的数据集中到一个中心节点，在中心节点执行集中式环境下的函数依赖挖掘算法．该方法可以实现分布式数据库的函数依赖挖掘，但是由于主要的挖掘执行过程还是在集中式环境进行，因此方法的效率比较低，而且不适合规模较大的数据．１．２条件函数依赖发现条件函数依赖（ｃｏｒ湎ｔｉｏｍｌｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｉｅｓ，ＣＦＤｓ）是对传统函数依赖的扩展，主要用于数据清洗、数据质量等方面．文献［１３—１６］对条件函数依赖发现的相关问题进行了研究，其中文献［１３—１５］主要研究了关系数据上条件函数依赖的发现．文献［１６］研究了半结构化数据ＸＭＬ上条件函数依赖的发现．ｗｅｎｆｅｉ等人口胡研究了集中式环境下条件函数依赖的发现问题，提出了３种发现条件函数依赖的方法：第１种方法称为ＣＦＤＭｉｎｅｒ，基于挖掘闭包项集的方法用于发现常量函数依赖；另外两种方法用于发现普通条件函数依赖．其中一种方法是对ＴＡＮＥ［３］方法的扩展，称为ＣＴＡＮＥ，逐层发现条件函数依赖；另外一种方法ＦａｓｔＣＦＤ在数据集规模比较大时比ＣＴＡＮＥ更加高效．２预备知识本节主要介绍函数依赖、元组等价类的划分等内容．２．１函数依赖函数依赖可以看作是定义在关系上的完整性约束．假定Ｒ是一个关系模式，在其上定义了一个函数依赖集合，Ａ≠ｆｒｓ（Ｒ）一｛Ａ，，Ａ。，…，Ａ。｝定义了Ｒ上的属性集合，Ｒ上的每一个属性Ａ∈Ａ￡￡”（Ｒ）的域用Ｄｏｍ（Ａ）表示．Ｒ的一个实例工是一个元组的集合，其中每一个元组属于Ｄｏｍ（Ａ，）×…×Ｄｏｍ（Ａ。）．这里用炬Ａ］表示元组￡的属性Ａ的值，用￡［Ｌ］表示Ａ≠￡，．ｓ（Ｒ）中一组属性Ｌ在￡上的投影．定义ｌ［１７｜．一个函数依赖（简称ＦＤ）是定义在关系Ｒ上的形如Ｘ—ｙ的表达式，这里Ｘ，ｙ是Ａ≠￡ｒｓ（Ｒ）上的属性集合．函数依赖Ｘ—ｙ在关系Ｒ上成立，当且仅当：对Ｒ的每一个实例，如果Ｒ中的任意两个元组有着相同的Ｘ属性值，则必然有着相同的ｙ属性值．在函数依赖Ｘ—ｙ中，Ｘ决定ｙ．函数依赖Ｘ—ｙ是平凡的，如果ｙ是Ｘ的一个子集．平凡函数依赖对所有的关系实例都成立．如果李卫榜等：分布式大数据函数依赖发现函数依赖满足ｙｎＸ一⑦，则这个函数依赖是非平凡的．对于函数依赖Ｐ：Ｘ—ｙ，ｘ是函数依赖９的左部（ＬＨＳ），而ｙ是９的右部（ｒｉｇｈｔｈａｎｄｓｉｄｅ，ＲＨＳ）．由于平凡函数依赖对所有关系实例都成立，这里所要发现的函数依赖为非平凡函数依赖．给定关系Ｒ的实例Ｄ，Ｄ水平切分为（Ｄ，，…，Ｄ。），假定Ｄ的每一个切分分布在一个单独的节点上，对于ｉ∈［１，押］，Ｄ；分布在节点Ｓ。上．假定三为关系Ｒ的候选函数依赖的集合，为发现关系Ｒ上的函数依赖，需要对三中的每一个候选函数依赖进行验证，即对于任一函数依赖９∈三，验证９在Ｒ上是否满足，即验证Ｒ上是否存在违反函数依赖妒的元组，记为Ⅵｏ￡Ⅱ（妒，Ｄ），如果１Ⅵｏ￡Ⅱ（妒，Ｄ）Ｉ＞Ｏ，说明存在违反妒的元组，９不是Ｒ上的函数依赖．２．２划分关系ｒ上的任意两个元组ｆ。和≠：在属性集合Ｘ∈Ｒ上是等价的，如果对任一属性Ａ∈Ｘ，满足条件￡。［Ａ］一￡。［Ａ］．定义２．关系ｒ在属性集合Ｘ上所有等价的元组组成的一个集合称为ｒ在ｘ上的一个等价类［３］．在例１中，，一。在属性Ａ上的一个等价类为｛１，２），这里用元组的ｉｄ表示一个元组．定义３．关系ｒ上基于属性集Ｘ将ｒ中所有元组分成不同的等价类，称为，一在Ｘ上的一个划分，用瓜表示关系ｒ在属性集Ｘ上的一个划分［３］．以例１中ｎ＋ｒ。为例，基于属性集合｛Ａ），可以将ｒ，＋ｒ：划分成等价类Ⅱ｛Ａ）一｛｛１，２，４），｛３，５，６｝）．同理，分别基于属性集合｛Ｂ｝和｛Ｃ），可以将ｒ。＋ｒ。划分成等价类Ⅱ｛。｝一｛｛１，２，５，６），｛３，４））和Ⅱ｛ｃ｝一｛｛１，３，５），｛２，４，６））．这里用ｌⅡｘＩ表示划分Ⅱｘ中等价类的个数．引理１［３］．函数依赖Ｘ—Ａ成立，当且仅当满足条件Ｉｍｌ—ｌⅡｘＬＪＡＩ．３候选函数依赖搜索和剪枝３．１搜索策略前面提到，由于平凡函数依赖在任何情况下都成立，这里只需要搜索非平凡函数依赖．给定关系ｒ的属性集合Ｘ，在进行候选函数依赖搜索时，对所有形式如Ｘ＼｛Ａ）一Ｘ进行搜索，这保证了搜索的所有候选函数依赖为非平凡的函数依赖．候选函数依赖的搜索本文采用逐层搜索的方法，如图２所示．在具万方数据体搜索过程中，本文采用候选函数依赖的ＬＨＳ部分包含属性个数由多到少的方向进行搜索，这种搜索的一个好处是便于进行候选函数依赖的剪枝．假定关系ｒ包含咒个属性，则在逐层搜索时，首先从第１层开始，搜索ＬＨＳ部分包含（咒一１）个属性的候选函数依赖，即（咒一１）一ａｔｔｒ候选函数依赖．然后进入第２层，搜索（狎一２）一ａｔｔｒ候选函数依赖，以此类推，直到搜索完第咒一１层，得到所有１一ａｔｔｒ的候选函数依赖为止．ＬｅｖｅｌｌＡＢＣＡＢＤＡＣＤＢＣＤＢＣＢＤＣＤ３ＡＢＣＤ４Ｆ‘ｌｇ．２ＣａｎｄｌｄａｔｅＦ、Ｄｓｃｏｍｂｌｎａｔｌｏｎｓｗｉｔｈａｔｔｒｉｂｕｔｅｓｓｅｔ｛Ａ，Ｂ，Ｃ，Ｄ）．图２属性集为｛Ａ，Ｂ，Ｃ，Ｄ）时候选函数依赖组合在图２中，关系ｒ包含４个属性，分别为Ａ，Ｂ，Ｃ和Ｄ．在进行函数依赖搜索时，从第１层开始，首先搜索在ＬＨＳ部分包含３个属性的候选函数依赖，共有４个，分别为ＡＢＣ—Ｄ，ＡＢＤ—Ｃ，ＡＣＤ—Ｂ，以及ＢＣＤ—Ａ．第１层搜索完毕转入第２层，该层包含的候选函数依赖有１２个，分别为ＡＢ—Ｃ，ＡＢ—Ｄ，ＡＣ—，Ｂ，ＡＣ—，Ｄ，ＡＤ—，Ｂ，ＡＤ—，Ｃ，ＢＣ—，Ａ，ＢＣ—，Ｄ，ＢＤ—Ａ，ＢＤ—Ｃ，ＣＤ—Ａ，ＣＤ—Ｂ．然后转入第３层，搜索１一ａｔｔｒ的候选函数依赖，共有１２个，分别为Ａ—Ｂ，Ａ—Ｃ，Ａ—Ｄ，Ｂ—Ａ，Ｂ—Ｃ，Ｂ—Ｄ，Ｃ—Ａ，Ｃ—Ｂ，Ｃ?Ｄ，Ｄ—Ａ，Ｄ—Ｂ，Ｄ—Ｃ．至此，所有非平凡函数依赖都搜寻完毕．３．２剪枝策略为提高函数依赖发现的效率，考虑对候选函数依赖集进行剪枝．在３．１节中给出了候选函数依赖的搜索策略，从ＬＨＳ部分包含最多属性的候选函数依赖开始，逐层向下进行搜索．在搜索过程中，如果出现候选函数依赖不成立的情况，则可以对与之相关的ＬＨＳ部分包含较少属性的候选函数依赖进行剪枝．引理２．如果候选函数依赖Ｘ—Ａ不成立，即Ｘ≯Ａ，则必然有ｙ书Ａ，其中ｙ［Ｘ．证明．假定函数依赖ｙ—Ａ成立，其中ｙ［Ｘ，则根据阿姆斯特朗公理系统的自反律：若ｙ∈Ｘ，则Ｘ—Ｙ成立．由于ｙｃＸ，故Ｘ—ｙ成立．根据阿姆斯特朗公理系统的传递律：若ｘ—ｙ，ｙ—Ｚ，则Ｘ—，ｙ．这里Ｘ—ｙ，而又假定函数依赖ｙ—Ａ成立，故函数依赖Ｘ—Ａ成立．这与已知函数依赖Ｘ—Ａ不成立相互矛盾．故假定函数依赖ｙ—Ａ不成立，即ｙ扣４．证毕．前面提到，在进行候选函数依赖搜索时，从ＬＨｓ部分包含最多属性的候选函数依赖开始，向下逐层进行．对每一个搜索到的候选函数依赖进行验证，如果遇到非函数依赖的情况，则对ＬＨＳ部分为当前候选函数依赖ＬＨｓ部分真子集的候选函数依赖进行剪枝．图３是对候选函数依赖进行剪枝的一个示例：Ｌｅｖｅｌ１２ＢＣＢＤＣＤ３爿ＢＣＤ４Ｆｉｇ．３ＰｒｕｎｉｎｇｏｆｃａｎｄｉｄａｔｅＦＤｓｃｏｍｂｉｎａｔｉｏｎｓ’ｓｅａｒｃｈｓｐａｃｅ．图３候选函数依赖搜索空间剪枝在图３中，假定经过验证候选函数依赖ＡＢＣ—Ｄ不成立，则根据引理２，ＬＨＳ部分为｛Ａ，Ｂ，Ｃ）真子集，且ＲＨＳ部分为｛Ｄ）的所有候选函数依赖都不成立，因此可以对候选函数依赖搜索空间进行剪枝，可剪枝的候选函数依赖包括：ＡＢ—Ｄ，ＡＣ—Ｄ，ＢＣ—Ｄ，Ａ—Ｄ，Ｂ—Ｄ，Ｃ—Ｄ，即图３中加粗的连线部分所表示的候选函数依赖，这样可以大大减少搜索空间及有效提高函数依赖发现的效率．对于包含挖个属性的关系ｒ，其上面的ＬＨＳ部分包含最多属性个数的候选函数依赖为（卵一１）一ａｔｔｒ候选函数依赖．引理３．任一（咒一１）一ａｔｔｒ候选函数依赖ｐ不成立，则可以对包含２”１—２个候选函数依赖的集合①中所有候选函数依赖进行剪枝，其中：Ｖｐ７∈①，满足ＬＨＳ（∞７）ｃＬＨＳ（∞）．证明．由于可剪枝的候选函数依赖的ＬＨＳ部万方数据计算机研究与发展２０１５，５２（２）分为（咒一１）一ａｔｔｒ候选函数依赖的ＬＨＳ部分的真子集，因此可剪枝的候选函数依赖ＬＨＳ部分包含属性个数最多为咒一２个，最少为１个．ＬＨＳ部分属性个数为挖一２的候选函数依赖个数为Ｃ：二ｊ个，ＬＨＳ部分属性个数为咒一３的候选函数依赖个数为Ｃ：二｛个，…，ＬＨＳ部分属性个数为１的候选函数依赖个数为Ｃ：一，个，因此总的可剪枝候选函数依赖个数为ＣＬ。＋Ｃ０。＋Ｃ０。＋…＋Ｃ篇一Ｃ譬。＋Ｃ■。＋Ｃ０。＋Ｃ■，＋…＋Ｃ：二｛＋Ｃ：二｛一Ｃ：一１一Ｃ：二｛一２”１—１—１—２”１—２．证毕．从引理３不难看出，如果（行一１）一ａｔｔｒ候选函数依赖不成立，则可以被剪枝的候选函数依赖与关系ｒ中包含属性的个数咒呈指数级增长，关系ｒ中包含属性的个数越多，可以被剪枝的候选函数依赖也越多，这样可以大大缩减发现候选函数的搜索空间．４水平切分的分布式大数据函数依赖发现与集中式相比，在分布式环境下进行函数依赖发现更具有挑战性，而且通常需要进行节点间的数据迁移．在进行函数依赖发现时，对于每一个候选函数依赖，需要确定哪些元组需要迁移以及迁移到哪个节点，对于单个函数依赖来说，该问题已经是非平凡的口８｜，根据前面的介绍，找出一个具有最小通信代价的函数依赖发现算法是ＮＰ一难的．这里给出了分布式环境下大数据函数依赖发现的有效方法：１）通过利用候选函数依赖的结构特征对候选函数依赖进行分组，组内的候选函数依赖可以通过一次数据重分配进行平行发现；２）利用各个节点并行发现函数依赖，有效提高函数依赖的发现效率，大大减少函数依赖发现所耗费的时间．４．１集中式发现算法首先给出分布式环境下水平切分的大数据函数依赖的集中式发现算法．算法ＦＤＣ盯一ＤｉｓｃｏｕＰｒ是一个基本方法，该算法将分布式大数据函数依赖发现问题转化为集中式数据函数依赖发现问题．首先统计各个节点的元组个数，然后选择一个节点作为函数依赖发现的执行节点，其余节点将本节点的所有元组数据发送到执行节点，然后在执行节点执行集中式函数依赖发现算法．算法执行过程中，首先选择一个节点Ｓ，作为函数依赖发现的执行节点，别的节点上的元组都迁移到节点Ｓｊ，最后函数依赖发现可