（计算机软件与理论专业论文）基于4r树的双时态索引扩展技术.pdf

论文题目： 专业： 硕士生： 指导老师： 基于4 r 树的双时态索引扩展技术 计算机软件与理论 周风华 叶小平副教授 摘要 时间一直贯穿客观事物发展的始终，作为记录和管理客观世界信息数据的数据 库技术，必然要将“时态”作为其理论研究和实际应用过程中的一个重要方面。由 于各种原因，当今的主流数据库，例如关系数据库以及对象关系数据库，大多缺乏 对时态数据索引的充分支持。而双时态数据和空间数据都具有“相同”的两维特征， 所以现有的时态索引技术大多是借鉴空间数据索引技术( 如r 树，r 树) ，并结合 双时态数据的特点，将其进行扩充和改进，以加快时态查询速度，提高时态索引操 作的效率，从而解决时态索引中的基本问题。目前时态数据索引技术主要是扩展r 树的功能，使其可以处理带变元的两维时间数据的g r 树，和通过变换消除变元再 利用r 树索引的4 r 树，这两种索引技术都能有效索引双时态数据，但存在以下不 足之处： 1 索引的双时态数据在有效时间终止值不确定时，要求事务时间起始值 必须大于或等于有效时间起始值。 2 有效时间变量只能取事务时间当前值。 3 只能查询当前和历史数据。 由于“1 ”，g r 和4 r 树不能有效处理双时态数据所有可能的情况；由于2 ， g r 树和4 r 树难以处理数据数据录入时刻与数据实际生效时刻之间的实时、滞后和 超前关系。由于3 ，g r 树和4 r 树不能查询将来的情况。所有这些，限制了g r 树 技术的深入研究和广泛使用。 本文在较为详细地讨论r 树，g r 树和4 r 树的基础上，根据双时态数据的特 点和时态变量的语义，鉴于4 r 树实现更为简单，所以将4 r 树进行扩充，提出了 g 4 r 树技术，解除上述4 r 树本身带来的限制，同时也较为充分地考虑到了时态变 中山大学硕士学位论文 量的语义实现。文中提出的g 4 r 树技术的基本思想是：首先通过数据变换，消除四 类双时态数据中的时间变元，然后分别对四类变换后的双时态数据建立4 个r 树索 引。查询时，对四个r 树的查询条件也要执行相应的变换，以查询到相应结果。并 且严格证明了g 4 r 树索引技术的正确性，最后通过实验验证此方法的可行性。 关键词：g 4 r 树，偏移，时态数据库，变换。 i i a b s t r a c t t i t l e ：e x t e n s i v et e c h n o l o g yo f t e m p o r a li n d e xb a s e do n4 rt r e e m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z h o uf e n g i i u a s u p e r v i s o r ：a s s o c i a t ep r o f e s s o ry ex i a o - p i n g a b s t r a c t t i m er a s st h r o u g ht h ew h o l e d e v e l o p i n gp r o c e d u r e so f t h eo b j e c t s t h et e c h n o l o g y o fd a t a b a s e ，w h i c hr e c o r da n dm a n a g et h ed a t ao fw o r l di n f o r m a t i o n ，m u s tr e g a r dt h e t e m p o r a la sa ni m p o r t a n ta s p e c to ft h e o r ys t u d ya n dp r a c t i c ea p p l i c a t i o n f o rs o m e r e a s o n ，t h em a i nd a t a b a s e s ，s u c ha sr e l a t i o n a ld a t a b a s ea n do b j e c tr e l a t i o n a ld a t a b a s e ， f a l lt oi n d e x b i t e m p o r a ld a t a a sb i t e m p o r a l d a t aa n d s p a t i a ld a t a b o t ha r et w od i m e n s i o n s ， c o m b i n e dw i t ht h ec h a r a c t e r i s t i co fb i t m e p o r a ld a t a ，n o wt e m p o r a li n d e xt e c h n o l o g i e s a l m o s ta r et h ee x t e n s i o na n di m p r o v e m e n to fs p a t i a li n d e xt e c h n o l o g y , f o re x a m p l er t r e ea n dr + t r e e ，t oa c c e l e r a t et h er a t eo fq u e r ya n di m p r o v et h ee f f i c i e n c yo ft e m p o r a l i n d e x t o d a yt h e r ei sg r t r e ew h i c hi st h ee x t e n s i o no frt r e et oi n d e xb i t e m p o r a ld a t a w i t hv a r i a b l e sa n d4 rt r e ew h i c he l i m i n a t et h et i m ev a r i a b l eb yt r a n s f o r m a t i o nf i r s ta n d t h e ni n d e xt h et r a n s f o r m e dd a t ao nr t r e e t h e y 8 u l ee f f i c i e n t ，b u ta l s oh a v e s h o r t a g e s ： 1 t r a n s a c t i o nt i m es t a r tm u s tb el a r g eo re q u a lt ov a l i dt i m es t a r tw h e nv a l i dt i m e e n di si n d e t e r m i n a t e 2 v a l i dt i m ev a r i a b l em u s t e q u a l t ot r a n s a c t i o nc u r r e n tt i m e 3 q u e r y i sl i m i t e do nt h ec u r r e n ta n dh i s t o r yd a t a g rt r e ea n d4 rt r e ef a l lt od e a lw i t ha l lb i t e m p o r a ld a t ad u et or u l e1 ；t h e ya r e l i m i t e dt od e a lw i t ht h el a g ，r e a lt i m ea n de x c e e d i n gb e t w e e nt h et i m eo fd a t ar e c o r d i n g o nd a t a b a s ea n db e i n gv a l i dd u et or u l e2 ，a n da l s ol i m i t e d t oq u e r yt h ef u t u r et i m ed u et o r u l e3 a l la b o v er e s t r i c tt h eb i t e m p o r a li n d e xt e c h n o l o g yt od e e pr e s e a r c ha n dw i d e a p p l i c a t i o n i l l 中山大学硕士学位论文 t h i sp a p e rf i r s td i s c u s sr t r e e ，g rt r e ea n d4 rt r e e ，a n da c c o r dt h ec h a r a c t e r i s t i co f b i t e m p o r a ld a t aa n ds e m a n t i co ft i m ev a r i a b l e ，t h e ne x t e n d 4 rt r e ea n d p u tf o r w a r dg 4 r t r e ei n d e x ，w h i c hi sf r e ef r o mt h el i m i to f4 rt r e ea n dc a nr e a l i z et h et e m p o r a lv a r i a b l e s e m a n t i c t h eb a s i ci d e ao fg 4 rt r e ei s ：f i r s t ，e l i m i n a t et h et i m ev a r i a b l eb ym e a n so f t r a n s f o r m a t i o n sa n dt h e ni n d e xt h er e s u l t i n gs t a t i o n a r yd a t ar e g i o nw i t hf o u rr + t r e e ，a n d q u e r yo i lt h eo r i g i n a ld a t aa r em a p p e d t oc o r r e s p o n d i n gq u e r i e so nt h et r a n s f o r m e dd a t a t h eg 4 rt r e ei n d e xi sp r o v e dt ob et r u e a tl a s t w et e s tt h ei n d e xi sv a l i d k e y w o r d s ：g 4 rt r e e ，o f f s e t ，t e m p o r a ld a t a b a s e ，t r a n s f o r m 第一章前言 1 1 时态数据库产生背景 第一章前言 时间作为宇宙问所有事物都具有的一种属性，一直贯穿着事物发展的始终。各 式各样与时间紧密相关的数据、信息及其联系无不深深影晌着人类社会生活的方方 面面。而当前最流行的关系数据库只是数据库当前状态的一个快照，不联系其过去 和未来，随着时间的推移，d m l 新提交的数据库状态将覆盖旧的数据库状态，旧 状态将永远消失，换句话说，状态的变迁是不可逆转的。 然而在现实的应用中，我们不仅需要当前时间数据，也需要过去时间数据。例 如从实际应用出发，在数据库中我们不仅需要记录数据库中数据的有效时间，还要 记录数据库的修改历史，修改记录的历史就依靠事务来维持。在医疗信息系统中我 们不仅要了解病人的当前病情，还需了解病人的病史，从而做出正确的诊断。同样 在处理自然灾害( 地震，气象，水文，洪涝等) 情况时，不仅需要有当前时间信息， 还需要这些事件的历史信息，这样才有助于通过数据挖掘、知识发现等技术揭示事 务发展的本质规律，从而预防可能的情况发生，使损失减少到最低【1 】。 时间是事物的本质属性，【2 】中指出很难找到一个与时间无关的应用程序域，很 多应用程序没有考虑时间维的情况最主要的原因是缺少支持时态模型的商业 d b m s 的产品。于是有人提出将多个不同时刻的快照数据库放在一起就构成了数据 库的历史，但是存在的一些问题是 1 】：取多大的时间间隔保存快照； 对于这些不 同时刻的数据如何进行传统的选择、投影、连接运算；传统数据库对数据库本身历 史的维护支持不足。一般只有供恢复回退用的事务日志，缺乏相应的事务查询命令。 所以建立一个与时间有关的数据库时态数据库系统迫在眉睫。 对于这些问题的思考导致了人们开始进行时态数据库的研究。 1 2 国内外研究现状 早在2 0 世纪7 0 年代初，许多学者已经开始探讨如何处理时间信息的问题。1 9 7 0 中山大学硕士学位论文 年g w i e d e r h o l d 和j f ：蹦e s 在他们开发的医疗信息系统中作了最早的尝试。 f a l k e n b e r g 在1 9 7 4 年的技术报告中讨论的d b m s 中的“时间处理”；j a b u b e n k o 和j a j r 在1 9 7 6 年的技术报告中讨论了信息建模的“时间维”问题；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 g t e m p o r a lk n o w l e d g e 的论 文【3 】。 在随后的十多年中，关于时态处理的模型引起了学者们的研究热潮，在1 9 9 3 年出版的t e m p o r a ld a t a b a s e s ：t h e o r y , d e s i g n ，a n di m p l e m e n t a t i o n l 4 1 - - 书中列出了1 3 种比较有影响的模型。其中t e m p s q kt s q lh s q l ，t q u e l ，t e e r , o o d a p l e s 几种 模型做出了实验室原型。1 9 9 8 年，在瑞士苏黎世大学诞生了一个商用的时态数据库 管理系统t i m e d b ，它构建在传统关系型d b m s 的前端，采用a t s q l 2 语言实现双 时态数据库管理系统( b i t e m p l o r a ld b m s ) 1 6 1 。 国内学者唐常杰，张师超，严小卫等也都对时态数据进行了一番研究 1 4 1 1 1 5 1 ， 在时态索引方面，最先出现的r 索引结构5 6 1 是g u t t m a n 于1 9 8 4 年提出的，它 的索引结构类似于b 树，是b 树在多维空问上的扩展，随后人们对它的算法和结构 进行了些改进，如r + 树 刀，r 。树 5 】【8 】，i - l i l b e ar 2 3 1 树等，不过它们大多数据 都保持了与原r 树相同或类似的结构特点。这些索引技术主要用两维空间索引，由 于空间数据和双时态数据的相似性，就有人提出引用r 树索引用于双时态数据的索 引，但r 树只能处理静态矩形数据，不能有效处理与n o w 相关的增长的矩形和楼 梯形时态数据问题，于是a k u m a r 提出了一个新的索引方法2 r 树【9 】和b r 树 ( b i t e m p o r a lr t r e e ) 【1 0 】，但是它们只能处理与n o w 有关的事务时间，不能处理与 n o w 有关的事务时间。随后又有【1 1 】中扩充r 树的功能使其可以处理与n o w 有 关的有效时间和事务时间，称之为g r 树( g e n e r a l i z e r t r e e ) 5 】，但是在当前基于 关系数据库的系统中g r 树还不能得到广泛应用，4 r 树【1 2 】充分利用g r 树的长处， 克服其不足，采用变换的方法将变量n o w 变换到已知值，再采用r 树的索引方法 来达到有效索引时态数据，加快了时态数据的检索速度。但是g r 树和4 r 树索引 的双时态数据有定限制，不能索引所有的双时态数据，查询也只限于当前和过去 数据的查询。 1 3 本论文的研究工作 中山大学“协同软件研究开发中心”承担了国家自然基金、广州市重点项目关 2 第一章前言 于“时态知识数据库模型及软件构件”这一科研项目，为时态数据库等方面的课题 提供了研究基础和应用，本论文在双时态索引技术g r 树和4 r 树检索效率相当， 但是4 r 树比o r 树更易于实现的优点，所以本文是4 r 树的基础上进行扩充，扩充 了4 r 树的如下方面： 一、扩充的4 r 树检索的数据类型。参照f 1 3 ，g 4 r 树扩充了4 r 树的双时态数 据类型：( 1 ) 引入来处理数据录入与生效的滞后，实时和超前。( 2 ) 扩 充双时态数据4 种类型的条件。o r 树和4 r 树能处理的双时态数据在有效 时间终止值为变元时，限定事务时间的初始值必须大于或等于有效时间的 的初始值。而且所处理的数据是对象生效和录入数据库是实时的基础上。 本文索引是对它们所有的双时态数据进行索引，该索引不仅能处理数据的 滞后，实时和超前，而且对于数据的事务时间的初始值和有效时间的的初 始值没有限制。突破了g r 树和4 r 树对双时态数据域的限制。 二、扩充了4 r 树的查询功能。g r 树和4 r 树索引只能查询对象的当前状态和 历史状态，不能有效查询将来的对象，本文提出的索引技术不仅能查询对 象的过去，现在，还能查询对象的将来。若是对将来时刻进行查询，通过 将时间变元绑定到将来某一时刻来查询将来的情况。 三、改进了相应的索引方法。对双时态数据进行扩充后，相应的索引方法也要 进行扩充，才能有效索引所有的双时态数据。 本文对4 r 的双时态数据作了扩充，并扩充了相应的索引方法。所以称之为 g 4 - r 树( g e n e r a l i z e 4 i r 树) 。 1 。4 本文安排 第二章介绍一下时态的基本知识，包括时间点，时间区间，时间粒度的基本定 义以及有效时间和事务时间的概念，以及它们之间的关系。 第三章首先介绍了一些基本的索引方法b 树，r l 树，r 树等，在此基础上引 入时态索引技术o r 树，4 垠树这两种重要的时态索引技术，并分析了各自的优点 和不足。 第四章是本文的重点，主要是扩充了4 r 树的功能使其能处理除4 r 树的双时 态数据外的其它一般的数据：数据录入与生效存在滞后，以及可以预知将来的情况； 3 中山大学硕士学位论文 对象录入时该对象还要到将来才生效的情形。查询时4 r 树只能查询当前和历史数 据查询的局限，还可查询将来情形，并改进了4 r 树的索引方法。 第五章给出了算法并对此算法作了测试，验证了此方法的可行性。 4 第二章时态基础知识 第二章时态基础知识 2 1 关于时间的基本概念 什么是时间? 时间作为事物的一种基本属性，其特点是一去不复返。在现实世 界中。时间是无时不在，无处不在的，它在时间轴上是连续存在。本章介绍时态数 据库中有关时间信息的基本表示方法，如时间量子、时间粒度、时间点、时间区间 等时间概念；进而描述了有效时间和事务时间与双时态域等基本概念；并讨论了双 时态域之间的关系。 2 1 1 时间量子和时间粒度 时间量子( c h r o n o n ) 是指时态系统所支持的最小的、不可再分解的时间间隔， 时间量子长短的选择与所描述的问题有关。例如描述农业产量可以取年为时间量 子；表示工资变化可以取月为时间量子；出生日期取日为时间量子；约会时间取分 为时间量子；在电子学中常常取秒、毫秒、微秒、毫微秒等为时间量子。而时 间戳( t i m p s t a m p ) 就是在数据产生或改变时，其发生时刻的时间，当时间量子足 够精确时，可以准确描述数据发生的时刻。这样数据不仅保留了其固有的属性，而 且反映了其变化的状态信息。这样的数据具有了时间状态，成为了时态数据 ( t e m p o r a ld a t a ) 【1 】。 在日常生活中，人们在记录事物发生的时间点时，会根据不同的应用场合选择 不同精度的计量单位。我们日常生活中的年、月、星期、日、时、分、秒，都 可以用来计量时间，在计算机中的时间脉冲长度甚至达到1 0 - 9 秒数量级。时间粒度 ( t i m eg r a n u l a r i t y ) 表明了记录时间时所用的度量单位，它是时间表示和推理的基 本单位。时间粒度是一个比较重要的概念，在时态表示和时态推理过程中，会遇到 时间粒度的转换闯题。同时选择不同精度的时间粒度，也会影响表述时间的数据结 构以及运算f 1 1 f 5 1 。 5 中山大学硕士学位论文 2 1 2 时间点( t i m ei n s t a n t ) 时间点( t i m ei n s t a n t ) 是时间轴上的一点，它是和时间粒度是相关的。例如 2 0 0 4 年4 月2 日，时间粒度精确到“天”。如果系统使用的最小时间粒度是“秒”， 则该时间点在系统内的表示必须换算成2 0 0 4 年4 月2 日0 时0 分o 秒。 2 1 3 基于区间( i n t e r v a l b a s e d ) 的时间 在这种方式中，时间的基本单位为时间段或者是时间区间。即通过描述时间段 的起始和终止点来描述时间。 采用时间区间的形式描述一段时间，可以有如下表示： 四种区间 a ) 匝b p d b ) p i ，p j ) c ) p j 】 d ) 慨枘) 区间含义 p j t p ! i p i t p j p i t 一 r i ) i t p j 图2 - 1 基于时间区间的时间描述方法 p i ，p j ：分别表示两个时间点； 【】：分别表示左右闭区间； ( ) ：分布表示左右开区间。 利用时间区间也可以方便的描述时阅点。例如： 图例 o o 令p i = p j ，这时的时间区间可以理解为延续时间为0 的一段时间，即时间轴上 的某个时间点。 第二章时态基础知识 2 _ 2 几种时间 时态数据库有别于其它的数据库主要是它提供对时态数据的支持，时态数据主 要包括有效时间和事务时间，而且时态数据还具有时间变元。 2 2 1 有效时阅 一个事实( 事件) 的有效时间( i dt i m e ) 是指在建模的现实世界中它为真( 存在) 的时间f 1 】。它有如下特点： 有效时间值的含义依赖于具体应用，取值是否有效视具体应用场合而定，即涉 及到数据约束问题； 有效时间可以指过去、现在和未来。s n o d g r a s s 把只支持有效时间的数据库称为 历史数据库( h i s t o r i c a ld a t a b a s e ) 。历史数据库记录现实世界在有效时间点的事件， 或者现实世界的状态变化，它对事物的描述比较符合直观理解。如表2 - 1 给出的一 个例子： 表2 1 一个包含有效时间的历史关系 姓名身份有效时间起始有效时间终止 吴州助教1 9 9 8 年7 月1 日2 0 0 0 年9 月3 日 吴州讲师2 0 0 0 年9 月4 日2 0 0 3 年7 月2 日 吴州副教授2 0 0 7 年7 月3 日 n o w 从表2 - 1 可以看到吴州的身份变动历史，通过增加有效时间起始( v a l i dt i m e s t a r t ) 和有效时间终l 上( v a l i dt i m ee n d ) 2 个字段，可以记录数据的有效时间。是否 增加了2 个字段，就可以从传统的关系型数据管理系统变为历史数据管理系统了 呢? 当然没有那么简单。作为一个时态d b m s ，必须支持时态数据定义语言 ( t d d l ) ，时态数据操作语言( t d m l ) ，时态查询语言( t e m p o r a lq u e r yl a n g u a g e ) 和时态约束( t e m p o r a l c o n s t r a i n t s ) 。例如：如果在关系型数据管理系统( r d b m s ) 下实现 表2 一l 的存储关系，可以修改第1 条记录的终止有效日期为2 0 0 1 年8 月3 日，修改 7 中山大学硕士学位论文 后的历史关系如表2 - 2 所示。 表2 2 一个包含有效时间的历史关系 姓名身份起始有效时间终止有效时间 吴州助教1 9 9 8 年7 月1 日2 0 0 1 年8 月3 日 吴州讲师2 0 0 0 年9 月4 日2 0 0 3 年7 月2 日 吴州副教授2 0 0 7 年7 月3 日 n o w 从数据存储的角度来看没有问题，但是从时态数据的角度观察，发现第1 条和 第2 条记录有时间冲突，在两个时间区间的交集 2 0 0 0 年9 月3 日2 0 0 1 年8 月3 日 这段时间，该人员到底是助教还是讲师? 这就涉及到时态的约束问题。时态 d b m s 自身提供时态约束管理，而简单的在关系型d b m s 基础上通过扩充字段来 实现历史数据库，需要用户编制程序完成约束。 2 2 2 事务时间 事务时间( t r a n s a c t i o nt i m e ) 就是一个事实存储在数据库中的时间，它记录着 对数据库修改或更新的各种操作历史【3 】对应于现有事务或现有数据库状态变迁的 历史。它有以下特点： 事务时间的值由系统时钟给出，它独立于应用，用户不能修改事务时间： 事务时间不能晚于现在时间，因为它反映着数据库实际操作的时间，不能指未 来，而有效时间可以指未来。 s n o d g r a s s 把只支持事务时间的数据库称为回滚数据库( r o l l b a c k d a t a b a s e ) a 回 滚数据库记录数据库自身变化，它沿着事务时间轴记录数据，按照事务时间排序， 保留了所有状态演变中过去的状态【1 1 。可以被看作是只能追加记录的数据库，它不 记录未来的数据库状态。 如果一个数据库同时支持有效时间和事务时间，这样的数据库被称为双时态数 据库( b i t e m p o r a l d a t a b a s e ) 。本文主要工作是基于双时态的索引技术，所以下面介 第二章时态基础知识 绍双时态域。 2 2 3 用户自定义时间 用户自定义时阗( u s e r - d e f i n e dt i m e ) 指用户根据自己的需要或理解定义的时 间，其数据的含义不需要d b m s 的解释。例如：b i r t h d a y 本来不是一种标准数据类型， 但是假如用户根据自己的需要定义了一种数据类型为b i n h d a y 那么该属性的值( 如 “1 9 7 3 年5 月6 日”) 被称为用户自定义时间。 现在的许多商业d b m s 都支持用户自定义数据类型，如s o ls e r v e r 允许在系 统数据类型的基础上建立自己定义的数据类型。这些用户自定义数据类型可以在数 据表建立或结构修改时，如同其它标准数据类型一样为用户所用，并且可以将规则 应用于用户自定义数据类型，从而为用户定义数据类型列提供完整性约束【1 7 】。 2 2 4 双时态数据中变元n o w 和u c 双时态数据中一般将有效时间中引入的变量记为“n o w ”，将事务时间中引入 的变量记为“u c ”( u n t i lc h a n g e d ) 【2 4 】。由于事务时间本身意义，变量“u c ”的语 义单一，容易处理，但有效时间变量“n o w ”却相对复杂。在实际过程中由于数据 库本身运作机理方面原因，n o w 除了取其自然意义外，还可以表示“过去”与“将 来”的语义。这主要是数据所反映客观事实实际成立( 或实际上不成立) 的时间t 1 与数据本身录入( 或退出) 数据库的时间t 2 之间会出现“错位”关系。一般来讲， t 1 t 2 。如果t l t 2 ，则n o w 可能表示“过去时间( p a s tt i m e ) ”，如果t 2 t l ，贝1 jn o w 可能表示“将来时问( f u t u r et i m e ) $ p o 2 3 双时态域 2 3 1 双时态域定义 为了有效索引双时态数据，我们需要有效表示双时态数据域，t q u e l 1 8 1 9 的 四个时间戳模式是当今最流行的表示双时态的方式如表2 - 3 。表中除了非时态属性 外，增加了四个时间属性：事务时间起始( t r s ) ，事务时间终止c 丌卫) ，有效时间起 始( v t s ) ，有效时间终止( v 1 e ) 。 9 中山大学硕士学位论文 由于当今网络和计算机的普及程度等方面的原因，在实际生活中，数据往往在 事实生效后经过一段时间才记录入库【1 3 】。所以在数据库系统中记录的往往是过去 某时刻的数据。例如，在学校学籍管理中某人已经开学入学，可能要到2 周后才 录入数据库。这种情况我们称为滞后。当然也有提前预知未来的情况，称之为超前 例如天气预报。也有实时记录的情况，如股市变化。我们用n o w + a 来统一表示这 三种种情况。下面看取负数，即滞后的情况，如表2 3 为某公司员工一览表， 以一1 ，即表示数据更新后要到下一月才会在数据库中体现。其中元组1 记录周凡自 4 2 0 0 3 至当前时间上一个月工作部门为技术部，数据库中自5 2 0 0 3 直记录至今。 元组2 记录了张三丰在3 2 0 0 3 至5 2 0 0 3 在广告部工作，这一记录从4 2 0 0 3 记录入 库至今。元组3 记录王明2 2 0 0 3 至当前上一个月在培训部上班，这个记录于3 2 0 0 3 记录入库，但到6 2 0 0 3 王明辞职，由于滞后一个月，所以该元组到7 2 0 0 3 才从当 前数据库中删除。元组4 记录李扬在6 2 0 0 3 至8 2 0 0 3 在市场部工作，这条记录3 2 0 0 3 录入数据库，7 2 0 0 3 从数据库的删除。当然这种删除只是逻辑上删除，而不是物理 上删除。即数据不是当前的。综上所述，双时态图形可分为以下四类如表2 - 4 ， 表2 3 职工关系表 职工名 部门订st t e1 sv t e 周凡技术部 5 2 0 0 3u c4 ，2 0 0 3n o w - 1 张三丰广告部4 2 0 0 3u c3 2 0 0 35 2 0 0 3 王明培训部3 2 0 0 37 ，2 0 0 32 2 0 0 3n o w - 1 李扬市场部 3 ，2 0 0 37 ，2 0 0 36 2 0 0 38 2 0 0 3 表2 4 双时态域的四种类型 t st ev sv e例子 at t lu cv t ln o w + - 元组1 bt t lu cv t l v t 2元组2 ct 1t t tv t ln o w + 元组3 dt t lt t l v t lv t 2元组4 1 0 第二章时态基础知识 n o w 和u c 分别代表有效时间变元和事务时间变元，其中表示数据偏移 ( o f f s e t ) ，数据偏移取负数，零和正数来分别处理时间的滞后，实时和超前的情 况。在如果用两维坐标表示双时态数据，其中横坐标表示事务时间，纵坐标表示有 效时间，对应的双时态图形如图2 - 2 ( 当a 0 楼梯形处在线v t = r 上方) 。 a c 2 3 2 双时态之间的关系 n b 图2 - 2 四种类型的双时域 d 上面介绍了双时态数据有四种类型：增长的楼梯形，增长的矩形，固定的楼梯 形和固定的矩形，那么在时态查询过程中查询主要有点查询，区间查询和矩形查询。 1 1 中山大学硕士学位论文 1 点与双时态域：a 包含i n s i d e ( q ，p ) b 分离o u t s i d e ( p ，0 3 ，如图2 - 3 点p 与双时态类型a 的关系 其余三种情形依此类推。 一一 谬辔一 由于在查询时只涉及到具体的时间，不存在时间变元，所以在此只讨论固定矩 第= 章时态基础知识 形框和双时态域之间的关系。固定矩形框与双时态域之间的关系有：相交( o v e r l a p ) ， 包含( c o n t a i n ) ，相离( d i s j o i n t ) 。矩形域与双时态数据a 类的关系如图2 - 5 。 0 咐i o p 0 ，劬 2 4 小结 h 【吼曲d 蚓。岫啦 图2 - 5 双时态域之间的关系 本章简要介绍了时态的一些基本概念，以及时态数据库中的两个重要时间 概念：有效时间和事务时间，并描述了时间点、时间区间和双时态域之间的关系， 为后面的索引技术打基础。 中山大学硕士学位论文 第三章索引技术 第二章介绍了时态数据中的时态的一些基本概念，如何对这些时态数据建立索 引以快速查询到与时间相关的数据，是时态索引的一个重要研究课题。而索引是用 于快速存取数据对象的一种数据结构。通常，一个数据库管理系统都会为数据建立 索弓1 以加快查询速度。因为当数据量非常巨大的时候，若不建立索引，那么查找满 足条件的数据的代价是相当大的。下面简要介绍传统的技术：b 树，r 树及其上的 扩展r 宰树，以及时态索引技术g r 树，4 r 树。 3 1b 树 b 树是r b a y e r 和e m c c r e i g h t 在1 9 7 2 年提出来的。随后b 树在数据库的检 索中大量运用，b 树涉及到了实现基于磁盘的检索树操作的所有问题。b 树有如下 特点： a ) b 树总是树高平衡的，所有的叶结点都是在同层。 b ) 更新和检索操作只是影响一些磁盘叶，因此性能较好。 c ) b 树把相关的记录放在同一个磁盘块中，从而利用了访问的局部性原理。 d ) b 树保证了树中至少有一定比例的磁盘页是满的，这样能够改进空间的利 用率，同时减少了检索和更新操作期间磁盘读取次数。 b 树的变体b + 一树，岔树都是在b 树上的扩充。目前使用最广泛的索引技术是 b + 一树，例如s q l s e r v e r 2 0 0 0 、o r a c l e 都是使用b + - 树来建立索引，但是b 树只适 用于一维数据的索引，不适用于两维双时态数据的索引。 3 2f i 树 r 树1 5 】【1 9 l 最早是由a g u t t m a n 在1 9 8 4 年提出的，其后又有了许多变形，形成 了由r 树、r + 树、r 树、h i l b e r t r 树、s r 树等组成的r 树系列空间索引。r 树在 1 4 第三章索引技术 结构很像b 树，只不过b - 树是用于一维数据的索引，而r 树是用于两维数据的索 引，r - 树是b 一树在一维数据索引上的扩充，可以认为r 树是b 树在两维空间的变 种， b 一树中的结点是一个数值( 关键码值) ，而r 树的结点是一些矩形。最初r 树主要是用于空间数据的索引，而时态数据库中的时态数据是由有效时间和事务时 间组成，也具有两维的特性，但是时态数据因为含有时间变元n o w 的原因，时态 数据除矩形外还存在楼梯形，所以r 树只能用于固定双时态数据的索引。 r 树通常多用在g i s ( 地理信息系统g e o g r a p h i c a li n f o r m a t i o ns y s t e m s ) 系统。它 是一种空间索引技术，为空间搜索提供了一种合适的数据结构，以提高搜索速度。 r 树空间索引技术的核心是：根据搜索条件，一个矩形，迅速找到与该矩形相交的 所有空间对象集合。当数据量巨大，矩形框相对于全图很小时，这个集合相对于全 图数据集大为缩小，在这个缩小的集合上再进行各种复杂的搜索，可以减少操 作，大大提高查询效率。 r 树适应的索引的对象是空间数据库、时态数据库和时空数据库。 3 2 1r - 树数据结构 r 树数据结构是一种时空索引数据结构，主要包括： a 1 b ) c ) r 树是n 叉树，r l 称为r - 树的扇 每个结点对应一个矩形。 叶子结点上包含了小于或等于r 1 个对象，其对应的矩形为所有对象的外包 矩形。 d ) 非叶结点的矩形为所有子结点矩形的外包矩形。 应用r 树的目的是将相邻的对象放在一个矩形框中，建立索引。而时间值相近 的结点，在树中出现的位置相邻。如图3 - 1 ，当外包矩形相交时，可看成该结点里 面的时态对象所发生作用的时间值相交。某个时态对象可能存在多个结点当中，因 为时态对象是连续的，所以有可能存在多个索引结点中。在查询的时候，只要查找 与检索的矩形框有相交的子树即可。这使得检索的步骤减少，检索中的磁盘i o 进 出减少，检索时间就会大量减少。 中山大学硕士学位论文 图3 1r 树的记录对象结构图 图3 2r 树的记录对象关系图 图例说明：图3 - i 是记录对象的结构，8 个实体被分成三个矩形，分别标记为i ，2 ，3 。图 3 - 2 为对象实体的r 一树记录，根结点保留了三个分支的外包矩形1 ，2 ，3 记录，并且含有指向 子结点的指针。叶结点保留了记录的矩形框和指向磁盘页记录的指针。 3 2 2r - 树基本操作 r 树的建立需要满足一定的规则，设m 为r 树中每个结点最多包含的结构个 数，m 为每个结点包含的最少结构个数，则有m m 2 。此外，r - 树还具有以下特征： a )每个根最少有两个子结点，除非它亦是叶子 1 6 第三章索引技术 b ) 每个目录结点有m m 个子结点，除非它为根 c ) 每个叶子结点有m m 个数据对象，除非它为根 d ) 所有的叶子结点在同一层上。 定义3 2 ：m 阶r 树( r t r e e o f o r d e r m ) m 阶r 树是1 t i 阶b + 树在处理多维空间对象上的延伸。 a ) 每个结点至多有m 棵子树； b ) 除了根结点外，每个结点至少有f 划棵子树； c ) 如果根结点不是叶结点，则根结点至少有两棵予树。 d ) 有k 棵子树的结点必有k 个形如( p ，m b r ) 的索引项，其中，p 是指 针，b r 是最小边界矩形； e ) r 树的叶结点包含了以下格式的索引项：( o b j c c t i d e n t i f i e r ，m b r ) ， 其中，o b j e c t i d e n t i f i e r 是指向一个数据对象的指针：m b r 是该数据对象 的最小边界矩形。 f ) r 树的非叶结点包含以下格式的索引项：( c h i l d p o i n t e r ，m b r ) ，其中 c h i l d p o i n t e r 是指向r 树中下一层次孩子结点的指针； 而m b r 是包含 此非叶结点的所有孩子结点m b r 的最小边界矩形。 1 r 树的插入操作 r 树的插入算法，主要是选择合适的叶子结点来插入数据并解决叶子结点的溢 出问题。结点的选取有下面三种情况： a ) 点包括在一个叶子结点区域内时，就选择该叶子结点。 b ) 点包括在几个不同的叶子结点区域内时，选择产生最小体积的叶子结 点。 c ) 点未被包括在任何叶子结点区域内时。选择扩大最小的区域即可包括该 点的叶子结点。如果几个叶子结点的扩大值相同，则选择本身体积最小 的叶子结点。 插入是r 树中开销最大的操作，对其性能影响很大。r 树采用了比较简单的优 化准则，即选择插入后面积扩大最小的目录m b r 来覆盖r i 。若有多个目录m b r 满足此要求，则选择其中面积最小的。目录m b r 选定后，就可确定其所在的叶结 1 7 中山大学硕士学位论文 点，若叶结点有空则直接插入即可，若叶结点插入后溢出，则需分裂为二，由于叶 结点中的索引项是无序的，索引项分组目录也有多种选择。时结点分裂后需要生成 两个目录m b r 覆盖分裂后的两组对象m b r ，以取代原来的目录m b r 。也就是叶 结点的上一级结点要增加一个索引项，这以可能导致该结点的分裂，最坏情况下， 这种分裂可传播至根。根分裂后，r 树就要增加一级。 r 树的插入与许多的有关树的操作一样是一个递归的过程。首先从根结点出发， 按照一定的标准，选择其中一个子结点插入对象的空间。然后再从孩子树的根结点 出发重复进行上面操作，直到叶子结点。 设m 和m ( m m 1 为r 树结点中单元个数的上限和下限，当新对象的插入使叶 子结点中的单元个数超过m 时，需要进行结点的分裂操作。 分裂操作是将溢出的结点按一定的规则分为若干个部份。在其父结点删除原来 对应的单元，并加入由分裂产生的相应的单元。如果这样引起父结点的溢出，则继 续对父结点进行分裂操作。分裂操作也是个递归操作，它保证了空间对象插入后r 树的仍能保持平衡。 2 r 树删除操作 当删除某个对象时，先按其对象m b r ，从根结点开始搜索一直到其所在的时 结点，再删除它，但在删除后可能引起叶结点的下溢( u n d e r f l o w ) ，即其中索引项的 个数可能低于最小值m 。在此情况下，可将此叶结点及其对应的目录m b r 删除， 并将其中剩余的对象m b r 及其指向对象的指针重新插入r 树中，这实际上相当于 把删除了的叶结点中剩余的对象m b r 分摊到与其相交或邻接的其他日录m b r 中。 目录对象的删除也会引起其所在的目录结点的下溢，从而导致该目录结点的删除。 其中剩余的目录对象可以重插入其他同级的目录缩点中，这个过程可能继续到根结 点的删除。当然根结点删除时，其中只有一个索引项，可以直接删除，无需重插入， 即r 树降低一级。此外，在重插入过程中也可能引起结点的溢出，例如除被删除的 结点外，其它结点都已达到或接近m ，重插入时可能导致叶结点的分裂，即一个叶 结点被删除，其他结点又分裂，这样有一点好处是，不但可消除叶结点的下溢，而 且在一定程度上改变了叶结点中索引项分配不均衡的情况，相当于对r 树的一次合 理的重组，保证了r 树结点的利用率。 1 8 第三章索引技术 r 树自g 变体r + 树，r + 树等是在r 树的基础上作了扩充，其中应用最广泛的是 r + 树，r + 树是在r 树的基础上优化了结点的重插入方法，尽量避免结点的分裂， 在必须分裂结点时提供了优化分裂的方法。使目录间的重叠最小，在奄询时减少了 i o 操作，提高了查询效率。 3 4g r 树 g r 树1 1 j 是在r 树基础上的扩充，r 树只能