一種可行的時態(tài)數(shù)據(jù)庫索引技術(shù)

摘 要：提出了一種基于歷史關(guān)系數(shù)據(jù)庫的時態(tài)索引技術(shù)，結(jié)合時空要求和時態(tài)數(shù)據(jù)庫的特征對該索引技術(shù)進行了改進和優(yōu)化，并將其與數(shù)據(jù)庫傳統(tǒng)技術(shù)一起應(yīng)用以適應(yīng)各種時態(tài)數(shù)據(jù)操作的需要。

關(guān)鍵詞：時態(tài)索引； 歷史關(guān)系數(shù)據(jù)庫； 時態(tài)查詢

中圖法分類號：TP315 文獻標識碼：A 文章編號：1001-3695(2006)10-0063-03

Available Time Index in TDBMS

LIU Yunsheng， YOU An

(College of Computer Science， Huazhong University of Science Technology， Wuhan Hubei 430074， China)

Abstract:This paper describes a new indexing techniques: the time index ，based on historical relational database management system， then adapt it to satisfy spacetime requests and the character of temporal DBMS. The time index is combined with other typical techniques so that the temporal queries become more efficient.

Key words:Time Index; Historical Relational Database Management System(HRDBMS); Temporal Query

時間是宇宙無所不在的特性；事件的動態(tài)性是自然公認的世界特性。時間信息及它與其他信息的聯(lián)系在我們生活中起著重要的作用，因此在數(shù)據(jù)庫及以其為核心的信息系統(tǒng)中，管理時態(tài)信息是必要而迫切的。然而傳統(tǒng)的數(shù)據(jù)庫均是固定的當前視圖，即在數(shù)據(jù)庫中的信息是其在一個非特別指定時刻的瞬像，但卻認為是當前的。這對有的應(yīng)用是足夠的，可對許多新的尤其是現(xiàn)代應(yīng)用而言卻是不夠的，因而人們很早就開始了關(guān)于時間(或時態(tài))信息管理的研究，時態(tài)數(shù)據(jù)庫也就應(yīng)運而生。

時態(tài)數(shù)據(jù)庫不僅記錄數(shù)據(jù)對象的當前映像，也管理對象的變化歷史。隨著時間的流逝，新的數(shù)據(jù)源源不斷地進入數(shù)據(jù)庫，而當前數(shù)據(jù)又逐漸變?yōu)闅v史性數(shù)據(jù)。在氣象、地震等應(yīng)用系統(tǒng)中，每天增加GB級的數(shù)據(jù)量，因此相對傳統(tǒng)數(shù)據(jù)庫來說，時態(tài)數(shù)據(jù)庫中的數(shù)據(jù)量可能要大得多。怎樣保證在大數(shù)據(jù)量下時態(tài)數(shù)據(jù)庫的高效查詢，是時態(tài)數(shù)據(jù)庫管理系統(tǒng)（TDBMS）必須要考慮的首要問題。此外，在時態(tài)數(shù)據(jù)庫中一切數(shù)據(jù)均被打上了時標的標記，從而使得數(shù)據(jù)庫中的基本操作如數(shù)據(jù)查詢、數(shù)據(jù)插入和刪除有了新的含義。作為提高數(shù)據(jù)庫查詢處理效率的常規(guī)索引技術(shù)失去了原有的功效。最后，在傳統(tǒng)數(shù)據(jù)庫應(yīng)用中，查詢一般說明為等相性謂詞（普遍的是等值連接、自然連接），若包含了不等性謂詞，則它很難與其他這類謂詞組合；而在時態(tài)查詢中正好相反，具有幾個不等性謂詞合取的連接出現(xiàn)較頻繁，故其優(yōu)化也更困難。

基于上述原因，本文在綜合借鑒和比較各種時空索引的基礎(chǔ)上，提出一種新的時態(tài)索引（Time Index）技術(shù)，并將其應(yīng)用于時態(tài)數(shù)據(jù)庫中。

1 歷史關(guān)系數(shù)據(jù)庫簡述

為了便于描述，下面僅選擇了一個簡單的歷史關(guān)系數(shù)據(jù)庫作為建立時態(tài)索引的基礎(chǔ)，它由兩個表（R和S）組成。關(guān)系R為雇員工作單位登記表，保存著雇員何時在何公司工作的簡歷；關(guān)系S為雇員工資表，存儲雇員的工資變動情況。該數(shù)據(jù)庫如表1、表2所示。

