BCDM雙時(shí)態(tài)信息規(guī)范化及實(shí)現(xiàn)

楊春蕾 王祥雒 鄭瑞娟 張明川 婁 穎

BCDM雙時(shí)態(tài)信息規(guī)范化及實(shí)現(xiàn)

楊春蕾1王祥雒2鄭瑞娟1張明川1婁 穎1

1(河南科技大學(xué)電子信息工程學(xué)院 河南 洛陽 471003)

2(洛陽師范學(xué)院信息技術(shù)學(xué)院 河南 洛陽 471022)

為簡化雙時(shí)態(tài)數(shù)據(jù)模型(BCDM)時(shí)態(tài)屬性表達(dá)、減少存儲(chǔ)空間、提高查詢效率，按照雙時(shí)態(tài)信息的3種表達(dá)形式，針對有效時(shí)間區(qū)間更新歷史是否保留的兩種情況，討論雙時(shí)態(tài)數(shù)據(jù)的合并描述、優(yōu)化算法、合并傳統(tǒng)雙時(shí)態(tài)序偶為“事務(wù)時(shí)間區(qū)間+有效時(shí)間區(qū)間”的表達(dá)機(jī)制，給出規(guī)范的BCDM雙時(shí)態(tài)形式定義。復(fù)雜性分析表明，規(guī)范的BCDM雙時(shí)態(tài)標(biāo)簽具有明顯的低存儲(chǔ)性和高查詢效率。

BCDM 雙時(shí)態(tài)信息 規(guī)范化 合并

0 引 言

目前，時(shí)態(tài)信息越來越多地滲入到眾多領(lǐng)域，人們?yōu)榱吮磉_(dá)信息隨時(shí)間變化的痕跡，將數(shù)據(jù)連同影響其值變化的時(shí)間因素合并存儲(chǔ)，促進(jìn)了各種時(shí)態(tài)數(shù)據(jù)模型的產(chǎn)生和發(fā)展。具代表性的有TDB(Time Relational Model)模型、HRDM(Historical Relational Data Model)模型等[1,2]。為了統(tǒng)一各種時(shí)態(tài)信息模型，TSQL2提出了BCDM，并成為SQL3所提出的標(biāo)準(zhǔn)化模型，不僅有HRDM可處理的有效時(shí)間表達(dá)機(jī)制，還融入了事務(wù)時(shí)間表達(dá)。雖然時(shí)態(tài)數(shù)據(jù)庫的規(guī)范和標(biāo)準(zhǔn)化過程艱難曲折，目前仍然存在不同觀點(diǎn)，而且涌現(xiàn)出在概念結(jié)構(gòu)、XML等方面及醫(yī)藥領(lǐng)域擴(kuò)展的多種數(shù)據(jù)模型[3,4]BCDM作為表示及演示數(shù)據(jù)模型的中介和雙時(shí)態(tài)表達(dá)機(jī)制的優(yōu)勢成為相對完善的時(shí)態(tài)數(shù)據(jù)模型[3]，從而促進(jìn)了它被推廣與應(yīng)用，基于BCDM的各方面研究也成為時(shí)態(tài)數(shù)據(jù)庫研究的一個(gè)熱點(diǎn)[5]。

但BCDM有個(gè)明顯的缺點(diǎn)，就是不便于存儲(chǔ)，主要原因在于其時(shí)態(tài)信息的表示方法占據(jù)大量空間(詳見1.1節(jié))，而TSQL2的實(shí)際存儲(chǔ)形式——面向存儲(chǔ)的表示模型可與BCDM等價(jià)轉(zhuǎn)換，但表示模型在TSQL2中沒有做統(tǒng)一規(guī)定。因此，眾學(xué)者提出了多種規(guī)范化BCDM時(shí)態(tài)存儲(chǔ)的方法，文獻(xiàn)[6,7]給出了BCDM的時(shí)態(tài)表達(dá)機(jī)制及規(guī)范化方法，但存在兩個(gè)問題：1) 對時(shí)態(tài)元素處理前沒有對非時(shí)態(tài)元素進(jìn)行規(guī)范化整理，不能保證非時(shí)態(tài)元素屬性值完全相同的元組只有一個(gè)，這樣規(guī)范化后的時(shí)態(tài)信息可能有二義性，規(guī)范化不徹底；2) 對now和UC進(jìn)行確定化綁定后未對時(shí)態(tài)信息進(jìn)一步梳理，可能會(huì)造成有效時(shí)間區(qū)間相同的組合其事務(wù)時(shí)間區(qū)間未合并，且用當(dāng)前時(shí)間CT綁定now和UC太過悲觀，忽略了有效時(shí)間的“將來”含義[8]；文獻(xiàn)[9]將BCDM同一數(shù)據(jù)項(xiàng)的時(shí)態(tài)區(qū)間進(jìn)行了合并，存儲(chǔ)事務(wù)時(shí)間和有效時(shí)間的起止時(shí)刻的方式與前人無本質(zhì)區(qū)別，雖給出算法描述但并未給出時(shí)態(tài)信息合并的方法，且未進(jìn)行規(guī)范化處理，對有錯(cuò)元組的分析、定義描述不清。此外，還有一些文獻(xiàn)雖給出了雙時(shí)態(tài)信息合并、優(yōu)化的方法，但由于研究的核心不在于此，不能達(dá)到本文規(guī)范化的目標(biāo)[10-12]。

