時間：2022-11-21 20:30:02 | 來源：信息時代
時間：2022-11-21 20:30:02 來源：信息時代
數據流連接 : 輸入兩個或多個數據流,根據一定的條件產生一個輸出數據流的連接。與傳統(tǒng)關系數據庫連接操作類似,不過由于數據流應用中最重要的一類查詢是連續(xù)查詢,數據流獨特的特點對連續(xù)查詢的數據流連接算法的設計帶來很大的挑戰(zhàn)。數據流連接算法主要有數據流二元連接和數據流多元連接。數據流二元連接的輸入是2個數據流S1和S2,數據流多元連接的輸入是n個數據流S1,…,Sn。常用的有二元對稱哈希連接、n元對稱哈希連接、M Join和X Join。
二元對稱哈希連接是一個管道(pipeline)連接,它是通過同時把它們的輸入插入到哈希表中工作的。每個輸入元組首先插入到該元組對應的哈希表中,然后立即搜索另一個輸入的哈希表。由于它的管道特性,所以很適合用來進行交互式處理,這個方法最初是作為內存算法的,后來擴展到內存約束環(huán)境中的硬盤上。
n元對稱哈希連接(n-way symmetric Hash join)可以有兩種方法實現,一種是用n-1個管道化二元對稱哈希連接實現,另一種是直接用n元操作實現。例如,考慮等值連接Ra⋈Sb_T。假設有四個哈希索引,R上的HRa,T上的HTb及兩個在S的連接屬性上的HSa和HSb,把所有的二元對稱哈希連接統(tǒng)一成為一個操作。當一個新R(或T)元組到達的時候,首先插入到對應的哈希索引HRa(或HTb),然后搜索HSa(或HSb)。如果有匹配結果,然后用來搜索HTb(或HRa)并輸出結果。當一個新S元組到來,類似地插入到HSa和HSb。這一點上,對應不同的連接次序,可以選擇其中一個?？梢杂肧元組搜索HRa或用匹配結果搜索HTb,或者也可以搜索HTb然后是HRa。
假設有n個數據流做連接運算,在M Join中,每個數據流都有一個獨立的查詢計劃,稱為管道,如果數據流中有新的元組達到,就同其他n-1個數據流分別進行連接運算,并最終給出結果,圖1展示了使用M Join實現的4元連接。
圖1 使用M Join實現的4元連接
圖2 使用X Join實現的4元連接
在線咨詢
