（计算机应用技术专业论文）时态数据库多时间粒度问题的研究.pdf

堕玺鎏墨三奎兰三兰堡圭：些鎏兰 时态数据库多时间粒度问题的研究 摘要 在时态数据库中，时间粒度是衡量时态数据的单位，通常用时态类型来 表示时间粒度。而对时间粒度的定义有粗有细，t d b m s 除了支持系统定义的 标准时间粒度之外，还应支持用户定义的各种时间粒度。而现在仅有的几个 t d b m s 的实现中，时间的含义和解释都是由用户应用程序实现，而不是 t d b m s 本身所理解。t d b m s 如何管理这些时间粒度，如何转换基于不同时间 粒度存储的信息，并使这种转换对数据库用户完全透明是本文研究的一个主 要方面。另外，在传统数据库中引入时态信息，会引发主键、索引、参照完 整性等一系列问题的出现，为了解决这些问题，本文在关系数据库规范化理 论的基础上对具有多时间粒度约束的时态数据库规范化理论进行了系统的研 究。 目前对时间粒度问题的研究大多集中在用时态类型表示时间粒度，而在 实际应用中，这种表示方法对于用户自定义的时间粒度具有很大的局限性。 本文基于粒度之间的五种关系提出了粒度关系集的概念，并且基于粒度关系 集给出了用旧粒度定义新粒度的算法；概括了时间常量、时间段、时间间隔 之间的粒度转换；给出间接粒度转换过渡到直接粒度转换的算法及其相关定 理的证明。用于支持t d b m s 的多时态粒度存储的特性。通过此算法将结果集 以用户所需要的时间粒度提交给用户接口，从而实现了t d b m s 对用户自定义 时间粒度的全面管理。 在时态数据库的研究领域中，对多时间粒度约束的时态函数依赖问题已 有了深入的研究，且针对具有多时间粒度的时态数据库的逻辑设计问题也进 行了系统的讨论。但现有的算法在实际的数据库设计中却很难使用，这主要 是因为两方面的原因：一方面，由于时态类型集所具有的偏序特性使得算法 中的些时态类型间的操作无法实现；另方面，算法是以范式判定为基础 的，而对于范式判定至今还没有有效的算法。为克服上述问题，本文提出了 时态初等关键字范式、时态简单范式的概念，并给出了时态模式在其上的相 应分解算法以及相关定理的证明，使其保持函数依赖性和无损连接性。 关键词 时态数据库；时间粒度；时态初等关键字范式；时态简单范式 哈尔演理工大学工学硕士学位论文 t h er e s e a r c ho fm u l t i p l eg r a n u l a r i t i e s i nt e m p o r a ld a t a b a s e a b s t r a c t i nt h et e m p o r a ld a t a b a s e ，t e m p o r a lg r a n u l a r i t yi st h eu n i tf o rm e a s u r i n gt h e t e m p o r a ld a t a u s u s l l yw eu s et i m et y p et oe x p r e s st e m p o r a lg r a n u l a r i t y b u tt h e u s e rm a yd e f i n et i m eg r a n u l a r i t i e si nt h e i rw i l l s t e m p o r a ld a t a b a s es h o u l d s u p p o r tt h e u s e rt o m a n i p u l a t ed a t ai na n yt i m eu n i t b u ti n t h es e v e r a l i m p l e m e n t a t i o n so ft e m p o r a ld a t a b a s e ，i t ，i st h eu s e ra p p l i c a t i o nr a t h e rt h a nt h e t d b m si m p l e m e n t st h et i m em a n a g e m e n t t h i sp a p e rd i s c u s s e st h ew a yi n w h i c ht h et e m p o r a ld a t a b a s em a n a g e st h e s et e m p o r a lg r a n u l a r i t i e s ，c o n v e r t s b e t w e e nd i f f e r e n tt e m p o r a lg r a n u l a r i t yr e p r e s e n t a t i o n so fi n f o r m a t i o na n dm a k e s t h ec o n v e r s i o nt r a n s p a r e n tt ou s e r s i nt h eo n l yr e a l i z a t i o no fs e v e r a lt d b m s s ， t h em e a n i n ga n de x p l a t i a t i o no fg r a n u l a r i t ya r ea l lr e a l i z e db yu s e r sa p p l i c a t i o n p r o g r a mn o w , b u tn o tt d b m so n ei su n d e r s t o o d h o wt d b m sm a n a g e st h e t e m p o r a lg r a n u l a r i t i e s ，h o wt oc h a n g eo nt h eb a s i so ft h ei n f o r m a t i o nt h a tt h e g r a n u l a r i t ys t o r e so fd i f f e r e n tg r a n u l a r i t i e s ，t h a ti sam a i nr e s p e c tt h a ts t u d i e so f t h i sa r t i c l et om a k et h i sk i n do fc o n v e r s i o nt o t a l l yt r a n s p a r e n tt od a t a b a s eu s e r s i na d d i t i o n ，i n t r o d u c et i m ei n f o r m a t i o ni nt h et r a d i t i o n a ld a t a b a s e ，w i l lc a u s et h e a p p e a r a n c e so fas e r i e so fq u e s t i o n s ，s u c ha sm a j o rk e y , i n d e x ，c o n s u l t i n g i n t e g r a l i t y ，e t c i no r d e rt os o l v et h e s ep r o b l e m s ，t h i sa r t i c l ec a r r yo ns y s t e m a t i c r e s e a r c ho nt h eb a s i so fs t a n d a r d i z e dt h e o r yo fr e l a t i o nd a t a b a s et oh a v em a n y t e m p o r a ld a t a b a s es t a n d a r d i z e dt h e o r yw i t hm u l t i g r a n u l a r i t i e sr e s t r a i n ， t h er e s e a r c ho ft h et e m p o r a lg r a n u l a r i t yq u e s t i o n sm o s t l yc o n c e n t r a t eo n e x p r e s s i n gt h et e m p o r a lg r a n u l a r i t yw i t ht h et i m et y p ea tp r e s e n t ，i np r a c t i c a l a p p l i c a t i o n ，t h ee x p r e s s i o nm e t h o dh a v eh e a v yl i m i t a t i o nt ou s e rs e l f - d e f i n i n g g r a n u l a r i t y t h i sa r t i c l eh a sp u tf o r w a r dt h ec o n c e p to ft h et e m p o r a lg r a n u l a r i t y r e l a t i o no nt h eb a s i so ff i v ek i n d so fr e l a t i o n sb e t w e e nt h et e m p o r a lg r a n u l a r i t i e s a n dc o l l e c t e da n dp r o v i d e da n dw o r no u tt h ea l g o r i t h mt h a tt h eo l dg r a n u l a r i t y d e f i n e st h en e wg r a n u l a r i t yo nt h eb a s i so ft h eg r a n u l a r i t yr e l a t i o n t h ep a p e r 竺玺堡塞三銮：三兰堡圭耋竺鎏兰 s u m m a r i z e sc o n s t a n t 、t i m es l o t t i m ei n t e r v a l ；p r o v i d et h ei n d i r e c tt e m p o r a l g r a n u l a r i t yt r a n s i t i o no nt h eb a s i so ft h ed i r e c tt e m p o r a lg r a n u l a r i t yc h a n g e s a l g o r i t h m o f f e rt h ee f f e c t i v ew a yf o rt h eu s e r ss e l f - d e f i n i n gg r a n u l a r i t yi n p r a c t i c a la p p l i c a t i o no nt h eb a s i so ft e m p o r a lg r a n u l a r i t yr e l a t i o n s h i p i tc a nb e u s e df o r s u p p o r t i n gt d b m sc h a r a c t e r i s t i c w i t hm u l t i t e m p o r a lg r a n u l a r i t y t h r o u g ht h i sa l g o r i t h m ，d a t aw i t ha l lk i n d so ft e m p o r a lg r a n u l a r i t i e sc a nb e s e n d e dt ou s e rj n t e r f a c ea n dr e a l i z et h et i m em a n a g e m e n ti na na 1 1 r o u n dw a y i nt h er e s e a r c hf i e l do ft e m p o r a ld a t a b a s e ，t h ei s s u eo nt e m p o r a lf u n c t i o n d e p e n d e n c yw i t hm u l t i g r a n u l a r i t yh a sb e e ni nad e e pd e g r e ea n dt h er e s e a r c ho n t h el o g i cd e s i g no ft e m p o r a ld a t a b a s ew i t hm u l t i - g r a n u l a r i t i e sh a sb e e nd i s c u s s e d s y s t e m a t i c a l l y b u tt h ee x i s t i n ga l g o r i t h mi sv e r yd i f f i c u l tt ou s ei nt h er e a l d e s i g no fd a t a b a s e ，t h i si sm a i n l yb e c a u s eo ft h er e a s o no ft w or e s p e c t s ：o no n e h a n d ，b e c a u s et i m et y p e sh a v el e a nt o w a r d sp r e f a c ec h a r a c t e r i s t i cw h i c hm a k ：e s o p e r a t i o nb e t w e e nt i m et y p eu n a b l et or e a l i z e ；o nt h eo t h e rh a n d ，t h ea l g o r i t h m i sj u d g e db yt h ef o u n d a t i o nw i t hn o r m a lf o r m ，b u ts of a rt h e r ei sn oe f f e c t i v e a l g o r i t h mt oj u d g en o r m a lf o r m i no r d e rt oo v e r c o m ea b o v e m e n t i o n e dp r o b l e m s t h i sp a p e rp r e s e n t st h ec o n c e p t so ft e k n fa n dt s n fa n dp r o v i d e sa na l g o r i t h m o nt h o s et e m p o r a lm o d e l sa n d p r o v e st h er e v e l e n tt h e o r e m 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 lg r a n u l a r i t y ；t e k n f ；t s n f 氅堡鎏矍三奎兰三耋坚圭兰竺鎏三一 1 1 研究背景与意义 第1 章绪论 现实世界是不断演变进化的，时间是那些反映现实世界信息的基本组成部 分。随着计算机的普及推广，大多数数据库应用程序都有时态的特性，例如： 会计、银行等财经类的应用程序；人事、培训、酒店预定、项目管理等记录性 应用程序：天气监测等科学类应用程序。传统的数据库管理系统对时态信息的 存储、处理和操作都十分有限，只能反映某个对象在某个时刻的状态，无法充 分反映数据库即数据库成员在现实世界的实际情况。正因为传统数据库缺乏对 时态数据的支持，因而在很多方面产生了很多问题，例如：它把时间数据作为 一个字段的值进行存储和管理，不联系对象的历史、现在和将来，无法将对象 的历史、现在和将来作为对象的一个发展过程来看待，而这样做有助于揭示事 物发展的本质规律，抓住事物的发展趋势( 这一点对于象实时信息管理系统这 类的应用程序来说是很基本，很重要的b 同时要求管理数据库系统中元事件 的时态信息，例如数据库被查询修改的时刻，时间区间。多用户系统中对锁定 排队以及资源竞争协调的时标等，这些时态数据也有助于提高数据库系统的可 靠性和效率。随着数据库技术的不断发展，人们开始逐渐意识到有必要为时态 数据建立时态数据库的模型，或者在现有的数据库模型上加以改造，于是提出 了时态数据库的概念。6 0 年代末，人们开始认识到时态信息的重要性，并展开 了研究。g w i e d e r h o l d 和j f f r i e s 在1 9 7 0 年研制的医疗系统在处理时态信 息方面做了较早的尝试，此后这方面的研究工作陆续展开。k a h nk e t a l 于 1 9 7 7 年在a r t i f i c i a li n t e l l i g e n c e 上发表的“m e c h a n i z i n gt e m p o r a l k n o w l e d g e ”反映了早期关于时态信息的基础性研究工作。近年来，对于时态 数据库设计有了相当多的研究，j e n s e nc s ，w i j s e nj 及w a n gx s 等人提出 了各自的时态函数依赖( t f d ) 的概念，其中w a n gx s 提出的时态函数依赖能 够较好地反映客观世界，w i j s e nj 又将其扩展到复杂对象的依赖约束。w a n g x s 基于t f d 系统地讨论了具有多时间粒度的时态数据库的逻辑设计问题，定义 了时态三范式及时态b o y c e c o d e 范式，并提出了相应的分解算法。姚春龙等 人对具有多时间粒度约束的时态函数依赖集的成员籍算法及具有全序时态类型 集的时态函数依赖集进行了深入研究。这些算法是时态数据库进一步规范化的 堕i ：耋墨三奎兰三兰墨土兰堡竺兰 。 基础，为找到更有效的时态数据库的规范化方法开辟了新路。 1 2 相关文献综述 时间粒度通俗地讲，就是时间单位比如日、月、年等，它是时态数据库中 的一项研究内容。时间是真实世界现象中的一个重要方面。事件发生于某个特 定的时间，实体和实体之间的相互作用关系存在于某个时间区域。传统的数据 库只表示出事务在单独时刻的状态，不能反映出事务状态的发展变化，所以可 将数据库中的内容看作是事物在某个时刻的快照。而且，传统数据库管理系统 按照查询和交易到达的顺序逐个执行它们，对查询和交易完成时间不能提供保 证。为了完全自动地支持时间属性，人们于2 0 世纪7 0 年代提出了时态数据库 的概念，它增加了对时间维的建模，有效时间( v a l i dt i m e ) 和事务时间 ( t r a n s a c t i o nt i m e ) 是常用的两种时间维。有效时间表示一个实事在现实中 为真的时间，事务时间则表示在此时间期间此实事记录在数据库中。 自时态数据库提出以来涌现出许多相关研究论文，其研究内容涉及多个方 面，有时间结构、时间的不确定性、时间粒度、时态数据模型、时态查询语 言、时态数据模型的实现、时态查询处理、存储数据管理器、多时问粒度时态 数据库、提高性能等等，具体可见”。自时态数据库提出以来已经提出了超过 3 0 种的关系数据模型的时态扩展模型，其中超过一半的模型仅支持有效时间， 少数几个仅支持事务时间，有的则是双时态的，模型的多样性给时态数据库的 实现和研究带来了不便。为了使现有的和将来的时态数据模型有一个共同的研 究基础，c s j e n s e n 等人提出了一个双时态概念模型b c d m ( b i t e m p o r a l c o n c e p t u a ld a t am o d e l ) ，并以此为基础对s o l - 9 2 进行扩充制定了 t s q l 2 1 1 , 1 14 0 1 ”。本文作者认为之所以出现如此多的时态数据模型，是因为时态数 据库本来就是一种特性数据库，它与传统数据库的区别是增加了对时间属性的 支持，至于支持何种时间维，支持到何种程度，是随应用而异，所以应该根据 应用特点选择合适的，易于实现的时态数据模型。 目前仅实现了少数几个通用的时态数据库，其中最好的也许是t q u e l 原型 ”“1 。许多专用时态数据库是建立在现有商业数据库或文件系统上的，其中时间 的含义和解释由用户应用程序实现，而不是由数据库本身所理解。 其实，人类的活动不仅与时间有关，还进一步与一定的时间单位或周期存 在重要联系，因此人们已逐渐认识到在时态数据库中增加对这些时间单位的支 持是必要的，在研究中通常用时间粒度表示不同的时间单位。 哈尔滨理工大学工学硕士学位论文 对于多粒度时态数据库，人们主要研究了粒度的定义、粒度的表示、多粒 度函数依赖关系、多粒度在时态推理和数据挖掘方面的研究“”1 ，并对相关 概念和术语达成了共识。人们已提出了多种表示时间粒度的方法，但这些时间 粒度的表示和粒度之间的关系定义很受限制，不能定义多种日历系统。 文献m 1 最早提出了多时间粒度的概念，时间粒度系统”在文献”的工作基 础上增加了“粒度链”并提出时间由粗粒度向细粒度的转换操作。文献“1 将时 间粒度系统“”的理论工作更加具体化，为多粒度的时态比较操作定义了一个特 殊的操作语法，它类似于本文中的“f i n e rs e m a n t i c s ”，但并没有涉及多种时 间类型之间的比较操作。文献1 提出了t e m p o r a lm o d u l e 和e x t e n d e d t e m p o r a lm o d u l e 这两种窗口函数，用于以不同时间粒度从对态关系中获取信 息，文中所涉及的粒度转换类似于聚集操作，比如如何将月工资聚集成年工资 返回，或者反之。 在一些支持多时间粒度的时态数据库系统中，对粒度的定义限制很多，要 求所有粒度之间存在全序关系，这种限制通常是为了便于系统实现和计算。文 献”提出了一个时间粒度系统，它着重于在大量时间相关的事件描述上执行时 态推理任务，采用一种叫做“h i e r a r c h i c a lp a r t i t i o n i n g ”( 层次划分) 的粒 度系统，用实数和整数分别表示绝对时间( a b s o l u t et i m e ) 和索引集( i n d e x s e t ) ，所有时间粒度之间存在完全有序排列，有几篇文章讨论了日历和粒度的 表示和实现，但他们提出的粒度都只能用一种表示语言描述。限制多，灵活性 ，j 、。 在办公室信息系统1 中，用格里历所包含的时间粒度表示相对的，绝对 的，周期的和不准确的时间，文中提出在时间比较操作中将时间操作数转换为 最粗的时间粒度方法，以避免产生中间信息。文献”的研究问题与”4 1 有些稍微 不同，它提出用延长粒度链的方法来支持宏事件，即带有持续时间的事件，同 时也提出了细粒度和粗粒度之间的转换问题，但并没有考虑粒度转换中的不确 定性问题。文献1 对”提出的时态形式化方法进行了修改，将时间粒度定义为 在一参考时间点集合上的时间间隔集合。文献”1 ”都提出了采用符号标记法 从其他粒度推导出新粒度的方法，比如f i r s tm o n d a yi na p r i l ，但他们都没 有给出用户定义新粒度和新日历的形式化方法。 以上所有论文都没有涉及到如何在关系数据库中实现用户定义的时间粒度 和日历，包括对s q l 语法的扩充和相关信息的存储，它们所讨论的粒度转换还 只限于“f i n e r ”关系。 文献”提出了一种通用时间粒度框架，其中给出了粒度的通用定义和粒度 哈尔滨hj 、肇r 学颇1 学位论卫 之间的典趔关系，并列出四个与f 训 和现实相关的待定义限制。并已将这个把 架使用于多种不同单粒度数据库的融合，多粒度数掘库的逻辑设计多粒发时 态关系的数据挖掘。 1 3 国内外概况 7 0 年代末，8 0 年代初，数据库技术的日渐成熟和大容量高速存储设备的 发展为时态技术和数据库技术的融合创造了条件，、f b e nz v i ，j c l i f f o r d 和 s g i n s b u r g 三位学者独自在时态数据库方面做了富有特色的先驱性工作： j b e nz v i 于1 9 7 9 一1 9 8 2 年对时态数据库做了开怠i j 性研究，他的博士论文( 加 州大学洛杉矶分校，1 9 8 2 ) 总结了他的一系列工作。b e nz v i 的贡献突出在下 列几点： l 他提出了时态数据库模型，引入了时间间隔( t i m ep e r i o d ) ，后来被学 术界改称为时闻区间。 2 在l 孵9 _ 1 9 8 2 这个关系规范型研究的热点时期，b e nz v i 突破思想禁 区，提出并研究了非i n f 的t d b 。 3 以时阆区间做字段值，刷新了人们认为数据库字段值只能是一个数或串 的观念。 4 弓i 入了后来被称为双时态的概念，即用有效时间表示被管理对象在库中 生命咫期，用事务时阆表示数据库本身的历史。 5 引入了时态索引结构。 上述成果都是开创性的工作。影响了t d b 领域中一代后来者的思路，仅管 1 9 8 2 年以后，b e nz v i 在t d b 领域销声匿迹了，他对t d b 的贡献功不可没。 j c l i f f o r d 于1 9 8 2 年对历史数据库做了开创性工作。他注意到了被管理对象 的生命周期( l i f e s p a m ) ，研究了关系。元组，字段值上加时态信息的技术细 节，引入了历史关系模型，历史关系代数，研究了历史数据库中投影，选择， 联接的特殊要求和特殊规律，研究了历史关系模型与传统关系模型的兼容性， 即当把区间缩小唯一点( n o w ，n o w ) 时历史数据库都退化为传统快照数据库， 且相应的时态代数运算退化为传统快照关系运算。 美国南加利福尼亚大学的s ，g i n s b u r g 教授于1 9 8 3 年提出对象历史模型 ( o b j e c th i s t o r y ) 。该模型与其它几十个t d b 模型有显著不同的风格。对象 历史最初以可以计算对象的历史为研究背景，例如银行帐目，支票账目，税 务，发票历史，证券经纪人数据。g i n s b u r g 工作的特色在于： 丝：至竺坠：! ：竺21 ：氅兰 ，一一 l 深刻分析了基于丁计饽冗组的对象历史的特殊要求和特殊规律，提池了 基于记录，事件驱动的代数站构模型。 2 研究内容( 包括提出的问题分析建模和成果表现) 与其他t d h 模型完 全不交叉，而且对于历史模型强调了计算规律，强调了历史+ 现状一束来的机 制。 3 揭示了一系列出人意料的结果，包括关于对象历史中的若干判定性问题 等难度很大的结果。 4 问题提出和解决都接近应用，特别是金融系统的各种应用。 1 4 发展趋势 时态数据库目前研究工作的缺失遗憾和未来的发展方向是： 数学模型多，但原型实现少；理论研究多，应用研究少；以模型划分的学 术门派多，支持时态数据库产品的厂商少。数据模型太多不一定是一件好事， 个个模受备持己见，没有妥协和融合的意向，不利于时态数据库的发展。数据 库厂商难l ：下疑心选用时态数据库技术用于产品。例如t q u e l 语言在理论和原 墅上都很成功，但其基于的语言q u c l 不是工业标准，t e m p s q l 标准性好，但 有不如删成功。所以在未来的研究中，应该集中力量研究现有模型的融合 和实现。爵辟雪不应该脱离主流数据库研究专门的时态数据库管理系统，而应该 研究在广泛接受的关系数据库产品上，逐步加入时态数据库的机制。另外还应 该大力研究时态数据库技术在数据采掘和k d d 中的应用。时态数据库有先天 的优势：它的有效时间反映了事物发生发展的过程，有助于揭示事物发展的本 质规律：它的事务时同反映了系统中元事件的肘态信息，有助于提高数据库系 统的可靠性和效率。时态数据库在“历史+ 现状 未来”的机制上，在 d m 和k d d 方面大有可为。 1 5 本文的主要工作 1 5 1 基于粒度关系集上的多时闻粒度转换 i 粒度关系集的定义以及其上的粒度定义 2 粒度转换操作：时间常量、时间段、时间间隔 3 时间操作中的粒度转换 哈尔滨理工大学工学硕士学位论文 4 直接粒度转换 5 间接粒度转换 1 5 2 时态初等关键字范式的研究 1 时态初等关键字范式相关概念 2 时态初等关键字范式约束能力的证明 3 时态初等关键字范式的模式分解算法 4 算法的相关证明 1 5 3 时态简单范式的研究 l 时态简单范式的相关概念 2 时态简单范式约束能力的证明 3 时态简单范式的模式分解算法 4 算法的相关证明 2 1 时态数据库 第2 章时态数据库简介 现实世界是四维的世界，有关时间的信息在许多事件上起着决定性的作 用。伴随着物理流( 例如人力，物力，财力的流动) 的信息流包含着事件的时 态信息( 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 f o r m a t i o n ) ，时间区间信息( i n t e r v a li n f o r m a t i o n ) 和相对时间信息( 之 前、之后、重叠) 等等。 传统的数据管理系统( 层次、网状和关系数据库) 对时态数据未作专门的 处理和对待，而只作为一般的属性值，作为用户定义时间进行存储和管理。因 此，传统数据库只反映了一个对象的发展全过程中在某一个时刻的状态( 快 照) ，不能很好地反映和存储其过去和未来。随着数据库的广泛应用，人们从 两个方面提出了管理时态信息的要求： l 要求管理被处理事件的历史性信息，例如：与自然灾害( 地震、气象、 水文、洪涝等) 有关的历史资料、人事、财务、金融方面的历史资料，这些数 据反映了事物发展的本质规律。 2 要求管理数据库系统中元事件的时态信息，例如：数据库被查删改的时 刻、时间区间，多用户系统中对锁定排队以及资源竞争协调的时标等，这些数 据有助于提高数据库系统的可靠性和效率。由此引入时态数据库的概念。 2 2 时态数据库的时间维 传统的关系数据库是属性木元组的二维结构，表2 - 1 表现了传统关系数据 库中的关系。 表2 - 1 传统关系数据库中的关系 t a b l e2 - 1t h er e l a t i o no ft r a d i t i o n a lr e l a t i o nd a t a b a s e 姓名 专业技术职务 李明副教授 王东讲师 表2 一1 只是当前时刻的快照，不能反映被管理对象的历史。 喻尔滨犁r 人# f 学蛳f 。沦空 以“年”为时间粒度，将1 9 9 6 年、1 9 9 8 年、2 0 0 0 年的三个快照放在 起。构成一一个育时悯维的三维数据库，如图2 i 。 2 0 0 0 图2 1 带时闽维的三维数据库 f i g 2 - 1d a t a b a s ew i t hd i m e n s i o n 这样。j ! i 用把多个快照( 即在不同时刻保存的数据库的备份) 放在一起 构成了历史，似乎能解决对象历史的管理问题。 长期以来，在传统数据库( 没有使用时态数据库) 的年代里，企业及机 关管理历史性数据都是这样保存的。然而，管理人员总为三个问题感到困惑： l 应取多大的时间间隔保存快照? 如果时间间隔太大，则不足以保证数据 的准确详实；如果间隔太小，则数据冗余多，占存储空间大。 2 传统关系数据库中，一个表的多个快照不能简单地同时载入内存，并简 单地使用传统的选择、投影、连接运算进行操作比较。因为同一元组同一属性 下的值在不同快照中可能不同，必须做较复杂，非通用的编程。例如：李辉于 2 0 0 0 年晋升为副教授时，王平不一定同时也晋升为讲师( 实际上，王平可能在 1 9 9 9 年已晋升为讲师) 。 3 传统数据库中，对数据库本身历史的维护支持不足，一般只有供恢复回 退用的事务日志( t r a n s a c t i o nl o g ) ，缺乏相应的事务查询命令( 例如快速地 查出哪一天哪个人修改了所有讲师的职务津贴) 。 竺垒鎏些。：查兰：耋堡耋堡耋兰 2 3 时态数据库中的基本概念 j e n s e nc 、c l i f f o r dj 、g a d i as 、s e g e va 、s o n d g r a s sr 几个盛名于时 态数据库的专家对时态数据库中的一些基本概念作了个分类，这种分类依据 4 个命名要求和9 个命名评价标准给出，反映了现有时态数据库方面的基本概 念，现作以简要论述： l 有效时间( v a l i dt i m e ) 指的是被管理对象的生命周期，也即一个事实 在模拟的现实世界中为真的时期。可替换的名字有现实世界时间( r e a l w o r l d t i m e ) ，内在时间( i n t r i n s i ct i m e ) ，逻辑时间( 1 0 9 i c a lt i m e ) ，数据时间 ( d a t at i m e ) 。 2 事务时间( t r a n s a t i o nt i m e ) 是指数据库本身被蠢删改的时间，也即 一个数据库事实被存放在数据库中的整个时期，可替换的名字有注册时间 ( r e g i s t r a t i o nt i m e ) ，数据库时间( d a t a b a s et i m e ) ，外在时间 ( e x t r i n s i ct i m e ) ，物理时问( p h y s i c a lt i m e ) 。 3 甩户定义时间( u s e r d e f i n e dt i m e ) 即用户根据某种需要定义的时 嬲，与有效时闯和事务时间无关。 4 有效时闻关系( v a l i d t i m e r e l a t i o n ) 是指支撑事实的有效时间关 系，可替扶的名字有历史关系( h i s t o r i c a lr e l a t i o n ) 。 5 事务时间关系( t r a n s a t i o n - t i m er e l a t i o n ) 是指支撑数据库事实的事 务时间关系，可替换的名字有滚回关系( r o l l b a c kr e l a t i o n ) 。 6 快照关系( s n a p s h o r tr e l a t i o n ) 及传统的关系，可替换的名字有关系 ( r e l a t i o n ) ，传统的关系( c o n v e n t i o n a lr e l a t i o n ) ，静态关系( s t a t i c r e l a t i o n ) 。 7 时态关系( t e m p o r a lr e l a t i o n ) 是指同时支撑事实的有效时间和事务 时间的关系。它也被称为双时态关系( b i t e m p o r a lr e l a t i o n ) 。 8 事务时间片算子( t r a n s a c t i o nt i m e s l i c eo p e r a t o r ) 它是用于处理带 事务时间的关系的事务时间操作。 9 有效时闻片算子( v a l i dt i m e s l i c eo p e r a t o r ) 它是用于处理带有效时 间的关系的有效时间操作。 1 0 惫元素( t e m p o r a le l e m e n t ) 是n 维时间坐标上有限个集合的并，时态 元素在集合论的与、或、非操作下是封闭的。 1 1 年历( c h r o n o n ) 它是一种时间单位制。 哈尔演州r 人学i 芦硕1 学位沦殳 1 2 时涮戳( t i m e s fa m p ) 它是。个j 体的时间值。 1 3 生存宽度( 1 “e s p a n )+ 个数引库对象的生存宽度是指它以某种i ；式 存在的整个时期。 1 4 时态均匀( t e m p o r a l l yh o m o g e n e o u s ) 一个时态元组是时态均匀的仅 当它的每个属性值的生存宽度是一致的。 1 5 时刻( i n s t a n t ) 是指个时间点。 1 6 区间( i n t e r v a l ) 是指两个时间点之间的所有时间组成的集合。 1 7 时态表达式( t e m p o r a le x p r e s s i o n ) 它是由时间变量和常量等用时态 操作有机构称的表达式。 1 8 独立于时间的属性( t i m e i n v a r i a n ta t t r i b u t e ) 它是指属性值不随 时间变化而异的属性。 1 9 时变属性( t i m e - v a r y i n ga t t r i b u t e ) 它是指属性值可随时间变化而 改变的属性。 2 4 时态数据库的分类 2 4 1 快照数据库 传统的数据库将动态世界某一时间点上的快照模型化，数据库的一个状态 ( s t a t e ) 或者是一个实例( i n s t a n c e ) 就是数据库当前的内容。这些内容并 不一定反映了现实世界的当前状态。更改数据库状态是通过使用像插入、删除 或者替换等数据操作来实现的，操作一旦提交则立即生效。在这个过程中。数 据库的旧状态就被丢弃和遗忘。这类数据库我们称作快照数据库。在快照关 系模型中，数据库是关系的集合。每个关系由带有同样属性的元组集组成，而 且通常表示成为一个两维表( 如图2 2 所示) 。当真实世界发生改变时，表也 要相应改变。 卜j 卜j n i 圈2 - 2 快照数据库 f ig2 - 2s n a p s h o td a t a b a s e 堕堡堡垩三奎兰三兰要圭兰竺鎏兰 2 4 2 回滚数据库 依赖快照的快照数据库不能满足许多时态方面的要求。一个解决这些缺陷 的方法就是存储过去所有快照数据库变化的状态，并通过时间来索引。这里的 时间采用事务时间( 它是指信息存储在数据库的时间) 来表示。在这种方式 下，事务时间作为第三轴，一个关系可以通过三维的方式在概念上加以说明， 这种关系可以视为由事务时间索引的若干个快照关系的系列。人们可以通过沿 着时间轴移动，并选择某一快照状态来取得过去某个时间的关系快照或者对一 个关系快照进行查询。选择快照状态的操作我们称为回滚，并且将支持这种操 作的数据库称为回滚数据库。 图2 3 列举的关系是由空间系开始，之后增加三个事务：加入三个元组； 增加一个元组；删除一个元组( 该元组由第一事务发生时输入的) 和增加另一 个元组。每个事务的结果都成为一个快照状态放置在时间轴的最右边，一旦事 务完成，滚回关系的快照状态就不能修改。事务时间由事务识别符来表示：这 个识别符是由d b m s 产生的单调增加的整数。假定d b m s 可以提供事务识别符与 事务执行时的时钟时间相匹配的信息供查询和显示之需。 圃闻囝 一至兰曼笪 2 4 3 历史数据库 图2 - 3 滚回关系 f i g 2 - 3r o ll b a c kr e l a ti o n 回滚数据库记录的是若干个快照状态的序列，而历史数据库记录的是每个 关系一个单独的历史状态( 即回滚数据库中记录的是快照状态的历史，历史数 据库中只有一个状态，但这一个单独的历史状态中记录了一个关系的历史) 。 堕垒鎏塞三查兰三兰堡圭兰堡篁兰 豳2 4 历史关系 f i g 2 - 4h i s t o r i c a lr e l a t i o n 历史数据库也可以用三维图来表示( 参看图2 - 4 ) 。这时，时间轴的标签变 为有效时间了，语义更加密切联系现实而不是更新的历史。在两个用历史关系 创立的独立快照之间，模型化世界的状况是不能修改的，我们称之为阶跃函数 连续性假设或时态密度原则。也就是在有效时间v 。和下一个有效时间v ：之间， v ，时快照数据库中的信息都有效。因此，这种关系的元组在时间区间 v 。v 2 有 效。 2 4 4 双时态数据库 我们可以通过将支持事务时间和有效时间结合起来实现上述两种方案的优 点。由于回滚数据库的元组是从某一个时间开始在一段时间内有效，因而时态 数据库的数据库管理系统就可以视元组相对于某一时刻的另一时刻有效。我们 用双时态数据库这个词来强调有效时间和事务时间来处理信息的必要性。现在 已经涉及到两个时间轴，所以就必须用四维图来表示双时态关系了。 图2 5 所示的时态关系是由空间体系开始到四个事务发生的结果：加入三 个元组；增加一个元组；加入一个元组和删除现有的一个元组；删除以前的一 个元组( 有较早的有效时间) ( 也许一开始它就不应该存在) 。每个修改操作都 要复制历史关系，然后对新产生的历史关系进行修改。 晴尔滨理r 大、毒t ：学顺i 。学“，【夸殳 凰回国露 一竺竺 图2 - 5 时态关系 f i g 2 - 5t e m p o r a lr e l a t i o n 2 5 时态数据库的特点及重要意义 2 5 1 时态数据库的特点 时态数据库技术已成为一个诱人且活跃的研究领域，时态数据库有下列几 个方面的特性： l 动态性：传统的数据库系统对数据进行静态或者动态的数据库管理。在数 据库更新对，过时的数据将从数据库中删除，这就不能反映出现实世界的动态 过程。而在时悉数据库中，过时的数据不再从数据库中删除，对历史数据也可 以进行更新。它能将整个变更过程都保存下来，使系统和现实世界一直都保持 着全方位的动态交换。 2 全面性：由于时态数据库是所有数据的集合体，可以提供任何时刻和时间 段的数据，使数据库成为真正意义上的数据库，这是传统数据库无法比拟的。 2 5 2 时态数据库的重要意义 时态数据库在下面两个方面具有重要意义： l 使数据库成为真正意义上的资源清单。目前的数据库基本上不存储旧