分布式大数据函数依赖发现(2)

李卫榜等：分布式大数据函数依赖发现以在节点Ｓ进行．这里选择元组数量分布最多的节点作为执行节点，可以减少数据迁移量及通信代价．具体算法如下：算法１．ＦＤＣ盯一Ｄｉｓ∞口Ｐｒ算法．输入：Ｄ一（Ｄ，，…，Ｄ。）、属性集合ｘ；输出：发现的ＦＤｓ集合三７．／＊在任一节点Ｓ；，并行执行以下操作：＊／①ｆｏｒｅａｃｈｉ∈［１，托］ｄｏ②ｃｏｕｎｔ（ｉ）一ＩｎＩ；／＊统计各节点元组个数＊／③ｅｎｄｆｏｒ④找出ｃｏｕｎｔ（Ｊ）值最大的节点Ｓｉ；／＊找出包含元组最多的节点，即执行节点＊／⑤ｆｏｒｅａｃｈ忌∈［１，７ｚ］ａｎｄｉ≠歹⑥Ｄｉ＋一Ｄ。；／＊其他节点将所有元组迁移到执行节点＊／⑦ｅｎｄｆｏｒ⑧三７一Ｄｉｓｃｏ口Ｐｒ（Ｄｉ，ｘ）；／＊在执行节点发现函数依赖＊／⑨返回三７．由于该算法将所有数据迁移到一个节点，在该节点进行函数依赖发现，在大数据背景下，大量数据迁移到一个节点，检测任务由一个节点承担，导致负载严重不均衡，该节点很容易成为影响算法执行效率的瓶颈．函数Ｄｉｓｃｏ粥ｒ（）对输入的数据，执行具体的函数依赖发现．Ｄｉｓ∞口ｅｒ（）的执行过程如下所示：函数１．Ｄｉ５ｆｏ口口ｒ（）函数．输入：Ｄ一（Ｄｌ，…，Ｄ。）、属性集合ｘ；输出：发现的ＦＤｓ集合三７．①生成候选ＦＤｓ集合三和搜索空间＠；②ｆｏｒｅａｃｈ候选ＦＤ够∈三③判断妒是否为ＦＤ；④ｅｎｄｆｏｒ⑤ｉｆ９ｉｓａＦＤ／＊９满足函数依赖＊／⑥｛三７＋一舻；）⑦ｅｌｓｅ｛对搜索空间＠剪枝；⑧三一一被剪枝的候选ＦＤｓ；）⑨返回三７．４．２分布式并行发现算法前面提到的算法ＦＤｃ以一Ｄｉｓ∞ｕ８ｒ由于负载均衡度低，仅能在单个节点执行函数依赖发现，效率较低，特别是在大数据背景下．为提高分布式大数据函数依赖发现的效率，本文提出了一种适合大数据的万方数据并行函数依赖发现算法ＦＤＰ以ＬＤｉｓ∞口∽在分布式环境下，进行函数依赖发现的过程中，除非采用诸如算法ＦＤＣ∞一Ｄｉｓ∞ｕＰｒ那种先将数据集中然后使用集中式发现方法，否则都需要对分布在各个节点的数据进行重新分布．数据重分布要满足的必要条件是：重分布后的数据，在各个节点上进行函数依赖的发现，要能保证发现的准确性，即对任意候选函数依赖，其潜在存在冲突的元组在重新分布后要分布在相同的节点．引理４．对于一个有咒个属性的关系ｒ，其候选函数依赖的个数为咒×２—１一咒个．证明．由于这里仅考虑简单非平凡函数依赖，也就是函数依赖右部ＲＨＳ部分包含一个属性的非平凡函数依赖的情况．对于关系ｒ的所有候选函数依赖，其ＬＨＳ属性个数最少为１个，最多为咒一１个．由此可见，关系ｒ的候选函数依赖中，ＬＨＳ部分属性个数为１的候选函数依赖个数为Ｃ：Ｃ：一，个，ＬＨＳ部分属性个数为２的候选函数依赖个数为Ｃ：Ｃ：一：个，ＬＨＳ部分属性个数为３的候选函数依赖个数为Ｃ：Ｃ：一。个，…，ＬＨＳ部分属性个数为，ｚ一１的候选函数依赖个数为Ｃ：＿１Ｃｉ个，因此总的候选函数依赖个数为Ｃ：ｃＬ，＋Ｃ：ｃＬ。＋Ｃ：ＣＬ。＋…＋ＣｒｌＣ｛一１×Ｃ：＋２×Ｃ：＋３×Ｃｉ＋…＋（咒一１）×Ｃ：ｑ—ｏ×Ｃ：＋１×Ｃ：＋２×Ｃ：＋３×Ｃ：＋…＋（竹一１）×Ｃ：『１＋咒×Ｃ：一咒×Ｃ：一∑．『×ｑ一咒×ｃ：一咒×２”～一咒．证毕．Ｊ＝Ｏ由引理４不难看出，候选函数依赖的个数随着关系ｒ的属性个数他的增加呈指数级增长．大数据背景下，为提高函数依赖发现的负载均衡度，对每一个候选函数依赖，需要对数据进行重分布．而数据的重分布会增加网络的负载，在大数据背景下，这种网络负载的增加对发现效率的影响十分明显．为了尽可能减少数据重分布的次数和因数据重分布对网络负载的影响，本文提出一种候选函数的划分方法，将候选函数依赖进行分组，使得组内的候选函数依赖可以通过一次数据重分布进行检测，从中发现函数依赖，去除不符合条件的候选函数依赖，并根据已发现的不满足条件的候选函数依赖，对候选函数依赖集合进行剪枝，从而提高分布式环境下大数据函数依赖发现的效率．具体的候选函数依赖分组的策略如下：考虑根据待发现的关系ｒ的属性集合的每一个２８８属性，对候选函数依赖进行分组，每一组内的候选函数依赖的ＬＨＳ部分有着公共的属性，不同分组的ＬＨＳ部分的公共属性不同，假定关系ｒ的属性集合包含ｍ个属性，则可以将候选函数依赖分成ｍ组．对每一组内的候选函数依赖，可以通过一次数据重分布进行检测从而发现其中包含的函数依赖．假定待发现的关系ｒ包含的属性个数为咒，以第１个属性为ＬＨＳ公共属性的候选函数依赖，其ＬＨＳ包含的属性个数最多为咒一１个，最少为１个，总的候选函数依赖个数可以按如下方式计算：ＬＨＳ部分包含竹一１个属性的候选函数依赖个数为Ｃ：二；Ｃ：一。一（。Ⅷ个，ＬＨＳ部分包含咒一２个属性的候选函数依赖个数为Ｃ：二；Ｃ：。一。。吲个，…，ＬＨＳ部分包含２个属性的候选函数依赖个数为Ｃ：一，×Ｃ：，一，个，ＬＨＳ部分包含１个属性的候选函数依赖个数为Ｃ：一。Ｃ：。～。个．总的候选函数依赖个数为Ｃ＝；ＣＬ，（，。）＋Ｃ＃；ＣＬ。一（，。）＋…＋ＣＬ，ＣＬ。一。＋Ｃ譬。ＣＬ，一。一１×Ｃ：一１＋２×Ｃ：一１＋…＋（咒一２）×Ｃ＝；＋（扎一１）×Ｃ：：二｝一”一１∑歹×ｃ０１一（咒一１）×２”１—１一ｊ＝０（，ｚ一１）×２”２．以第２个属性为ＬＨＳ公共属性的候选函数依赖，去除前面以第１个属性为ＬＨＳ公共属性的候选函数依赖，其ＬＨＳ包含的属性个数最多为咒一１个，最少为１个，总的候选函数依赖个数可以按如下方式计算：ＬＨＳ部分包含咒一１个属性的候选函数依赖个数为Ｃ：二；Ｃ：。。。吲个，ＬＨｓ部分包含行一２个属性的候选函数依赖个数为Ｃ：二；Ｃ：一，一。。吲个，…，ＬＨＳ部分包含２个属性的候选函数依赖个数为Ｃ：一：×Ｃ：。一，个，ＬＨＳ部分包含１个属性的候选函数依赖个数为Ｃ：一。Ｃ：。～。个．总的候选函数依赖个数为Ｃ＝；Ｃ：，（。２）＋Ｃ＝；ＣＬ，一（。一３）＋…＋ＣＬ：Ｃ：一。一。＋Ｃ娶：ＣＬ。一。一１×ＣＬ：＋２×Ｃ：一：＋…＋（咒一２）×Ｃ＝；＋Ｃ■：＋ＣＬ。＋…＋Ｃ＝ｌ—ｒ２ｎ一２∑歹×ａ一。＋∑睥ｚ—Ｊ＝Ｏｊ一０（咒一２）×２”３＋２”２．同理，以第３个属性为ＬＨＳ公共属性的候选函数依赖，去除前面以第１个属性和第２个属性为ＬＨＳ公共属性的候选函数依赖，其ＬＨＳ包含的属万方数据计算机研究与发展２０１５，５２（２）性个数最多为咒一２个，最少为１个，总的候选函数依赖个数可以按如下方式计算：ＬＨＳ部分包含咒一２个属性的候选函数依赖个数为Ｃ：二ｉＣ：一。咱－３）个，ＬＨＳ部分包含咒一３个属性的候选函数依赖个数为Ｃ：二｛Ｃ：一，一。。叫个，…，ＬＨＳ部分包含２个属性的候选函数依赖个数为Ｃ：一。×Ｃ：，一，个，ＬＨＳ部分包含１个属性的候选函数依赖个数为Ｃ：一。Ｃ：一。。个．总的候选函数依赖个数为Ｃ＝；ＣＬ，。，。）＋Ｃ＝｛ＣＬ，一（，ｒ。）＋…＋ＣＬ。ＣＬ。一。＋Ｃ■Ｃ■，一。一２×Ｃ譬。＋３×Ｃｈ＋…＋（咒一２）×Ｃ墨＋（咒一１）×Ｃ霜＝∑歹×睥。＋２×∑睥。一ｊ＝０ｊ＝Ｏ（ｎ一３）×２”４＋２×２”３．同理，以第４个属性为ＬＨＳ公共属性的候选函数依赖，去除前面以第１个属性、第２个属性和第３个属性为ＬＨＳ公共属性的候选函数依赖，其ＬＨＳ包含的属性个数最多为卵一３个，最少为１个，总的候选函数依赖个数可以按如下方式计算：ＬＨＳ部分包含”一３个属性的候选函数依赖个数为Ｃ：二：Ｃ：一，一。。叫个，ＬＨＳ部分包含咒一４个属性的候选函数依赖个数为Ｃ：二ｉＣ：一，一（。＿５）个，…，ＬＨＳ部分包含２个属性的候选函数依赖个数为Ｃ：一。×Ｃ：。。个，ＬＨＳ部分包含１个属性的候选函数依赖个数为Ｃ：一。Ｃ：一。一。个．总的候选函数依赖个数为Ｃ＝：Ｃ：～，一（。一。）＋Ｃ：二ｉＣＬ。一（，ｒ＿。）＋…＋Ｃ：一。Ｃ：～，一，＋Ｃ：一。ＣＬ。一。一３×Ｃ■＋４×ＣＬ。＋…＋（咒一２）×Ｃ叠＋（咒一１）×ｃ霉一∑Ｊ×ｃ０。＋ｊ＝０３×＞：（￥。一（船一４）ｘ２”５＋３×２”４．ｊ鲁Ｏ同理，进一步可以求出以第５个属性为ＬＨｓ公共属性的候选函数依赖，去掉前面以第１个属性、第２个属性、第３个属性和第４个属性为ＬＨＳ公共属性的候选函数依赖，其包含的候选函数依赖个数为（７２——５）×２”６＋４×２”一５个．由引理３可知，包含以个属性的关系ｒ的候选函数依赖个数为咒×２”１一咒个．根据前面的结果，总的候选函数依赖中所占比例为与专筹，在以第１个属性为ＬＨＳ公共属性的候选函数依赖在挖趋于无穷大的情况下，所占比例近似结果为李卫榜等：分布式大数据函数依赖发现罂玄又方ｉ一嬲Ｆ帝一虿‘。一。。咒×２”一１一咒ｉ＝２—１／２『｛２‘同理，以第２个属性为ＬＨＳ公共属性的候选函垒［鲁笔暑竽，在以趋于无穷大的情况下，所数依赖在总的候选函数依赖中所占比例为占比例近似结果为！婴—■＆ｉ丁＝；■一一罂Ｆ而一百‘，．（咒一２）×２”一３＋２一一２，．】】以第３个属性为ＬＨｓ公共属性的候选函数依赖在总的候选函数依赖中所占比例为（（挖一３）×２—４＋２×２”３）／（，ｚ×２—１一咒），在咒趋于无穷大的情况下，所占比例近似结果为，．婴——‘叉虿丁ｉ：－一百‘（挖一３）×２—４＋２×２”一３】以第４个属性为ＬＨＳ公共属性的候选函数依赖在总的候选函数依赖中所占比例为（（咒一４）×２—５＋３×２—４）／（竹×２”１～规），在咒趋于无穷大的情况下，所占比例近似结果为！翼——‘又虿丁ｉ＿一丽。，．（咒一４）×２—５＋３×２，ｒ４】从以上不难看出，即便在不利用已发现结果对候选函数依赖进行剪枝的情况下，通过１次数据重分布，对第１个候选函数依赖分组进行处理，就可以对整合候选函数依赖集合中大约一半的候选函数依赖进行检测，从中发现函数依赖；通过２次数据重分布，可以对整合候选函数依赖集合中大约３／４的候选函数依赖进行检测，从中发现函数依赖；通过３次数据重分布，可以对整合候选函数依赖集合中大约７／８的候选函数依赖进行检测，从中发现函数依赖；通过４次数据重分布，可以对整个候选函数依赖集合中大约１５／１６的候选函数依赖进行检测从中发现函数依赖．假定关系ｒ包含属性集合为｛Ａ，Ｂ，Ｃ，Ｄ），根据引理３，包含的候选函数依赖总数为４×２４－１—４—２８个，假定属性Ａ为第１个属性，属性Ｂ为第２个属性，属性Ｃ为第３个属性，属性Ｄ为第４个属性，则根据前面提到的分组原则，以Ａ属性为ＬＨＳ公共属性的候选函数依赖个数为（４一１）×２４＿１—１２个，分别为ＡＢＣ—Ｄ，ＡＢＤ—Ｃ，ＡＣＤ—Ｂ，ＡＢ—Ｃ，ＡＢ—Ｄ，ＡＣ—，Ｂ，ＡＣ—Ｄ，ＡＤ—Ｂ，ＡＤ—Ｃ，Ａ—Ｂ，Ａ—ｃ，Ａ—Ｄ．该分组内的候选函数依赖在搜索空间上的表示如图４所示，其中画虚线的连线所代表的候选函数依赖即为当前分组中包含的候选函数依赖．万方数据２８９，／／／：爪Ｌｅｖｅｌ１，７／＼＼／，一Ｚ一ＢＣＢＤＣＤ３一占ＣＤ４上．１９．４Ｇｒｏｕｐｏｆｃａｎｄｌｄａｔｅ上．‘ＩＪｓｄｌｖｌｄｅｄｂｙＡ．图４依据属性Ａ分组候选函数依赖同理，以属性Ｂ为ＬＨＳ公共属性的候选函数依赖分组中包含的候选函数依赖个数为（４—２）×２４＿３＋２”２—８个，分别为ＢＣＤ—Ａ，ＢＣ—Ａ，ＢＣ—Ｄ，ＢＤ—Ａ，ＢＤ—＋Ｃ，Ｂ—Ａ，Ｂ—Ｃ，Ｂ—Ｄ．以属性Ｃ为ＬＨＳ公共属性的候选函数依赖分组中包含的候选函数依赖个数为（４—３）×２４－４＋２×２４－３—５个，分别为ＣＤ—Ａ，ＣＤ—Ｂ，Ｃ—Ａ，Ｃ—Ｂ，Ｃ—Ｄ．以属性Ｄ为ＬＨＳ公共属性的候选函数依赖分组中包含的候选函数依赖个数为（４—４）×２４＿５＋３×２４＿４—３个，分别为Ｄ—Ａ，Ｄ—Ｂ，Ｄ—Ｃ．在分布式环境下，为实现函数依赖的并行发现，需要对分布式数据进行重分布．为保证函数依赖发现的准确性和完整性，本文考虑对各个节点上的所有元组计算散列值，每次重分布时，以当前分组内候选函数依赖ＬＨＳ部分公共属性的值为散列值，通过散列函数将元组映射为。到咒一１的整数值，押为节点的个数．假定Ｄ为关系模式尺的一个实例，Ｄ水平切分为（Ｄｌ，．一，Ｄ。），根据各个元组的对应散列值的不同，散列函数将Ｄ的任一切分Ｄ。分成ｎ块，分别为Ｈ¨，…，Ｈ７．对Ｖ忌∈［１，靠］，Ｈ；内的元组有着相同的散列值．这样可以将Ｄ分成挖块，每一块内的元组有着相同的散列值，如图５所示．Ｈ１为散列值为。的元组组成的块，Ｈ２为散列值为１的元组组成的块，以此类推．对Ｖ歹∈［１，咒］，有印一川Ｕ…ＵＨ：．引理５．假定Ａ为关系，一的一个属性，Ｘ为ｒ的一个属性集合且Ａ∈Ｘ，则对于ｒ中任意两个元组￡。和ｔ：，若满足ｆ。（｛Ａ）ＵＸ）一￡：（｛Ａ）ＵＸ），则必然有￡，（Ａ）一￡２（Ａ），这里￡１（Ａ）表示元组￡。关于Ａ的属性值．证明．假设￡，（｛Ａ）ＵＸ）一≠：（｛Ａ）ＵＸ）且￡，（Ａ）≠￡。（Ａ），由ｆ。（｛Ａ）ＵＸ）一￡。（｛Ａ）ＵＸ）可知，对ＶＫ∈｛Ａ）ＵＸ，￡１（Ｋ）一￡。（Ｋ）成立．又Ａ∈｛Ａ）ＵＸ，故２９０计算机研究与发展２０１５，５２（２）Ｄ１》＆Ｄ２岛Ｆｉｇ．６Ｂｒｏａｄｃａｓｔｃｏｍｍｕｎｉｃａｔｉｏｎｂｅｔｗｅｅｎｄｉｓｔｒｉｂｕｔｅｄｎｏｄｅｓ．Ｆｉｇ．５Ｔｈｅｐａｒｔｉｔｉｏｎｏ｛Ｄ１，…，Ｄ。ｂｙＨａｓｈｆｕｎｃｔＩｏｎ．图６分布式各节点之间的广播通信图５Ｄ．，…，Ｄ，，被散列函数切分算法ＦＤＰ口Ｌ眈ｓｃｏ伽ｒ的具体执行过程如下所示：算法２．ＦＤＰ口ｒ—Ｄｉ５ｃｏｕｅｒ算法．输入：Ｄ一（Ｄ，，…，聩）、属性集合Ｘ、公共属性Ａ；输出：发现的ＦＤｓ集合三７．／＊在每一个节点Ｓ。，并行执行：＊／①ｆｏｒｅａｃｈ忌∈［１，九］ｄｏ②③ｆｏｒｅａｃｈ￡∈Ｄ：ｄｏｆ，（Ａ）一￡：（Ａ）成立，与假设矛盾，故假设不成立．因此原命题成立，即若满足ｆ，（｛Ａ｝ＵＸ）一￡。（｛Ａ｝ＵＸ），则必然有ｆｌ（Ａ）一ｆ２（Ａ）．证毕．由引理５可知，对于Ｉ。ＨＳ有着共同属性的每一个分组内的候选函数依赖来说，假定其公共属性为Ａ，则对关系ｒ上的所有元组来说，Ａ属性值相同是｛Ａ）ＵＸ属性值相同的必要条件．根据引理５不难看出，通过散列函数的方法将所有节点上的元组进行分组，保证了对一个组内的所有候选函数依赖，其潜在冲突的元组都划分到相同的数据块上，以图５中散列函数的切分为例，重分布后的函数满足：Ⅱ｛ｘ｝（Ｄ）一ＵⅡ（Ｕ？∈Ｌ１ⅢＪｉｆ∥（ｆ）一一是一１；／＊ｐ（￡）为散列函数，将元组属性值映射为从。到札一１的整数＊／④⑤磁一Ｈ；Ｕ￡；／＊将Ｄｉ散列成行份＊／ｅｎｄｆｏ。Ｈ；），，∈Ｌ１ⅢＪ｛ｘ｝⑥ｅｎｄｆｏｒ其中Ｘ∈Ａｆｒｒｓ（Ｒ），即数据重分布后，对关系Ｒ的任一属性集合Ｘ，各个子节点上等价类的并集与集中式情况下等价类相同，这样保证了函数依赖发现的准确性．同时，不同数据块可以在不同的节点并行进行函数依赖发现，这又可以提高函数依赖发现的效率．⑦ｆｏｒｅａｃｈ忌∈［１，行］ｄｏ⑧如果睁！Ｊ，传输Ｈ；到节点Ｓ，；⑨ｅｎｄｆｏｒ⑩逐层生成候选Ｉ。ＨＳ包含属性Ａ的ＦＤｓ集合三；⑩ｆｏｒｅａｃｈ妒∈三＆＆妒在搜索空间顶部⑥Ｃｈｅｃｋ（妒）；并行函数依赖发现过程中，数据重分布以后，首先根据属性集合生成候选函数依赖集合，然后依据３．２节中介绍的剪枝策略和当前的函数依赖发现结果，对候选函数依赖集合及时进行剪枝．在各个节点并行执行函数依赖发现时，如果发现当前验证的候选函数依赖不满足函数依赖，则通过广播通知其余节点，如图６所示，然后在所有节点同时停止对当前函数依赖的验证，从候选函数依赖集合删除掉当前候选函数依赖，并依据引理３对候选函数依赖集合中所有ＬＨＳ部分，为当前候选函数依赖Ｉ，ＨＳ部分真子集的候选函数依赖进行剪枝．⑩ｅｎｄｆｏｒ⑩⑩ｉｆ（Ｃ矗Ｐｃ是（舻）！一ｔｒｕｅ）｛广播舻到其他节点；停止执行Ｃｈｅｃｋ（９）；三一一妒；⑩⑥⑩⑩）ｅｌｓｅ｛三７＋一ｐ；三一一ｐ；）⑩⑤返回三７．其中函数Ｃ＾ｅｃ是（）的功能为检测候选函数依赖万方数据李卫榜等：分布式大数据函数依赖发现是否为函数依赖，如果是则返回ｔｒｕｅ，否则返回ｆａｌｓｅ，Ｃ矗Ｐ如（）的实现过程如下所示：函数２．Ｃ＾Ｐｆ忌（）函数．输入：候选ＦＤ∞：Ｘ—ｙ；输出：ｔｒｕｅｏｒｆａｌｓｅ．①ｉｆ（ＪⅡｘｆ—Ｉ风ｕｖＩ）｛／＊如果候选函数依赖Ｘ—ｙ满足函数依赖＊／②返回ｔｒｕｅ；③）ｅｌｓｅ｛返回ｆａｌｓｅ．）前面提到，第１次数据重分布后可对约１／２的候选函数依赖进行验证，第２次数据重分布后，可检测约３／４的候选函数依赖并从中发现存在的函数依赖．对于有行个属性的关系ｒ来说，生成的（，ｚ—１）一ａｔｔｒ候选函数依赖有Ｃ：１Ｃ：一。川，一咒个．依据前面的候选函数依赖分组规则，依据第１个属性得到的（咒一１）一ａｔｔｒ候选函数依赖个数为卵一１个，依据第２个属性得到的（咒一１）一ａｔｔｒ候选函数依赖个数为１个，也就是说，前面２次分组得到的候选函数依赖包含了所有的（，２—１）一ａｔｔｒ候选函数依赖．由引理３可知，任一（行一１）一ａｔｔｒ候选函数依赖如果不成立，则可对２—１—２个ＬＨＳ部分为当前（咒一１）一ａｔｔｒ候选函数依赖ＬＨＳ部分真子集的候选函数依赖进行剪枝，如果所有的咒个（行一１）一ａｔｔｒ候选函数依赖均不成立，则可以对，ｚ×（２”１—２）个Ｉ。Ｈｓ部分为当前（咒一１）一ａｔｔｒ候选函数依赖ＬＨｓ部分真子集的候选函数依赖进行剪枝，可被剪枝的咒×（２—１—２）个候选函数依赖与现有的咒个（靠一１）一ａｔｔｒ候选函数依赖个数之和为７２×（２—１—２）＋咒一行×２—１一九，即引理４所述的总的候选函数依赖的个数．由此可见，在理想情况下，算法ＦＤＰ吖一Ｄｉｓｃｏ剧ｅ，．可以通过２次数据重分布实现对所有函数依赖的并行发现．引理６．假定关系ｒ的属性个数为规，在理想情况下，一次数据重分布可检测的候选函数依赖个数占候选函数依赖总个数的比例为生二．。一１Ⅳ证明．前面提到，在理想情况下，以第１个属性为ＬＨＳ公共属性的候选函数依赖个数为（行一１）×２—２个，其中ＬＨＳ部分为第１个属性的候选函数依赖个数为咒一１个，因此（以一１）×２”２个候选函数依赖中，在ＬＨＳ部分去掉第１个属性后不为空的候选函数依赖个数为（咒一１）×２—２一咒一１一（佗一１）×（２—２—１），这部分候选函数依赖也是在理想情况下一次数据重分布可以剪枝的候选函数依赖个数．也就是说，在理想情况下第１次数据重分布可以检测万方数据的候选函数依赖个数为（他～１）×２”２＋（ｎ一１）×（２—２—１）一（卵一１）×（２—１—１）．由引理４可知，属性个数为行时，可生成的候选函数依赖总个数为咒×（２—１～１）个，因此，一次数据重分布可检测的候选函数依赖个数占候选函数依赖总个数的比例为（行一１）×（２”１一１）一７ｚ一１‘卵×（２”１—１）７２由引理６可知，理想情况下，当ｎ趋于＋。。时，函数依赖总个数的比例近似为ｌｉｍ生』一１．证毕．…１实验设置１）实验环境本文实验使用了由８台服务器通过局域网连接ＧＢ的Ｉｎｔｅｌｘｅｏｎ２处理器和１６ＧＢ内存；操作系统为台为分布式系统架构Ｈａｄｏｏｐ平台与基于ＢＳＰ（ＢｕｌｋＰａｒａｌｌｅｌ）并行计算框架的Ｈａｍａ平台．２）实验数据本文使用了２种不同类型的数据集，一种是美国ＳｔａｔｅｓＤｅｐａｒｔｎｌｅｎｔｏｆｍａｎｓｐｏｒｔａｔｉｏｎ）网ｏｎ—ｔｉｍｅＩＤ）、ｎｕｍｂｅｒ）、起飞机场（ｏｒｉｇｉｎａｉｒｐｏｒｔ）、ａｉｒｐｏｒｔ）等．数据集的规模为ＧＢ，包含了１５亿条元组．使用该数据集生成一个０００万条元组的数据库实例ｏ￡户＾，一个包含０００万条元组的数据库实例ｏ￡ｐ厂。：．另外一种数Ｏｏｏ万０００万条元０００万条元组的数据库实例ｓ￡“ｄｍ一次数据重分布可检测的候选函数依赖个数占候选５实验结果与分析５．１构成的一个集群，每台机器配备了主频为１．８７Ｕｂｕｎｔｕｌｏ．４．所有算法均由Ｊａｖａ实现；算法运行平Ｓｙｎｃｈｒｏｎｏｕｓ运输部（Ｕｎｉｔｅｄ站提供的航班按时间统计数据（ａｉｒｌｉｎｅｓｔａｔｉｓｔｉｃｓ）［”］，这是一个真实的数据集，另外一种是人工生成的数据集．第１种数据集简称“０ＴＰＦ”，包含了航班调度信息和航班的起飞降落信息，数据集ＯＴＰＦ包含了６４个属性，如航线编号（ａｉｒｌｉｎｅ航班号（ｆｌｉｇｈｔ降落机场（ｄｅｓｔｉｎａｔｉｏｎ３５包含８１２据集是一个人工生成的ＳＴＵＤＥＮＴ表的数据集，简称“ｓＴｕＤ”，是一个学生信息表，包含学号、姓名、性别、身份证号、手机号、院系、班级、课程、成绩、任课教师等共１０个字段，２亿条元组，使用ＤａｔａＦａｃｔｏｒｙ工具生成．利用数据集ＳＴＵＤ生成一个包含８条元组的数据库实例５￡“ｄ。，一个包含１０组的数据库实例ｓｆ“ｄ，。，一个包含１２