基于BCDM的含有變量的雙時態關系代數研究

摘 要:在BCDM(雙時態概念數據模型)中，時間變元Now和UC的存在解決了時態記錄的頻繁更新問題;但是時態變元的存在又給數據庫的操作帶來某種不確定性甚至是錯誤，同時引起關系代數運算的歧義。基于BCDM，通過綁定時間變元，用時態映射的集合定義時態關系，由此建立了一種含有時間變元的雙時態關系代數體系。該關系代數體系在雙時態運算下是封閉的。

關鍵詞:雙時態概念數據模型; 雙時態數據庫; 時態變量; 雙時態關系代數

中圖分類號:TP311.13文獻標志碼:A

文章編號:1001-3695(2010)06-2071-04

doi:10.3969/j.issn.1001-3695.2010.06.021

Bitemporal relational algebra with temporal variables based on BCDM

WANG Lu-bang1，2， QIAN Xing-san1

(1. School of Management， University of Shanghai for Science Technology， Shanghai 200093， China; 2. Commercial College， Zhejiang Wanli University， Ningbo Zhejiang 315100， China)

Abstract:In BCDM (bitemporal conceptual data model)， the valid time variable Now and the transaction time variable UC resolved the problem about the frequent temporal record update. But the existence of temprol variables brought some unsertainty， even wrong on database operations， as well as the temprol relational algebra operations. Based on BCDM， binded the temporal variables， then defined the temporal relational by using the temporal mapping set， at last， established the temporal relational algebra system. The algebra system is close under the bitemporal operation.

Key words:BCDM; bitemporal database; temporal variables; bitemporal relational algebra

0 引言

現實世界是隨著時間變化而變化的，對時變屬性的記錄是時態數據庫的重要功能[1~4]。在時態數據庫中，元組記錄的不斷更新引起時間記錄經常更新，出于解決時間頻繁更新的問題，用Now和UC來表達時間變元[3~7]。但是時間變元的引入也帶來了新的問題，對于時態數據庫來說，因為增加了時間變元而使得數據庫的記錄存在不確定性，這樣對于含有變元的時態數據庫就增加了數據記錄的不確定性[3~7]。在文獻[8]中對于時間變元Now提出了一種綁定的算法，用于解決Now的語義模糊的問題。雙時態概念數據模型(BCDM)是時態數據庫中的一種典型形式，它具有二維時間屬性——有效時間和事務時間。因BCDM自身的雙時態特性，隨著數據庫新的記錄產生，時間變元的值會因為后續時間信息的記錄而使得以前的時間變元記錄得以確定[3，4]。利用BCDM的這種特性，在文獻[3]中提出了一種基于BCDM的冗余時間變元綁定思想，并對其進行了實現。

對于時態關系代數的研究，文獻[9]中描述了歷史數據庫中的一種關系代數。文獻[10]中給出了基于謂詞時態邏輯的時態演算和支持離散線性有界時間的時態代數，并指出兩者的等價性。文獻[11]描述了一個模糊的時態關系代數，它是在N1NF的歷史數據庫的模型上構建的。文獻[12]中，對于遞歸查詢給予一種時態代數的描述。文獻[13]分析了時態變量Now語義，并由此提出了一種一維的時態關系運算。文獻[14]提出了一種基于關系代數的時態擴展模型，其表達能力不低于基于演算的時態查詢語言TQuel。這些都是著眼于有效時間的時態關系代數。文獻[15]中“An Algebra for TSQL2”建立了基于TSQL2查詢語言的關系代數，但所談及的時態關系運算中有效時間的問題研究得較多，關于雙時態的問題，主要描述的是雙時態的連接操作，其他操作并沒有給出形式化的定義。文獻[16]中提出了一種基于ER時態數據模型的時態關系代數，它對于ER模型和時態代數運算給出了較好的形式化。文獻[17]中提出了一種基于多媒體表述的時態代數操作的語言。文獻[18]中提出了一種傳統關系代數上的時態擴展，解決時態查詢的優化問題。在最近研究的文獻中，文獻[19]中用區間矩陣表達時態區間，構造了區間矩陣的特征集，實現了時態區間運算的矩陣方式表達。文獻[20]結合模糊時態邏輯，對時態數據庫的概念模型進行模糊時態約束擴展和數據記錄的模糊化處理，提出模糊時態關系代數運算模型。以往文獻中對于時態關系代數的研究主要是基于有效時間的研究，而基于雙時態的模型較少。文獻[2]中提出了一種基于BCDM的雙時態關系代數，對于雙時態關系代數運算進行了形式描述，但該關系代數中沒有涉及到時間變元問題。對于雙時態關系代數的研究中，因為時間變元Now和UC的不確定性，這給雙時態代數的形式描述增加了難度，在形式描述雙時態關系代數運算時，有意回避或簡化了時態變元的問題[2]。這樣的處理手段雖然是可行的，但離實用的關系代數還有一定的距離。要解決實際的關系代數問題，時間變元是不能回避的。本文基于BCDM，在充分考慮時間變元Now和UC綁定問題的基礎上，研究了雙時態的代數運算問題，形式化地描述了含有時間變元的時態關系代數運算系統，并確定了其封閉性。本文先給出BCDM中雙時態規范元素的一些相關定義，并對其進行規范化處理，給出了時間變元的綁定操作;對于規范的雙時態標簽之間的運算也給予了描述;對雙時態關系進行定義，并對七種含有變元的雙時態代數運算進行了形式化的描述。