上述文獻(xiàn)提供了簡化時(shí)態(tài)表達(dá)、合并時(shí)間區(qū)間的方法，存在一些缺點(diǎn)且均未給出實(shí)現(xiàn)的算法。Luca Anselma等學(xué)者在文獻(xiàn)[11]中提出了用類似[1,UC]×[1,100]的形式表達(dá)雙時(shí)態(tài)信息的方式，但僅限于錄入BCDM雙時(shí)態(tài)信息時(shí)讀取，還需要按照文獻(xiàn)[12]中提出的方法轉(zhuǎn)化回傳統(tǒng)BCDM時(shí)態(tài)表示的形式。此外，文獻(xiàn)[12]還進(jìn)行了BCDM更新操作的時(shí)態(tài)延展處理，將事務(wù)時(shí)間和有效時(shí)間的區(qū)間表達(dá)方式轉(zhuǎn)換為離散時(shí)間點(diǎn)的表達(dá)，并給出now相關(guān)的語義處理方法。提供了依據(jù)本文進(jìn)行規(guī)范化后的BCDM轉(zhuǎn)化回傳統(tǒng)BCDM時(shí)態(tài)表示的方法。文獻(xiàn)[13]提出了一種對BCDM復(fù)雜更新操作提案的語義時(shí)態(tài)關(guān)系數(shù)據(jù)模型，其中研究BCDM時(shí)態(tài)信息的過程為本文提供了研究有效時(shí)間區(qū)間特征的思路。

在總結(jié)前人經(jīng)驗(yàn)、結(jié)合大量實(shí)例的基礎(chǔ)上，本文提出對BCDM規(guī)范化的完整步驟，分析是否保留有效時(shí)間更新歷史對時(shí)態(tài)信息表達(dá)機(jī)制的影響、優(yōu)化時(shí)態(tài)信息的合并方法、優(yōu)化不確定時(shí)態(tài)元素now和UC在合并中的處理方式，并給出以上步驟的實(shí)現(xiàn)算法，最后定義規(guī)范的BCDM雙時(shí)態(tài)信息表達(dá)形式。

1 優(yōu)化的BCDM的時(shí)態(tài)表達(dá)機(jī)制

時(shí)間的演進(jìn)狀態(tài)可以通過時(shí)間軸表示，即使用非負(fù)實(shí)數(shù)軸上的點(diǎn)來表示各個(gè)時(shí)刻?；趯r(shí)間軸結(jié)構(gòu)的選擇，時(shí)間模型可以劃分連續(xù)、步迸、離散和恒定四種類型。其中被廣泛應(yīng)用的時(shí)間模型是離散模型。

1.1 傳統(tǒng)的BCDM時(shí)態(tài)表示

恰當(dāng)?shù)碾p時(shí)態(tài)表達(dá)形式可以簡化對傳統(tǒng)屬性向量的存儲(chǔ)，BCDM采用了離散模型表達(dá)時(shí)態(tài)信息，事務(wù)時(shí)間TT={0,1,…,UC}和有效時(shí)間VT={0,1,…,Now}均用離散的時(shí)間點(diǎn)來表示，可用自然數(shù)進(jìn)行編碼。有效時(shí)間和事務(wù)時(shí)間都是絕對時(shí)間，它們構(gòu)成BCDM模型中的時(shí)間域，其中，UC表示until changed，指數(shù)據(jù)庫的數(shù)據(jù)在沒有更新之前記錄是當(dāng)前的；Now表示當(dāng)前時(shí)間，指數(shù)據(jù)庫中的有效時(shí)間在當(dāng)前依然有效[7]。BCDM模型中，定義雙時(shí)態(tài)標(biāo)簽(TT,VT)這種時(shí)間二元組的形式表達(dá)時(shí)態(tài)信息，TT和VT可以是時(shí)間點(diǎn)、時(shí)間區(qū)間、時(shí)間區(qū)間的交、并、補(bǔ)的其中之一[3]。

在常規(guī)數(shù)據(jù)庫元組上加上雙時(shí)態(tài)標(biāo)簽即可得到雙時(shí)態(tài)元組。BCDM的雙時(shí)態(tài)標(biāo)簽首先可以看做一些離散的二維時(shí)間點(diǎn)的集合，如表1所示，表達(dá)了一個(gè)帶UC和now的BCDM中雙時(shí)態(tài)序偶的分布情況。

表1 帶UC和now的BCDM中雙時(shí)態(tài)序偶分布示例

續(xù)表1

1.2 雙時(shí)態(tài)標(biāo)簽

