（计算机软件与理论专业论文）基于时态拟序的关系数据索引技术.pdf

基于时态拟序的关系数据索引技术摘要 基于时态拟序的关系数据索引技术 专业：计算机软件与理论专业 硕士生：杨贤德 指导教师：叶小平副教授 摘要 随着数据库和时态信息技术的迅速发展，时态信息处理技术的应用领域越来 越广阔，时态信息的应用已渗透进各行各业中。对时态信息的索引效率的要求越 来越高。 本文针对时态信息的有效时间，利用现实数据相似性的特点，提出一种新的 索引模型豫f ，z 矾提高时态关系数据索引的效率。本文研究基于时态关系索引技 术。首先，讨论时态摘要类和时态拟序基本概念和相应性质，为时态关系数据索 引提供基本数学框架；其次，提出时态线序分枝有效算法，解决索引建立过程中 关键技术；最后，构造索引模型豫f 积，实现时态关系数据的查询，同时基于索 引模型豫f 耐的特性，讨论索引的增量式更新。本文工作意义在于：第一，有效 地利用时态关系数据的相似性，压缩原始数据；第二，利用时态信息的包含拟序 关系构造专门针对有效时间的时态索引模型豫f 刀矾第三，在豫f 玎d 框架内，基 于数据查询算法研究索引更新操作，进而在某种意义上实现了数据操作( 查询和 更新) 统一；第四，通过较大数据量的仿真对比实验，验证了索引模型豫f ，z d 的 可行性和有效性，提高时态关系数据索引的效率。 关键词：有效时间，时态摘要，时态拟序，时态线序分枝，时态关系数据查询和 更新 基于时态拟序的关系数据索引技术 a b s t r a c t t e c l m o l o g yo fr e l a t i o nd a t ai n d e x b a s e do nt e m p o r a lp r e o r d e r m 旬o r ： n 锄e ： c o m p u t e rs o f h v a r ea 1 1 d1 1 1 e o 巧 1 9x i a j l d e 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 w i mt l l er a p i dd e v e l o p m e n to fd a t a b a s ea n dt e m p o r a li n f o n n a t i o nt e c h n o l o g y ， t e m p o r a li n f o m a t i o np r o c e s s i n gt e c h n o l o g i e sa r ei n v 0 1 v e di nv a r i o u sa p p l i c a t i o n f i e l d s ，a 1 1 dg e t t i n gam u l t i p l e x 伊o w t h t h er e q u i r e 】n e n to fi n d e xe m c i e n c yo f t e m p o r a li 1 1 f o m a t i o ni sg e t t i i l gh i g h e ra n dh i g h e r t h i sp a p e rp r e s e n t san e wi n d e xm o d e l 一刀f 刀df o rv a l i dt i m e ，w i t ht h es i m i l a r i t ) ， o ft h er e a l i t ) ，d a t a ，a i 】【dt h i sm o d e lc a ni m p r o v et h ee m c i e n c yo ft e m p o r a lr e l a t i o nd a t a i n d e x t h er e s e a r c hi n t h i sp a p e ri sb a s e do nt e m p o r a lr e l a t i o ni n d e xt e c 王h 1 0 l o g y f i r s t l y ，w ed i s c u s sm eb a s i cc o n c e p t sa n dc h a r a c t e r i s t i co ft e m p o r a ls u m m a r yc l a s s ( 7 w ) a n dt c m p o r a lp r e o r d e r w h i c hp r o v i d et l l e 丘a m e w o r ko fb a s i cm a t hf o r t e m p o r a lr e l a t i o nd a t ai n d e x s e c o n d l y ，w ep r o p o s et h ea l g o r i t h mo ft e m p o r a ll i n e a r o r d e r b r a n c ha n ds o l v et h ek e yt e c l l i l o l o g yi i lp r o c e s so f b u i l d i n gi n d e x t l l i r d l y ，w e s t m c t u r et h ei n d e xm o d e l 一豫f 门df o r t h eq u e r ) ro ft e n l p o r a l r e l a t i o nd a t aa 1 1 dd i s c u s s t h ei n c r e m e n t a lu p d a t eb a s e do nm ec h a r a c t e r i s t i co f 豫加以t h i sp a p e rh a ss o m e s i g n i f i c a n c e 1 ) c o m p r e s so r i g i n a ld a t au s i n gt h es i m i l a r i t ) r t om er e a l i t yd a t a 2 ) s t m c t u r ei n d e xm o d e l - 7 r f 疗du s i n gt h ec o n t a i m n e n tr e l a t i o no ft e m p o r a li n f o m l a t i o n b a s e do nt e m p o r a lp r e o r d e rf o rv a l i dt i m eq u e r y 3 ) i nt h ef r a m eo f 豫f 聆么r e s e a r c h t l l eo p e r a t i o no fi n d e xu p d a t eb a s e do na l g o r i t i u no fq u e r ) ，；u n i 匆q u e r ) ，a 1 1 du p d a t ei n s o m es e n s e 4 ) t h r o u 曲t h es i m u l a t i n ga n dc o m p 撕n ge x p e r i m e n tw i ml a 略e ra m o u n t o fd a t a ；v e r i 黟t h ef e a s i b i l i t ) ，a n de f r e c t i v e n e s so f 豫加以i m p r o v et h ei n d e x i n g e m c i e n c yo ft e m p o r a lr e l a t i o nd a t a k e yw o r d s ：v a l i dt i m e ，t e m p o r a ls 眦吼a d r ，t e m p o r a lp r e o r d e r ，t e m p o r a ll i n e a ro r d e r b r a n c h ，q u e r ya i l du p d a t eo ft e m p o r a lr e l a t i o nd a t a n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：前移呦强j 惫 日期：呵年亍月日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：司移惋伤 日期：知炉r 月协日 导师签名： 计 罕 日期：叶年f 月n 日 基于时态拟序的关系数据索引技术第一章绪论 1 1 研究背景 第一章绪论 自上世纪8 0 年代时态数据库技术产生以来，经过2 0 多年的研究和实践，时 态数据库在基础理论、索引模型、数据库语言、应用技术等方面都取得了丰硕的 成果，已经成为数据库与信息系统中一个非常重要的学科。 任何事情的发生都有时间，任何事物都有所谓的生命期。时间是现实世界中 无所不在的客观因素。现实世界无时无刻都在“时间 的刻划下不断地演变发展。 在信息时代，时间更加显示它的重要性它是“信息”的基本属性。人们从客 观事物所得到的任何信息，都只有在一定的时间范畴之内才有意义。数据库发展 至今，已不仅是当初只为了记录信息而存在，和任何事物的运动一样，数据库系 统整个运行过程都贯穿着时间特性。很多数据库技术的应用都是时态相关的。例 如通信业的通话记录、业务办理：金融界的股票市场、会计、银行业；人事、医 疗记录、目录管理等记录保存应用；航空、列车、旅店预定、项目管理等计划应 用；天气监测等科学应用；这些应用都依赖于时间相关的数据。随着数据库技术 的迅速发展，特别是多媒体技术和网络技术的发展，时态信息的应用已渗透进各 行各业中。 如果称具有时间特性的信息为“时态信息 ，那么具有时间特性的数据就是 时态数据，能对时态数据进行存储、管理和各种必要操作的数据库系统就是时态 数据库系统。时态数据模型就是将时间特性引入数据讨论所得到的数据模型。然 而，时态信息处理与传统模式有着很大的不同。传统的数据库只是将时间看成是 普通属性，简单地将事物的时态特性与事物非时态属性同等对待、一并处理，没 有体现时态关系的特点。而时态数据库具有丰富的时态语义以及多种时态操作， 并且将时间看作特殊的属性，构造相应的数据索引模型来处理。 幕于时态拟序的关系数据索引技术第一章绪论 1 2 论文出发点和意义 由于传统数据库在处理时态信息方面比较笨拙，这不利于数据库管理时态信 息，难以加强系统的可靠性和提高系统的运行效率。特别是对时间期间进行查询 时，传统数据库要进行多重交集的操作，这样大大影响到索引效率。可见，对于 时态关系数据构造专门的索引结构，缩短索引时间，最终提高时态处理的效率。 这是现代数据库研究的一个方向。 尽管时态关系数据模型的研究已经具有多年的历史，也出现了许多时态索引 模型，但是这些模型大多是以开始时间、结束时间，或周期性插值等方法给定时 间属性一个索引值，再构造索引模型；实质上还是把时间属性看成是普通数据来 处理，没有真正利用时态特性( 例如：包含关系、相交关系等) ，不适合处理时 态语义，具有一定的局限性。 另外，在日常中的数据的时态信息有着相似的特性：所谓相似，就是指不同 的数据具有相同的时间属性，也就是说这些数据都在同样的时间段中有效。例如， 企业每年在校园中招聘的学生，他们统一签订合同，这些合同的有效期是相同的： 工厂同一天所生产的产品，它们的有效期也是相同的。这些数据的在时间上具有 相似性。 本文研究基于时态关系有效时间索引技术。主要工作： 1 ) 讨论时态摘要类和时态拟序基本概念和相应性质，为时态关系数据索引 提供了基本数学框架； 2 ) 由时态拟序扩展至时态线序，并提出时态线序分枝有效算法，解决索引 建立过程中关键技术； 3 ) 最后，构造索引模型豫f 聆以实现时态关系数据的查询，同时利用索引模 型豫f 玎d 的特性，实现索引的增量式更新。 本论文创新点： 1 ) 把简单的二维表结构转换成树形结构，为构造索引模型提供对象； 2 ) 合理利用现实生活中时态信息的相似性；以及真j 下地利用时态包含关系， 基于时态拟序关系，构造索引结构，起到两重压缩的效果： 3 ) 利用最大跨度与查询的关系减小查询时的索引量。 本论文的意义在于： 2 基于时态拟序的关系数据索引技术第一章绪论 1 ) 有效地利用时态关系数据的相似性，压缩原始数据； 2 ) 利用时态信息的包含关系构造专门针对有效时间的时态索引模型豫加巩 3 ) 在豫加d 框架内，基于数据查询算法研究索引更新操作，进而在某种意 义上实现了数据操作( 查询和更新) 统一； 4 ) 通过较大数据量的仿真实验，验证了索引模型豫f 丹d 的可行性和有效性， 提高时态关系数据索引的效率。 1 3 国内外研究现状 在时态关系数据索引方面，可以分为单时态( 单独考虑事务时间或有效时间) 和双时态两种情形。 1 3 1 基于事务时间索引技术 早期单时态索引多集中于事务时间方面，由于事务时间可表示数据实体历史 版本时态信息，因而可以通过事务时间建立索引。事务时间不能进行更新，事务 时间索引本质上不需要对数据实体进行动态管理。事务时间的引入使得数据库中 的记录出现版本问题，由于需要保存各个版本的数据，使得数据库的索引空间急 剧增加。基于事务时间的索引结构主要分为基于传统索引结构2 】【3 1 和基于独立 索引结构【4 】【5 】【6 】【7 】【8 1 。 基于传统索引结构 t s b t t s b t ( t i m es p l i tb t r e e ) 【1 1 基于b t r e e ，是一种能够索引事务时间和属性值 的混合索引方法。它是基于时间片分割的，共有3 中分割方法：属性值分割、时 间分割和属性值时间分割。当前版本的查询是高效的，然而过去已久的版本的 查询在实验中被证明是低效的，原因是许多过去版本中没有有效的记录，而且时 间片被分割使得时态关系查询变复杂。 w o b t w o b t ( w r i t eo n c eb 一仃e e ) 【2 1 是基于t s b t 时态索引方法，它改进了b + t r e e ， 分割事务时间和属性值。w o b t 的目标是提供一种适合于光盘的结构。w o b t 基于时态拟序的关系数据索引技术第一章绪论 的空间利用率高，适合做时间片查询；但是由于时间片被分割使得更新操作相对 比较麻烦。 o b + t e 基于事务时间的数据库设计到多版本的问题，而版本与版本之间有很多相同 的记录。o b + t r e e ( o v e r l a p p i n gb + 仃e e ) 【3 1 就是利用这种相似性，将原来每个版 本各自对应的b + 仃e e 中相同的结点( 内部结点和叶子结点) 合并共有，使得这 些b + t r e e 在逻辑和物理上重叠，从而一定程度上缓解了事务时间数据库索引空 间大的问题。 基于独立时态索引结构 a p - t r e e h i m 删g u n a d h i 和a r i es e g e v 提出了a p t r e e 来实现时间索引4 】【5 】，该模型 是基于事务时间的，利用了开始时间作为索引值，叶子结点中每个索引值指向一 个已该时刻为开始时间的时间期i 、j 集合。类似于b + 树来构造索引树，但是允许 叶子结点跳过内部索引结点直接连接到根结点，这样就克服了b + 树在插入结点 时可能导致的各层结点连锁分离的情况。然而，只是适用于事务时间，因为事务 时间是一直延展，而有效时间期间需要动态地处理插入、删除。 a d t r e e a d - t r e e ( a p p e n d d e l e t et r e e ) 【6 1 是用于索引时间点的多路树，类似于b + 树。 所有的数据都在一个f i f o 的队列中进行插入或删除操作，所有的插入都在右端 进行，而删除都在左端操作，因此称为a p p e n d - d e l e t et r e e 。它和a p t r e e 类似， 但是a p 仃e e 因为不能调整结构，所以不能做删除操作。 s n a p s h o ti n d e x s n 印s h o ti n d e x 【7 1 是一种有效索引时间片的结构。虽然它能够达到i o 最优， 但是由于s n a p s h o ti i l d e x 会将事务时间期间分割成许多小的子期间，所以会产生 数据冗余，也影响到了它的效率。并且由于时间期间被分割了，所以s n a p s h o t i n d e x 在做相交、包含的时态关系查询时非常麻烦。 ar c h i v a b l et i m el n d e x 4 基于时态拟序的关系数据索引技术第一章绪论 觚k v a l et i m ei n d e x 【8 1 基于p v a s 二叉树，它索引时不是直接针对事务时间， 而是针对于事务时间所对应的版本号。每个历史版本的事务时间映射到一个版本 号，它需要一个特别的结构来完成这样的映射。p v a s 二叉树是将一个时间期间 二等分为两个时间期间作为儿子结点建成的一棵树，根结点是时间域。每个时间 期间被分配至包含该期间的结点中。p v a s 二叉树的结点分为三种：过去结点、 现在结点和将来结点。这样的结构对于事务时间的索引有着天然的优势，但是当 版本不多的情况下，索引空间的利用率很低。而且时间域越大，时间粒度越小时， 索引空间会变得非常大。 1 3 2 基于有效时间索引技术 相对于事务时间数据索引，有效时间索引应当具有必要的动态管理与操纵约 束。首先，有效时间会随着数据主体变化而需要进行插入、删除和修改等更新操 作；另外j 实际应用中许多数据实体有效时间本身就随时间演进而不断变化，例 如具有有效时间变量疗d w 情形。 近2 0 年来，国际上在有效时间索引的研究方面提出了许多索引模型 【9 】【l o 】【1 1 】【1 2 】【1 3 】【1 4 】【1 5 】【1 6 】【1 7 】【1 8 】【1 9 】【2 0 】【2 1 】【2 2 1 ，主要可以分为两种，一种是扩展传统的索 引结构( b + 树，r 树) 来实现时态索引功能【9 】【1 0 】【1 1 1 【1 2 】【1 3 】【1 4 1 【1 5 】；一种是构造符合 时态索引的结构【1 6 】【1 7 】【1 8 】【1 9 】【2 0 】【2 i 】。但由于时态数据自身特点，通常b + 树等方法 难以有效用于时态数据索引，尤其是带有时态变元的各种时态运算【2 3 】。 基于传统索引结构 t i m ei n d e x 1 9 9 0 年，e l m a s r i 、w u u 和k i m 提出了t i m ei n d e x 模型【9 】【1o 】【l l 】，这是一个将 所有时间期间的结束时间集合按线序作为索引值，建立b + t r e e ；叶子层的每个索 引值对应一个时间期间集合，这个集合是所有包含该结束时间的时间期间，也就 是说在该结束时间点依然有效的时间期间。在他们的论文还提出了一个两层索引 结构来实现时间属性和非时间属性的混合索引，其思想是：第一层是针对非时间 属性的b + t r e e 索引，叶子结点包含有属性值和指向一个t i m ei n d e x 树的指针， 也就是说，每个属性值都有一棵t i m ei n d e x 树与之对应。t i m ei n d e x 模型合理地 利用了结束时间来分割时间轴，然而只适用于时间期间跨度小或者时间期间重叠 5 基于时态拟序的关系数据索引技术 第一章绪论 度低的情况，因为跨度大的时间期间或时间期间重叠度大会使得时间期间对应多 个索引值，造成索引结构的膨胀。 改进t p i n d e x 1 9 9 6 年，c h e n gh i a i lg o h 、h o n 自u i ll u 、b e n gc l l i no o i 和k i 2 u 1l e et 跚改进 了t p i n d e x 【12 1 ，利用t p i n d e x 的映射方法，将时间期间映射到二维平面上，然 后按照水平、垂直或者斜线的顺序将平面上的点映射到一维上，再利用b + 饥e 进行索引。 m a p 2 1 1 9 9 7 年，m a n a s c i m e n t 0 和m h d u n h a m 提出了m a p 2 1 方法【1 3 】，这个方 法将时间期间的开始时间和结束时间映射为一个值，再利用b + t r e e 对这些值进行 索引。m a p 2 l 方法需要对结果超集进行遍历，而且对所有时间期间的最大跨度 很敏感，当最大跨度很大时，结果超集就会变的很大，这是影响效率了主要原因。 1 9 9 9 年，他们又针对这个问题提出了m u l t i p l em a p 2 1t r e e s 的思想【1 4 1 ，缩小了 结果超集的规模。这种改进主要是将时间期间按跨度分成小、中、大以及含有时 间变元托o w ，然后各自构建m a p 2 l 树，然而这样也增加了对索引维护的代价。 i b + t r e e 1 9 9 8 年，t 0 1 9 ab o z k a y a 和m e r a lo z s o y 0 9 1 u 提出了i b + 骶e 【6 】实现有效时间 的索引，这是对i n t e r v a l t r e e ( 基于二叉树) 【1 6 1 的扩展，利用时间期间的开始时 间作为索引值建立i b + t r e e ，叶子结点由按开始时间从小到大排列的时间期间和 其时间期间中最大结束时间。然而，当叶子结点的最大结束时间很大，也就是说 当叶子结点中含有跨度很大的时间期间时，则需要对该叶子结点进行遍历，这是 影响i b + - t r e e 效率的主要原因。同年，b o z k a y a 和o z s o y o g l u 在i b + - t r e e 的基础上 引入了分割大时间期间思想【1 5 】，提高了i b + t r e e 树的效率；可是，分割时间期间 也使得时态操作变得复杂，因为需要对时间期间进行分割或还原。 基于独立时态索引结构 i n t e n r a i t 1 e e i n t e r v a l t r e e 【1 6 1 是一棵支持时间期间操作的二叉树，它通过动态操作( 插入和 删除) 保持树的平衡。i n t e r v a l t r e e 使用时间期间的开始时间作为索引值，另外 6 基于时态拟序的关系数据索引技术 第一章绪论 每个结点中保存有以该结点为根的子树中所有时间期间中最大的结束时间。插入 和删除操作时间复杂度为o ( 1 0 9 ：聆) 。 c h e c l 【p o i n ti n d e x 1 9 9 2 年，t y c l i 行l e u n g 和础c h a r dr m u n t z 提出c h e c l 【p o i n ti n d e x 【1 7 1 ， 通过周期性的检查点将时间期间分割成时间片，这样一个时间期间就可能被多个 检查点分割储存。文章中还给出了时间片连接和合并的理论和算法，这个索引方 法的性能取决于检查点的周期频率。然而时间期间被分割成多个时间片，这样也 影响到时态关系的各种操作效率。 i s t n e 和e s t r e e g b l a l l k e n a g e l 和r h g u t i n g 提出了i s t r e e ( i n t e m a ls e g m e n tt r e e ) f 1 8 1 ，实质 上是利用结束时间集合的时间点的大小为序构成的一棵二叉树。1 9 9 4 年，他们 两人将i s 树移植到外存中去，提出了e s t r e e ( e x t e m a ls e g m e n tt r e e ) 【1 9 】，这是 把每个结点都有c o v e rl i s t 和l e a f l i s t 来保存外存的页标号和叶子结点所对应的时 间期间。 t p i n d e x 1 9 9 4 年，h ms h e n 、b e n gc h i no o i 和h o n 萄眦l u 提出了t p - i n d e x ( t i m e p o l y g o n ) 【2 0 1 ，将时间期间的开始时间和结束时间分别映射到二维平面的x 轴和 y 轴上，然后将平面分割成多边形块，每一块所包含的时间期间分配在一个存储 块中。将这些块组织成类似与b + t r e e 的所谓t p t r e e 来索引。每一个时态查询都 被转换成三角形内的块查询。然而，t p i n d e x 并不适合时间动态延伸特性，因为 随着时间的延伸，二维平面上的时态空间也会变大。 r i t r e e 2 0 0 5 年，j o s te n d e r l e 、n i c 0 1 es c h n e i d e r 和t h o m a ss e i d l 提出了r i t r e e 【2 1 1 ， 这是一棵二叉树，树高为h ，结点为所有可能时间点【0 ，2 “一1 】的中序遍历。每个元 组对应一棵包含其开始时间和结束时间的最小子树的根结点，分别由1 0 w e r i n d e x 和u p p e r i n d e x 来标志开始时间和结束时间在二叉树的位置。然而当时间粒度很 小、时间域很大的时候，树的索引空间会变得很大，并且这种结构会浪费很 多无谓的空间。 7 幕于时态拟序的关系数据索引技术第一章绪论 1 3 3 双时态索引技术 在双时态情形( 同时考虑有效时间和事务时间) ，主要是利用有效时间和事 务时间相互“正交 的“二维 性质，借鉴空间数据库r 树技术，研究基于时 间标签的r 树、2 r 树、g r 树、4 r 树等时态索引方法。 文献 2 4 】用r 树来索引双时态数据，但是r 树双时态时间值固定的索引，不 利于处理时态变元刀d w 问题；2 r 树2 5 1 索引采用2 棵r 树，其中第一棵r 树索引 所有固定时间的双时态数据，第二棵r 树索引所有带变元的双时态数据，但是 树只处理事务时间变元”c ，而不能处理有效时间变元以d w ；g r 树( g e n e r a l i z e d r - 慨e ) 1 2 6 】是根据时态变量“c 和刀d w 出现与否以及是否同时出现将相应时态分为 四种基本类型，可以处理钟和刀d w ，g r 树中每个索引项都是这样若干基本类型 集合，通过考察查询矩形与之相交与否完成索引工作。由于现有技术仅支持r 树索引，为避免改造d b m s 内核，人们提出4 r 树【2 7 】技术，将四种基本类型分 别转换为四种形式r 树。文献【2 8 】提出一种通过点转换技术实现聆d w 相关双时态 数据索引方法。 1 3 4 模型产品化 自1 9 9 4 年，陆续开始将时态数据模型“标准化 和“产品化”。目前时态关 系数据库已有实验原型，例如瑞士t i m e c o n s u l t 公司的t i m e d b 2 0 ( 1 9 9 8 ， h t t p ：w 、v wt i m e c o n s u l t c o m s o r w a r e s o r w a r e h t m l )和中国中山大学的 1 e m p d b 2 0 l ( 2 0 0 7 ，h t t p ：、 ，、 ，、v c o s o r s y s u e d u c n 1 m p d b i n d e x h t m ) 。 1 4 论文结构 论文分5 部分，安排如下： 第l 章阐述时态关系数据索引研究的背景，本论文的出发点和意义，国内外 在时态索引结构方面的研究情况以及论文结构编排； 第2 章阐述时间的相关概念和本论文使用的基本理论，介绍与本论文索引模 型做测试对比的m a p 2 1 方法； 第3 章详细阐述时态摘要类和时态拟序的基本概念和性质，时态关系索引模 型豫加d 的索引结构、索引技术以及查询、更新算法； 8 基于时态拟序的关系数据索引技术第一章绪论 第4 章设计和完成相应仿真实验，并且与m a p 2 1 方法进行性能对比，以验 证时态关系索引模型豫加d 的可行性与有效性。 第5 章为结语部分，总结本论文的主要工作成果，分析其中不足，并展望下 一步研究工作。 9 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 第二章时态数据库和时态索引技术 时间是一个既实又虚的概念。“实”是指时间在现实世界中切切实实的存在， 它是刻划事物发展的刻度；“虚是指时间的“无形，时间到底是怎样刻划事物 发展，怎样定义一个时间模型。本章首先介绍时态数据库中时间的基本概念、时 间期间的关系以及时态关系数据中的时态特性，为时间建模：然后介绍时态数据 库基础和分类；最后简单介绍与本论文索引模型做测试对比的m a p 2 l 方法。 2 1 时间建模 2 1 1 时间的基本概念 定义2 1 时间元( c 1 1 r o n o n ) 时间元是计算机系统支持的最小的，不可分割的时间间隔。理论上，时间离 散化的程度可以任意小，但在计算机系统中，离散化程度受到机器性能的制约。 一般p c 平台上，时间元的范围可以从o 0 1 秒到1 秒，可以满足一般应用的需要。 定义2 2 时间粒度( t i m eg r a n u l 撕t ) r ) 时间粒度是时态信息系统中描述时间数据的最小单位，表示时间点之间离散 化程度。时间粒度的选取受到时间元精度的制约。在具体的时态信息系统中，选 择怎样的粒度，由应用需要及系统的能力决定。 定义2 - 3 时间域( t i m ed o m a i n ) 在系统中，给定一个“最小 的不可再分解的时间单位，称其为系统时间元； 时间元的长度称为系统的时间粒度；时间粒度的所有正整数倍数值在正实轴上对 应点称为系统中的时刻；系统最小时刻朋淞和最大时刻聊硝之间所有时刻的 集合称为系统的时间域，记为r ，即r = 沏加s ，聊缄嗣。 定义2 4 时间期间( t i m ei n t e r v a l ) 1 0 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 设f 卜勿r ( “勤) ，f l 、f 2 间所有时刻组成的集合称为以“为起始时刻以f 2 为终止时刻的时间期间，记为弘 r l ，f 2 ) = 【& 口厂f ( 乃，勘政乃) 。单个时刻硒可以看 作是起始时刻与终止时刻相同的时间期间。时间期间是r 中常用的基本子集，r 中所有时间期间集合记为冲。 定义2 5 时间元素( t i m ee l e m e m ) 1 1 的幂集2 。中的子集称为时间元素，即时间元素是由时刻、时刻集和时间期 间构成。 定义2 - 6 时间期间的跨度( i n t e r v a ls p a n ) 设时间期间仁p l ，f 2 ) ，则丁的跨度为f 2 一r l 。 2 1 2 时间期间的关系 a l l e n 在其论文中指出了1 3 种时间期间的关系【2 8 】，为时态关系研究做出了开 创性的工作。这1 3 种关系可以在时间轴上表示如下，其中f l 和乞是时间期间： 表2 1a l l e n 的1 3 种时间期间的关系 时态区间关系图示说明 ，l f 2 f l 在垃之前发生b e f o r e ( f l ，垃) t _ ji _ j f 2f l f l 在如之后发生 a 舭r ( f l ，f 2 ) i 一1 _ j f l ，l 的区间范围包 d u r i n g ( f l ，f 2 ) 。 如 -i 含在如内 f 2赴的区间范围包 c o n t a i n s ( f l ，如) 力 - 含在r l 内 f l 比如早开始且 o v e r l a p s ( ，l ，允) f 2 - 两个区间有相交 o v e r l a p p e d - b y ( ，l ， 如 允比r l 早开始且 于l 幻) li 两个区间有相交 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 r l 允开始于“的结 m e e t s ( f l ，允) l 一如 i 束点 ，2 f l 开始于允的结 m e t - b y ( r l ，允) l 一，l -_ 束点 ，l 和，2 有共同的 s t a r t s ( f l ，f 2 ) 卜一红 _ 起点，f l 比如先结束。 ，1 。 r l 和如有共同的 s t a r t e d - b y ( ，l ，2 ) i f 2 起点，2 比，l 先结束。 “ r l 和乞有共同的 f i n i s h e s ( ，l 如) ，2 ! -i 结束点， 比如晚开 始。 r l ：，l 和如有共同的 - f i n i s h e d - b y ( ，l ，仂 2 i 结束点，垃比r l 晚开 始。 ，i ，l 和如在时间轴 e q u a l s ( ，l ，功 i f 2 i 上重合 在这1 3 种关系中，其中7 对关系可以互相转换，如下： b e f o r e ( f l ，f 2 ) = a r e r 他，f 1 ) d u r i n g o l ，忽) = c o n t a i n s ( ，2 ，1 ) o v e r l a p s ( ，l ，f 2 ) 2o v e r l 印p e d - b y m ，r 1 ) m e e t s ( r l ，允) = m e t - b y ( ，2 ，f 1 ) s t a n s ( 九免) = s t a n e d - b y m ，1 ) f i n i s h e s ( ，l ，2 ) = f i n i s h e d - b y ( ，2 ，1 ) e q u a l s o l ，赴) 2e q u a l s ( 如，1 ) 2 1 3s n o d g r a s s 表示数据模型 s n o d g r a s s 表示数据模型( r e p r e s e n t a t i o n a ld a t am o d e l ，月d 俨9 1 ) 的数据模式 表示为豫( 彳，彳2 ，么门；飓，飓，豫，豫) 。其中彳，彳2 ，彳月，为豫 1 2 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 的非时态属性；胁，忍和胁，m 分别表示有效时间与事务时间的起始于终 止时刻，满足1 n f 要求。这里，胁和m 可以分别为时间变量加w 和甜c 。在 实际数据库存储中，变量材c 和 d w 的取值在r 中单调增长，其最大值可以设定， 例如可取值为“9 9 9 9 一1 2 3l ”。s n o d g r a s s 表示数据模型的基本意义在于将时态标 签看作关系属性。 2 1 4 时态关系数据的基本概念 本文中，时态结点p 定义为一个二元组( 旧( p ) ，玎( 尸) ) ，其中，丁( p ) 和玎( p ) 分别表示p 的非时态部分和有效时间标签。时态结点尸，和n 相等定 义为胛( 尸j ) 却玎( 乃) 八玎( p ) = 刀( n ) 。在讨论时态问题时，不引起混 淆情况下，符号尸和玎( p ) 通常有意混用，可表示有效时间。结点尸的有效 时间期间( v a l i dt i m ep e r i o d ) 玎( 尸) = 胁( 尸) ，豫( p ) ) ，其中胁( p ) 、 m ( 尸) 分别表示玎( p ) 起始和终止时刻。在p 和玎( p ) 混用情况下，也 记风= 胁( p ) ，尸p = 飓( 尸) 或阢村( p ) = 胁( 尸) ，勘d ( p ) = 胁( 尸) 。 另外，记时态结点p 的有效时间跨度三( p ) = p p 珊。时态结点全体记为d ，相 应时间期间集合记为d ( r ) 或r 。 本文涉及时态关系都是基于s n o d 鲈嬲s 表示数据模型( r e p r e s e n t a t i o n a ld a t a m o d e l ，见d 膨2 9 】) ( 1 ) 时间无关属性与时间相关属性 在时态关系豫中，并非所有属性都与时间( 直接) 相关。设彳是豫中属 性。么中所有属性值对应的有效时间期间集合记为纵。设厂是彳的属性值域吆 到吼上的映射场一亿。如果v x 场，都有厂( x ) 气玖，则称彳为时间无关 属性，否则为时间相关属性。例如，在时态关系( n a m e ，i d ，t i t l e ，d e p t ，s a l a r y ， 玎) 中，n a m e 和i d 可以看作时间无关属性，t i t l e 、d e p t 和s a l a r y 可以看作 是时间相关属性。时态关系豫中可以存在多个时间无关属性，时间无关属性在 一定环境中相对稳定，不随时间消长而变化。时间无关属性是具有更强限制的非 时态属性。 1 3 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 ( 2 ) 主体属性和主体实例 定义2 7 ( 主体属性和主体实例)设彳是豫的时间无关属性，则通过彳 可在豫元组之间引入等价关系“三”：时态元组乃，乃具有关系乃兰死营兀a ( 乃) = n a ( 乃) ，其中兀a ( 丁) 表示元组丁在属性彳上的投影。由此得到豫 关于“三 的等价类集合 枷，慨，讹) 。上述彳称为豫的主体属性( m a i n b o d ya t t r i b u t e s ) ，等价类蚴( 1 9 敛) 称为豫关于彳的一个主体实例( m a i n b o d yi n s t a n c e s ) 。 例2 1 ：在表2 2 所示的时态关系p e r s o n n e l 中，“n 锄e ”是时间无关属性， 可作为主体属性。此时表3 中一共有5 个主体实例，分别是a l i c e ，b o b ， c h r i s t i n e ，d a n e ，e l l e n 。另外，c o d e 表示相应时态关系树模型伢幽( 豫) 中 的先序遍历编码( 阡幽将在本文第三章中有所介绍) ，这在数据库中可以不存在， 它的设置是为了下文建立时态索引对结点进行编码之用。 表2 2 时态关系数据实例：人事关系表 c o d en a m e d e p t w t i e s a l a u v s ：v e 2 a l i c e c sv i c e 1 e a d e r5 0 0 0 【3 ，9 ) l 3a l i c ec sc e 1 e a d e r6 0 0 0 9 ，1 8 ) 4a i i c ec sl e a d e r7 0 0 0 1 8 ，n o w ) 6b o bm a t hl e a d e r4 5 0 0 5 ，8 ) 5 7 b o b m a t hl e a d e r5 5 0 0 8 ，2 0 ) 8b o bm a t hl e a d e r7 0 0 0 2 0 ，2 5 ) 1 0c h r i s t i n el sc e 1 e a d e r 5 0 0 0 【5 ，8 ) 9 1 1 c h r i s t i n el sc e 1 e a d e r6 0 0 0 【8 ，2 0 ) 1 3d a n ep h ya s s i s t a n t3 5 0 0 【3 ，9 ) 1 2 1 4d a n ep h ya s s i s t a n t4 5 0 0 【9 ，1 8 ) 1 6 e l l e n c s v i c e 1 e a d e r4 0 0 0 3 ，9 ) 1 5 1 7e l l e nc sc e 1 e a d e r5 0 0 0 【9 ，1 8 ) 1 8e i i e nc sc e 1 e a d e r6 0 0 0 【1 8 ，n o w ) 表2 2 对应的时间期间图如图2 1 所示，从图2 1 可以看出，每个主体实例 对应的时间期间集合： 1 4 基于时态拟序的关系数据索引技术第二章时态数据库的基础知识 ( ijjjj 竺坚坐竺j ! 芏笙笙芏j ! liii i 掣， 6 d i x 。1 ：1 i - j b o b iill c h r i s t i iii d a 鹏 lll e l l t ：r 1 i j 【j i 图2 1 表2 2 的时间期间图 ( 3 ) 时间约束 由于每个主体实例在任意时间点上最多只能属于一个元组，所以同一个主体 实例所包含的时间期间是不重叠的( n o n o v e r l 印) ( 如图2 1 所示) ，但是主体实 例内的时间期间之间允许出现跳跃，即允许之前( b e f o r e ) 或之后( a