關(guān)系R或S中每個元組代表某一數(shù)據(jù)對象在某一時期得到的一個映像，Ts和Te分別代表這一時期的起始時間和截止時間，稱之為有效時間（Valid_time）區(qū)間。時間區(qū)間將以如下形式表示：[t1，t2]。[t1，t2]被定義為一系列連續(xù)的間距相等的時間點的集合，這其中t1代表時間區(qū)間起始時間點，t2為該時間區(qū)間的截止時間點。因此，時間維其實是一個特殊的時間區(qū)間，時間維以如下形式定義[0，Now]。這里0代表時態(tài)數(shù)據(jù)庫時間維的起始點，也代表時態(tài)數(shù)據(jù)庫中有關(guān)涉及時態(tài)數(shù)據(jù)應(yīng)用程序的事務(wù)的最早運行時間；Now則代表現(xiàn)實世界中的現(xiàn)在時間，因而它是連續(xù)不斷地沿著時間維的方向向前延伸的。當然，兩個相鄰的時間點之間的距離可以根據(jù)應(yīng)用的需要而調(diào)整，可以是月、日、小時、分、秒或其他合適的時間單位。于是，一個簡單獨立的時間點t可以定義為[t，t]，甚至可以更簡單地定義為[t]。在歷史關(guān)系數(shù)據(jù)庫中的插入、刪除和更新操作均涉及到對元組開始時間和截止時間的修改。

2 建立時態(tài)索引模型

下面將以表1、表2中所示的時態(tài)數(shù)據(jù)庫為基礎(chǔ)建立時態(tài)索引。

傳統(tǒng)的索引方案均會假定某一索引上的數(shù)據(jù)值都能完全排序。但是時態(tài)數(shù)據(jù)庫與傳統(tǒng)數(shù)據(jù)庫不一樣，作為一個二維數(shù)據(jù)庫，其時間區(qū)間特有的特性將使得傳統(tǒng)的索引技術(shù)在運用到時態(tài)索引上時顯得比較困難。首先，該時態(tài)索引需要搜尋的屬性類型——有效時間，大多數(shù)情況下是一個時間區(qū)間而不是一個時間點。各數(shù)據(jù)對象不同映像的有效時間區(qū)間以任意的方式重疊著。時間區(qū)間的這些特性使得其不能進行完全排序，傳統(tǒng)的索引技術(shù)已不再適用。其次，基于對時態(tài)數(shù)據(jù)庫特性的考慮，數(shù)據(jù)庫中的更新操作是以一種添加的方式執(zhí)行的，各時態(tài)數(shù)據(jù)對象的舊映像依然保存在數(shù)據(jù)庫中。因此，針對數(shù)據(jù)對象的過去映像，其刪除操作并不是真正意義上的刪除，只是對原有數(shù)據(jù)對象截止時間進行的修改；相應(yīng)的，對于數(shù)據(jù)對象的插入也不是真正意義上的插入，大部分情況下也只是延長原有對象的截止時間。同時，時態(tài)數(shù)據(jù)庫的搜索條件也與傳統(tǒng)數(shù)據(jù)庫不同，時態(tài)數(shù)據(jù)庫中的搜索條件往往是要求提取出在某一特定時間區(qū)間中滿足某一特定條件的數(shù)據(jù)對象。一個特定時間區(qū)間是眾多時間點的集合，目前的索引技術(shù)還不支持對某一集合的搜索。

時態(tài)索引定義在一個基于元組的時態(tài)數(shù)據(jù)庫TDBMS（Temporal Database）上，一個時態(tài)數(shù)據(jù)庫可以簡單地定義為保存了各類數(shù)據(jù)對象不同時間段的映像的大型數(shù)據(jù)存儲倉庫，TDB={eij}，這里eij表示數(shù)據(jù)對象i在某一時間段內(nèi)的映像j。通過上面的分析可知，時態(tài)數(shù)據(jù)庫索引應(yīng)該支持基于時間段的時間搜索，下面給出了一個時態(tài)查詢的定義。

假定一個搜索區(qū)間Is，Is=[ta，tb]，一個時態(tài)查詢可以定義如下：

S(Is)={eij ∈TDB|(eij.valid_time∩Is)≠}

一種簡單但低效的數(shù)據(jù)執(zhí)行方式是按順序線性地掃描整個時態(tài)數(shù)據(jù)庫，然后提取出那些與搜索區(qū)間Is相交的滿足條件的數(shù)據(jù)對象（在該時態(tài)數(shù)據(jù)庫中即元組）。如果以N表示數(shù)據(jù)庫中數(shù)據(jù)對象的數(shù)目，M則為每個數(shù)據(jù)對象可能存在數(shù)據(jù)庫中的版本數(shù)目。以這種方式執(zhí)行一次時態(tài)查詢顯然是十分耗時的，其計算量為O(N×M)數(shù)量級，為此我們引入了時態(tài)索引。

