多維數(shù)據(jù)及時態(tài)數(shù)據(jù)索引研究.pdf

1、隨著計算機科學(xué)的發(fā)展和計算機應(yīng)用的廣泛化，計算機中處理的數(shù)據(jù)越來越復(fù)雜。相應(yīng)地對各種復(fù)雜數(shù)據(jù)的處理也成為了計算機科學(xué)中的熱點問題。在復(fù)雜數(shù)據(jù)中多維數(shù)據(jù)類型和時態(tài)數(shù)據(jù)類型的應(yīng)用非常廣泛。多維數(shù)據(jù)可以分為兩類，一類是其本身意義是多維的，比如空間數(shù)據(jù)；另一類雖然本身并不是多維的，但是在實際應(yīng)用中把它看做多維處理卻更加自然和方便。多維數(shù)據(jù)的應(yīng)用必將隨著應(yīng)用的深入越來越廣泛。時態(tài)數(shù)據(jù)廣義上也可看作是一類多維數(shù)據(jù)，但是時態(tài)數(shù)據(jù)有其自身的特點，比如獨

2、有的時態(tài)變元等。時態(tài)數(shù)據(jù)在電子政務(wù)，證卷，銀行，保險等多個商業(yè)領(lǐng)域都有重要意義。而現(xiàn)有商業(yè)數(shù)據(jù)庫中的關(guān)系數(shù)據(jù)索引并不適應(yīng)多維數(shù)據(jù)和時態(tài)數(shù)據(jù)的存取，從而使得多維數(shù)據(jù)和時態(tài)數(shù)據(jù)的索引研究具有理論和應(yīng)用價值。 本文對多維索引和時態(tài)索引進(jìn)行了深入研究，其主要貢獻(xiàn)如下： ●本文系統(tǒng)地綜述了現(xiàn)有多維索引的研究狀況，并通過分析主要多維索引的特點和不足之處，提出了一種新的多維點索引：DHPR—Tree。其基本結(jié)構(gòu)基于R*—Tree，通過

3、兄弟葉節(jié)點均勻機制增加了整個索引的負(fù)載，延緩了葉節(jié)點的分裂；通過葉節(jié)點動態(tài)重構(gòu)機制有效減少了葉節(jié)點層乃至整個索引結(jié)構(gòu)的重疊區(qū)域；通過引入并改進(jìn)虛擬外包矩形的概念，大大增加了節(jié)點的扇出；還通過引入動態(tài)有效維機制大大減少了多維下節(jié)點內(nèi)的冗余信息，進(jìn)一步提高了節(jié)點特別是高層節(jié)點多維情況下的扇出。 ●本文給出了DHPR—Tree詳細(xì)的查詢算法和更新算法，并給出算法解釋和流程圖，對其中復(fù)雜的算法還給出了例子。然后為多維數(shù)據(jù)設(shè)計了系統(tǒng)詳細(xì)的

4、實驗，通過大量實驗，可以證明DHPR—Tree在多種分布的數(shù)據(jù)中都能保持范圍查詢和點查詢的高效性，并且結(jié)構(gòu)緊湊，物理利用率高，同時其維護(hù)代價仍然是可控制的。 ●本文給出了一個時間期間集合上的數(shù)學(xué)框架。本文基于時間期間的內(nèi)在特性，研究了時間期間集合上的數(shù)學(xué)關(guān)系，提出了時態(tài)等價關(guān)系和時態(tài)擬序關(guān)系，由此引出了時間期間集合上的時態(tài)線序和時態(tài)線序劃分的概念，并提出了兩種對于索引結(jié)構(gòu)非常有意義的劃分方法，即最小線序劃分和最長線序劃分。還分別

5、給出了得到這兩種線序劃分的算法，其正確性證明和時間復(fù)雜度分析。 ●本文對時態(tài)數(shù)據(jù)及時態(tài)索引進(jìn)行了研究。針對傳統(tǒng)關(guān)系模型表達(dá)能力不足，不適合時態(tài)數(shù)據(jù)的缺陷，本文將時態(tài)信息結(jié)合到面向?qū)ο髷?shù)據(jù)模型。本文通過分析時態(tài)對象數(shù)據(jù)的特點，提出了時態(tài)對象數(shù)據(jù)模型Toqdm，并在時態(tài)對象數(shù)據(jù)模型和其時態(tài)類圖的基礎(chǔ)上，通過對時間期間集合上時態(tài)等價關(guān)系的應(yīng)用，得到了時態(tài)數(shù)據(jù)摘要Tosum。然后結(jié)合時態(tài)數(shù)據(jù)摘要和時間期間集合上的線序劃分算法，提出了時態(tài)