事務(wù)時(shí)間一般是離散的時(shí)間點(diǎn)，文獻(xiàn)[6,7,12-14]用間斷的時(shí)間區(qū)間表示離散時(shí)間點(diǎn)的方法處理時(shí)間元素，且雙時(shí)態(tài)標(biāo)簽的規(guī)范化使用在具有時(shí)間變元Now和UC的系統(tǒng)中優(yōu)點(diǎn)尤為突出，具有普遍性。本文延用這種方法處理BCDM時(shí)態(tài)信息，采用的雙時(shí)態(tài)結(jié)構(gòu)用雙時(shí)態(tài)點(diǎn)[3](表示一個(gè)事務(wù)時(shí)間加有效時(shí)間二元組(tt,tv))、雙時(shí)態(tài)組合集[3](表示雙時(shí)態(tài)點(diǎn)的集合)、雙時(shí)態(tài)區(qū)間組和雙時(shí)態(tài)標(biāo)簽表達(dá)。

定義1雙時(shí)態(tài)區(qū)間組Cbt表示兩個(gè)時(shí)態(tài)區(qū)間的組合，含事務(wù)時(shí)間區(qū)間和有效時(shí)間區(qū)間，用([tts, tte] ,[tvs,tve])表示，其中tts和 tte均表示事務(wù)時(shí)間點(diǎn)，tvs和tve均表示有效時(shí)間點(diǎn)。

雙時(shí)態(tài)區(qū)間組的提出，描述了元組的有效時(shí)間區(qū)間[tvs,tve]在tts至 tte的事務(wù)時(shí)間區(qū)間內(nèi)均是合法的。

定義2 雙時(shí)態(tài)標(biāo)簽Lbt表示雙時(shí)態(tài)區(qū)間組的集合，用{([tts, tte] ,[tvs,tve])| tts∈TT∧tte∈TT∧tvs∈VT∧tve∈VT∧tts≤tte∧tvs≤tve}表達(dá)，其中，tts和 tte表示事務(wù)時(shí)間點(diǎn)，每一個(gè)[tvs,tve]均有某一個(gè)事務(wù)時(shí)間區(qū)間[tts, tte]與之對應(yīng)，雙時(shí)態(tài)標(biāo)簽表達(dá)了非時(shí)態(tài)屬性組在包含UC和Now兩個(gè)時(shí)態(tài)變量的時(shí)間元素特征。

2 BCDM雙時(shí)態(tài)表示的規(guī)范化

本文中，用符號(hào)變量表示雙時(shí)態(tài)點(diǎn)、組合集和區(qū)間組的事務(wù)時(shí)間和有效時(shí)間，具體表達(dá)如表2所示。

表2 符號(hào)變量含義說明

2.1 整理非時(shí)態(tài)屬性相同的元組

若BCDM關(guān)系R={A|T}，其中A表示一個(gè)集合{A1,A2,…,An}是R中所有的非時(shí)態(tài)屬性，T為R的時(shí)態(tài)屬性，對于R的一個(gè)實(shí)例r，有元組t1,t2∈r,t1={a11,…,a1n|T1},t2={a21,…,a2n|T2}，若t1[A]=t2[A], 則t1∪t2={ a11,…,a1n| T1∪T2}。

Function 1 ReorgTuplea(t1,t2)

begin

if (t1[A]= =t2[A])

{ t1={ a11,…,a1n| T1∪T2} ; delete t2; }

end

2.2 合并雙時(shí)態(tài)點(diǎn)為雙時(shí)態(tài)組合集

經(jīng)過整理非時(shí)態(tài)屬性相同的元組的時(shí)態(tài)屬性后，BCDM關(guān)系R中各元組非時(shí)態(tài)屬性集A取值各不相同，時(shí)態(tài)屬性T各由一組雙時(shí)態(tài)點(diǎn)Pbt表示，接下來需要將各元組的雙時(shí)態(tài)點(diǎn)Pbt合并為雙時(shí)態(tài)組合集Abt的形式，使得相同事務(wù)時(shí)間點(diǎn)下的有效時(shí)間點(diǎn)連接成有效時(shí)間區(qū)間。

Function 2 ComPbt(t[T])

/*t[T]={ Pbt|Pbt=(tt,tv), tt∈TT , tv∈VT }*/

begin

for all Pbts

{整理所有Pbt按照(tt第一順序、tv第二順序)升序排列，UC和now分別為tt和tv的最大值；

if (Pbt(i).tt=UC) delete(Pbt(i)); /*優(yōu)化，避免后續(xù)事務(wù)時(shí)間添

加新的信息時(shí)未刪除前序事務(wù)時(shí)間添加的UC信息情況*/

}

for all Pbts

