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

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

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

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