1 雙時態概念數據模型BCDM及其時間元素

1.1 BCDM及其時間元素

時態數據庫經歷了回滾數據庫、歷史數據庫和雙時態數據庫三種類型。BCDM(bitemporal conceptual data model)是雙時態數據庫中的重要模型，它是面向查詢和數據庫邏輯設計的雙時態概念數據模型， BCDM模型在概念上盡量與關系數據庫保持兼容[2]。BCDM最主要的特點可以歸納如下:

a)支持有效時間和事務時間的雙時態性，這種雙時態性反映在元組的時態標簽上面。

b)屬性的原子性。在除去時間標簽后，其元組記錄滿足關系數據庫特性，沒有重復記錄，滿足1NF。

c)有效時間的同質性。所有記錄的事實定義在同一類型的時間粒度上。

BCDM 的時間元素包括有效時間VT={0，1，…，Now}和事務時間TT={0，1，…，UC}。其中UC表示until changed ，在文獻[4]中的定義是數據沒有被邏輯地刪除和更新，是指數據庫的數據在沒有更新之前記錄是當前的;Now表示當前時間，指數據庫中的有效時間在當前依然有效。在BCDM模型中，元組的時間記錄中既包含了有效時間又包含了事務時間，這種雙時態的時間表示是通過雙時間標簽來表示的。其中雙時態點Pbt是個時間二元組(tt，tv)。式中tt∈TT，TT是包含UC的事務時間點的集合;而tv∈VT，VT表示含有Now的有效時間點集合。而雙時態標簽Lbt是雙時態點的集合，用{(tt，tv)|tt∈TT，tv∈VT}來形式表達。BCDM中的雙時態標簽包含時間變元Now和UC。在處理時間元素的問題中，Allen的時間區間模型是經典的連續區間模型，因而在計算機系統中應用起來比較麻煩。本文采用文獻[2～4，11]的手法，用間斷的時間區間表示離散時間點的辦法處理BCDM中的時間元素問題。

1.2 BCDM中的時間標簽的轉換

BCDM的時態元組是以快照1NF關系元組加上雙時間標簽的形式記錄的，時間標簽反映了時態元組的時間屬性。BCDM雙時態標簽中常會含有事務時間變元UC和有效時間變元Now，對這兩個時間變元進行綁定操作用于明確時間變元的語義，便于對含有時間變元的時態關系進行時態運算，在實際的時態數據庫的集合運算、查詢、更新等操作中是有重要意義的。

定義1 雙時態標簽的組合形式(bitemporal time label)。

形如{(tt，[tvs，tve])|tt∈TT∧tvs∈VT∧tve∈VT∧(tvs≤tve∨tve=Now)}的雙時態標簽稱為雙時態標簽的組合形式。所謂雙時間標簽的組合形式是指時間標簽在相同事務時間點的有效時間區間組合，用時間區間的方式表達離散的時間點。

定義2 規范的雙時態標簽組合形式(normal bitemporal time label)。