{ i←1;j←0;

if (not the first∧Pbt(i). tt=Pbt(i-1).tt)

{ if (Pbt(i).tv=Pbt(i-1).tv+1)

Abt(j). tve←Abt(j). tve+1;

if (Pbt(i).tv=now) Abt(j). tve←now;

continue;

}

/*是第一個(gè)雙時(shí)態(tài)點(diǎn)，或事務(wù)時(shí)間不同，或有效時(shí)間不等于上一雙時(shí)態(tài)點(diǎn)增1，則生成新的Abt*/

j←j+1;

Abt(j)←(Pbt(i). tt,[ Pbt(i).tv, Pbt(i).tv]);

}/* for all Pbts，合并后Abt的個(gè)數(shù)j將遠(yuǎn)遠(yuǎn)小于原雙時(shí)態(tài)點(diǎn)的個(gè)數(shù)i*/

Abt(j+1) ←( UC,[ tvs, tve]);

/*最后添加UC信息*/

end

合并后的Abt具有如下特征：

(1) 在合并前對所有Pbt先進(jìn)行了排序，UC作為事務(wù)時(shí)間最大值，刪除出現(xiàn)在前面的UC，重新添加UC信息在所有Pbt歸并為Abt之后，所以，對于有效時(shí)間區(qū)間相同的一組Abt，UC必定出現(xiàn)在最后那個(gè)Abt中。

(2) 由于Function 2 ComPbt(t[T])先將事務(wù)時(shí)間為UC的那些Pbt刪除才進(jìn)行合并，避免了后續(xù)事務(wù)時(shí)間添加新的信息時(shí)未刪除前序事務(wù)時(shí)間添加的UC信息情況，若UC由Function 2 ComPbt(t[T])添加，則其有效時(shí)間區(qū)間與最后一個(gè)確定的事務(wù)時(shí)間對應(yīng)的有效時(shí)間區(qū)間相同。

(3) now作為有效時(shí)間的最大值，不可能出現(xiàn)在有效時(shí)間區(qū)間的起始端。

(4) 事務(wù)時(shí)間相同、有效時(shí)間連續(xù)的Pbt才會(huì)被合并為一個(gè)Abt。也就是說不同的事務(wù)時(shí)間在不同的Abt中；相同的事務(wù)時(shí)間若有效時(shí)間不連續(xù)，也會(huì)按照有效時(shí)間的連續(xù)情況被生成多個(gè)Abt，比如：{Pbt}={(1,2), (1,3), (2,2), (2,3), (3,2), (3,3), (4,2), (4,3), (4,7), (4,8)}→{Abt}={(1,[2,3]), (2,[2,3]), (3,[2,3]) , (4,[2,3]) , (4,[7,8])}。

2.3 合并雙時(shí)態(tài)組合集為雙時(shí)態(tài)區(qū)間組

這個(gè)階段最核心的工作就是將有效時(shí)間區(qū)間相同的、事務(wù)時(shí)間連續(xù)的Abt合并為一個(gè)Cbt。在此期間，一些細(xì)節(jié)需要考慮，也是算法優(yōu)化的第三處，即對于與前面Abt有效時(shí)間區(qū)間不相同或事務(wù)時(shí)間不連續(xù)的Abt應(yīng)怎么處理，是生成新的Cbt異或?qū)η懊娴腃bt進(jìn)行修正? 解決這個(gè)問題的關(guān)鍵在于討論當(dāng)前Abt與已經(jīng)生成的Cbt事務(wù)時(shí)間連續(xù)性和有效時(shí)間區(qū)間相關(guān)性，事務(wù)時(shí)間連續(xù)性可總結(jié)為：連續(xù)、不連續(xù)、UC因素；而有效時(shí)間區(qū)間相關(guān)性則研究不同事務(wù)時(shí)間下對應(yīng)有效時(shí)間區(qū)間的關(guān)系。

(1) 事務(wù)時(shí)間連續(xù)性：事務(wù)時(shí)間的值由系統(tǒng)時(shí)鐘給出，它獨(dú)立于應(yīng)用，用戶不能修改事務(wù)時(shí)間；且不能晚于現(xiàn)在時(shí)間，因?yàn)樗从持鴶?shù)據(jù)庫實(shí)際操作的時(shí)間，不能指未來。本文中，有效時(shí)間區(qū)間更新歷史是否保存(被修正)，決定了是否允許后續(xù)事務(wù)時(shí)間將前序事務(wù)時(shí)間延展為連續(xù)區(qū)間。

UC是最后一個(gè)確定的事務(wù)時(shí)間錄入信息時(shí)被表示“未來”而自動(dòng)添加的，被認(rèn)為和眾Abt中最后一個(gè)確定的事務(wù)時(shí)間是連續(xù)的，且二者有效時(shí)間區(qū)間相同，含UC的Abt出現(xiàn)在{Abt}最后。

