（计算机软件与理论专业论文）近似技术在时态计数及求和聚集计算中的应用.pdf

哈尔滨- i = 程大学硕士学位论文 摘要 时态数据库是对传统关系型数据库的扩展，因此时态数据库对时态聚集 查询的支持是非常重要的。由于时态聚集查询在数据仓库应用中的重要性， 时态聚集查询已经成为时态数据库技术中的研究热点之一 现有的时态聚集算法存在着查询内存空间需要较大、处理开销较高、基 于复杂的数据结构( 不能适用于现有的商业产品中) 等缺点。基于这些缺点， 本文提出了两种基于有限误差近似技术的改进算法。第一种是基于多版本b 树的改进算法，针对查询内存空间占用大和时间开销大的缺点，由于引入了 近似技术，该算法的空间开销大大减少，因此在最坏情况下的查询开销为对 数级，但该算法并没有解决基于复杂的数据结构，因此并不适合在商业产品 中实现；第二种算法采用b 树和r 树相结合的算法，针对现有算法查询内存 空间需要较大、处理开销较高、特别是基于复杂的数据结构的缺点，采用现 代广泛应用于商业产品中的数据结构b 树和r 树，并结合近似技术来解决这 个问题。该算法查询开销也可以达到对数级，因此在现代商业产品中实现的 可能性大大提升。 本文对于以上两种算法的结果，分别进行了理论证明和实验证明，结果 表明这两种算法的确在空间开销上有了数量级上的优化，并且其时间复杂度 达在很大程度上得到了提高。以往用户对于历史数据的检索都是基于精确查 询的，但是事实上并不需要那么精确，有时仅仅是想了解一个趋势，因此近 似技术的应用使用户能够高效的查询历史数据，了解趋势的发展，以便制定 发展方向。 关键词：时态数据库；时态聚集；m v b 树；b 树；& 树 哈尔滨工程大学硕士学位论文 i v a b s t r a c t t e m p o r a ld a t a b a s es y s t e mi se x t e n d e df r o mt r a d i t i o n a lr e l a t i o n a ld a t a b a s e s y s t e m , t h e r e f o r e , t h et e m p o r a l d a t a b a s es y s t e ms h o u l d s u p p o r tt e m p o r a l a g g r e g a t i o n f o ri t si n c r e a s i n gi m p o r t a n c ei nt h ed a t aw a r e h o u s ea p p l i c a t i o n s ， t e m p o r a la g g r e g a t i o nq u e r yh a sb 0 m eo n eo ft h em o s ti m p o r t a n tf i e l d so ft h e t e m p o r a ld a t a b a s er e s e a r c h c u r r e n tt e m p o r a la g g r e g a t i o na p p r o a c h e sh a v ea tl e a s to n eo ft h ef o l l o w i n g s o m es h o r t c o m i n g sw h i c ha 托l a r g es p a c er e q u i r e m e n t s ，h i g hp r o c e s s i n gc o s ta n d b a s i n go i lc o m p l e xd a t as t r u c t u r e s w h i c h 日i en o ta v a i l a b l e i nc o m m e r c i a l p r o d u c t s i nt h i sp a p e r , a i m i n ga tt h e s es h o r t c o m i n g so fc u r r e n tt e m p o m i a g g r e g a t i o na l g o r i t h m s ，t w oi m p r o v e da l g o r i t h m sb 曲i n g o na p p r o x i m a t i o n t e c h n i q u e sw i t hb o u n d e de r r o r a r ep r o p o s e d 1 1 bf i r s to n eu s e st h em u l t i - v e r s i o n s b t r o et os o l v et h ep r o b l e m sa b o u tl l i g hl e v e ls i z ec o n s u m e s i n c et h ea p p l i c a t i o n o f a p p r o x i m a t et e c h n o l o g y , t h i sa l g o r i t h m sh a sl o g a r i t h m i cw o r s t - c a s eq u e r yc o s t b u tt h ep r o b l e mi st h i sm e t h o di sa l s ob a s i n go nc o m p l e xd a t a 硎n l c 嘶t h e r e f o r e i ti si m p o s s i b l et oi m p l e m e n ti nc o m m e r c i a lp r o d u c t s t os o l v et h ed i s a d v a n t a g e s i nc u r r e n tt e m p o r a la g g r e g a t i o n , e s p e c i a l l yt os o l v et h es h o r t c o m i n ga b o u tb a s i n g o nc o m p l e xd a t as t r u c t u r e ，t h es e c o n da l g o r i t h mm e r g e sb t r e ea n dr - t r e e ，t h e s e t w od a ms t r u c t u r e sa r ew i d e l yu s e di nc u r r e n tc o m m e r c i a lp r o d u c t sa n dt h e a l g o r i t h mh a sa c h i e v e dt h e 黜p e r f o r m a n c ei nt h ee x p e n d 1 f 1 地h m e rh a s o v e r c o m et h em o s ts h o r t c o m i n g so ft h ec u r r e n tt e m p o r a la g g r e g a t i o na l g o r i t h m s t h e r e b yi ti se a s yt oi m p l e m e n ti nc o m m e r c i a lp r o d u c t s ， t h e o r i e sa n de x p e r i m e n ta p p r o a c h e sa r eu s e di no r d e rt op r o v et h ev a l i d i t i e s o f t h et w om e t h o d s 1 1 ”s i z ec o i i s u m eo f t h et w op r o p o s e dm e t h o d s i nt h i sp a p e r , a r ed e c r e a s e dm o r et h a na no r d e ro fm a g n i t u d ea n dq u e r yc o s to ft h e mi sg r e a t l y o p t i m i z e d i nt h ep a s t u s 日sr e t r i e v e dd a mw a sb a s e do ne x a c tq u e r y i nf a c t , w h a t t h eu s e r sn e e dw a so n l yau e n dn o ta ne x a c tn u m b e r , t h e r e b yt h ea p p l i c a t i o no f 哈尔滨工程大学硕士学位论文 a p p r o x i m a t et e c h n o l o g y 锄m a k eu s e f sr e n i e v eh i s t o r i c a ld a t am o r ce f f i c i e n t l y a n dk n o wt h ed e v e l o p m e n to ft h et r e n d , t h r o u g hw h i c hu s e r sc 8 nd e c i d et h e d i r e c t i o no f t h e i rd e v e l o p m e n t k e y w o r d s ：t e m p o r a ld a t a b a s e ；t e m p o r a la g g r e g a t i o n ；m v b - t r e e ；b - t r e e ； r - t r e e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体己 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 步衣勇 日期：司年 月fe t i 哈尔滨丁程大学硕士学位论文 1 1 引言 第1 章绪论 现实世界是四维的，真实事件无不具有时间属性。例如，物理流信息都 包含着事件时态信息( t e m p o r a li n f o r m a t i o n ) ，其中有即时信息( i n s t a n t ) 、 时间间隔( i n t e r v a l ) 信息，以及相对时间信息等。从2 0 世纪7 0 年代开始， 关系数据库由于其卓越的性能而变得非常流行。然而，现今几乎所有的关系 数据库没有对随时间变化而变化的信息进行特殊处理，具有时间属性的数据 在关系数据库中和普通数据一样对待，这远远不能满足能处理过去、现在以 及将来的应用需求“t 。 如果用传统的关系数据库模型来管理时态数据，则大量对时间信息的处 理将转移给开发软件开发人员，并且针对不同的实际应用，软件开发人员必 须用结构化查询语言( s q l ) 编写不同的时间信息处理代码，这样不仅会降 低软件开发效率，而且会增加程序出错的可能性。因此，提出新的时态数据 模型变得十分迫切，而出发点就是从数据库系统本身来解决这个问题。传统 的数据库系统( 层次、网状和关系数据库) 对时态数据信息并没有作为特殊 数据信息来考虑，而仅仅把时态数据信息当作一个时间值来存储和管理n ，。因 此，在传统关系数据库中元组的时间信息仅仅只能反映当前该元组( 即上一 次更新之后) 的状态，并没有考虑到元组本身的过去与未来发生的变化。也 正是因为数据库广泛的应用与各种行业的软件开发，因此对传统的关系型数 据库提出了两个方面的要求“1 ：( 1 ) 管理事件的时态信息；( 2 ) 管理数据库系 统元事件时态信息。 事件时态信息包括自然灾害( 地震、气象、水文、洪涝等) 有关的历史 资料，人事、财务、金融方面的历史资料等等。这些数据反映了事物发生发 展的过程，有助于揭示事物发生发展的本质规律。 元事件时态信息包括事务处理时刻、时间区间、多用户系统中对封锁解 哈尔滨工程大学硕士学位论文 锁的申请，排队、协调资源竞争的时间戳标记等等。这些数据有助于提高数 据库系统的功能和效率。现今大多数的关系数据库系统中对历史信息的处理 所采用的算法是：将多个数据库快照放在一起从而反映历史信息。但是这样 会对信息的管理造成极大的困难，其主要表现方面有以下三个方面n 1 。 ( 1 ) 取多大的时间间隔保存快照。如果时间间隔太大，则不足保证数据 的准确详实，如果间隔太小，则数据冗余大，浪费存储空间； ( 2 ) 一个表的快照不能简单地同时存入内存。由于同一元组同一属性的 值在不同快照中可能是不同，因此不能简单地用传统的关系运算来解决，必 须用复杂的、非通用的编程来实现； ( 3 ) 数据库本身历史的维护支持不足，一般只有提供回滚的事务日志， 缺乏相应的事务查询命令。 正是由于对传统关系型数据库的这些要求和对时态信息的管理上的困 难，时态数据库技术的出现也就成为了必然。经过二十多年的研究，时态数 据库领域取得了大量的研究成果，它们涉及时态术语定义、时态数据模型、 时态关系代数、时态查询语言、时态聚集算法、时态数据库实现等数据库理 论的各个方面，时态数据库也因此逐渐形成了一套比较完备的理论体系。因 此，那些从系统内部支持存储和检索时态数据的数据库，都统称为时态数据 库。时态数据库处理的是时态数据，丽时态数据只在一段时间上有效，并且 随时间持续变化而变化。在传统关系数据库中，聚集函数是应用在数据库基 本表、视图和索引之上，针对某个或者某几个显式属性展开计算。而在时态 数据库中，时间域定义为由基本时间粒( g r a n u l e ) 组成的全序集合，而聚集 计算则是时间域上从某个粒度向更粗粒度上的一个概括”。 在相关系统中，元组的时间属性通常由二维时间问隔表示。例如：一个 电信公司将用户电话通话信息保存成下面的形式； ( 1 ) 每个电话的开始结束时间； ( 2 ) 它对应的话费( 以美元为单位) 。 如图1 1 所示，图中有6 个间隔来表示6 个电话，纵坐标( 值) 表示相 应的话费，横坐标表示每个电话的通话时间。 2 哈尔滨下程大学硕士学位论文 3 5 3 2 5 2 1 5 l 0 5 i2 3 4 5 678 时间 图1 1 时态数据间隔表示图 针对图1 1 的存储形式，对时态信息进行查询就表现为一个二维的区域 查询。举例来说，给定值的范围为口乜时间间隔为前提，一个时态计数聚集 查询就是获取在时间范围内，神话费范围内的通话数。如图1 1 的阴影部 分表示满足在时间范围q t = 6 ，8 1 内正在通话的电话数量，并且这些电话的话费 都在q k = - 1 7 5 ，3 】之内。这等价与求与查询矩形相交的间隔数量。时态求和聚 集查询，先假定每个数据间隔都有一个权值，然后将符合条件的数据间隔的 权值的总和返回。举例来说，如果数据库也存储了每个电话的参与者的数量 那么求和查询将返回所有符合条件的电话的参与人数的总和。现今的大部分 时态数据库的研究都旨在获取对象的个体信息以满足特定的预测。但是从实 际出发，考虑到大量实际应用需求仅仅是为了得到一个聚合的结果。而这个 结果在满足应用需求的前提下，是可以用有可允许的较小的边界内误差近似 结果来满足。除了上面这种简单的应用中需要时态聚集查询外，近些年来的 数据仓库( d a t aw a r e h o u s e ) 应用对时态聚集查询提出了进一步的要求。数据 仓库的一个主要用途是提供复杂查询，特别是时态聚集查询，而时态聚集查 询所关心的就是时间。在数据仓库中，时间值通常是一个整数，表示现实世 界的一个时间粒度。举例来说，假设某个员工的工资是按天付的，那么要在 数据仓库中记录他的工资信息，必须每一天都有一条相应的元组。这样就会 导致大量的空闻来记录工资信息。但在时态数据库中，只需要一条或者几条 记录就可以表示该员工的工资信息了。假设在数据仓库中，工资是按天记录 的，现在想计算周平均工资，即使在关系中明确地记录了每一天的只期，用 3 哈尔滨工程大学硕士学位论文 s q l 表达起来也是特别困难的，但是如果数据仓库支持时态聚集查询，用时 态查询语言表达起来就非常容易了。下面是用t s q l 2 来表示这个应用的例 子。 s e l e c ta v g ( s a l a r y ) f r o me m p l o y e ea se g r o u pb yv a l i d 但) u s i n g7d a y s 值得注意的一点是，对于员工工资的每一次变动，只需要用相应的一条 记录来记录它，而不需要每一天都要记录一条工资记录n - s ! 。 通过上面的分析，本文得出数据仓库中支持时态聚集查询有以下3 个优 点“i 首先，大大减少了数据冗余；第二，使用时态查询语言表达时态查询 清晰、简洁；最后，有效地提高与时间有关的聚集应用的整体执行效率。 1 2 国内外时态数据库研究及时态聚集算法的现状与发展 2 0 世纪8 0 年代中期，学术界提出了近百种为数据库管理系统增加时态 信息处理能力的方案，经过了十多年的研究，逐渐将这近百种数据库管理系 统模型归并为1 3 种具有代表性的模型。这1 3 种模型中，大部分只支持有效 时间，有小部分既支持有效时间又支持事务时间，并且每种模型基本上都有 自己对应的查询语言。这1 3 种模型、其代表性人物以及模型的提出时间如下 列出“= ( 1 ) 时间关系模型( t i m er e l a t i o n a lm o d e l ，t r m , b e nz v i ，1 9 8 2 ) ； ( 2 ) 历史关系数据模型( h i s t o r i c a lr e l a t i o n a ld a t am o d e l ，h r d m ， j c 1 i i i o r d ，1 9 8 2 ) ； ( 3 ) 对象历史模型( o b j e c th i s t o r ym o d e l ，o h m ，s g i n s b u r g , t a n k , 唐常 杰等，1 9 8 3 ) ； ( 4 ) 时态结构化查询语言( t e m p s q l ，s h a r s h i i c g a d i a & s u n i l ，s n a i r , 1 9 3 5 ) ： ( 5 ) 增强实体关系模型时态查询语言( t e m p o r a lq u e r yl a n g u a g ef o r e n h a n c e d e n t i t y r e l a t i o n s h i p m o d e l ， l e e r 兄e l m a s r i ，1 9 8 5 h ( 6 ) 双时态数据模型( t q u e l ，r s n o d g r a s s , 1 9 8 5 ) ： ( 7 ) 历史查询语言( h i s t o r i c a lq u e r yl a n g u a g e , h s q l n l s a r d a , 1 9 8 7 ) ： 4 哈尔滨工程大学硕士学位论文 ( 8 ) 扩展b j 隔关系模型( i n t e r v a l - e x t e n d e dr e l a t i o n a lm o d e l ，i x r mn i k o s a l o r e n t z o s ，1 9 8 7 ) ； ( 9 ) 时态扩展关系模型( t e m p o r a le x t e n s i o n st ot h er e l a t i o n a lm o d e l ， 硼b r m ，k b n a v a t h e ，1 9 8 7 ) ； ( 1 0 ) 基于时序的时态数据模型( t e m p o r a ld a t am o d e lb a s e do nt i m e s e q u e n c e ，t d m ，a r i es e g e v & a r i es h o s h a m , 1 9 8 8 ) ； ( 1 1 ) 面向对象a p l e x ( o b j e c to r i e n t e da p l e x , o o d a p i e x , u d a y a l ， 1 9 8 9 ) ； ( 1 2 ) 时态演绎数据库( t e m p o r a ld e d u c t i v ed a t a b a s e ，t d d ，m a r i a n n e b a n d i n e t , 1 9 8 9 ) ； ( 1 3 ) 时态关系微分( t e m p o r a lr e l a t i o nc a l c u l u s ，t r c ，a b d u u a ht a n s e i ， 1 9 9 2 ) 。 现有时态聚集算法可分为两类：基于时态索引的聚集计算和无索引聚集 计算。基于索引的聚集算法预先对数据作局部聚集计算，并将结果存储在外 存中。在需要进行聚集计算时，利用已存储的局部聚集结果快速计算出结果。 无索引聚集算法通过对数据库的一次预扫描，在内存中生成一些可用于存储 局部聚集结果的数据结构来进行计算。k l i n e 通过对时态关系的一次扫描，建 立聚集树( a g g r e g a t i o nt r e e ) 利用深度优先搜索法可快速求得聚集结果。 聚集树不是平衡树，因此其节点的插人会大大影响算法整体性能。后来k l i n e 又提出2 - 3 树，利用叶节点存储聚集结果的时闯信息n ”。2 3 树是平衡树，因 此其搜索效率和调整效率较高，但是由于事先需要对各元组按时间排序，因 此额外开销很大。k i m 等人提出的p a 树以a v l 树组织数据，存储时间戳和 局部聚集值，在计算时，中序遍历p a 树得到结果”。m o o n 等人提出利用 m e t a 数组将关系元组分为各个子集，采用分治法对各个子集进行聚集计算， 最终结果通过对各子集结果的归并得到n “。此外一些并行时态聚集算法，基 于时态索引的聚集计算采用存储于外存的数据结构来提高算法效率。s b 树就 是最好的例子，通过对s b 树的深度优先搜索得到递增的局部聚集结果和其 对应的时间段聚集结果。在调整时，s b 树利于新节点的插入，但是不利于节 点的删除，因为对节点的删除会破坏聚集值的递增规律。与s b 树不同，m v s b 树为一系列s b 树，每个时间戳对应一棵s b 树，适合时态范围聚集计算的实 s 哈尔滨：t = 程大学硕七学位论文 现”。 总体来说，非索引聚集算法需要预先对关系作一次预扫描，根据查询谓 词在主存中生成相应数据结构，现有的算法都需要聚集值满足一定的递增规 律，因此只适合分布聚集函数- 一，。本文中，阐述了c o u n t 和s u m 聚集算法， 其他聚集算法并未提及，日后的研究方向也必将涉及这些聚集函数。更进一 步说，文中对a v e r a g e 聚集处理( a v e = c o u n t s u m ) 的研究也非常感兴趣， 由于c o u n t 和s u m 并不需要对c o u n t s u m 的商进行误差限制，因此其主要的 难点就是绝对错的限制。另外一个研究方向是将这些技术在时空聚集上扩展。 在时空数据库中，数据对象既有时间属性又有空间属性，而在历史中任何一 个时间戳上定位对象，这样做的目的是近似查询在某一时间间隔内一个具体 区域中所有存在对象的数量。要实现这些就要在现有的算法上提出适应于更 高维度的解决算法，然而这也需要更多完善地改进。由于数据库规模的日益 扩大以及时态聚集实现的复杂性，通常时态聚集计算量非常大。如何结合人 工智能、并行计算等领域的研究成果来提高时态聚集算法的效率，将是今后 时态聚集算法的研究方向。 1 3 课题的意义目的和作者工作内容 现今的时态聚集查询技术都关注于精确查询处理，而现实中对于历史数 据的查询有时候并不要求非常精确，仅仅只需要了解一个历史的趋势，并且 这种应用在现实世界中越来越多。正因为如此，本文的研究意义就在于为用 户提供基于有限误差的快速高效的时态聚集算法。 由于现代商业产品中并没有成熟的时态数据库产品，主要其主要原因是： ( 1 ) 现有的时态查询算法都是基于复杂的数据结构而提出的，这种复杂 的数据结构在现代商业数据库产品中很难实现，需要找到一种现有的并且被 广泛应用的数据结构来对时态数据进行索弓j ； ( 2 ) 时态查询算法在执行时对内存空间开销要求很高，还没有找到一种 高效的算法来降低算法执行的空间复杂度，因此这方面的问题应该从另外一 个角度来进行思考，并提出较为择中的解决算法； ( 3 ) 当t f 流行的时态查询算法对于算法执行的时问复杂度也存在改进的 6 哈尔滨工程大学硕士学位论文 空间。这个原因的产生一个是由于复杂的数据结构，第二是因为这些算法所 求结果是基于精确查询，这样对于庞大的时态数据索引会陷入多重循环和递 归调用中，其时间复杂度必定很高，或者难以达到在商业产品中实现的可能。 本文的研究目的在于：利用近似时态聚集处理操作来解决现有时态聚集 算法存在的主要问题。特别对于计数聚集计算，基于本文所提出的近似算法 预计与精确结果的误差在占n 内，其中是一个小于l 的正常数，而在性能 的改进方面预期达到在满足时问开销不下降的情况下对于空间开销有较大幅 度的提升( 时问复杂度达到对数级，空间复杂度达到线性级) 。通过对当前流 行的时态聚集算法的分析，作者的工作内容一目了然，为了解决上述问题， 首先必须转换思考的角度，以减少时间复杂度和空间复杂度为出发点，在现 有索引结构中找到合适的结构，来对庞大的时态数据进行索引；其次通过了 解现代时态数据库应用的需求，在满足用户需求的情况下，可以适当降低查 询结果的精确性；最后通过问题一步一步地解决，对本文所提出算法进行试 验论证。 1 4 论文的组织 第1 章介绍了时态数据库和时态聚集算法的基本概念，简单阐述了对态 数据库的时间特性，并且分析了国内外相关课题的研究现状阐明课题的研究 目的和主要研究工作。 第2 章详细说明了时态数据库的概念，并对时态数据库术语、特点和流 行的时态数据模型进行了简单的描述。总结时态数据库的重要意义。 第3 章描述了时态聚集技术，对现有的较新、较典型的聚集算法。这一 章是本文的理论基础，本文所提出的改进算法都是基于这一章中所提出的技 术。 第4 章综合以上各部分内容，引入近似技术，提出了两种近似求解算法， 并简单介绍所提出算法在求和查询中的应用，最后对本文所提出算法进行分 析，在理论上证明了算法的改进后的性能。 第5 章通过理论证明和仿真实验验证了近似m v b 树算法和近似b + r 树 算法性能的提高，达到了预期效果。 7 哈尔滨工程大学硕士学位论文 第2 章时态数据库概述 本章中主要介绍时态数据库的相关概念、术语和特点，同时也将现有流 行的时态数据模型进行概述性的介绍。 2 1 时态数据库术语 在时态数据库研究的早期，由于没有统一的术语规范，这给时态数据库 的研究工作和学术交流带来了很大的不便。后来在j a m e sc l i f f o r d ，r a l t l e z e l m a s r i ，s h a s h ii c c r a d i a 等人的倡导下，逐渐达成了时态数据库术语，并要 求在文献中采用统一约定术语。下面简要介绍一些比较重要的术语忸，。 现实模型( m o d e l e dr e a l i t y ) ：对现实世界的一部分进行建模并且记录其 信息的数据库模型称为现实模型。 事实( f a c t ) ：任何可以被赋予真值( 真或假) 的逻辑表述，称为事实。 时间粒度( t n n eg r a n u l e ) ；数据库中所采用的时间单位称为时间粒度。 时刻( i n s t a n t ) ：时间轴上的一个时间点称为时刻。 时间区间( t u n e p e r i o d ) ：两个时刻之间的时间称为时间区间。时间区间 就是连续时问粒度值的集合。 时间间隔( 1 钿1 ei n t e r v a l ) ：时间的长度称为时间间隔。对于时间间隔， 它有确切的长度，却没有确切的起始时间和结束时间，这也是它与时间区间 的区别所在。 对态元素( t e m p o r a le l e m e n t ) ：时间区间的集合称为时态元素。其中， 每个时间区间是不重叠的，如果有两个时间区间重叠了，则把它们合并为一 个时间区间。 用户自定义时间( u s e r - d e f m e d t i m e ) ：用户定义的，具有特殊含义的时 间属性称为用户自定义时间。 生命周期( l i f e s p a n ) ：一个数据库对象在数据库中存在的时间称为该数 据库对象的生命周期。数据库对象在现实模型中存在的时间称为有效时间生 e 哈尔滨工程大学硕士学位论文 命周期。数据库对象在数据库中存在的时间称为事务时间生命周期。 有效时间( v a l i d v m i e ) ：在现实模型中一个事实为真的时间称为该事实 的有效时间。有效时间可能跨越过去，现在以及将来。通常，有效时间由用 户来提供。 事务时间( t r a n s a c t i o nt i m e ) ；一个数据库实体( d a t a b a s ee n t i t y ) 从被 存入数据库的某个时间点开始，将一直存在于数据库中直到它被逻辑删除为 止。一个数据库实体在逻辑上存在于数据库的时间称为该数据库实体的事务 时间。通常，事务时间由数据库系统产生和提供。 有效时间只对于事实而言的，而事务时间却对于任何数据库实体都具有 含义。举例来说，一个数值“6 3 ”，它可以有一个事务时间，表示它存在于数 据库的时间。但是数值“6 3 ”却不会有一个有效时间，因为并没有具体的事 件与其对应，因此单单给出。6 3 ”一个值并不能代表真正的事件在现实中的 意义。 有效时简记录了现实模型随时间而变化的状态信息，而事务时间则记录 了数据库系统随时间而变化的状态信息。 2 2 时态数据库的特点 时态数据库在大量工程需要的情况下，已经引起了许多专家学者的关注， 可以说对于时态数据库的研究已经成为众人瞩目的焦点。因此，本节将重点 介绍一下时态数据库的特点，从这些特点中，读者可以简单的了解到时态数 据库的研究领域以及技术上的难点m “。时态数据库有下列几个方面的特性。 ( 1 ) 动态性。传统关系型数据库系统对仅仅对数据进行静态或准动态的 管理。在数据库更新时，被更新的原始数据将从数据库中删除，这就不能反 映出现实世界的动态性。例如，“顾超的职称是：2 0 0 0 年7 月至2 0 0 2 年1 0 月为助教，2 0 0 5 年1 1 月至2 0 0 6 年1 0 月为讲师，2 0 0 6 年1 1 月至今为副教授”。 在传统关系数据库中只保存最近一次的数据快照，也就是“顾超的职称为副 教授”。而在时态数据库中，过时的数据不再从数据库中删除，对历史数据也 可以进行更新，它能将以上顾超的职称变更过程都保存下来，使系统和现实 世界一直保持一致。 q 哈尔滨丁程大学硕士学位论文 ( 2 ) 全面性。时念数据库是所有具有时态属性数据的集合体，可以提供 任何时刻和时间段的数据，使数据库成为真正意义上的数据库。 2 3 时态数据模型 管理时态信息的共同目的使得现有t d b 模型在概念、研究算法和机制上 有些共同的特点w ： ( 1 ) 时间量子的概念。时间量子( c h r o n o n ) ，被定义为时态系统所支持 的最小的、不可分解的时间间隔。在微机w i n d o w s 平台上，时态系统通常取 时间量子为0 0 1 秒( 高精度系统) 至1 秒( 低精度系统) 。系统支持的时间起点 记为0 ，系统时间域是有限、离散、有序的时间量子的集合，一般记为式2 1 ： s y s r = o l ，2 ，n o w , ，m a x s y s t i m e ( 2 1 ) ( 2 ) 扩展关系数据库。t d b 模型一般是传统关系数据库的扩展，而传 统关系数据库则是时态数据模型的一个特例。如何理解这个说法昵? 举个简 单的例子，当一个事实的生命周期 t j t 2 1 缩小为时亥l j n o w 时，它是个被管 理对象的快照，即传统关系数据库。传统关系数据库的操作如选择、投影、 连接都在这里有相应的扩展，而当生命周期缩为 n o w , n o w 时，这些运算与 传统关系数据库运算兼容。t d b 中增加了些传统关系数据库没有，却对时 态数据库有意义的运算，如时态连接、时态选择、a f t e r 、b e f o r e 和 o v e r l a p 等等；并且引出了很多命题和定理。 ( 3 ) 形式化描述。t d b 模型一般都有形式化的描述如：定义时刻、时 间区间、时态元组、时态关系等一大批概念，引入或扩展传统关系数据库的 运算，例如：时态选择、时态投影、时态连接等等。在模型和概念基础上深 入下去，取得了一批有意义的结果。例如某些性质在关系数据库上成立，在 时态数据库上也成立；某些性质在关系数据库上成立，但在时态数据库上加 条件才成立。 2 。3 。1 历史关系数据库模型 传统的关系数据库是一个二维表。如表2 1 记录了学院的当前院长的信 1 0 哈尔滨工程大学硕士学位论文 息。 表2 1当前学院院长信息 学院名称院跃姓名 计算机科学与技术a a a 经济管理学院 b b b 表2 1 只是一个当前学院院长的信息，但这仅仅是一个快照，并不能反 映出院长信息的过去。如果想要其能够表示院长信息的历史，就应该添加一 个能够代表时间粒度的属性。改粒度可以取不同的时间粒度。可以去年、月、 日、时等等，如图2 1 所示，图中的时间粒度取年为单位，分别取了2 0 0 4 年， 2 0 0 5 年，2 0 0 6 年的三个快照，构成一个拥有时间维的三维数据库。 学院名称院长姓名 计算机a a a 经济管理d d d 学院名称院长姓名 根节点 计算机 c c c 经济管理d d d 学院名称院长姓名 2 0 0 57 计算机 a a a 经济管理 b b b 图2 1 带时间维的数据库 j a m e sc l i f f o r d 等学者于2 0 世纪8 0 年代末提出了历史关系数据库模型 ( h r d m ) ，h r d m 作为先驱模型之一，提出了元组生命周期的概念，这样 就可以解决保存时间间隔选取问题。在表2 1 的基础上引入了“任职时间” 属性，添加属性后如表2 2 所示。 在表2 2 中，属性“任职时间”就为元组的有效时间或生命周期，属性 值域是区间集合。元组生命周期为：元组的插入时间为开始时间，结束时间 哈尔滨t 程大学硕士学位论文 为逻辑删除元组的时间。在时念数据库中，不能物理删除元组( 理论上) ，这 也反映了历史不能删除只能追加的特性。引入生命周期概念有下列优点： ( 1 ) 减少数据冗余，从以年为时间粒度的三维关系中共三个关系和6 个元组来描述历史，而表2 2 中只有一个关系和四个元组； ( 2 ) 提高了准确度，表2 - 2 中准确地给出了任职时间，从中可以推导出 历史快照。 表2 2 增加任职时间的院长表 学院名称院长姓名任职时间 计算机a a a 2 0 0 4 - 2 0 0 6 u 2 0 0 6 - n o 州 计算机 c c c 2 0 0 4 ，2 0 0 6 】 经济管理 b b b 2 0 0 4 2 0 0 6 经济管理d d d 【2 0 0 6 - n o w 】 h r d m 建立了严格的数学模型，并在此基础上讨论了时态投影、时态选 择、时态连接以及时态函数依赖等深刻性质，发表了一大批理论成果。 2 3 2 对象历史模型 现今，一个普遍的机制“历史+ 觋状一未来”被许多人所接受，1 9 8 3 年，s g - i n s b u r g 等人引入了对象历史模型( o b j e c th i s t o r ym o d e l ) ，它封装了 属性和函数，具有面向对象的特性m ，。对象历史的数学模型与o o p 中的c l a s s 类似，含有四个要素：( 1 ) 一些属性集合；( 2 ) 函数；( 3 ) 语义约束集合； ( 4 ) 初始化条件。s g i n s b u r g 引入了计算元组序列模式( c s s ) ，它是一个 八元组：t = ( ， ， ，e v a ，s e te ，爹) 。八个元素分别为状态属性 集、输入属性集、评价属性集、评价函数集合、状态函数集合、语义约束的 集合和初始序列集。c s s ( t ) 的合法序列集记为v s e q ( t ) ，是符合语义约 束和函数计算法则的那些元组的集合。t 在计算机上实现一个对象，评价函 数和状态函数是该对象的成员函数。 1 2 哈尔滨一r ：程大学硕士学位论文 2 3 3t e m p s o l 模型 1 9 8 6 年，s h a r s h ik g a d i a 提出了同时关系模型( h o m o g e n e o u sr e l a t i o n a l m o d e l ) ，这个模型因为提出了时态查询语言t e m p s q l 成名，称之为t c m p s q l 模型1 。 ( 1 ) t e m p s q l 概述 t e m p s q l 是s q l 在时态聚集上面的扩展。保持了s q l 的功能。t a n p s q l 能查询对象的历史数据、数据库本身插入、删除和修改的历史，以及用户和 数据库本身出错的历史，保持了时态数据和非时态关系型数据的无损连接。 数据快照是时态数据库数据的特例。其生命周期缩小为一个时间点 n o w ， n o w 。它要求一个元组中各个属性的生命周期一致，郎满足同时性条件，该 模型的名称也因此得来。 表2 3 是学院院长信息关系表。表中元组的各个属性的生命周期( 可以 是几个区间的并集) 是一致的。它还反映了一个传统关系数据库难于简捷表 达的事实：2 0 0 2 2 0 0 4 期间，在b 先生任院长时，该系曾一度改名为计算机 科学学院。 表2 3同时性模型中的系主任关系 学院名任职时间院长姓名 2 0 0 0 ，2 0 0 h ， a 【2 0 0 0 ，2 0 0 2 1o 2 0 0 4 ，n o w 【2 0 0 1 ，2 0 0 2 ， b 计算机学院 2 0 0 4 ，2 0 0 s ， c 【2 0 0 5 ，n o w ， d 2 0 0 2 ，2 0 0 4 】 计算机科学学院 2 0 0 2 ，2 0 0 4 ， b ( 2 ) 特殊术语 时态属性值，t e m p s q l 中允许时态属性值是形如( 区间，值) 这样的二 元组，例如，( 2 0 0 0 , 2 0 0 4 ，“在大学学习”) ，表示某人在大学学习的时间是 哈尔滨工程大学硕士学位论文 2 0 0 0 ，2 0 0 4 】。【2 0 0 0 2 0 0 4 为元组的生命周期。 时态表达式：如a 是一个属性。a 的时态表达式，记为【a 】，表示在 该关系各个元组中属性a 的定义域的并集。例如在表2 3 中【 院长姓名】= 2 0 0 0 ，n o w ) ，说明数据库中保存着 2 0 0 0 ，n o w ) 期间学院院长的姓名。如 a ，b 是属性，0 是比较算符( 例如 ， 1 5 ， 聚集函数出现在h a v i n g 子句中。 3 1 7 时态分组 时态分组是指在时态数据库中，对闯序列被划分成时间区间，关系表中 元组按照时间区间进行分组，最后在这些分组上进行聚集计算的过程。传统 关系数据库不支持这个特性m ，。时态分组的概念源于在特定时间区间上计算 聚集值的需要，例如计算每年的平均工资等。在时态分组上计算聚集值有三 个步骤，这三个步骤的结果称为聚集分组。 首先，划分时间序列，这决定了计算聚集值时对应的时间区间。对于时 间的划分，可以按照时间粒度( 月、日、年等) 来划分，也可以把整个时间 1 8 哈尔滨工程大学硕士学位论文 作为一个区间，也可以把任何长度的时间作为一个区问。 接着，对于划分后得到的时间区间，需要同时考虑位于这个区间之前或 之后的时间。例如，要计算一个工厂每年的平均产值，假设这种平均产值的 计算算法是去年、今年、明年的产值加起来除以三，那么计算每年的平均产 值时，虽然是以年为单位，但是也要考虑该年的前一年和后一年的产值。 最后，必须决定哪些元组落入这些时间区间内。可以选择a l l e n 操作符 中的任何一种作为这种从属关系( m e m b e r s h i p ) 的表示。a l l e n 操作符是一个 比较时问区间的完整集合。例如，比较两个时间区问是否重叠，是否重合， 以及是否一个区间包括另一个等等。 3 2 多版本b 树 多版本b 树( m v b t r e e ) 是用来在时态数据库中处理时间戳范围查询 的索引结构“。该查询检索所有在时刻，有效的数据间隔并且它的值在和 范围内。如图1 1 所示，查询q t - - - - 6 并且q k = - 1 7 5 ，3 】，将返回间隔d 和p 。 m v b 树是一个利用具有高效分配空间结构存储多( 逻辑) b 树的算法。 每一条目都以 的形式存储，这里幻是数据问隔的开始时间，切是 结束时间( i ，。，白) 是该条目的生存周期) 。对于叶子条目来说，均，是一个间 隔的值，对于中间条目f 来说，七就等于其生存周期中，子树中最小的叶子 条目的