偏序环境下时态数据库中的TBCNF分解问题研究

减小字体 增大字体 作者:万 静 郝忠孝  来源:www.zhonghualunwen.com  发布时间:2009-10-12 23:33:08

  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)的时间窗口函数。

[1] [2] [3] [4]  下一页

Tags:

作者:万 静 郝忠孝
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论