时间：2022-11-21 20:30:02 | 来源：信息时代
时间：2022-11-21 20:30:02 来源：信息时代
数据流连接 : 输入两个或多个数据流,根据一定的条件产生一个输出数据流的连接。与传统关系数据库连接操作类似,不过由于数据流应用中最重要的一类查询是连续查询,数据流独特的特点对连续查询的数据流连接算法的设计带来很大的挑战。数据流连接算法主要有数据流二元连接和数据流多元连接。数据流二元连接的输入是2个数据流S1和S2,数据流多元连接的输入是n个数据流S1,…,Sn。常用的有二元对称哈希连接、n元对称哈希连接、M Join和X Join。
二元对称哈希连接是一个管道(pipeline)连接,它是通过同时把它们的输入插入到哈希表中工作的。每个输入元组首先插入到该元组对应的哈希表中,然后立即搜索另一个输入的哈希表。由于它的管道特性,所以很适合用来进行交互式处理,这个方法最初是作为内存算法的,后来扩展到内存约束环境中的硬盘上。
n元对称哈希连接(n-way symmetric Hash join)可以有两种方法实现,一种是用n-1个管道化二元对称哈希连接实现,另一种是直接用n元操作实现。例如,考虑等值连接Ra⋈Sb_T。假设有四个哈希索引,R上的HRa,T上的HTb及两个在S的连接属性上的HSa和HSb,把所有的二元对称哈希连接统一成为一个操作。当一个新R(或T)元组到达的时候,首先插入到对应的哈希索引HRa(或HTb),然后搜索HSa(或HSb)。如果有匹配结果,然后用来搜索HTb(或HRa)并输出结果。当一个新S元组到来,类似地插入到HSa和HSb。这一点上,对应不同的连接次序,可以选择其中一个。可以用S元组搜索HRa或用匹配结果搜索HTb,或者也可以搜索HTb然后是HRa。
假设有n个数据流做连接运算,在M Join中,每个数据流都有一个独立的查询计划,称为管道,如果数据流中有新的元组达到,就同其他n-1个数据流分别进行连接运算,并最终给出结果,图1展示了使用M Join实现的4元连接。
图1 使用M Join实现的4元连接
图2 使用X Join实现的4元连接
在线咨询
