时间：2022-12-13 02:30:01 | 来源：信息时代
时间：2022-12-13 02:30:01 来源：信息时代
并行排序合并连接算法 : 对排序合并算法并行化的连接算法。它的最大优点是产生一个有序的结果集合。如果被连接关系已经按照连接属性排序,可以省略算法的排序阶段,只用合并操作就可以产生连接结果。这时,排序合并连接算法的效率相当高。并行排序合并连接算法由两个阶段组成,即排序和连接阶段。在排序阶段,它按照连接属性的值排序每个连接关系;在连接阶段,使用合并算法完成两个排序关系的连接。主要有两种并行排序合并连接算法。
1. 第一种排序合并算法PSMJ1
首先在多处理机之间分布连接关系,然后每个处理机对连接子集合进行排序合并连接。设“R1,R2,…,RP”是R的P个子集合,“S1,S2,…,SP”是S的P个子集合,A是关系R和S的连接属性。如果对于所有r∈Ri,所有s∈Sj,r[A]≠s[A],则称子集合对(Ri,Sj)是可独立连接对。PSMJ1算法的输入为:处理机个数P;关系R和S;连接属性A。算法的输出为关系R和S的连接结果。算法主要思想如下:首先把R和S分别划分为P个可独立连接对(R1,S1)…(RP,SP),(Ri,Si)并发送到各处理机Pi;然后各处理机Pi并行地排序Ri和Si;最后各处理机Pi并行地用合并算法完成Ri和Si的连接。算法PSMJ1的数据划分的实现方法有多种。例如,可以使用Hash方法实现这一步的数据划分。
2.第二种排序合并算法PSMJ2
该算法首先使用随机数据划分方法把R和S划分为P个可独立连接对(R1,S1)…(RP,SP),(Ri,Si)送处理机i; 然后,各个处理机i完成Ri和Si连接。PSMJ2算法的输入为: 处理机个数P;分布于P个处理机上的关系R和S;连接属性A。算法的输出为关系R和S的连接结果。算法主要思想是: 各处理机Pi从Ri抽取样本SAMPLEi并将排序后的样本SAMPLEi发送到指定处理机P1;处理机P1把其他处理机送来的样本合并为一个有序样本SAMPLE并将其划分为P个相等的子序列,分点集合Pv＝〈x1,…,xP-1〉作为R和S的划分向量;然后处理机P1把Pv广播给其他处理机; 随后各处理机Pi并行地读R和S的子集合Ri和Si并按Pv划分Ri和Si为SRi,1＝{x|x∈Ri,x<x1},SRi,j＝{x|x∈Ri,xj-1≤x<xj},2≤j≤P-1,SRi,P＝{x|x∈Ri,xP-1≤x},SSi,1＝{x|x∈Si,x<x1},SSi,j＝{x|x∈Si,xj-1≤x<xj},2≤j≤P-1,SSi,P＝{x|x∈Si,xP-1≤x},同时把(SRi,j,SSi,j)送处理机Pj(1≤j≤P);同时各处理器接收其他处理机送来的R和S的子集合,合并成SRi和SSi; 最后各处理机Pi并行地使用顺序排序合并算法完成SRi和SSi的连接并输出R和S的连接结果。
在线咨询