為了避免上述時態(tài)數(shù)據(jù)庫時間區(qū)間不能完全排序的問題，在建立時態(tài)索引時我們采用了維護一個在時間維上能線性排序的時態(tài)索引節(jié)點（時間點）的思想。每當代表一個對象映像的元組添加到數(shù)據(jù)庫中時，相應(yīng)地在時態(tài)索引節(jié)點集合BP中增加一個索引節(jié)點，該索引節(jié)點的時間點值可能是該新添加的元組有效時間區(qū)間的開始時間點，也可能是其截止時間點。所有的時態(tài)索引項的節(jié)點定義如下：

BP={ti|eij∈TDB((ti=eij.valid_time.Ts)∨(ti=eij.valid_time.Te+1))}∪{now}

在描述時態(tài)索引組成結(jié)構(gòu)之前，將定義一些輔助操作符以幫助下面的討論。設(shè)tj表示一個時間維上的任意時間點，定義t-j（t+j）為時態(tài)數(shù)據(jù)庫中的時間點，并有t-j

既然時態(tài)數(shù)據(jù)庫中所有的時間點tj能做到完全排序，現(xiàn)在可開始考慮使用常規(guī)的B+樹對來建立時態(tài)索引了。該B+樹葉節(jié)點中的時態(tài)索引節(jié)點按如下方式定義：

{ti，bucket}

其中變量Bucket為一個指向指針集的指針，該指針集中的指針則指向時態(tài)數(shù)據(jù)庫中代表不同對象映像的元組。在時態(tài)索引設(shè)計方案中，每一個Bucket B(ti)包含一些指針，這些指針指向那些有效時間含有時間段[ti，t+i-1]。現(xiàn)將其形式化定義為

