（计算机软件与理论专业论文）基于4r树双时态索引的研究与改进.pdf

哈尔滨工程大学硕士学位论文 摘要 4 r - 树索引是当前较为实用的双时态索引技术，它由r i 、1 1 2 、1 1 3 和r 4 四棵相互独立的r - 树构成。4 r - 树索引能够有效地处理时间变元n o w 和c ，c ， 且可在任何支持r 树的数据库管理系统上使用。 4 r 树索引中的r 2 树负责索引时间区域为线段的数据，但由于r - 树本身 对线段索引的缺陷，致使在r 2 树上查询时需要大量不必要的i o 操作，进而 影响了4 r 树索引的整体查询性能所以，本文主要针对r 2 树查询性能较差 的缺点提出了改进方案。该方案的主体思想是将i t 2 树上中间节点中的索引 项和叶子节点中的数据项所包含的最小边界矩形由原来的二维空间有效 时间维和事务时间维，提升至三维空间有效时间起始值维、有效时闯截 止值维和事务时间维。这样，r 2 树所负责索引的双时态数据经4 r 数据变换 消除时间变元后在该三维空间上的时间区域表现为空间点，而不再是原先二 维空间上所表现的线段。改进后的r 2 树回避了r - 树在二维空间上对线段索 引的劣势，充分利用了其在三维空间上对点查询的优势 本文最后，直接利用实验对改进后4 r - 树索引的整体更新和查询代价进 行评测。由于4 r 树索引的4 棵r - 树之间是相互独立的，且本文只改进了1 1 2 树，所以改进后4 r 一树索引整体性能的变化也正反映出了改进后r 2 树的性能 变化。实验结果表明，改进后4 r 树索引虽然在更新代价上有所提高，但是 却非常有效地抑制了查询代价，使得4 r 树索引整体查询性能提高了许多， 这同时也表明了改进后1 1 2 树的查询性能得到了提高的。 关键词：双时态索引；4 r - 树索引：时间变元；r - 树 哈尔滨工程大学硕士学位论文 a b s tf a c t 4 r - t r i n d e xi sap r a c t i c a lb i t e m 删i n d e x , w h i c he o n s i 哟o ff o 叫r - t r e e s n a m e dr 1 ，r 2 ，r 3a n dr 4r e s p e c t i v e l y h 锄h a n d l et i m e - v 鼬l en o wa n du c e t f i c i 训y , a n dc a nb ee r a p l 州i na n yd a t a b a s em a n a g e m ts y s t e mt h a t 酬唧肿r t r o e t r e e1 1 2i n d e x 嚣d a t aw i 血n 触f 嘲t r a n s a e f i o n - t i m ei n t e r v a l sb yp h y s i e a l l y s t o r i n go n l yv e r t i c a ll i n e s ，b u to w i n gt ot h ed i s a d v a n t a g et h a tr - t r e ec 锄n o ti n d e x l i n e sc 衢c i 吐y ，t h eq u e r yp 口如m a n i n 心o e1 1 2i st o ob a d , t h i sm a yh 孙俺t l a c l e v c r 鸵e f f e c to nt h ep e r f o r m a n c eo f4 r - t r e ei l l d c x h c n e e , t h i sp a p 盱p r o _ v i d e sa l l n i t or e d u c et h eq u e r yc o 哟i nt r e er 2 黜i s 蛐c d b yt r a n s f o r m i n gt h e m i n i l n l l m d i n g 曲m g l 髂o ft h ei 耐麟i t e m sj nn o n - l e a fn o d e sa n dt h ed a t a i t e m si n l e a fn o d 船f r o mt w od i m e n s i o n s , t h a ti sv a l i d - t i m ed i m c o s i a n d t r a n s a c t i o n - t i m ed i m e n s i o n , t ot h r e ed i m e m i o m , t h a ti sv a l i d - s t a r t - t i m ed i m e n s i o n , v a l i d - - e n d - t i m ed i m e m i a n dt r a n s a c t i o n - t i m ed i m e l 2 s i o o s ot h a t , l i s l m i i n c l u d e st h et r a m f o r m a ：i i o no f t l a e 栅o - d i m e m i o n a li n t e r v a l sf r o mt h eo r i g i n a ln r 2i n t ot h et l a r e e - d i m e m i o m lp 妇t sa n dt h ea e e o m l 瑚y i n gq u e r yt r a m f o r m a t i o m n 峙m o d i f i c dt r c e1 1 2t a k e sa d v 哪o fi 扭卸丘d 枷p o m t - s e a r e hi n n e e - i i m 髓s i a ls p a c ei n s t e a do f i n t c n r a l - s e a r c hi n 铆o - d i m e m i o n a ls p a c e b e c a m ee a c hr - t r e ei n4 r - t r e em d e xi su n a t t a e h e dt oo 由e 舟a n do n l yt r e er 2 i sm o d i f i e d , t h em o d i f i e d4 r - t r e ei n d e xi sd i r e c t l yt e s t e di nt w oa s p e c t so f 础 c o s t sa n dq u e r yc o 啦t od e m o n s t r a t et h ep e r r o r m 嘁o ft l a em o d i f i e d 仃e er 2i n t h ee n do ft h i sp a p e r , c o l l u d e df r o mt h ea ( p 目i n 姗伽他鲫，t h e 侧u l ，d 啦 s t so f4 r - t r e ei n d e xi n c l e a t l eal i t t l e , b u tt h eq u e r y 啦r e d u c e 瑚陀a tt h e s a m et i m e 9t h i sc o n c l 璐i a l s or e f l e c t st h a tt h eq u e r ye f f i c i 鼬e yi nt h em o d i f i c d l a c er 2i si m p r o v e d k e y w o r d $ ：b i t c m p o r a li n d e x ；4 r - t r e ei n d e x ；t i m e - v a l i a b l 髓；r - t r e e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 陋 字7， 签 聊 辫 呻 者 期 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 时间是自然界无所不在的一种客观属性，任何信息都具有其相应的时间 效应。随着数据库与信息技术的广泛应用与深入发展，信息系统面临着许多 新的应用和需求，对时态信息处理的需求也越来越迫切，特别是在电子政务、 数据仓库、决策支持系统等信息领域。然而，传统数据库中记录的信息均是 对象在一个非特别指定时刻( 通常是接近当前状态的最近时刻) 的快照，但 是却被认为是其当前的状态对于一些传统的信息管理系统应用而言，这己 满足应用需求，可对许多新的尤其是现代应用而言却是不够的，因而人们很 早就开始了时间( 或时态) 信息管理的研究，于是时态数据库也就应运而生 与传统数据库不同，时态数据库不仅需要记录其所管理数据对象的当前 信息，也要管理对象的变化历史所以，随着时间的流逝，新的数据对象的 相关信息或已记录在数据库中的旧数据对象的新状态信息会源源不断地进入 数据库，而数据库中的当前数据又逐渐变为历史数据。这样，时态数据库所 管理的数据只会不断增加而不会物理删除因此相对于传统数据库而言，时 态数据库所需管理的数据量要大得多，通常会达到g b 级那么，如何保证 时态数据库在大数据量下的高效查询。是时态数据库管理系统( t e m p o r a l d a t a b a s em a n a g e m e n ts y s t e m ，t d b m s ) 必须考虑与解决的首要问题。 而且，由于时态数据库中引入了有效时间和事务时问的二元结构，使得 其所管理的所有数据均具有了时态效应，所以导致时态数据库中的基本操作 ( 如数据查询、插入和删除等) 都具有了新的含义。这就使得应用于传统数 据库中的常规索引技术( 如h a s h 和b 树等索引方法) 已不能满足时态数据 库高效查询的要求。 所以，对于时态数据库索引技术而言，在不能引用现有传统数据库的索 引技术后，对其进行积极地研究是非常重要的，这对时态数据库实际应用与 哈尔滨工程大学硕士学位论文 推广有着重大的意义。 1 2 国内外研究现状 由于传统数据库的索引技术己不能满足时态数据库索引的要求，所以， 国内外相关人士都在进行研究，以希望提出一种高效、实用的时态索引技术。 但由于时态数据库相关课题在国内开始研究时期比较晚，大量的技术研究主 要还是集中在国外下面，就双时态索引技术，简单地介绍一下国内外的研 究状况。 在国外，对双时态索引技术研究的专家很多，也提出了不少的时态索引 方案。在这其中，比较有代表性的主要有以下几种方法。 在2 0 世纪年代末期，由n o r b e r tb e c k m a n n 等人在文献【l 】中提出了以 空间索引技术r - 树来索引双时态数据的方法，将双时态看成一个二维空间。 但是r - 树索引方法只适用于双时态固定值的索引，不能有效处理时间变元 n o w 和u c 的问题。之后，随着r 树变体的不断出现，如r + 树”、r 一树等 等，有人又将这些变体引入到了双时态索引中，但它们都没有很好地解决时 间变元的问题。 ， 在2 0 世纪9 0 年代，k u m a x ，v j t s o t 瑚，c f a l o u t s o s 等人提出了2 r 树 索引m 。该方法主要思想是：采用前、后两棵r 树，其中前r 树用来索引所 有带变元的双时态数据，而后r - 树则索引所有固定的双时态数据。但是，2 r - 树也只能处理事务时间变元u c ，而不能处理有效时间变元n o w 之后，r a s ab l i u j u t e ，c h r i s t i a ns j e n s e n 等人在文献【4 】中提出了g r - 树索 引方法。该方法对r - 树的功能进行了扩充，使其能够既可以有效处理有效时 间变元n o w 和事务时间变元u c 的双时态数据，又可以处理一般的双时态数 据，是一种较优的双时态索引方法。但是，由于当前还没有一个数据库管理 系统( d a t a b a s em a n a g e m e n ts y s t e m ，d b m s ) 对这种索引提供支持，因为如 果要将g r - 树索引技术应用到数据库o r m ：l e 、s y b a s e 等中，则需要扩充d b m s 的内核。为了解决g r - 树索引实用性较低的问题，随后他们又进一步提出4 r 树索引w ，其索引效果与g r - 树相当，又可应用于支持r 树的d b m s 的上层， 如i n f o n n i x ，来进行索引该索引方法的实现比( 3 r - 树索引简单且又有比较 2 哈尔滨工程大学硕士学位论文 成熟的r - 树作为基础，所以4 r 树索引也是一种较优的双时态索引技术。但 是，4 r - 树索引并不能对所有双时态数据建立索引，且查询时只限于查询当前 和过去的数据，并且其中有些r 树的查询性能较差 在国内，对双时态索引的研究并不是很多，其中比较有代表性的是由周 风华、汤庸与康向锋针对4 r - 树索引的缺点提出的g 4 r - 树索引”。该方法克 服了4 r 树索引的不足，使其可以对所有双时态数据建立索引，并扩充4 r 树索引的查询功能，使其可以查询将来的情况。 1 3 研究意义及热点 传统常规的索引技术所能索引的数据值都能按照某种规则完全排序。但 是时态数据库与传统数据库不同，由于其引入了有效时间和事务时间两个维 度，所以可以将之看作一个二维数据库。该数据库中时间区间特有的特性( 如 重叠、包含等) 将使得传统的索引技术很难有效地对时态数据进行索引 首先，时态数据库索引需要搜寻的属性类型有效时间和事务时间， 大多数情况下它们都是一个时间区间而不是一个时间点。通常，各个数据对 象的有效时间区间和事务时间区间都以任意的方式重叠着，这样就不可对这 些时间区问进行完全排序。所以，传统的索引技术已不再适甩。 其次，基于对时态数据库特性的考虑，数据库中的更新操作是以一种添 加的方式执行的，各时态数据对象的旧映像依然保存在数据库中。因此，针 对数据对象的过去映像，其删除操作并不是真正意义上的删除，只是对原有 数据对象截止时间进行的修改；相应的，对于数据对象的插入也不是真正意 义上的插入，大部分情况下也只是延长原有对象的截止时间。同时，时态数 据库的搜索条件也与传统数据库不同，时态数据库中的搜索条件往往是要求 提取出某一特定时问区间中满足某一特定条件的数据对象。一个特定时间区 间是许多时间点的集合，目前的索引技术还不支持对某一集合的搜索m 。所以， 对时态索引的研究是必要的，而双时态索引在数据库中普遍存在，对它的研 究是时态索引研究的重中之重 目前，双时态数据索引技术研究的热点及发展趋势主要有以下几个方面： ( 1 ) 双时态数据中存在着两个重要的时间变元- d ，和功巴它们的 3 哈尔滨工程大学硕士学位论文 值会伴随着当前时间c t ( c t a - r e n tt u n e ) 的变化而变化。也正是因为这两个 变元的存在，才使得时态数据库中的时态数据的管理变得更加符合实际和高 效。但是，另一方面，也正因为这两个变元，使得双时态索引变得比较困难。 所以，对于能够同时有效地处理咖和嘲个变元的双时态索引的研究是比 较热门的 ( 2 ) 由于时态数据库中存储的数据，可能存在某数据对象的某个状态在 现实世界中还没有为真，但是却已经成为了数据库中的一条当前记录在该 状态在现实中存在之前，数据库应该支持对这种情况的查询。但是，现在的 索引技术绝大多数只能查询当前和历史数据，而不支持对将来查询m ( 3 ) 现今的双时态索引技术大多数都是以空间索引r - 树为基础来建立 的，它们在查询时只考虑了相交查询，并未考虑完全包含查询的情况 1 4 研究内容及论文结构 在现有的双时态索引技术中，4 r 树索引有较好的综合性能以及较强的实 用性。但是，它也存在一些不足，如4 r - 树索引中的r 2 树的查询成本代价较 高，查询时需要大量的磁盘f o 操作等。本文就是在对4 r - 树索引进行研究 与分析的基础上，对该r 2 树进行了改i 争一以在三维空间上对空间点的索 引来代替在二维空间上对线段的索引，充分利用r - 树能有效索引数据点的特 性来提高r 2 树的查询性能。 。本论文内容组织如下： 第1 章分析了课题的研究背景以及国内外研究现状，阐述了该课题研究 的热点与难点，并介绍了课题研究的主要内容。 “ 第2 章介绍了时态数据库的相关基础概念以及四种比较典型的时态表示 模式。 第3 章首先介绍了r 树的数据结构及其特点，然后对以r 树为基础结构 的2 r - 树和g r - 树双时态索引技术进行了简要说明。 第4 章介绍和分析了4 r 树索引技术的建立过程，并在此基础上对其中 一棵名为r 2 的r 树进行了改进，提出了具体的改进方案。 第5 章通过具体实验来验证4 r 树索引改进方案的优越性。 4 哈尔滨工程大学硕士学位论文 第2 章时态数据库 传统的数据库管理系统只反映了一个对象在其发展全过程中某一个时刻 的状态，并不能很好地反映与存储其过去和未来的相关信息。所以，随着数 据库技术的广泛应用，人们对时态信息的管理提出了两个要求：一是要求管 理被处理事件的历史性信息；二是要求管理数据库系统中元事件的时态信息 一。为此，引入了时态数据库的概念。 2 1 基本概念 时态数据库中比较基本和关键的概念，主要包括时间模型( t u n em o d e l ) 、 事件( e v e n t ) 和状态( s t a t e ) 、时间粒度( 髓mg r a n u l a r i t y ) 与时间量子 ( c h r o n o n ) 、有效时间( i dt u n e ) 与事务时间( t r a n s a c t i o nt i m e ) 2 1 1 时间模型 时间模型即是对时间轴的结构或是时间表示模式的选择。时闻模型按照 时间轴的结构主要可以分为以下几种：连续模型( c o n t i n u o u sm o d e l ) 、步进 模型( s t e p w i s em o d e l ) ，离散模型( d i s c r e t em o d e l ) 和恒定模型( n o nt e m p o r a l m o d e l ) 一连续模型是将时间与实数建立对应关系，每个实数对应于一个时 间点。因此该模型在时间轴的两个时间点之间是可以存在其他时间点的，通 常适用于许多实时控制场合步进模型把数据的状态看成一个时间的函数， 当时间点上的数据状态发生变化时才记录状态变化信息，否则保持不变。该 模型不可以在任意两个时间点之间通过插值的方法来进行取值。离散模型将 时间看成是与整数同构的，且在相邻的两个时间点之间不存在其他时间点， 任一时间点都有前驱和后继。该模型适用于记录那些在关键时间点上才有意 义的数据。恒定模型主要是在数据不随时间变化的情况使用，这些数据只有 本身固有的属性，7 并不存在时态属性。 5 哈尔滨工程大学硕士学位论文 2 1 2 事件与状态 事件和状态是时态数据库中最重要的一对基本概念之一事件和状态具 有二重性和二元性。一个对象( 实体) 在其生命期( 1 i f e - s p a n ) 里有不同的状 态，事件是对象从一个状态变化到另外一个状态的过程一般来说，在数据 库中事件采用时刻的方式表示，而状态则采用时间区间表示，类似于空间中 的点和线的关系。事件和状态具有二元性，由事件可以导出状态，由状态可 以导出事件。但两者不是对等的，一个事件的产生标志着一个状态的开始， 相应的另一个事件的产生，标志着该状态的结束m 事件和状态是可以相互转 换的，当事件以一个更小的时问单位来表示时，事件就变成了一个单一状态 2 1 3 时间粒度与时间量子 时间粒度是指描述时间数据的最小时间单位，表示了时间点之间离散化 的程度。它反映了时态信息系统中时间点描述的最小单位时间粒度越小，离 散的时间点就越多，描述的事件变化的信息就越精细准确；反之，描述的事 件变化的信息越粗糙。时间量子是计算机所能支持的最小的、不可分割的时 间间隔。客观世界中的时间，离散化的程度可以任意小，但是计算机系统的 离散化程度是受到机器性能的影响与制约的。可见，时间量子是系统记录时 间属性的精确程度的一个度量，时间量子越小，系统记录的精确度就越高w 所以，时间粒度的大小是要受到时间量子的限制的。 2 1 4 有效时间与事务时间 有效时问i r a - u 是指一个对象( 事件) 在现实世界中存在的那段时间，或者 该对象在现实世界中为真的时间。它既可以是过去和现在的时间，也可以是 将来的时问。有效时间可以是单一的时间点、单一的时间区间，或者是时间 点的集合、时闻区间的有限集合，也可以是整个时间域。也就是说，元组的 属性可以在任意的时间点、任意的时间区间里取值为真。与用户自定义时间 6 哈尔滨工程大学硕士学位论文 不同，当查询语句被检测到有时态语义的时候，有效时间是由数据库系统解 释的，而且有效时间是可以被更新，其提供和更新是由用户来完成的n ， 有效时间，常用 f r o m ，t o 区间来表示，其中f r o m 表示有效时间起始值， 而为有效时间截止值，即事物处于某一状态时的起始时间和截止时间但是， 由于在实际应用中，存在截止时间为未来某个未知时刻的情况。所以，引入 了时间变元n o w ( 。一该值会随着当前时间的变化而变化，记录着随时间变化 的信息，它的有效值依赖于当前时间。时间变元n o w 的使用避免了时态数据 库频繁更新时间的问题，因此在时态数据库中应用变元n o w 是非常便利和实 用的。 事务时间”是指对一个数据库对象进行操作的时间，是一个事实存储在 数据库中的时问，它记录着数据库修改或更新的各种操作历史，对应于现有 事务或现有数据库状态变迁的历史m 。例如，对象录入数据库的时间，对象修 改的时间，对象删除的时间等。与有效时间不同，数据库中的数据录入、修 改和删除等操作的事务时间是由系统时钟决定的，用户是不同填写与修改的 处理事务时间的方法是存储所有数据库的状态，即每处理一个事务就存储一 个数据库状态，而修改只能对最近的状态进行，但是可以查询任一状态。 事务时间，一般用 s t a r t , s t o p 时间区间来表示，其中的s t a r t 表示事务时 间起始值，s t o p 表示事务时间截止值在表示事务时间截止值时，引入了一 个时间变元u c ( u n t i lc h a n g e d ) ( a , c t u f 。它有比时间变元n o w 更精确的解释语 义，并与之相区别。当在时态数据库中插入一个元组时，将s t a r t 值初始化为 插入时的当前时刻值，s t o p 值记为u c 当删除该元组时，则将该元组的s t o p 值u c 改为当前删除操作的时刻值，这表示该元组在逻辑上已被删除，不属 于当前数据库状态 2 2 时态数据库分类 当前，时态数据库通常都是在传统数据库的基础上引入有效时间维和事 务时间维来形成的这样，数据库不仅可以表示当前数据，还能反映出数据 对象的变化历史。按照数据库对时问维的支持能力，可以将数据库分为快照 数据库、回滚数据库、历史数据库和时态数据库“四种类型它们都属于时 7 哈尔滨工程大学硕士学位论文 态数据库的范畴，而且其发展过程也正反映了时态数据库的发展历程 2 2 1 快照数据库 快照数据库( s n a p s h o td a t a b a s e ) 是以在特定时刻的快照来建模所考虑 的现实世界，即快照数据库只表示建模世界的“最近”快照。数据库的状态 就是它的当前内容，而这个。当前”状态并不一定就反映了现实世界中的当 前状态。而且，快照数据库不涉及现实世界的动态变化，所以这种数据库又 叫“静止”数据库。所有的传统数据库均属于这类数据库，之所以将它算在 时态数据库的范畴，是因为它也支持一种时间维用户自定义时间”，。 2 2 2 回滚数据库 回滚数据库( r o l l b a c kd a x a b a s e ) 支持事务时间，它按事务时间编址，将 过去每次事务提交、状态演变之前的状态保存这种数据库由“回滚关系” 组成。一个“回滚关系”是一种三维结构，可当作是一个按时问编址的快照 ( 静态关系) 的序列，即一个“立方体”通过沿事务时间轴向后移动并切取 。立方体”的一个垂直片，则可得到该回滚关系作为在过去某个时刻的一个 快照，并可对其查询，这种回溯和切取垂直片的操作称为“回滚”，支持这种 回滚操作的数据库就称为回滚数据库”1 回滚数据库的优点是支持事务时间，并可进行数据库历史状态的查询。 但是，它也存在明显的不足： ( 1 ) 不能记录数据对象在现实世界中的变化信息。回滚数据库因为是按 照事务时间进行编址的，所以其所记录的是数据库状态变迁的历史，而不是 现实世界的历史虽然现实世界中某元组的属性在某时刻改变了，但由于数 据库在该时刻没执行事务，所以该元组时态属性的变化在数据库中并无体现 ( 2 ) 不可更正过去元组的错误信息，只能查看。当发现元组有错误的时 候，如果此事务已经提交，只能等待下次系统事务时间时对当前状态进行改 动，不可改变过去的任何状态。但是，可以对过去元组信息进行查看。 ( 3 ) 回滚数据库中数据冗余太多在前一个事务时间内提交的数据，即 i 哈尔滨工程大学硕士学位论文 使在下一个事务时间时没有改变或改动很小，也需要重新输入与储存所有数 据，这种冗余是较大的，特别是在时变较小的情况下 2 2 3 历史数据库 记录事实的有效时间的数据库称为历史数据库( h i s t o r i c a ld a t a b ；a 辩) 。它 是由。历史关系”组成的，每一个元组记录了数据的一个“历史”状态。历 史数据库存储和管理客观对象在有效时间点的事件或状态变化的经历，它可 以被看作记录了事实在真实世界的变化过程。历史数据库是可以任意修改的 ( 包括以前的记录) ，但是历史数据库无法记录数据库的修改历史。因此，在 历史数据库中有效时间的修改历史也是不能被记录的 历史数据库的特点是支持有效时问，数据冗余度小，且结构相对简单。 但是也存在不足，主要不足之处是：不支持事务时间，不能像回滚数据库一 样对以前的某个状态进行查询w 。 2 2 4 时态数据库 时态数据库( 也可称为双时态数据库，b i t e m p o r a ld a 舡i b a 辩) 既支持事务 时间又支持有效时间。时态数据库由“时态关系”组成，一个时态关系是一 个四维结构，其中两维是属性与元组，另外两维是事务时间和有效时间。当 然，一个时态关系也可想象为一个历史关系的序列，对时态关系的回滚操作 则是选取一个特定的历史关系，可对该历史关系进行查询，而每一事务则引 起一个新的历史关系的建立m 时态数据库集成了以上三种数据库的功能特 性，存储了数据库和现实世界两者变更的历史这种数据库才是真正的对数 据时态属性支持的数据库，不过它是以牺牲大容量的储存空间为代价的。 2 3 时态数据表示模式 目前，时态数据库中时态数据表示模式一般是在关系模式的基础上通过 添加时态属性来实现的。现有的数十种时态数据表示模式可以分为两类：一 9 哈尔滨工程大学硕士学位论文 类属于i n f ，即元组时标；另一类则属于n 1 n f ，即属性时标m 1 。目前尚未出 现统一的时态表示模式，只有c h r i s t i a ns j e n s e n 和砒c h a r dt s n o d g r a s s 在这方 面做了些工作。开发了一个b c d m 概念模型n 来统一这些表示模式。b c d m 模 型主要是用来阐明时态数据的本质，不用于具体实现。概念模型和表示模型 之间，用快照相等来进行映射。快照是在时闻点上的切片，如果在所有的时 问点上的快照都相等的，那么这两个模型的表示的内容是一致的。现今比较 富有影响力的时态表示模式有：s n o d g r a s s 的元组时标表示模式，j e n s e n 的 b a c k l o g 表示模式，g a d i a 的属性时标表示模式以及b e n - z v i 的元组时标表示模 式。 2 3 1 $ n o d g r a s s 的元组时标表示模式 s n o d g r a s s 的元组时标表示模式属于1 n f 表示。双时态关系模式剐娶有属性 a ，如，厶，乃其中腥定义在双时态元素域上的时标属性。用s n o d g r a s s 的元组时标表示模式来表示震如下： r = ( 4 ，4 ，z ，互，匕，k ) 这里瓦，k 是原子值，其含义分别是：疋为事务时间开始值，l 为事务时问截止值，k 为有效时间开始值，k 为有效时间截止值。这里事务 时伺起始值是事实在数据库中被记录的时间，事务时间截止值是记录被逻辑 删除的时间w 。该表示模式下的插入、删除与修改等基本操作执行情况如下： ( 1 ) 插入操作 当插入一个事实时，先查看数据库中是否存在相同内容并且事务时间截 止值为时间变元矾珀q 元组存在。如果存在，则在待插入的有效时间中去掉重 叠的部分，将待插入的有效时间用有效时间元素来表示，然后将每个有效时 间元素与插入的内容形成元组插入。否则，直接插入元组信息即可 ( 2 ) 删除操作 删除是将元组中的事务时间截止值u c 以当前时间值( 确定时刻值) 替代 ( 3 ) 修改操作 修改是删除和插入的组合，先删除当前版本，然后进行插入操作。 例2 1 ，小王在某公司工作，经常要求出差，从1 2 到1 7 号他在北京出差。 1 0 哈尔滨工程大学硕士学位论文 人事部门在7 号对此信息进行了记录。人事部门后来发现对小王的出差时间记 录有误，应该是从7 到2 2 号，在1 2 号时对信息进行了更正。后来人事部门又发 现更正后的信息是错误的，小王的出差时间确实是从1 2 号到1 7 号该信息在 1 7 号得到更正现在出差有效时问是正确了，但是却又发现小王的出差地点 不是北京，而是天津，于是做出修改，增加一个事实( 小王，天津) 到数据 库中，该操作进行的时间为2 2 号。同一时间，人事部门收到确认另一雇员小 张将从2 5 号到3 0 号被安排到北京出差，于是将该信息记录到数据库中现当 前时间为2 2 号用该模式表示的记录如表2 1 所示 表2 1s n o d g r a s s 元组表示模式 e m p l o y e e p l a c e l疋k圪 小王北京 7l l1 2 1 7 小王北京1 21 672 2 小王北京 1 72 11 21 7 小王天津 2 2c 7 c1 21 7 小张北京2 2c ，c2 53 0 2 3 2d e n s e n 的基于b a c k i o g 表示模式 b a c k l o g 也是一个双时态关系，它与前面的时态关系模式的不同在于：在 这个关系模式中元组只能追加，而不能修改这种表示模式能记录操作日志， 但是由于它只能增加，会导致数据量不断增大用b a c k l o g 关系模式来表示双 时态关系如下； 太= ( 4 ，4 ，屹，屹，l o p ) 其中，圪为有效时间起始值，k 为有效时间结束值，功事务时间，用来 记录元组插入的时间，却表示操作标识( i 表示插入，d 表示删除) 。插入的 事实在数据库中的当前时间是从插入时的事务时问起始值到删除时的事务时 间截止值为止。显然这个表示模式是基于事件的w 在该表示模式下的插入、 删除与修改等基本操作执行情况如下： ( 1 ) 插入操作 哈尔滨工程大学硕士学位论文 当插入一个事实时，首先查看是否有相同内容且事务时间截止值为时间 变元u c 的元组存在，如果存在则在待插入的有效时间中去掉重叠的部分，将 去除重叠后的待插入有效时间以有效时间元素来表示，然后将每个有效时间 元素与待插入的事实内容形成元组，进行插入否则，直接插入该事实即可 ( 2 ) 删除操作 删除操作首先需要检索整个关系表，找到显式属性与要删除的事实属性 与有效时间均相同的记录，并确保被定位的当前记录没有被删除 ( 3 ) 修改操作 修改操作是删除和插入操作的结合，先删除当前版本，后插入新版本 例2 1 用b a c k l o g 模式表示，其具体表示情况如表2 2 所示。 表2 2 b a c k l o g 关系模式 e m p l o y e e p l a c e 匕匕 r o p 小王北京 1 21 75i 小王北京 1 21 71 2d 小王北京7 2 21 2 i 小王北京 7 2 21 7d 小王北京 1 21 71 7i 小王北京1 21 7 2 2d 小王天津 1 21 72 2i 小张北京 2 53 0 2 2 i 2 3 3g a d i a 的属性值时标表示模式 属性时标属于n i n f ( 即非l n f ) ，n i n f 将有关一个对象的所有信息都放 在一个元组中，其表示比较灵活。这种方法的重要特性是关系可以被重新组 织，但是操作比较复杂w 以c r d d i s t 的属性时标表示模式来表示r 如下： 置= ( ( 【z ，t a x v , ，k 】4 ) ) ， ( 【，】【k ，匕】4 ) ) ) 震中的每个元组都是由几个集合组成，每个集合元素又是由事务时阅区 间【死明和有效时间区间【吲组合构成。 1 2 哈尔滨工程大学硕士学位论文 例2 1 用属性时标表示，可以按职工姓名、出差地点或职工姓名和出差地 点来组织，其具体表示分别详见表2 3 ，表2 4 与表2 5 ( 1 ) 按职工姓名来组织( 一个元组包含职工所有的出差地点) 表2 3 按职工姓名组织 e m p l o y e e p l a c e 【7 。i l 】【1 2 , 1 7 】 小王 f 7 ，“】x 【1 2 , 1 7 北京 【1 2 ，1 6 】【7 ，2 2 1 小王 1 1 2 , 1 6 。f 7 2 2 】 北京 【1 7 ，2 1 】x 1 2 。1 7 】 小王 1 7 。2 1 】x 【1 2 1 7 】 北京 2 2 ，u c x 【1 2 ，1 7 小王 2 2 ，u c x 【1 2 ，1 7 】 天津 2 2 ，u c 2 5 ，3 0 小张 2 2 。u c 。 2 5 ，3 0 】 北京 ( 2 ) 按出差地点来组织( 一个元组中包含在该地出差过的所有员工) 表2 4 按部门组织 p l a c e e m p l o y e e f 7 ，h ix 【1 2 , 1 7 】北京 1 7 ，i i l 【1 2 , 1 7 】 小王 【1 2 ，1 6 f 7 ，2 2 】 北京 【l2 ，1 6 f 7 ，2 2 】小王 【l7 2 1 1x 【1 2 ，l7 】 北京 【1 7 , 2 1 x 【1 2 ，1 7 小王 1 2 2 ，u c x 【2 5 ，3 0 l 北京 c 2 2 ，u c x 【2 5 ，3 0 1 小张 2 2 ，t c x 【1 2 ，1 7 】 天津 【2 2 u c x 【1 2 , 1 7 】 小王 ( 3 ) 按职工姓名和出差地点来组织 表2 5 按姓名和部门组织 函甲协w p l a c e 【7 ，i i 】x 1 2 ，1 7 1 小王 【7 ，i i 】x f l 2 ，l 刀 北京 1 2 ，1 6 】x 【7 ，2 2 】 小王 【1 2 1 6 】x 【7 ，z 2 北京 【1 7 2 l 】【1 2 ，1 7 】 小王 【1 7 ，2 1 】f i e ，1 7 】 北京 2 2 ，u c x 【1 2 ，1 7 】 小王 【2 2 ，u c x 【1 2 ，1 7 】 天津 2 2 ，v c 3 2 5 ，3 0 1 小张 2 2 ，u c lx1 2 5 ，3 0 】北京 哈尔滨工程大学硕士学位论文 2 3 4b o r r - z vi 的元组时标表示模式 b e n - z v i 的元组时标表示模式属于1 n f ，双时态关系鼬勺表示模式如下： 太= ( 4 ，4 ，瓦，巧，乙，砭，瓦) 其中，瓦表示有效时间起始值，表示有效时间截止值，记录存储 的时间，记录瓦存储的时间，死表示逻辑删除的时间。z 0 ，不一定同时 记录，用“- ”表示没有记录”。例2 1 用b , m - z v i 元组时标表示，如表2 6 所示 表2 。6b e n - z v i 元组时标模式 e m p 妨e e p l a c e兀k 乃 小王北京 1 271 771 2 小王北京 71 22 2 1 2 1 7 小王北京1 21 71 71 7 2 2 小王 天津 1 2 2 21 72 2 小张北京 2 52 23 02 2 以上四种时态数据表示模型都是在传统关系模型的基础上通过时态扩展 形成的，都支持事务时间和有效时间。元组时标数据模型即l n f 模式，保持 了关系模型的简单性属性时标数据模型即n 1 n f 模式，在一个元组中记录了 有关对象的所有信息；b a c k l o g 易于实现，保持了可操作性及较高的查询效率。 从总体来讲，元组时标表示模式操作相对简单，而属性时标则较为复杂m ， 2 4 本章小结 ， 本章首先给出了时态数据库的一些基本概念。然后，在此基础上，对快 照数据库、回滚数据库、历史数据库和双时态数据库进行了简要的介绍随 后，介绍了四种时态数据表示模式：s n o d g r a s s 的元组时标表示模式、j e n s e n 的基于b a c k l o g 表示模式、g a d i a 的属性时标表示模式和b e n - z v i 的元组时标表 示模式，并分别使用它们对同一时态数据信息进行了描述。 1 4 哈尔滨工程大学硕士学位论文 第3 章双时态索引技术 双时态索引m t 是一种快速查询技术，是时态数据库管理系统解决查询效 率的重要手段。当前，存在大量的双时态索引技术，较为典型的有2 r - 树索引 和g r - 树索引等。这些双时态索引技术大部分都是建立在r - 树* w 数据结构基 础上的。所以，本章首先将对r 树进行介绍，然后再对2 r - 树索引和g r - 树索 引进行简单的说明 3 1r - 树索引 r - 树最早是由q 蚰啪在1 9 8 4 年提出的，主要是用于对空间数据的索引 t t a - l t ! 但是，由于时态数据库中的时态数据一般是由有效时间和事务时间组成， 所以可以将这两个时间分别看成维度，这样时态数据也具有了二维性。因此， r 树也是可以用来索引时态数据的 3 1 1r 一树的数据结构 r 树在结构上类似于b 树，只不过b 树是用于一维数据的索引，而r - 树 是用于多维空间数据的索引，它是在b 树一维数据索引上的扩充。& 树中的 节点是一个数值( 关键字码) ，而r 树的节点是一些矩形由于时态数据库中 的时态数据是由有效时间和事务时问组成，也就具有二维的特性，所以其节 点也是一个矩形。 对于一棵肘阶的r - 树而言，该树中节点的数据结构所包含的信息格式如 下： 叶子节点：( c o u n t , l e v e l , , , ，) 脚 纠 中间节点：( c o u n t , l e v e l , , , c p i 扭r p ) 其中， 称为数据项，0 1 , 为空间目标对象的标识，即指向目标 对象存储地址的指针，m b r ，为该目标对象在n 维空间中的最小边界矩形 1 5 哈尔滨工程大学硕士学位论文 ( m i n i m u mb o u n d i n gr e c t a n g l e s ，m b r ) ，这里简称为数据矩形。 称为索引项，c 只为指向子树根节点的指针，懈最代表其子树索引空间，为 包围其子树根节点中所有目录矩形或数据矩形的最小边界矩形( 简称为目录 矩形) 。c o 功订兰； i 在叶子节点中表示该节点中用到的数据项个数，而在中间 节点中，则表示该节点中包含的索引项的个数，即该节点的。孩子个数。 i f , v e l 2 0 指示该节点在树中的层数，o 表示叶子节点。由于整数和指针所占存 储空间相同，且可以相互转换，因此r - 树的叶子节点和中间节点在结构上是 相同的1 。 对于上述提到的最小边界矩形，现做一下详细的解释。假设最小边界矩 形肘刀r = ( 缸而，l ，) ，其中每一个矗表示二个闭合的有限区间k ，6 d ，该 区间表示在第融匪空间上的矩形的起点和终点如果区间厶的终点值趋于无限 大的话，这就意味着被描述表示的对象在第七维空间上向外延伸的范围是不确 定的。因此，每一个空间对象都可以用一个包含指定对象的最小包围框表示， 通常也就称为最小边界矩形图3 1 中所示为一个在二维空间上的最小边界矩 形。 有界 最小边界矩形 维度。 图3 1 二维空间的最小边界矩形 综合节点结构与最小边界矩形的概念可以看出，r 树数据结构中每个节 点都对应一个矩形。对于叶子节点而言，它所对应的矩形为其所包含的所有 数据矩形的外包矩形( 必须为最小边界矩形) 对于中问节点而言，该节点对 1 6 哈尔滨工程大学硕士学位论文 应的矩形为包围其所有其予树根节点矩形的外包矩形。 3 1 2r - 树的特征 r 树的建立需要满足一定的规则。假设膨( 取决于机器磁盘页的大小和 维数捍) 为r 树节点中所包含的数据项或索引项的最大数目，而所为最小数旨 值，并且规定历m 2 。那么，r 树必须满足以下特征： ( 1 ) 每个叶子节点，若它不是根节点，则必包含m 到朋个数据项；