雙時態標簽的組合形式按字典排序，用集合元素羅列的形式表達為

{(a1，[c1.1，d1.1])，(a1，[c1.2，d1.2])，…，(a1，[c1.k1，d1.k1])，(a2，[c2.1，d2.1])，…，(a2，[c2.k2，d2.k2])，…，(an，[cn.1，dn.1])，…，(an，[cn.kn，dn.kn])}(1)

其中:ai∈TT，ci，j∈VT，di，j∈VT

如果滿足下列要求，則稱該標簽為規范的雙時間標簽組合形式，用LNbt表示。

1)[ci，j，di，j]為時間凸區間，即指該區間內的任何點都屬于該時態區間[8]。

2)在(ai，[ci，j，di，j])(i=1，2，…，n)中，若x

3)在(ai，[ci，j，di，j])(j=1，2，…，ki-1)中，[ci，j，di，j]∩[ci，j+1，di，j+1]=。

定理1 BCDM中的雙時態標簽都是可以用一個規范的雙時態標簽的組合形式來表達。定理的有關證明見文獻[3]有關闡述。

為了便于后文描述的方便，在規范的雙時態標簽的組合形式描述中，將式(1)中LNbt的形式修改為{((a1，∑k1i=1[c1，i，d1，i])，(a2，∑k2i=1[c2.i，d2.i])，…，(an，∑kni=1[ cn.i，dn.i]))}(∑kji=1[cj.i，dj.i]為時態元素)。

2 BCDM中的時態演算

2.1 BCDM中去冗余時間變元的綁定操作

在BCDM中，因事務時間的記錄已經更新，在過去事務時間點的有效時間變元Now沒有及時更新就會產生時間變元記錄冗余。LNbt是BCDM中規范的雙時態標簽組合形式，其形式如定義2所示。如果LNbt滿足以下條件，則稱LNbt中含有冗余時間變元:

di.ki=Now，dn.kn≠Now，∨([ci+j.x，di+j.x])st:(ci.ki∈[ci+j.x，di+j.x])∧(di+j.x≠Now)(其中:j=1，2，…，n-i;st表示“使得”之意)。

BCDM模型中因為雙時態數據庫的兩重性(歷史快照性和事務回滾性[2，3])以及事務時間和有效時間的關聯性，這給時間變元帶來了一定的確定性。可以根據BCDM自身的特性將BCDM中的冗余時間變元綁定。在對BCDM的冗余時間變元的綁定中，用當前事務時間(current transition time，CTT)來綁定冗余是最為有實際意義的。一方面在數據庫的不斷更新中需要它，另一方面在當前的時態查詢中要用到它。用當前事務時間CTT來綁定冗余時間元素，其形式如下:

設LNbt={(a1[c1.1，d1.1])，(a1，[c1.2，d1.2])，…，(a1，[c1.k1，d1.k1])，(a2，[c2.1，d2，1])，…，(a2，[c2.k2，d2.k2])，…，(an，[cn.1，dn.1])，…，(an，[cn.kn，dn.kn])}。對其進行當前事務時間CTT的冗余時間變元綁定操作用BCTT(LNbt)表達，形式描述如下:

BCTT(LNbt)={(aCTTi，[cCTTi.j，dCTTi.j]) |(di.j≠Now(aCTTi=ai，[cCTTi.j，dCTTi.j]=[ci.j，di.j]))∨(di.ki=Now，[ci+j.x，di+j.x](ci.ki∈[ci+j.x，di+j.x])∧(aCTTi=ai，[cCTTi.ki，dCTTi.ki]=[ci.ki，di+j.x]))∨(dn.kn=Now(aCTTn=an，[cCTTn.kn，dCTTn.kn]=[cn.kn，dn.kn]))}(i，j，x∈N+)(2)

2.2 單時態變元的時間元素演算

1)Ground時間區間的演算問題

不含有時間變元的時間區間為Ground時間區間。在文獻[3]中已經定義了時態元素和規范時態元素，在這里沿用文獻[3]的定義來處理時態區間的演算問題。有效時間VT和事務時間TT中元素滿足線性序，即VT和TT 中任意元素t1、t2圴滿足t1t2三種關系之一。Ground時間區間的演算問題定義為I1、I2都是Ground時間區間(不含有時間變元的時間區間)，則I1和I2的并、交、差定義為