(2) 有效時(shí)間區(qū)間相關(guān)性：Allen的13種時(shí)間區(qū)間基本關(guān)系[17]雖是在連續(xù)模型中提出，但可被離散模型參考。這13種關(guān)系中有6對是可逆的，equals表示了兩個(gè)起始和終止時(shí)間都相同的時(shí)間區(qū)間，BCDM中存在不確定的時(shí)間點(diǎn)now，本文中加入與now相關(guān)的時(shí)間區(qū)間關(guān)系now-relating。圖1描述了兩個(gè)時(shí)間區(qū)間(t1,t2)的now-relating關(guān)系，將now作為有效時(shí)間的最大值，可認(rèn)為now-relating是基本關(guān)系的特殊情況。

圖1 有效時(shí)間區(qū)間now-relating關(guān)系

2.3.1 不保存有效時(shí)間區(qū)間更新歷史的合并

這種環(huán)境下，后續(xù)事務(wù)時(shí)間如發(fā)現(xiàn)前序事務(wù)時(shí)間下錄入的有效時(shí)間區(qū)間無效(或部分無效)，則直接對無效的部分進(jìn)行修正、且不保存曾經(jīng)存在的歷史。在合并事務(wù)時(shí)間為時(shí)間區(qū)間的過程中認(rèn)為所有的事務(wù)時(shí)間點(diǎn)在有效時(shí)間區(qū)間有變化前是連續(xù)的，若存在{Abt}={(1,[2,3]), (2,[2,3]) , (4,[2,3]), (4,[7,8])}的情況，則認(rèn)為當(dāng)tt=3時(shí)仍然滿足有效時(shí)間區(qū)間為[2,3]，雙時(shí)態(tài)組合集(1,[2,3]), (2,[2,3]) , (4,[2,3])將被合并為([1,4],[2,3])，這是對Abt所做的關(guān)于事務(wù)時(shí)間連續(xù)性修正。合并后的時(shí)態(tài)標(biāo)簽含雙時(shí)態(tài)區(qū)間組合數(shù)目少、易讀取、易操作。

由于在合并前對所有Pbt先進(jìn)行了排序，所以Abt關(guān)于事務(wù)時(shí)間和有效時(shí)間區(qū)間升序有序。對于默認(rèn)事務(wù)時(shí)間連續(xù)、允許后續(xù)事務(wù)時(shí)間下對有效時(shí)間區(qū)間進(jìn)行修正的BCDM雙時(shí)態(tài)信息，其最終有效時(shí)間區(qū)間僅與確定的最大事務(wù)時(shí)間(除去UC的事務(wù)時(shí)間最大值)對應(yīng)的有效時(shí)間區(qū)間有關(guān)，前序值或無效被修正、或有效被合并、或被誤修正后再被納入回有效區(qū)間。

下面給出Function 3 ComAbt(t[T])用以不保存有效時(shí)間更新歷史條件下歸并Abt為Cbt(事務(wù)時(shí)間區(qū)間+有效時(shí)間區(qū)間)的表示形式，在此期間將除最后一個(gè)有效時(shí)間區(qū)間tve之外的now確定化。

Function 3 ComAbt(t[T])

/*t[T]={ Abt|Abt=(tt,[tvs, tve]), tt∈TT∧tvs∈VT∧tve∈VT∧tvs≤tve}*/

begin

i←1;

for all Abts

{if (i=1)

tt-max ← Abt(1). tt;

else

if (Abt(i). tt>Abt(i-1). tt∧Abt(i). tt≠UC)

tt-max ← Abt(i). tt;

}

k←0;

for all Abts

if (Abt(i). tt=tt-max)

{k←k+1;

Cbt(k) ←([Abt(1). tt, UC],[ Abt(i). tvs, Abt(i). tve]);

}

end

2.3.2 保存有效時(shí)間區(qū)間更新歷史的合并

這種環(huán)境下，尤其是時(shí)態(tài)相關(guān)屬性具有反復(fù)性、周期性特征時(shí)[18]，后續(xù)事務(wù)時(shí)間如發(fā)現(xiàn)前序事務(wù)時(shí)間下錄入的有效時(shí)間區(qū)間無效(或部分無效)，不對無效的部分進(jìn)行修正、保存曾經(jīng)存在的歷史，后續(xù)時(shí)態(tài)信息生成新的雙時(shí)態(tài)區(qū)間組。在合并事務(wù)時(shí)間為時(shí)間區(qū)間的過程中認(rèn)為所有的事務(wù)時(shí)間點(diǎn)在有效時(shí)間區(qū)間有變化時(shí)應(yīng)生成新的雙時(shí)態(tài)區(qū)間組；有效時(shí)間區(qū)間相同但事務(wù)時(shí)間不同時(shí)不能對事務(wù)時(shí)間進(jìn)行連續(xù)性延展、合并，若存在{Abt}={(1,[2,3]), (2,[2,3]) , (4,[2,3]), (4,[7,8])}的情況，則認(rèn)為當(dāng)tt=3時(shí)不滿足有效時(shí)間區(qū)間為[2,3]，雙時(shí)態(tài)組合集(1,[2,3]), (2,[2,3]) , (4,[2,3])將被合并為([1,2],[2,3])和([4,4],[2,3])。合并后的時(shí)態(tài)標(biāo)簽含雙時(shí)態(tài)區(qū)間組在有修正的情況下數(shù)目相對較多，讀取及操作相對復(fù)雜。

