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

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

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

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

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

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