時態(tài)索引技術及算法的研究.pdf

1、目前的數(shù)據(jù)庫應用系統(tǒng)管理的數(shù)據(jù)大部分是與時間有關的,數(shù)據(jù)倉庫就是一個很好的例子。通常把具有一種時間屬性的數(shù)據(jù)稱作是時態(tài)數(shù)據(jù),時態(tài)數(shù)據(jù)的時間屬性是指有效時間或事務時間,而把同時具有兩種時間屬性的數(shù)據(jù)稱為雙時態(tài)數(shù)據(jù)。與空間數(shù)據(jù)一樣,雙時態(tài)數(shù)據(jù)也構成了一個二維數(shù)據(jù)區(qū)域。在時態(tài)數(shù)據(jù)中,最重要的是那些與當前時間(Now或UC)相關的時態(tài)數(shù)據(jù),但從近幾十年時態(tài)數(shù)據(jù)庫的發(fā)展來看,大多數(shù)的研究都集中在普通的時態(tài)數(shù)據(jù)索引技術上,而只有很少的研究著眼于與當

2、前時間相關的時態(tài)數(shù)據(jù)的索引問題上,這也許就是為什么現(xiàn)有的商業(yè)RDBMS不支持時態(tài)數(shù)據(jù)索引技術的因為。雖然4R-tree索引在不需要修改現(xiàn)有關系數(shù)據(jù)庫核心代碼的情況下,就可以在現(xiàn)有支持R樹的RDBMS上實現(xiàn)時態(tài)數(shù)據(jù)的查詢,而且性能也和理論上最優(yōu)的雙時態(tài)索引GR-tree相當。但是,能為時態(tài)數(shù)據(jù)庫設計出一種比現(xiàn)有的時態(tài)索引技術更健全且更有效的索引技術是當今時態(tài)數(shù)據(jù)庫研究的重要課題。
　　 本文提出了一種新的索引技術,稱為G2R-tr

3、ee索引。它能有效地處理所有類型的雙時態(tài)數(shù)據(jù),而且性能與4R-tree索引和GR-tree索引相當。G2R-tree索引結合了2R-tree索引、GR-tree索引和G4R-tree索引,在2R-tree索引的基礎上,對2R-tree索引技術的查詢功能進行了擴充,并支持對將來情況的查詢,使其既具有G4R-tree索引的優(yōu)點又具有2R-tree索引的優(yōu)點,同時卻克服了2R-tree索引并和G4R-tree索引的不足,查詢時只需要同時訪問2

4、棵R-tree而不同于4R-tree索引并和G4R-tree索引需要同時訪問4棵R-tree,因此大大降低了I/O操作,較好地解決了查詢時4R-tree索引不可避免的I/O操作劇增的問題。在索引算法和存取算法上也進行了一些改進,以便在處理所有類型的雙時態(tài)數(shù)據(jù)的同時提高G2R-tree索引的性能。
　　 論文具體給出了G2R-tree索引的雙時態(tài)數(shù)據(jù)變換和在2棵R-tree樹上的查詢變換,同時也給出了相關操作的算法和通過定理說明了