0 引言
　　
　　多粒度时态数据库中由于多粒度时间维的引入,使得其规范化设计极其复杂。如何为多粒度时态数据库设计行之有效的规范化方法,是近年来时态数据库理论研究人员致力研究的方向。在时态数据库的规范化研究过程中,Jensen等人[1]、Wang等人[2]、Wijsen[3,4]以及Combi等人[5]提出了各自的时态数据依赖概念。其中Wang和Combi等人提出的时态函数依赖能够处理多时间粒度。时态范式在时态数据库的规范化设计中起着重要的作用。在时态数据库设计的研究领域中,已经提出的一些时态数据库的范式有Segev的1TNF、Navathe的TNF、Lorentzos的P和Q范式、Jensen等人的T3NF和TBCNF[1]、Wang等人的T3NF和TBCNF[2]。其中,Segev的1TNF、Navathe的TNF、Lorentzos的P和Q范式都是针对特定的时态数据模型,而且它们都偏离了传统的关系数据库范式,不是传统范式真正意义上的扩展;Jensen等人的T3NF和TBCNF是对传统范式的扩展,但只考虑了时态关系快照中的数据冗余,没有考虑快照间的数据冗余,而且没有考虑多时间粒度的问题;Wang等人的T3NF和TBCNF是对Jensen等人工作的扩展,考虑了快照间的数据冗余,而且考虑了多时间粒度的问题,但是,由于多时间粒度的引入以及时态类型间的复杂操作,使得其分解算法相当复杂,难以用其进行有效的时态数据库设计。根据多粒度时态数据库中所涉及的时态类型之间是否存在细于关系,可以将多粒度时态数据库的规范化设计研究划分为全序时态数据库的规范化设计研究与偏序时态数据库的规范化设计研究。国内郝忠孝教授等人[6,7]对全序时态模式中的模式分解问题进行了讨论,对强全序时态模式中的多值依赖问题[8]进行了相关研究。
　　本文针对偏序时态模式的分解问题进行了相关研究,提出了偏序时态模块模式、偏序TFD集的模式投影、偏序时态模块投影和偏序时态BC范式(PO_TBCNF)等概念,并给出了避免时态类型间复杂操作的偏序时态BC范式的分解算法,对其正确性、可终止性进行了证明,并对算法的时间复杂度进行了分析。
　　
　　1 基本概念
　　
　　有关时态类型、细于关系、集细于关系、时态模块模式与时态模块、时态候选关键字、时态函数依赖(TFD)和TFD导出等概念的定义以及TFD推导公理、TFD有限推导公理的描述均参见文献[2]。
　　定义1 偏序时态类型集。给定时态类型集T = {μ1, μ2, …, μn},若其中存在两个μi,μj(1≤i≤j≤n),有μiμj不成立且μjμi不成立,则称T是偏序时态类型集。
　　定义2 严格偏序时态类型集。给定时态类型集T = {μ1, μ2, …, μn},如果其中存在时态类型μi,使得 μiμj不成立,且μj≤μi不成立,1≤j≤n,j ≠ i,则称T是严格偏序时态类型集。
　　定义3 非严格偏序时态类型集。给定偏序时态类型集T={μ1, μ2, …, μn},如果其中存在时态类型μi,使得 μic{μ1, μ2, …, μi-1, μi+1, …, μn}成立,1≤i≤n,则称T是非严格偏序时态类型集。
　　定义4 最大下限。给定非严格偏序时态类型集T = {μ1, μ2, …, μn},设T1为T的子集,则T1在T中的最大下限为μi,μicT1且不存在μj,使得μiμj,μjcT1(1≤i, j≤n)记为gll(T1, T) = μi。
　　定义5 TFD集的时态类型集[6]。F是一个TFD集,则F的时态类型集T={ν|存在TFD X→νY∈F},也称F具有时态类型集T。
　　定义6 偏序TFD集。设F为一TFD集,如果F的时态类型集T为偏序时态类型集,则称F为偏序TFD集。
　　 　　定理1 设M= (R, μ,)为一时态模块,则对于任一TFD X→νY,XYR且μ与ν为偏序关系,X→νY在M上不成立。
　　证明 根据TFD的定义,如果一个TFD X→νY在M= (R, μ,)上成立,意味着在被ν的同一时刻j1覆盖的μ的任意两个时刻i1,i2上存在的两个元组t1=(i1),t2=(i2),若有t1[X]=t2[X],则有t1[Y] = t2[Y]。但因为μ与ν为偏序关系,在μ中必存在某时刻i,μ(i)ν(j),j为ν中任意时刻,所以无法判断TFD X→νY在有关μ(i)的元组上能否成立,即无法证明TFD X→νY是否能在M上成立。证毕。
　　根据定理1,在一个时态模块(R, μ,)上,对于任一TFDX→νY,XYR且μ与ν为偏序关系,都无法论证X→νY在M上的满足性,因此只有当XYR且μγ,TFD X→γY才有可能被M所满足。由此得出偏序时态模块模式定义如下:
　　定义7 偏序时态模块模式。一个时态模块模式(R, μ),如果(R, μ)上成立的TFD集F为偏序TFD集,且对于任一TFD X→νY∈F,有μν(即μ与F的时态类型集T构成一个非严格偏序时态类型集),则称(R, μ)是偏序时态模块模式。一个偏序时态模块是一个三元组(R, μ,)。其中:(R, μ)为偏序时态模块模式;是一个时间窗口函数,即从N(正整数)到2Tup(R)的映射(Tup(R)为全部元组的集合),使得对每个i≥1,如果μ(i)=,则(i)=。
　　定义8 偏序TFD集的模式投影。给定时态模块模式(R, μ)和偏序TFD集F,则F到模式(R, μ)上的投影记做π(R,μ)(F),定义为:π(R,μ)(F)={X→νY∣F├f X→νY,XYR且μν,或μ与ν为偏序关系,ν∈{μ∪T}(T为F的时态类型集)｝。
　　对于X→γY∈F,XYR且μ与γ为偏序关系,X→γY在时态模块(R, μ,)上将不再成立。
　　定义9偏序时态模块投影。偏序时态模块M=(R, μ, ), R1R,μν,则M 在(R1, ν)上的投影π(R1,ν)(M)=(R1, ν,1),对任意i≥0,1 (i)=∪j:μ(j)ν(i)πR1((j))。其中:π为传统关系数据库中的投影操作;及1分别为M及π(R1,ν)(M)的时间窗口函数。
　　
　　2 偏序时态BC范式
　　
　　Wang等人[2]指出,由于文中的TBCNF分解算法是基于Ullman在1988年提出的复杂度为指数级的BCNF分解算法,其TBCNF分解算法的复杂度也是指数级的。并且由于算法中涉及时态类型间的复杂计算而使之难以理解,更难以运用到实际的时态数据库设计中,本文针对偏序时态模块模式提出了偏序时态BC范式的概念,并给出了它的一个满足无损连接性的模式分解算法,其算法复杂度为多项式级的。
　　定义10 偏序时态BC范式(PO_TBCNF)。对于偏序TFD集F约束的偏序时态模块模式(R, μ),T为F的时态类型集,如果对于F中的每个TFD X→νA,XAR,AX,以下条件成立:X是(R, μ)的时态超候选关键字,且μ=ν,则称(R, μ)是属于偏序时态BC范式(PO_TBCNF)的。
　　定义11 时态模块在时态类型上的展开模块。设M=(R, μ,),γμ,Mγ= (R, γ,γ),对每个i≥1, j≥1,γ(j) μ(i),有γ(j) =(i),称Mγ为M在时态类型γ上的展开模块。
　　定义12 偏序时态自然连接。设M1=(R1, μ,1),M2=(R2, ν,2)。其中:μ,ν∈T(T为非严格偏序时态类型集)。M1和M2的偏序时态自然连接M1  PO_T M2,是时态模块M = (R1∪R2, γ,),其中,γ=gll({μ, ν}, T),对每个i≥1,有(i) =1γ(i) 2γ(i)。其中:为传统的自然连接操作;1γ、2γ分别为M1和M2在γ上展开模块的时间窗口函数。
　　定义13 偏序时态模块模式分解。偏序时态模块模式(R, μ)的分解是一个时态模块模式集合ρ= {(R1, μ1), …, (Rk, μk)},满足:
　　a)R= R1∪…∪Rk。
　　b){μ, μ1, …, μk}为一偏序时态类型集,且μμi,i= 1, …, k。
　　与传统的关系模式分解类似,在对偏序时态模块模式进行分解从而得到一个性能较好的偏序时态数据库模式设计时,必须考虑所产生的分解与原偏序时态模块模式的等价性问题。如果偏序时态模块模式的一个分解与原偏序时态模块模式等价,则在原偏序时态模块模式下的任一满足原模式中全部TFDs的时态模块在分解之后应能通过偏序时态自然连接运算恢复出来,这一特性被称做偏序分解的连接无损性。
　　定义14 偏序无损分解。设(R, μ)为一偏序时态模块模式,F为偏序TFDs集。如果对(R, μ)上的每个满足F中全部TFDs的时态模块M,有M=π(R1,μ1)(M) PO_T …PO_Tπ(Rk,μk)(M),称(R, μ)关于F的一个分解ρ= {(R1, μ1), …, (Rk, μk)}为偏序无损分解。
　　定义15 偏序时刻无损分解。设(R, μ)为一偏序时态模块模式,F为偏序TFDs集。如果对μ的每个非空时刻T≥1,(T) =1μ(T)… kμ(T)成立,则称(R, μ)关于F的一个分解ρ= { (R1, μ1),…,(Rk, μk)}为偏序时刻无损分解。为(R, μ)的时间窗口函数,1μ,…,φkμ分别为(R1, μ1),…,(Rk, μk)在μ上展开模块的时间窗口函数。
　　定理2 设(R, μ)为一偏序时态模块模式,F为偏序TFDs集,ρ为(R, μ)关于F的一个分解,则ρ为(R, μ)关于F的一个偏序无损分解,当且仅当它是(R, μ)关于F的一个偏序时刻无损分解。
　　证明 充分性。设M = (R, μ,)为一满足F的偏序时态模块,ρ= {(R1, μ1),…,(Rk, μk)} 为(R, μ)关于F的一个偏序时刻无损分解。对每个1≤i≤k,设Mi =π(Ri,μi)(M)= (Ri, μi,i),∪ki=1Ri =R。设M′ = M1 PO_T … PO_T Mk =(∪ki=1Ri, ν,′) = (R, ν,′),因为ρ为(R, μ)关于F的一个偏序时刻无损分解,所以对于μ的每个非空时刻T≥1,(T)=1μ(T) … kμ(T)。由定义12可知,即为′ 而ν=μ,因此M = M′ = M1 PO_T … PO_T Mk,即ρ为(R, μ)关于F的一个偏序无损分解。
　　 　　必要性。设ρ= {(R1, μ1),…,(Rk, μk)} 为(R, μ)关于F的一个偏序无损分解,M=(R, μ,)为一个满足F的偏序时态模块。对每个1≤i≤k,设Mi =π(Ri,μi)(M)= (Ri, μi,i),∪ki=1Ri =R。由ρ为(R, μ)关于F的一个偏序无损分解可知,M=M1 PO_T … PO_T Mk;再根据定义12可知,对于μ的每个非空时刻T,(T) =1μ(T) …kμ(T)。即ρ为(R, μ)关于F的一个偏序时刻无损分解。证毕。
　　定理3 给定偏序时态模块模式(R1∪R2, μ),F为其上成立的偏序TFD集,如果F中存在R1∩R2→νR2,则(R1∪R2, μ)的分解ρ= {(R1, μ),(R2, ν)} (μν)关于F是偏序无损的。
　　证明 设M= (R1∪R2, μ,)为一满足F中全部TFDs的偏序时态模块,π(R1,μ)(M)= (R1, μ,1),π(R2,ν)(M) = (R2, ν,2) 分别为M在(R1, μ)、(R2, ν)上的偏序时态模块投影。只需证明对于μ的每个非空时刻T≥1,(T)=1μ(T) 2μ(T),1μ,2μ分别为(R1, μ),(R2, ν)在μ上的展开模块的时间窗口函数。然后根据定义15即可知ρ= {(R1, μ),(R2, ν)}为一偏序时刻无损分解,再根据定理2可证明它是(R1∪R2, μ)关于F的一个偏序无损分解。
　　设元组t∈(T),由定义9可知t[R1]∈1(T),t[R2]∈2(T′),μ(T) ν(T′);由定义11知t[R1]∈1μ(T),t[R2]∈2μ(T),则由自然连接的定义可知t∈1μ(T) 2μ(T),因此(T) 1μ(T) 2μ(T)。
　　设元组t∈1μ(T) 2μ(T),则在1μ(T)和2μ(T)中分别存在t1和t2使得t[R1] = t1,t[R2] = t2。由定义11知,在1(T)和2(T′)中必存在t1和t2使得t[R1] = t1,t[R2] = t2。再由定义9知,在(T)中存在t1′使得t1′[R1] = t1,且存在T′′使(T′′)中有t2′使得t2′[R2] = t2,μ(T,T′′) ν(T′)。由R1∩R2 R1,R1∩R2 R2可知,t1′[R1∩R2] = t1[R1∩R2] =t[R1∩R2] = t2[R1∩R2] = t2′[R1∩R2]。因为R1∩R2→νR2,μ(T,T′′) ν(T′),t1′∈(T),t2′∈(T′′),可得t1′[R2] = t2′[R2]。再由t[R1] = t1= t1′[R1],t[R2]= t2 = t2′[R2] = t1′[R2]可知,t[R1∪R2] = t1′[R1∪R2],即t = t1′,所认t∈(T),1μ(T) 2μ(T) (T)。证毕。
　　算法1 PO_TBCNF_DECIDING(PO_TBCNF判定算法)
　　输入:偏序时态模块模式(R, μ),(R, μ)上成立的偏序TFD集F。
　　输出:若(R, μ)属于PO_TBCNF,则输出true,否则输出false。
　　PO_TBCNF _DECIDING(R, μ,F)
　　TK := Temporal—Candidate—keys(R, μ, F);
　　for 每一个TFD:X→νY∈F and Test do
　　if μ≠ν then [Test :=false; Violate_TFD := X→νY;]
　　for 每一个TFD:X→νY∈F and Test do
　　[Flag :=false;
　　for 每一个 K∈TK do
　　 if KX then Flag:=true;
　　 if not Flag then [Test:=false;
　　Violate_TFD:= X→νY;]]
　　return(Test);
　　end.
　　定理4算法PO_TBCNF_DECIDING能正确判定偏序时态模块模式(R, μ)是否属于偏序时态BC范式,并且是可终止的,其时间复杂度为O(n2p+pq+q2)。其中:n为全部时态候选关键字的个数;p为F中TFD的个数;q为R中的属性个数。
　　证明 正确性。算法1中用到的算法Temporal—Candidate—keys[7]能正确求出(R, μ)的时态候选关键字集。算法1根据偏序时态BC范式的定义,对于F中的每一个TFD,先测试它的时态类型是否与偏序时态模块模式(R, μ)的时态类型一致,再测试它的左部是否包含时态候选关键字,只有全部条件都满足时,才判定为偏序时态BC范式,故算法是正确的。
　　终止性。由于算法Temporal—Candidate—keys是可终止的,并且F中TFD的个数和(R, μ)中时态候选关键字的个数都是有限的,故算法中的for循环可终止。
　　时间复杂度。算法Temporal—Candidate—keys的时间复杂度为O(n2p+ pq+q2),算法1中第一个for循环的时间复杂度为O(p),第二个for循环的时间复杂度为O(np),故算法总的时间复杂度为O(n2p+pq+q2)。
　　
　　3 偏序时态BC范式分解方法
　　
　　在一个偏序时态模块模式(R, μ)向偏序时态BC范式分解的过程中,由于其上成立的TFD集F为偏序TFD集,当根据其子模式(Ri, μi)中使其违反PO_TBCNF条件的TFD X→vY来分解得到两个子模式(Ri-Y, μi) 和(XY, ν)时,如果有Z→γW∈π(XY, ν) (F),ZWXY且ν与γ为偏序关系,则TFD Z→γW在分解后得到的子模式(XY, ν)上不能够继续成立,因而无法消除子模式(XY, ν)中由TFD Z→γW引起的时态冗余,称这一类时态冗余为偏序时态冗余。为了消除偏序时态冗余,需首先根据子模式(Ri, μi)中的TFD Z→γW来分解得到两个子模式(Ri-W, μi) 和(ZW, γ),然后再继续分解。寻找造成偏序时态冗余的TFD的算法如下。
　　算法2 TFD_FIND(查找造成偏序时态冗余的TFD)
　　输入:偏序时态模块模式(R, μ)上成立的偏序TFD集F,F中的一个TFD X→νY。
　　 　　输出:造成偏序时态冗余的TFD。
　　TFD_FIND(F, X→νY)
　　while 存在TFD Zi→γiWi∈π(R1, type) (F) 且γi与type
　　为偏序关系do
　　[R1:=ZiWi;
　　type:=γi;
　　i:= i+1;]
　　 if i≠0 then result :=Zi-1→γi-1Wi-1;
　　 return(result);
　　end.
　　定理5 算法TFD_FIND能够正确求得在偏序时态模块模式(R, μ)向(XY, ν)子模块上进行分解时,造成(XY, ν)子模块中存在偏序时态冗余的TFD,并且是可终止的,其时间复杂度为O(pq)。其中p和q的含义同算法1。
　　证明 正确性。 算法2在while循环语句的第一次循环中,查找是否存在TFD Z0→γ0W0∈π(XY, ν) (F) 且γ0与ν为偏序关系。如果存在,则此TFD必定会造成子模块(XY, ν)中的偏序时态冗余,但如果按照此TFD Z0→γ0W0向(Z0 W0, γ0)子模块上进行分解,一旦存在TFD Z1→γ1W1∈π(Z0 W0, γ0) (F) 且γ0与γ1为偏序关系,则TFD Z1→γ1W1还会造成子模块(Z0 W0, γ0)中的偏序时态冗余,依此类推。算法2在最终再也找不到会造成下一级偏序时态冗余的TFD的情况下退出while循环,此时得到的TFD Zi-1→γi-1Wi-1即为造成最终的偏序时态冗余的TFD。
　　终止性。由于(R, μ)中属性个数与F中TFD的个数是有限的,while语句的循环次数是有限的,算法是可终止的。
　　算法时间复杂度。设p为F中TFD的个数,q为R中的属性个数,而算法中while循环的时间复杂度为O(pq),因此算法总的时间复杂为O(pq)。
　　由此得到偏序时态BC范式分解方法如下:
　　算法3 PO_TBCNF(偏序时态BC范式分解算法)
　　输入:偏序时态模块模式(R, μ),(R, μ)上成立的偏序TFD集F。
　　输出:满足偏序连接无损性的PO_TBCNF数据库模式ρPO_BC。
　　PO_TBCNF(R, μ,F)
　　begin
　　ρNBC := {(R, μ)};
　　ρPO_BC :=;
　　for ρNBC中每一个子模式(Ri, μi) do
　　[if PO_TBCNF_DECIDING(Ri, μi , π(Ri,μi)(F))
　　then ρPO_BC :=ρPO_BC∪(Ri, μi);
　　else [ redun_TFD := TFD_FIND(F, Violate_TFD); { Violate_TFD 为PO_TBCNF_DECIDING 算法中求得的使(Ri, μi)违反PO_TBCNF 条件的TFD }
　　X:= redun_TFD的左部;
　　Y:= redun_TFD的右部;
　　ν:= redun_TFD的时态类型;
　　ρNBC := ρNBC-(Ri, μi)∪{(Ri-Y, μi), (XY, ν) };]]
　　 return(ρPO_BC);
　　end.
　　定理6 算法PO_TBCNF正确求得了偏序时态模块模式(R, μ)关于偏序TFDs集F的一个满足偏序无损连接的PO_TBCNF的分解ρPO_BC,并且是可终止的。其时间复杂度为O(mn2p+mpq+mq2)。其中:n、p和q的含义同算法1;m为(R, μ)的满足PO_TBCNF分解的子模式个数。
　　证明 终止性。由于(R, μ)中属性个数与时态类型数目是有限的,(R, μ)的子模式的个数是有限的,并且由定理4知算法PO_TBCNF_DECIDING是正确的,故算法是可终止的。
　　正确性。a)PO_TBCNF满足性。算法在for循环中,对每一个不属于PO_TBCNF的子模式都进行再次分解,直至所有的子模式都属于PO_TBCNF为止,因此结果返回的ρPO_BC中的子模式必定都属于PO_TBCNF,并且由于算法中考虑了分解过程中可能产生的偏序时态冗余,使得最终的分解更优化。b)偏序无损连接性。算法中对于(R, μ)的每一次分解,都是根据其子模式(Ri, μi)中使其违反PO_TBCNF条件并且会造成偏序时态冗余的TFD X→νY来分解的,分解后的两个子模式为(Ri-Y, μi) 和(XY, ν),根据定理3,分解一定满足偏序无损连接性。
　　算法时间复杂度。设(R, μ)满足PO_TBCNF分解的子模式个数为m,由于算法PO_TBCNF_DECIDING的时间复杂度为O(n2p+pq+q2),算法TFD_FIND的时间复杂度为O(pq),算法总的时间复杂为O(mn2p+mpq+mq2 )。
　　
　　4 结束语
　　
　　时间粒度是所有时态数据所拥有的共同特点。已经提出的基于多时间粒度时态函数依赖的范式分解算法相当复杂,在实际应用中难以用其进行有效的时态数据库设计。这种复杂性在很大程度上是由偏序时态类型间的复杂运算引起的。本文针对偏序时态数据库进行研究,提出了非严格偏序时态类型集、偏序时态模块模式、偏序TFD集的模式投影、偏序时态模块投影和偏序时态BC范式(PO_TBCNF)等概念,并给出了避免时态类型间复杂操作的偏序时态BC范式的分解算法,对其正确性、可终止性进行了证明,并对算法的时间复杂度进行了分析。下一步的主要工作是涉及时态多值依赖的偏序时态模块模式的规范化研究。
　　
　　参考文献:
　　[1]JENSEN C S, SNODGRASS R T, SOO M D. Extending existing dependency theory to temporal databases[J]. IEEE Trans on Know-ledge and Data Engineering, 1996, 8(4):563-582.
　　[2]WANG X S, BETTINI C, JAJODIA S. Logical design for temporal databases with multiple granularities[J]. ACM Trans on Database System, 1997, 22(2):115-170.
　　[3]WIJSEN J. Design of temporal relational databases based dynamic and temporal functional dependencies[C]// Proc of International Workshop on Recent Advances in Temporal Databases. New York:Sprin-ger-Verlag, 1995: 61-76.
　　[4]WIJSEN J. Temporal FDs on complex objects[J]. ACM Trans on Database System, 1999, 24(1):127-176.
　　[5]COMBI C, ROSSATO R. Temporal functional dependencies with multiple granularities: a logic based approach[C]//Proc of the 15th International Conference on Database and Expert Systems Applications. Berlin:Springer, 2004: 864-873.
　　[6]姚春龙,郝忠孝.具有全序时态类型集时态函数依赖集的研究[J].软件学报,2003,14(2):247-252.
　　[7]万静,郝忠孝.全序时态模块模式的TO_TSNF分解问题研究[J].计算机科学,2007,34(3):114-119.
　　[8]万静,郝忠孝.具有多时间粒度的强全序时态模式中多值依赖问题研究[J].计算机研究与发展,2008,45(6): 1064-1072.