設(shè)Abt(i)是當(dāng)前讀取的雙時(shí)態(tài)組合集，取i=1,2,…,n研究Abt(i)與前序生成的Cbt的關(guān)系并進(jìn)一步處理，只有Abt(i)·tv與已生成的某Cbt(s)的有效時(shí)間區(qū)間相等(在此，本節(jié)認(rèn)為當(dāng)Cbt(s)·tvs=Abt(i)·tvs∧Cbt(s)·tve=now∧Abt(i)·tve≠now時(shí)，Abt(i)·tve是對Cbt(s)·tve的now值確定化，二者應(yīng)視為相等)，且Abt(i)·tt=Cbt(s)·tte+1，設(shè)Cbt(s)·tte值增為Cbt(s)· tte+1便將Abt(i)合并；其他情況均需生成新的Cbt。

下面給出Function 4 ComAbt_PreHis(t[T])用以不保存有效時(shí)間更新歷史條件下歸并Abt為Cbt(事務(wù)時(shí)間區(qū)間+有效時(shí)間區(qū)間)的表示形式，在此期間將除最后一個(gè)有效時(shí)間區(qū)間tve之外的now確定化。

Function 4 ComAbt_PreHis (t[T])

/*t[T]={ Abt|Abt=(tt,[tvs, tve]), tt∈TT∧tvs∈VT∧tve∈VT∧tvs≤tve}*/

begin

i←1; k←0;

for all Abts

