海量時態(tài)數(shù)據(jù)的JOIN操作算法研究.pdf

1、在時態(tài)數(shù)據(jù)庫中時態(tài)數(shù)據(jù)的JOIN操作是一種能起到關(guān)鍵作用的操作，一方面是由于該操作本身代價比較高。設(shè)想兩個大小為n的表進(jìn)行JOIN操作，如果采用最簡單的嵌套循環(huán)方式，這個代價是非常高的，特別是對于數(shù)據(jù)量迅速增長的今天，這個n將十分龐大，n2更是我們無法想象的。另一方面高效實現(xiàn)該操作有助于解決其他一些問題，對于提高查詢優(yōu)化器的效率至關(guān)重要。
　　如今解決該問題的算法主要有四類：基于嵌套循環(huán)、基于排序合并、基于劃分和基于索引?；谇短?/p>

2、循環(huán)的算法簡單且易于實現(xiàn)，但時間復(fù)雜度太高，對于實際問題往往不能勝任。基于排序合并的算法需要在JOIN屬性上進(jìn)行排序，然而時態(tài)數(shù)據(jù)的JOIN屬性是二維的，因此很難找到一個線性順序，這就導(dǎo)致進(jìn)行JOIN的關(guān)系要被多次讀取，進(jìn)而造成性能下降。雖然也有其他的一些算法在JOIN屬性上添加限制，但這樣的算法就喪失了一般性?；趧澐趾突谒饕乃惴ù_實出現(xiàn)了一些不錯的算法，如文獻(xiàn)[1]中提出的重疊區(qū)間劃分算法，但該算法不是一個精確算法，產(chǎn)生的連接結(jié)

3、果會多于實際的連接結(jié)果。
　　針對現(xiàn)如今這些算法的缺陷，本文提出了基于對稱索引的增量式重疊區(qū)間JOIN算法SISJoin。首先該算法是一個精確算法，其次該算法簡單且易于實現(xiàn)，最后通過理論分和實驗驗證該算法非常高效。該算法是直接針對JOIN條件構(gòu)建索引結(jié)構(gòu)，且索引結(jié)構(gòu)非常簡單構(gòu)建也非常高效。在JOIN算法中又利用JOIN必要條件提前過濾掉不可能產(chǎn)生JOIN結(jié)果的數(shù)據(jù)，這樣就減少了參與JOIN的數(shù)據(jù)規(guī)模，然后還采用增量策略又極大的減少