B(ti)={ eij∈TDB|([ti，t+i-1]∈(eij.valid_time)}

由于時態(tài)索引節(jié)點集合中的所有索引節(jié)點為元組有效時間區(qū)間的開始時間和截止時間點，故代表數(shù)據(jù)對象任何不同時間段映像的元組均能完整地被保存到時態(tài)數(shù)據(jù)庫中。

在一個實用的時態(tài)數(shù)據(jù)庫中，每個時態(tài)索引節(jié)點（時間點）都會有很多數(shù)指向元組的指針與之相關(guān)聯(lián)。不難發(fā)現(xiàn)，兩個相鄰的時間點其相應(yīng)的指針桶中的指針可能具有很大的重復性。為了減少這種冗余以使時態(tài)索引空間利用率更高，引進了一種增量存儲方式。在該存儲方式中，將葉節(jié)點中的時態(tài)索引節(jié)點分成兩類，即首項索引時間點和非首項索引時間點。在首項索引時間點中，除了保存該時間點的值外，還將保存三組相應(yīng)的指針桶，即SP，SM，SC。SP指針指向的指針桶中保存的是所有指向開始時間為該時間點的元組的指針；SM指針指向的指針桶中保存的是所有指向終止時間加1后為該時間點的元組的指針；而SC指針對應(yīng)的指針桶中則保存的是所有在前一時間點有效且在該時間點繼續(xù)有效的元組的指針。對于非首項索引時間點，則省略了指針桶SC，只記錄在該時間點增加和減少的時間點的元組的指針，即只保留兩個指針桶SP和SM。任何計算在該時間點有效的對象映像的要求均可通過以下公式計算得到：

B(ti)=t1.SC∪(∪tj∈BP，t1≤tj≤titj.SP)-(∪tj∈BP，t1≤tj≤titj.SM)

其中，t1是該葉節(jié)點中的首項索引時間點。

時態(tài)索引樹的葉節(jié)點如圖1所示。為了更好地讓讀者了解時態(tài)索引，圖1中也給出關(guān)系R相應(yīng)的時態(tài)索引圖。

至此已完全建立起了時態(tài)索引，現(xiàn)在可以利用時態(tài)索引來完成時態(tài)查詢操作。假設(shè)該時態(tài)查詢的時間搜索區(qū)間Is=[ta，tb]，則時態(tài)查詢將分為以下兩步執(zhí)行：

（1）通過搜索時態(tài)索引樹得到所有處于該時間區(qū)間的時間點。

PI(Is)={ti∈BP|ta≤ti≤tb}∪{t-=a}

（2）計算每個時間點滿足條件的元組，將結(jié)果集合并。

T(Is)=∪ti∈PI B(ti)

在沒有時態(tài)索引的數(shù)據(jù)庫中，一個簡單的查詢也將變得非常復雜。下面可以基于上述基本的時態(tài)索引作種種變體，以適應(yīng)各種時態(tài)查詢的需要。

3 根據(jù)時態(tài)操作的要求對時態(tài)索引樹進行擴展

在基本時態(tài)索引樹建立起來后，可以利用該索引樹很方便地找出某一時間區(qū)間內(nèi)所有數(shù)據(jù)對象。但是對時態(tài)數(shù)據(jù)庫而言，這還不能滿足其各種操作的要求。時態(tài)選擇的選擇條件與傳統(tǒng)數(shù)據(jù)庫相比更加嚴格，它要求的是在某段時間內(nèi)待考查的屬性值滿足特定條件的所有數(shù)據(jù)對象不同映像的集合。時態(tài)選擇操作的條件由兩部分組成，即屬性值比較和有效時間區(qū)間選擇。因此它可分為兩步完成，首先得到一個屬性值滿足條件的元組集合，然后在該元組集合中選出有效時間區(qū)間包含選擇條件中所給出的時間區(qū)間段的元組。基于上述分析并參考傳統(tǒng)數(shù)據(jù)庫經(jīng)典技術(shù)，提出了一個兩層索引方案。

對于傳統(tǒng)數(shù)據(jù)庫而言，目前已經(jīng)建立起了多種成熟的索引技術(shù)，它們可分為兩大類：①數(shù)據(jù)保持某種自然順序，如各種樹結(jié)構(gòu)；②數(shù)據(jù)隨機分布，如各種Hashing結(jié)構(gòu)。Hashing實際上也是一種索引技術(shù)。現(xiàn)實世界中的數(shù)據(jù)在大部分情況下是隨機的。因此本文著眼于第二類，選擇Hashing技術(shù)作為兩層索引方案中的第一層索引。

這里先簡要介紹一下Hashing索引法。在Hashing索引法中，必須首先構(gòu)造一個散列函數(shù)，它以查找鍵（散列鍵）為參數(shù)并計算出一個介于0~B-1的整數(shù)，其中B是散列桶的數(shù)目。散列桶數(shù)組，即一個序號為從0~B-1的數(shù)組中包含B個鏈表的頭，每一個對應(yīng)于數(shù)組中的一個桶。如果記錄的查找鍵為K，則通過將該記錄鏈接到桶號為h(K)的桶列表中來存儲它，其中h是散列函數(shù)。顯然，在Hashing算法的每一個桶中保存的都是屬性值等于某一特定值的所有元組的集合。可以將每個桶視為一個個獨立的小型時態(tài)數(shù)據(jù)庫，利用第2節(jié)講述的方法建立時態(tài)索引。

圖2較為形象地顯示了兩層索引結(jié)構(gòu)方案。在該圖中，第一層為一個建立在散列鍵Dept上的Hashing數(shù)組，該數(shù)組中每一項均指向一個時態(tài)索引樹。不難看出，利用該兩層索引樹，使用上述的兩步查找方法能有效地完成時態(tài)選擇操作。

4 結(jié)束語

用于科學研究和數(shù)據(jù)統(tǒng)計的數(shù)據(jù)庫往往需要保存時態(tài)數(shù)據(jù)，本文根據(jù)時態(tài)數(shù)據(jù)庫的特點，提出了一種有別于傳統(tǒng)B+樹的索引技術(shù)，它支持對指定段時間內(nèi)滿足條件的元組集合的搜索。基于節(jié)省空間的考慮，應(yīng)用者可以根據(jù)實際情況調(diào)整葉節(jié)點的大小。最后根據(jù)時態(tài)數(shù)據(jù)庫中時態(tài)操作的相應(yīng)要求，利用成熟的Hashing索引技術(shù)，對時態(tài)索引進行了改進和擴展。

參考文獻：

[1]劉云生.現(xiàn)代數(shù)據(jù)庫技術(shù)[M].北京:國防工業(yè)出版社，2001.64-65，97-99.

[2]Hector GarciaMolina， Jeffrey D Ullman， Jennifer Widom.數(shù)據(jù)庫系統(tǒng)實現(xiàn)[M].楊東青，唐世渭，徐其鈞，等.北京：機械工業(yè)出版社，2000.124126.

[3]Ramez Elmasri， Gene T J Wuu， Yeongjoon Kim. The Time Index: An Access Structure for Temporal Data[C].Brisbane Australia: Proceedings of the 16th VLDB Conference， 1990.112.

[4]Daeweon Son， Ramez Elmasri. Efficient Temporal Join Processing Using Time Index[C]. Proc. of the 8th International Conf. on Scientific and Statistical Database Systems， 1996.252-261.

[5]何新貴，唐常杰，劉云生.特種數(shù)據(jù)庫技術(shù)[M].北京：科學出版社，2000.27-28.

作者簡介：

劉云生（1940-），男，教授，博導，研究方向為現(xiàn)代數(shù)據(jù)庫理論與技術(shù)及其集成實現(xiàn)、數(shù)據(jù)庫與信息系統(tǒng)開發(fā)、實時數(shù)據(jù)庫工程軟件方法與軟件開發(fā)；游安（1984-），男，碩士研究生，研究方向為現(xiàn)代數(shù)據(jù)庫技術(shù)、移動、實時數(shù)據(jù)庫系統(tǒng)等。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文