{ s←1;

for all Cbts

if (Abt(i).tt=Cbt(s).tte+1)

if (Cbt(s).tv=Abt(i).tv)∨(Cbt(s).tvs=Abt(i).tvs∧Cbt(s).tve=now∧Abt(i).tve≠now)

{Cbt(s).tte←Cbt(s).tte+1;

find←true;

break;

}

if ( find≠true) /*new Cbt*/

{k←k+1;

Cbt(s).tts←([Abt(i).tt, Abt(i).tt],[ Abt(i).tvs, Abt(i).tve];

}

}

end

2.4 規(guī)范的BCDM雙時(shí)態(tài)形式

經(jīng)過2.1至2.3節(jié)的處理，BCDM的雙時(shí)態(tài)信息被合并為Lbt的形式，UC和now只會(huì)在最后一個(gè)雙時(shí)態(tài)區(qū)間組中出現(xiàn)，需不需要確定化、如何確定化在不同的環(huán)境中語義不同，可根據(jù)文獻(xiàn)[8,12]等提供的方法進(jìn)行分析和處理，本文不再贅述。

將具有規(guī)范化特征的BCDM雙時(shí)態(tài)信息稱為規(guī)范的BCDM雙時(shí)態(tài)標(biāo)簽。

定義3 規(guī)范的BCDM雙時(shí)態(tài)形式。若BCDM的雙時(shí)態(tài)信息滿足以下三種條件的任一種，則稱之為規(guī)范的BCDM雙時(shí)態(tài)形式；

(1) 若Lbt={ Cbt| Cbt=([tts, tte] ,[tvs,tve]) ∧ tts∈TT∧tte∈TT∧tvs∈VT∧tve∈VT∧tts≤tte∧tvs≤tve}，且對?Cbt(i)和Cbt(j)，i≠j，均有Cbt(i)· [tts, tte]=Cbt(j)·[tts, tte] ∧tte=UC∧(Cbt(i)· [tvs,tve] ∩Cbt(j)· [tvs,tve]=φ)成立；

(2) 若Lbt={ Cbt| Cbt=([tts, tte] ,[tvs,tve]) ∧ tts∈TT∧tte∈TT∧tvs∈VT∧tve∈VT∧tts≤tte∧tvs≤tve}，對?Cbt(i)和Cbt(j)，i≠j，若Cbt(i)· [tts, tte]=Cbt(j)·[tts, tte]均有(Cbt(i)·[tvs,tve] ∩Cbt(j)·[tvs,tve]=φ)成立；

(3) 由(1)、(2)按文獻(xiàn)[12]轉(zhuǎn)化的用雙時(shí)態(tài)點(diǎn)集合表達(dá)雙時(shí)態(tài)信息的形式；

以上三種情況均被稱為規(guī)范的BCDM雙時(shí)態(tài)形式，(1)、(2)被稱為規(guī)范的BCDM雙時(shí)態(tài)標(biāo)簽，(3)被稱為規(guī)范的BCDM雙時(shí)態(tài)點(diǎn)集。

3 規(guī)范BCDM雙時(shí)態(tài)標(biāo)簽復(fù)雜性分析

為了分析規(guī)范的BCDM雙時(shí)標(biāo)簽這種表達(dá)形式的空間復(fù)雜性及查詢響應(yīng)，基于MySQL數(shù)據(jù)庫、JDK和NetBeans，我們完成了對比實(shí)驗(yàn)。實(shí)驗(yàn)針對雙時(shí)態(tài)信息分別為雙時(shí)態(tài)點(diǎn)、雙時(shí)態(tài)組合集和規(guī)范化的雙時(shí)態(tài)標(biāo)簽(由雙時(shí)態(tài)區(qū)間組集合形式表達(dá))三種形式下的教師信息開展，其中，雙時(shí)態(tài)組合集和規(guī)范化的雙時(shí)態(tài)標(biāo)簽在合并時(shí)不保存有效時(shí)間區(qū)間更新歷史。

圖2和圖3顯示了教師信息元組數(shù)目從100增至500時(shí)，元組的雙時(shí)態(tài)信息分別以上述三種形式表達(dá)時(shí)在數(shù)據(jù)的空間占用和查詢效率兩方面的對比情況。

圖2 雙時(shí)態(tài)信息在三種形式下數(shù)據(jù)的空間占用對比

圖3 雙時(shí)態(tài)信息在三種形式下數(shù)據(jù)的查詢響應(yīng)時(shí)間對比

實(shí)驗(yàn)數(shù)據(jù)顯示，數(shù)據(jù)的雙時(shí)態(tài)信息采用規(guī)范化雙時(shí)態(tài)標(biāo)簽形式表達(dá)和存儲(chǔ)時(shí)，其空間利用效率和查詢響應(yīng)效率要大于采用雙時(shí)態(tài)組合集形式，二者均遠(yuǎn)遠(yuǎn)高于采用雙時(shí)態(tài)點(diǎn)集的形式。由于實(shí)驗(yàn)數(shù)據(jù)不僅依賴于雙時(shí)態(tài)信息的表達(dá)形式，也和數(shù)據(jù)結(jié)構(gòu)、屬性組成、雙時(shí)態(tài)信息在整個(gè)數(shù)據(jù)中占有的比重相關(guān)，因此規(guī)范化BCDM雙時(shí)態(tài)標(biāo)簽的復(fù)雜性還可從理論推導(dǎo)來分析。

3.1 存儲(chǔ)空間壓縮率

可以看出k為定值時(shí)，有效時(shí)間區(qū)間越大，規(guī)范化的雙時(shí)態(tài)標(biāo)簽存儲(chǔ)空間壓縮越多；有效時(shí)間區(qū)間為定值時(shí)，區(qū)間個(gè)數(shù)越多，壓縮越少。

3.2 查詢復(fù)雜度

顯然，無論空間壓縮率還是查詢復(fù)雜度，規(guī)范化的BCDM雙時(shí)態(tài)標(biāo)簽具有比雙時(shí)態(tài)點(diǎn)集的形式占用空間少、查詢效率高的明顯優(yōu)勢。

4 結(jié) 語

BCDM的優(yōu)勢使之能夠被廣泛推廣和應(yīng)用，其應(yīng)用領(lǐng)域廣泛、存儲(chǔ)表達(dá)不統(tǒng)一使得學(xué)者們在這方面的研究和討論將持續(xù)升溫。本文在分析了已有相關(guān)文獻(xiàn)的優(yōu)缺點(diǎn)、結(jié)合大量時(shí)態(tài)數(shù)據(jù)信息的基礎(chǔ)上提出了雙時(shí)態(tài)區(qū)間組的概念用以合并傳統(tǒng)BCDM的雙時(shí)態(tài)點(diǎn)并表示規(guī)范的BCDM雙時(shí)態(tài)信息；合并算法在是否修正有效時(shí)間區(qū)間、是否保留更新歷史等方面做了更加全面的分析和研究，算法優(yōu)化表現(xiàn)在：① 合并前整合非時(shí)態(tài)屬性相同的元組，排除非時(shí)態(tài)屬性相同的元組其時(shí)態(tài)屬性可能存在的重復(fù)性、二義性；② 整理所有Pbt按照(tt第一順序、tv第二順序)升序排列，刪除最大確定事務(wù)時(shí)間之前含UC的Pbt，合并完畢后添加UC，體現(xiàn)UC現(xiàn)實(shí)意義、簡化算法實(shí)現(xiàn)；③ 依據(jù)14種有效時(shí)間區(qū)間基本關(guān)系決定“保留更新歷史與否”兩種情況下的合并方法，并確定化非最大事務(wù)時(shí)間對應(yīng)的其他now變元。復(fù)雜性分析表示這種規(guī)范的BCDM雙時(shí)態(tài)信息表達(dá)機(jī)制能有效降低存儲(chǔ)空間、提高查詢效率。

經(jīng)歷了十幾年的沉積，商業(yè)數(shù)據(jù)庫供應(yīng)商發(fā)現(xiàn)伴隨著與雙時(shí)態(tài)信息相關(guān)的數(shù)據(jù)與日俱增，這使得雙時(shí)態(tài)特征被納入SQL:2011，雙時(shí)態(tài)信息在表示層獲得了充分的支持和利用，顯然，其表示和應(yīng)用方面的研究也將活躍起來。我們急切地希望規(guī)范化的BCDM雙時(shí)態(tài)形式能夠被廣泛應(yīng)用，后續(xù)工作將進(jìn)一步完善在基于規(guī)范的BCDM雙時(shí)態(tài)信息表達(dá)機(jī)制的數(shù)據(jù)依賴及更新技術(shù)研究。

[1] Clifford J.A Model for Historical Databases[C]//Proceedings of Workshop On Logical Bases for Database.Toulouse,France:Ls.n.J,1982.

[2] 湯庸,湯娜,葉小平.時(shí)態(tài)信息處理技術(shù)研究綜述[J].中山大學(xué)學(xué)報(bào):自然科學(xué)版,2003,42(4):4-8.

[3] 楊春蕾,王祥雒,鄭瑞娟.基于對象時(shí)態(tài)穩(wěn)定性分類特征的雙時(shí)態(tài)ER模型[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(4):69-74.

[4] Tang Y,Ye X,Tang N.Temporal Information Processing Technology and Its Applications[M].Springer,2011:1-42,67-131.

[5] 湯庸.時(shí)態(tài)數(shù)據(jù)庫導(dǎo)論[M].北京大學(xué)出版社,2004.

[6] Lubang W,Jin W.Presentation Mechanism about Temporal Attributes in BCDM Based on RDBMS[C]//2009 International Conference on Electronic Commerce and Business Intelligence,ECBI,2009:49-52.

[7] 王路幫.BCDM 中的時(shí)間標(biāo)簽規(guī)范及優(yōu)化[J].華東師范大學(xué)學(xué)報(bào):自然科學(xué)版,2006,5(1):110-115.

[8] 朱雄雄.在各種查詢條件下Now語義處理[D].中山大學(xué),2010:5-10,17-18.

[9] 劉智,李唯唯.有效的BCDM時(shí)態(tài)信息簡化方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(12):3269-3271.

[10] 印國成,孫茂圣.時(shí)間上下文的屬性限制及一致性分析研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4548-4550.

[11] Anselma L,Bollzighi A,Monlani S,et al.Managing proposals and evaluations of updates to medical knowledge:Theory and applications[J].Journal of Biomedical Informatics,2013,46(2):363-76.

[12] Anselma L,Stantic B,Terenziani P,et al.Querying now-relative data[J].Journal of Intelligent Information Systems,October 2013,41(2):285-311.

[13] Lubang W,Bottrighi A,Montani S,et al.Extending BCDM to Cope with Proposals and Evaluations of Updates[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(3):556-570.

[14] 王路幫,錢省三.基于BCDM的含有變量的雙時(shí)態(tài)關(guān)系代數(shù)研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(6):2071-2074.

[15] Allen J.Maintaining Knowledge about Temporal Intervals[J].ACM,1983,26(11):832-843.

[16] 樓婷淵.時(shí)態(tài)文本數(shù)據(jù)的周期性挖掘研究[D].浙江工業(yè)大學(xué),管理科學(xué)與工程,2012:26-30.

[17] Kaufmann Martin,Fischer Peter M,May Norman,et al.TPC-BiH: A benchmark for bitemporal databases[C]//Performance Characterization and Benchmarking - 5th TPC Technology Conference,TPCTC 2013,LNCS,2014,v8391:16-31.

[18] Kulkarni,Krishna,Jan-Eike Michels.Temporal features in SQL: 2011[J].ACM SIGMOD Record,2012,41(3):34-43.

BCDM BITEMPORAL INFORMATION STANDARDISATION AND ITS IMPLEMENTATION

Yang Chunlei1Wang Xiangluo2Zheng Ruijuan1Zhang Mingchuan1Lou Ying1

1(SchoolofElectronicandInformationEngineering,HenanUniversityofScienceandTechnology,Luoyang471003,Henan,China)2(SchoolofInformationTechnology,LuoyangNormalUniversity,Luoyang471022,Henan,China)

For simplifying temporal attributes expression of bitemporal concept data model (BCDM), reducing storage space and increasing querying efficiency, according to three expression forms of bitemporal information and aiming at two situations of whether or not to keep the update history of effective time intervals, we discuss the combination description of bitemporal data, the optimisation algorithm, and combine the traditional bitemporal ordered pair to the expression mechanics of “transaction time interval + valid time interval”. At last, we present the standardised BCDM bitemporal formal definition. Complexity analysis indicates that the standardised BCDM label has obvious low storage property and high querying efficiency.

BCDM Bitemporal information Standardisation Combination

2014-09-25。國家自然科學(xué)基金項(xiàng)目(61142002，U120 4614，61003035，61370221)。楊春蕾，講師，主研領(lǐng)域：數(shù)據(jù)庫理論及應(yīng)用，機(jī)器學(xué)習(xí)。王祥雒，講師。鄭瑞娟，副教授。張明川，副教授。婁穎，副教授。

TP311.13

A

10.3969/j.issn.1000-386x.2016.04.051