I1和I2的并為I1∪I2={t|t∈I1∨t∈I2}

I1和I2的交為I1∩I2={t|t∈I1∧t∈I2}

I1和I2的差為I1-I2={t|t∈I1∧tI2}

2)含有變元的時間元素的演算問題

I1、I2至少有一個含有變元Now的時間區間，則I1和I2的并、交、差運算可以先進行綁定操作，然后才進行時態演算。

(1)時間變元的綁定操作

假若有時態元素I1=(t1，Now)是含有變元Now的時間區間，而u是Ground時態元素，記為u=I1+I2+…+In，則I1相對于u的綁定定義為

B(I1→u)={(tB1，tB2)|tB1=t1，Ii∈u(first(I1)∈Ii)∧tB2=last(I1)∨Ii∈u(first(I1)Ii)∧tB2=Now}

兩個時間元素u和v的去冗余綁定操作:

設u和v是兩個含有時間變量的時態元素，u=I1+I2+…+In，其中In=[first(In)，Now]。而v=I′1+I′2+…+I′m。其中I′m=[first(I′m)，Now]。定義u與v之間的綁定操作如下:

B(u→v)=(u-In)∪B(In→u)，同理:B(v→u)=(v-Im)∪B(I′m→u)

(2)含有時間變元的時態元素演算

含有時間變元的演算可以通過時態綁定操作，將u與v分別進行時態綁定，再進行操作。這樣u與v之間的時態元素演算可以表達如下:

u∩v=B(u→v)∩B(v→u)

u∪v=B(u→v)∪B(v→u)

u-v=B(u→v)-B(v→u)

2.3 LNbt中的演算問題

含有變元的LNbt之間的演算可以先對式(1)采取綁定操作BCTT(LNbt)，之后進行綁定后的LNBT演算。其形式化描述如下:

設LNbt1形式為((a1，∑k1i=1[c1.i，d1.i])，(a2，∑k2i=1[c2.i，d2.i])，…，(an，∑kni=1[cn.i，dn.i])，而LNbt2形式為((a′1，∑k′1i=1[c′1，i，d′1，i])，(a′2，∑k′2i=1[c′2，i，d′2，i])，…，(a′n，∑k′ni=1[c′n，i，d′n，i])，它們之間的運算如下:

LNbt1∪LNbt2={(a，∑ki=1[c，d])|(aj(a′k(aj=a′k)∧(∑ki=1[c，d]=∑kki=1[ck.i，dk.i]+∑kji=1[cj.i，dj.i])))∨(aj(a′k(aj≠a′k)∧(a=aj，∑ki=1[c，d]=∑kki=1[ck.i，dk.i])))∨(a′j(ak(a′j≠ak)∧(a=a′j，∑ki=1[c，d]=∑kki=1[ck.i，dk.i])))}

LNbt1∩LNbt2={(a，∑ki=1[c，d])|(aj(a′k(aj=a′k)∧(∑ki=1[c，d]=∑kki=1[ck.i，dk.i]∩∑kji=1[cj.i，dj.i])))}

LNbt1-LNbt2={(a，∑ki=1[c，d])|(aj(a′k(aj=a′k)∧(∑ki=1[c，d]=∑kki=1[ck.i，dk.i]-∑kji=1[cj.i，dj.i])))∨(aj(a′k(aj≠a′k)∧(a=aj，∑ki=1[c，d]=∑kki=1[ck.i，dk.i])))}

3 含有時間變元的雙時態關系代數運算

3.1 雙時態映射及其演算

令ξ∶u→(a1，a2，…，an)。其中u用規范的雙時態標簽的組合形式表達，如表達式[2]所示。在BCDM中，可以用雙時態映射表示雙時態元組。用ξ表示時態定義域，用|ξ|表示雙時態映射的值域，即ξ=u，而|ξ|=(a1，a2，…，an)。為了表述方便，用|ξ|Ai表示對應的雙時態映射值域中的第i屬性的屬性值，式中|ξ|Ai=ai。

定義3 雙時態元素的一致性。

設關系R1中含有ξ1∶LNbt1→(a1，a2，…，an)，關系R2含有關系ξ2∶LNbt2→(a′1，a′2，…，a′n)。其中LNbt1=(a1，∑v1)和LNbt2=(a2，∑v2)是規范的雙時態標簽組合形式。當滿足以下條件，則稱LNbt1和LNbt2是一致的。

若雙時態點(a1，b1)∈ LNbt1，且存在(a2，b2)∈LNbt2，使得(a1，b1)=(a2，b2)，均有(a1，a2，…，an)=(a′1，a′2，…，a′n) ，則此時稱LNbt1和LNbt2是雙時態元素一致的。

定義4 雙時態映射的演算。

雙時態映射ξ1和ξ2，它們是同關系模式下的映射，而且它們的映射值域是相同的，即|ξ1|=|ξ2|。定義ξ1和ξ2相關的演算，歸并()、交()、差(-)如下:

ξ1ξ2=ξ。其中ξ=ξ1∪ξ2，|ξ|=|ξ1|。ξ1ξ2=ξ 。其中ξ=ξ1∩ξ2，|ξ|=|ξ1|。

ξ1-ξ2=ξ。其中ξ=ξ1-ξ2，|ξ|=|ξ1|。

3.2 含有變元的雙時態關系代數運算

類似于文獻[2]，將含有變元的雙時態關系看成是雙時態映射的組合矩陣，它是雙時態映射的N×1矩陣。關系中的每個元組都是雙時態映射。

那么雙時態關系r可以表示為r=ξ1ξn 。其中ξi是BCDM中的含有變元的雙時態映射。相對定義雙時態關系的代數運算(分別為并、交、差、笛卡兒積、自然連接、投影和選擇運算)如下:

r1∪Btr2={ξ|(ξ1|∈r1，ξ2∈r2(|ξ2|=|ξ2|)∧ξ=ξ1ξ2)∨(ξ1∈r1∧(ξ2∈r2(|ξ1|≠|ξ2|))∧ξ=ξ1)∧(ξ2∈r2∧(ξ1∈r1(|ξ1|≠|ξ2|))∧ξ=ξ2)}

r1∩Btr2={ξ|(ξ1∈r1，ξ2∈r2(|ξ1|=|ξ2|)∧ξ=ξ1ξ2)}

r1-Btr2={ξ|(ξ1∈r1，ξ2∈r2(|ξ1|=|ξ2|)∧ξ=ξ1(-)ξ2)∨(ξ1∈r1，ξ2∈r2(|ξ1|≠|ξ2|))∧ξ=ξ1}

r1×Btr2={ξ|(ξ1∈r1，ξ2∈r2(ξ1∩ξ2≠))∧(|ξ|=(|ξ1|，|ξ2|)，ξ=ξ1∩ξ2)}r1∞Btr2={ξ|ξ1∈r1，ξ2∈r2(ξ1∩ξ2≠∧Ai∈X，|ξ1|Ai=|ξ2|Ai)

∧(|ξ|=(|ξ1|R-X，|ξ1|X，|ξ2|S-X)，ξ=ξ1∩ξ2)}

∏BtX(r)=∪Bt(∏x(r))

σBtp∧Q(r)={ξ||ξ|=σp∧q(|ξ1|)}

定理2 基于BCDM的含有時間變元的雙時態關系運算是封閉的。

定理是指:對于任意的雙時態關系r1和r2 。r1和r2 在雙時態并、交、差、笛卡兒積、自然連接、投影和選擇的運算下(并、交、差運算需要同關系模式)，所得到的關系仍是雙時態關系。

定理的證明較為顯然:同關系模式間的并、交、差運算不改變關系模式，只是可能改變元組的個數和雙時態標簽，其結果當然是雙時態關系;笛卡兒積和自然連接只是增加了關系的屬性數目，改變了時態標簽的時間點集合，但其結果還是雙時態關系的形式;投影和選擇運算更是顯然不會改變雙時態關系，因為它們是單關系內的運算。

4 結束語

本文從BCDM模型的雙時態性出發，對BCDM中的時間標簽進行了規范的組合表達，給出時間元素之間的演算描述;在此基礎上，定義了BCDM中的時態元組和時態關系，并給出了BCDM中含有變元的時態關系代數的運算問題，證明了關系代數運算的封閉性。對于BCDM中時態關系問題，還可以將時間變元Now和UC綁定到過去和將來時間來構造關系代數運算。但是，對于變元綁定到過去的情況來說，因為BCDM自身的雙時態特性，會造成一些時態信息的丟失甚至是錯誤。而將時間變元綁定到將來的情況，這給BCDM模型的時間變元綁定增加了一種在概率值意義下的不確定性，相關的工作筆者正在研究。時態數據庫的實際模型TimeDB2.0beta4對于雙時態的支持已經更改，新的版本對于事務時間已不再支持，而在本實驗的時態中間件的設計中，一方面要考慮到雙時態性的支持，另一方面對于時間變元Now和UC的當前更新和綁定的關系運算也是設計時需考慮的另一重要因素，適當的辦法可以在設計時增加中間件來實現具體的綁定。

參考文獻:

[1]湯庸， 湯娜， 葉小平. 時態信息處理技術研究綜述[J].中山大學學報:自然科學版，2003，42(4):5-9.

[2]王路幫，湯庸，余陽.基于BCDM的雙時態關系代數[J].計算機研究與發展，2004，41(11):1949-1953.

[3]王路幫，湯庸. 基于BCDM的冗余時間變元綁定[J].計算機應用研究，2007，24(2):33-36.

[4]王路幫. 時態數據庫中的時間變元及其綁定[J].浙江大學學報:理學版，2006，33(6):662-666.

[5]TORP K， JENSEN C S， SNODGRASS R T. Modification semantics in now-relative databases[EB/OL].(2000-04).http://www.cs.auc.dk/~csj/Thesis/.

[6]CLIFFOR J， DYRESON C， ISAKOWITZ T， et al. On the semantics of “now” in database[J]. ACM Trans on Database Systems，1997，22(2):171-214.

[7]CLIFFORD J， DYRESON C E， SNODGRASS R T，et al.Now[EB/OL].(2000-04).http://www.cs.auc.dk/~csj/Thesis/.

[8]王路幫，葉小平，邢鴻雁，等. 時態變元Now的綁定算法[J]. 中山大學學報:自然科學版，2004，43(S1):152-154.

[9]CLIFFORD J， CROKER A. The historical relational data model (HRDM) and algebra based on lifespans[C]//Proc of the 3rd Inter-national Conference on Data Engineering. Washington DC: IEEE Computer Society，1987:528-537.

[10]TUZHILIN A， CLIFFORD J.A temporal relational algebra as a basis for temporal relational completeness[C]//Proc of the 16th International Conference on Very Large DataBase. San Francisco CA: Morgan Kaufmann Publishers Inc，1990:13-23.

[11]張師超. 一個模糊的時態關系代數[J]. 軟件學報，1994，5(9):59-64.

[12]ORGUN M A. A temporal algebra with recursive equations[R]. Sydney:Department of Computing， Macquarie University， 1995.

[13]葉小平，湯庸. 時態變元“Now”語義及相應的時態關系代數[J]. 軟件學報，2005，16(5):838-845.

[14]DEY D， BARRON T M， STOREY V C.A complete temporal relational algebra[J].The VLDB Journal，1996，5(3):167-180.

[15]JENSEN C S. Temporal database management[EB/OL].(2000-04).http://www.cs.auc.dk/~csj/Thesis/.

[16]LEE J Y，ELMASRI R A . A temporal algebra for an ER-based temporal data model[C]//Proc of the 17th International Conference on Data Engineering.Washington DC:IEEE Computer Society，2001:33-40.

[17]STEPHANE L P， DIDIER B， ANDRZEJ D. TAO:temporal algebraic operator for modeling nultimedia presentations[J].Journal of Network and Computer Applications，2002，25(4):319-342.

[18]JET W， ALEXIS B. On query optimization in a temporal SPC algebra[J]. Data and Knowledge Engineering，2003，44(2):165-192.

[19]胡廣朋，邵玉寶，程輝. 基于區間矩陣的時態關系的簡化方法[J]. 江蘇科技大學學報:自然科學版，2008，22(2):63-66.

[20]鄧立國，馬宗民. 一個模糊時態數據庫關系代數理論[J]. 東北大學學報，2008，29(10):1414-1418.