（计算机软件与理论专业论文）基于有效时间的时态索引查询技术研究.pdf

中山大学硕士学位论文 基于有效时问的时态索引查询技术研究 基于有效时间的时态索引查询技术研究 专业：计算机软件与理论 硕士生：刘永丽 指导老师：叶小平副教授 摘要 随着数据库和时态处理技术的迅速发展，时态数据库的应用已经渗透在很多 领域。而时态数据库中的数据都是海量存储，时态数据管理的一个基本特征是需 要管理大容量存储的时态数据，因此如何有效、合理、快速和正确地进行时态数 据查询成为人们近年来关注和研究的热点，其中时态索引就是提高时态数据查询 效率的基本技术之一。 基于有效时间的数据管理与查询是一般时态数据库技术研究的起点与基础， 因此有效时间数据库的时态索引技术有其自身可供研究的必要性。现阶段，人们 主要通过一些映射技术将传统的b + 树等进行某些时态扩充来进行有效时间时态 数据字段的索引查询。但是时态数据具有不同于通常关系数据的一些基本特点和 要求，比如时态变量的引入和使用等，使得用b + 树等结构来进行时态索引查询 存在一定的不足之处。因此考虑采用一种新的思路来研究有效时间索引技术具有 一定的意义。 本文的主要工作和贡献是采用一种新的思路来研究基于有效时间的时态索 引查询技术。首先，给出针对历史数据库的有效时间时态数据模型( v t d m ) ； 其次，引入时态连通关系和时态包含关系等相关概念及相关定理，建立有效时间 索引查询模型( v t i q m ) ；然后，在有效时间索引查询模型基本框架内，设计和 分析有效时间时态查询和时态更新算法；最后，设计和完成索引模型的实验模拟 系统来验证本文研究成果，实验结果表明有效时间索引技术具有合理性和高效率 性。 关键词：时态连通关系时态包含关系有效时间索引查询模型 中山大学硕十学位论文基于有效时间的时态索引查询技术研究 s t u d yo ft e m p o r a li n d e x i n gq u e r yt e c h n o l o g y b a s e do nv a l i dt i m 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 ：l i u y o n g l i s u p e r v i s o r ：y ex i a o p i n ga s s o c i a t ep r o f e s s o r a b s t r a c t 、m t ht h 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 r m a t i o nh a n d l i n g t e c h n o l o g y , t h ea p p l i c a t i o no ft e m p o r a ld a t a b a s eh a sc o v e r e da l lw a l k so fl i f e t h e b a s i cf e a t u r eo ft e m p o r a ld a t am a n a g e m e n ti sl a r g e - s c a l et e m p o r a ld a t as t o r a g ei n t e m p o r a ld a t a b a s e ，s oh o w t oi m p r o v et h eq u e r ye f f i c i e n c yh a sb e c o m eah e a t e d i s s u ea n dt e m p o r a li n d e x i n gi so n eo ft h em e t h o d so fi m p r o v i n gq u e r ye f f i c i e n c y t h ed a t am a n a g e m e n ta n dd a t aq u e r yb a s e do nv a l i dt i m ea r et h eb a s i so f t e m p o r a l d a t a b a s e r e s e a r c h ，s o i t s n e c e s s a r yt os t u d yt e m p o r a li n d e x i n g t e c h n o l o g yb a s e do nv r a l i dt i m ed a t a b a s e c u r r e n t l y , p e o p l eh a v ep r o d u c e ds o m e m a p p i n gt e c h n o l o g y t oe x t e n dt h eb + 一t r e et oi n c l u d et e m p o r a ld a t a h o w e v e r ， b e c a u s eo fi m p l i c i tf e a t u r e sa n dr e q u i r e m e n t so ft e m p o r a ld a t a b a s e s u c ha s i n t r o d u c i n gi n t on o w , u s i n gb + - t r e ef o ri n d e x i n gh a ss o m ed r a w b a c k s d i f f e r e n tf r o m t h ee x i s t e dw o r k ，t h i sp a p e rm a k e su s eo fan e wt h i n k i n gt os t u d yt e m p o r a li n d e x i n g q u e r yt e c h n o l o g yb a s e do nv a l i dt i m e t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra l ea sf o l l o w s ：f i r s t ，r a i s e sv a l i dt i m e t e m p o r a ld a t am o d e lb a s e do nh i s t o r yd a t a b a s e s e c o n d ，i n t r o d u c e si n t od e f i n i t i o n s a n dt h e o r e m sr e l a t e dt ot e m p o r a lc o n n e c t e dr e l a t i o na n dt e m p o r a lp a r t i a lr e l a t i o n a n db u i l d sv a l i dt i m ei n d e x i n gq u e r ym o d e l t h i r d ，w i t h i nt h ev t i q mf r a m e w o r k ， d e s i g n sa n da n a l y z e st e m p o r a lq u e r ya l g o r i t h ma n dt e m p o r a lu p d a t i n ga l g o r i t h m f i n a l l y , d e s i g n sa n di m p l e m e n t sa ne x p e r i m e n t a ls i m u l a t i o ns y s t e mo nt h er e l a t i o n a l d a t a b a s ep l a t f o r m ，w h i c hs h o w st h ew o r ko ft h i sp a p e ri sr e a s o n a b l ea n de f f i c i e n t k e yw o r d s ：t e m p o r a lc o n n e c t e da n dt e m p o r a lp a r t i a lr e l a t i o n ，i n d e x i n gq u e r y m o d e 】f o rv a l i dt i m e 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 使用授权声明 签名：童盘面 e t 期：泓年工月卫日 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 刘筮面 e t 期：地卫年月卫日 导师签名：! 厶壬 日期：盈盈年玉月玉e t 中山大学顾：b 学位论文基于有效时间的时态索引查询技术研究 第1 章绪论 本章概要性地论述了时态数据库在数据库研究中的重要地位以及本文研究 的出发点，总结了有效时间索引查询技术的国内外研究现状，阐明了本文的研究 思路，创新点和研究意义，最后介绍了该论文总体的组织结构安排。 1 1 引言 时间是一个客观存在，现实生活中的所有信息都具有相应的时态属性。随着 数据库技术的发展，信息时态性所起的作用越来越关键，因此人们对时态信息处 理的需求也越来越迫切【l 】。 传统的数据管理系统没有对时态数据作处理和对待【2 】，因此不会反映出相关 的历史信息，所以表中的记录总是被认为是实体的当前状态。而我们现实生活中 的很多应用都是跟时间联系在一起的，例如人事管理、医疗管理、财务管理等记 录保存的应用；旅店预定、项目管理等行程安排应用；天气监测等科学应用【3 】。 所有这些应用都要求数据不仅仅反映当前状态，而且也要反映数据发生变化的过 程，所以对历史数据的保存非常重要。因此人们逐渐认识到必须将时态标签“添 加 到数据库应用系统中，数据库技术才真正能在我们的实际生活中发挥它应有 的作用，这就是对时态相关信息展开研究的最初目的。 时态信息的应用早在二十世纪七十年代就已经被关注，并于八十年代至九十 年代中后期的二十余年间，无论在理论方面还是应用开发方面都取得了很大的进 展【3 】。直观上看，时态数据库就是在经典关系数据库数据模式上引入时间标签属 性，但这并不是一种简单的“添加”，随之会引出许多基本问题需要人们研究解 决，包括时态变量的不确定性研究( 变量数据库) 、时态关系代数、时态数据模型、 时态知识表达与逻辑方法以及时态数据索引技术等等。 时态数据库的一个核心特征是，表中记录的删除只是逻辑上进行删除，而在 物理上虽然现在已经失效的记录实际还是作为一个实体存在于数据库中，这样久 而久之，随着插入、更新以及删除操作的不断进行，数据库就会存储有超大规模 的时态数据，因此研究有效的时态数据索引技术来提高查询效率成为人们关注和 中山人学硕i ：学位论文基于有效时间的时态索引查询技术研究 研究的热点。时态数据库的特性主要是由有效时间和事务时间决定的，因此通常 的研究对象包括有有效时间数据库，事务时间数据库和双时态数据库。而在现实 生活中，有效时间数据库是一种较为常见的应用情形，同时也是一般时态数据库 技术研究的起点与基础，它反应数据的有效性，所以基于有效时问的时态数据索 引技术有其自身可供研究的必要性，这也就是本文研究的出发点之一。 1 2 国内外研究现状 在本节，我们对国内外主要的有效时间时态索引技术研究成果进行回顾，包 括有m a p 2 1 索引方法【4 5 】，时间索引【6 1 以及t p 索引 6 ，7 】。下面参考以上提到的文 献对这三种索引方法进行简要阐述。 1 2 1 时间索引( t i m ei n d e x ) 时间索引方法通过扩张b + 树来包含时态信息，树的每个叶结点中持有一个 线性有序并且介于 0 ，n o w 问的索引点集合，其索引点主要根据n o w ，某元组有 效时间的开始端点和某元组有效时间末端点之后的那个时间点来决定。扩展后的 b + 树中每个叶子结点都包含一组形如( 卉，彳r ) 的指针集合，这里彳，是指向所有在 时间t i 有效的元组的指针。为减少存储的指针数，每个叶子结点仅保留主要的指 针桶。而且对于每个叶子结点的某指针彳，仅仅记录发生的改变。 假设有关系如表1 1 所示。该有效时间数据库中每个人都有唯一的p i d ，属 性e n t r y p t 代表某人进入美国的入口点，t u p l e 代表元组，v ( t ) 代表某人参观城 市的持续时间，开始端点代表进入时刻，结束端点是离开时刻。根据前面提到的 时间索引方法，得到表1 1 的索引b + 树如图1 1 所示。 根据索引树，就可以根据给定的查询目标进行查询。假如要查询“在第4 天 到第6 天期间一直待在美国的所有人。我们仅需要遍历该b + 树找到包含有点 4 的叶结点，然后一直往右搜索到点6 ( 利用有序特点) 。 该方法相对遍历整个数据库来说，显然获得了很高的效率，因为它不必遍历 所有的元组就可以找到答案。但是它的实现要占用大量的空间组件，而使得现有 d b m s 不能很好的受益于此方法，其次由于索引的最大时间点只能到n o w ，所 2 中山人学硕士学位论文 基于有效时间的时态索引查询技术研究 以我们只能局限于索引末端点值小于n o w 的有效时间区间。因此这种方法不能 很好地运用在变量数据库的情形之上，因而也没有得到广泛的应用。 表1 - 1 到达离开关系 t u p l ep i de n t r y - p tv ( t ) t l p l n y 0 , 3 】 t 2 p l l a 【4 , n o w 】 t 4 p 2 s f o 0 , 5 t 7 p 3 l a 0 ，7 】 t 8 p 3 s f o 8 , 9 】 t 1 0 p 4 n y 【2 , 3 】 t 1 1 p 4 l a 8 ，n o w t 1 2 p 5 l a 1 0 ，n o w 】 t 1 3 p 6 n y 1 2 ，n o w 】 t 1 4 p 7 n y 1 1 ，n o 吲 ( + t 8 ，+ t 11 , - t 7 )( + t 1 4 ) 图1 - 1 时间索引b + 树 1 2 2t p 索引( t i m e p o l y g o ni n d e x ) t p 索引方法就是把给定的有效时间区间通过映射策略i s t 变换成二维空间 点，通过这个变换，数据被分配在不同的多边形中。 定义1 - 1 映射函数 设= 口，纠，a ，b 【o ，n o w ，伊= 口，a 【o ，n o w ) 且映射函数为善：- - - 伊2 ， 则给定有效时间【口，b 】，有善( k ，易】) = ( 口，b - a ) 。 我们利用映射函数可以把表1 1 中的元组映射到二维坐标上，如图1 2 所示。 3 中山人学硕士学位论文 基于有效时间的时态索引查询技术研究 y 图1 2 映射有效时同为二维至同点 由图1 2 可知，如果一个元组的有效时间起始时间v s = a ，则该元组一定在线 x = a 上；如果一个元组的有效时间结束时间v e - - - b ，则该元组一定在线 x + y = b 上；如果一个元组有效时间的间隔为c ，则该元组一定在线y = c 上。 假如有三个查询任务： ( a ) 列出所有在第厶天进城或者第如天之前进城的人 ( b ) 列出所有在第如天离开城或者第如天之后离开城的人 ( c ) 列出所有待在城里总共厶天或少于如天的人 则搜索的结果分别如图1 3 ( a ) ，( b ) ，( c ) 所示。 y (a)(b)( c ) 图1 - 3 时态对应的空间二维查询 同样地，这种方法最大索引时间点只能到n o w ，因此也不能很好地应用在 4 中山大学硕：仁学位论文 基于有效时间的时态索引查询技术研究 变量数据库的情形之上，从而得不到广泛应用。 1 2 3m a p 2 1 索引 m a p 2 1 是一个简单且有效的索引时间区间的方法。其基本思想是映射一个 有效时间区间为一个一维点，然后运用b + 树索引该点来达到索引有效时间区间 目的。 一个索引区间的开始和结束点满足条件：( 口) 非负整数( b ) 限定上界，如 y = 殆，v e j0 眙v e 1 0 口- 1 ，口是一定值常量。将一个区间转换为点的映 射函数为：f ( 矿) = f ( v s ，您) = v s l o 口+ v e 。给定= 嘭，哆】，v 7 = 【，形 以及 f ( y ) ，则哆 jf ( v 。) f ( v 7 ) ；嘭= 嘭 z ”，则称r ”修正了r ”。 如图2 1 ( a ) ，( b ) 所示【4 1 。 v a l i dt i m e 川 r l r 2 川 v a l i dt i m e 川 图2 - 1 修正与版本 1 5 r 1 r 2 川 ( b ) r 2 i sac o r r e c t i o n o f r l 中山人学硕士学位论文 基于有效时间的时态索引查询技术研究 定义2 - 2 有效时间的查询 给定有效时间间隔t = 【v s ，v e ) ( 查询目标) ，找到”d u r i n g ”t 的所有记录。 ”d u r i n g ”的语义因人而定，按照一般情况，可以把”d u r i n g ”定义为四种情况，如 图2 2 所示【4 1 。 q u e r yt y p e( a ) l o c a t i o n( b ) c o n t a i n m e n t( c ) i n c l u s i o n( d ) i n t e r s e c t i o n l n p u t p o s s i b l h 卜叫 1 jh e 日 ；h _ o u t p u t ii i lill：_ 图2 - 2 有效时间的查询形式 需要说明的是，本文采用的查询形式是“c o n t a i n m e n t ”和“i n c l u s i o n ”，即 查询所有包含目标区间的记录或查询所有包含目标区间的记录，其它形式的查询 还有待在今后的工作中进一步完成。 1 6 中山大学硕士学位论文 基于有效时间的时态索引查询技术研究 第3 章有效时间时态索引查询算法 在国内外研究现状章节中，我们已经介绍了现有的有效时间时态索引技术研 究成果，从中可知这些时态索引采用的结构普遍都是b + 树，其中最为著名的是 m a p 2 1 算法。而本章将完全脱离传统所使用的b + 树结构，通过一种新的研究思 路和方法来设计有效时间时态索引查询模型，具体内容安排如下：首先，给出针 对历史数据库的有效时间时态数据模型；其次，引入时态期间关系的相关定义和 定理建立有效时间时态索引查询模型( v t i q m ) 然后，在时态索引模型框架内 阐述索引查询算法的具体实现步骤，并通过具体实例来分析阐述；最后，对时态 查询算法进行复杂度分析。 3 1 有效时间时态数据模型 从理论分析和实际应用出发，现阶段人们已经提出了多种时态数据模型2 6 1 。 其中较为著名的是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 ) ， 其数据模式为： r ( 4 ，4 l ，t s ，t e ，v s ，v e ) 其中彳l ，么。为关系数据的属性( 非时态属性) ，t s ，t e 分别表示事务时间 的起始时刻和终止时刻，殆，您分别表示有效时间的起始时刻和终止时刻，即 事务时间期间为 乃，死) ，有效时间期间为 v s ，v e ) 。 为了能在已有数据库系统上实现有效时间时态索引技术，本文将表示数据模 型进行必要修改和扩充，得出针对历史数据库的有效时间时态数据模型。 定义3 - 1 有效时间时态数据模型( v t d m ) 考虑到历史数据库中有效时间变量n o w 的存在性，本文将变量绑定算子整 合在有效时间的时态数据模型中，得到二元组v t d m = ( v t r ，b i n d i n g ( ) ) 。 m 为v t d m 对应的数据模式：v t r ( a 1 ，4 ，v t s ，v t e ) 其中彳l ，彳。为关系数据非时态属性，v t s ，v t e 分别表示有效时间阿起始 时刻和终止时刻。且必须有v t s v t e 。 1 7 中山人学硕上学位论文 基于有效时问的时态索引盎询技术研究 b i n d i n g o 为有效时间终止端点v t e 的时间绑定算子。其定义为，如果v t e 是确定时刻，则b i n d i n g ( v t e ) = v t e ；如果v t e 是有效时间变量n o w ，则b i n d i n g ( ) 算子根据n o w 的具体语义有不同的绑定结果。本文将b i n d i n g ( v t e ) 绑定为当前时 间c t ，由于对有效时间变量n o w 的不确定性研究不在本文的讨论范畴内，所以 关于n o w 过去语义和将来语义的具体绑定算法本文不加以探讨。 例3 1 ：下面是一个v t d m 的关系实例，包括有属性n a m e ，t i t i l e ，s a l a r y ，v t s 和v t e 。如表3 1 所示。 表3 - 1 基于v t d m 模型的实例 n a m et i t l e s a l a r y v t sv t e b o b a s s o c i a t ep r o f4 0 0 02 0 0 3 0 9 一ol2 0 0 4 一0 8 3l b o ba s s o c i a t ep r o f4 5 0 02 0 0 4 0 9 01 2 0 0 5 0 8 31 b o bp r o f6 0 0 02 0 0 5 0 9 一o12 0 0 5 1 2 3 1 b o b p r o f6 5 0 02 0 0 6 0 1 0 1n o w 基于数据库系统时态完整性考虑，对于任何一个元组a 的有效时间区间 v t s ( a ) ，v t e ( a ) 】，都有v t s ( a ) v t e ( a ) 。此外还需要引入有效时间约束条件如下： 设有两个时态关系实例v t r l 和v t r 2 ，若属性集合a 是v t r l 中关于v t r 2 的 外键，则有v t ( a ，v t m ) n v t ( a ，v t r 2 ) 囝，其中a 是属性集a 对应的关系元组， v t ( a ，v t r l ) 和g t ( a ，v t r 2 ) 分别表示a 在v r r l 和v t r 2 中的有效时间期间。 3 2 时态期间关系 在给定系统中，根据问题需要确定的时间单位称为系统的时间粒度；所有时 间粒度的正整数倍称为系统的时间点；根据问题需要取定的所有时间点或部分时 间点组成的集合称为系统的时间域。给定两个时间点t l 和t 2 ，t l 和f 2 之间所有时 间点的集合t 称为时间期间( t i m ep e r i o d ) ，记为t = f l ，t 2 】，时间点t o 可以看作 是特殊的时间期间【f o ，f o 】。 设v r ( a ) 表示时态元组a 所对应的有效时间期间，则有表示形式如下：记 玎( 口) = g t s ( a ) ，v t e ( a ) 】( v t s ( a ) g t e ( a ) ) ，其中g t s ( a ) 和v t e ( a ) 分别表示 v t ( a ) 起始时间点和终止时间点。时间期间是研究一般时间元素的基础，本文提 及的时态数据有效时间均假设为时间期间。对数据进行操作( 查询或更新) 的时 中山大学硕i ：学位论文基于有效时间的时态索引查询技术研究 间称为当前时间( c u r r e n tt i m e ) ，记为c t 。下面考察时间期间的关系。 定义3 2 时态连通关系 设r 是元组集合。r 中的两个元素u 和v 存在时态连通关系，当且仅当u 和v 满足下面条件中的其中一个。( 1 ) u t ( u ) nr t ( v ) f 2 j 。( 2 ) f 中存在元组 u l ，9 2 ，u 一，使得如下关系成立：玎 ) nv t ( m ) g ，u r ( u , ) nv t ( u 2 ) o ， v t ( u 月一1 ) nv t ( u 以) o ，v t ( u 盯) nf t ( v ) g ( “f 是集合r 中的元素) 【2 7 】。 定理3 - 1 时态连通关系是一个等价关系 证明：设u 和1 ，是元组集合r 中的任意两个元组。 自反性：由于玎似) n 刀 ) g ，因此“与u 存在时态连通关系。 对称性：如果u 和v 存在时态连通关系，则根据定义知，存在元组u l ，u 2 ，u 疗， 使得如下关系成立：玎似) nv t ( m ) o ，v r ( u , ) nv t ( u 2 ) o ， 玎( “打一o n v t ( u n ) o ，r r ( u 厅) n 玎( v ) 囝。由于交集本身又是 等价关系，则显然v t ( v ) n v t ( u 一) f 2 j ，v t ( u 。) nv r ( u 门一i ) g ， v r ( u 2 ) nv t ( u 1 ) 0 ，v t ( u 0 nv t ( v ) g 也成立，即元组v 与u 存 在时态连通关系。 传递性：如果甜和v 存在时态连通关系，y 和p 存在时态连通关系，则存在 元组“l ，u 2 ，“一，使得阿似) nv t ( m ) g ，v t ( u o nv t ( r 2 ) o ， ，v t ( u n onl t ( u n ) g ，刀( 甜月) n 阿( y ) o 成立，且存在元 组v i ，v 2 ，v n ，使得v t ( v ) nv t ( v 1 ) g ，v t ( v 1 ) nv t ( v 2 ) - t t ：o ， v t ( v n 1 ) n v t ( v n ) a ，v t ( v ) n 刀( p ) g 成立，根据交集的性 质知有关系v t ( u ) nv t ( p ) o ，所以“和p 也存在时态连通关系。 综上，时态连通关系满足自反性、对称性和传递性，故它是一个等价关系。 定义3 3 拟序关系 给定集合彳，如果有关系r 互a x a 且尺仅满足自反性和传递性，则称r 是 彳上的拟序关系。 定义3 4 时态包含关系 1 9 中山人学硕上学位论文 基于有效时间的时态索引查询技术研究 如果两元组u 和1 ，的有效时间区间存在包含与被包含的关系，则称u 和v 之 间存在时态包含关系。由上述定义可知，时态包含关系“尺 是满足自反性和传 递性的拟序关系。 定义3 5 端点比较关系 设1 1 为有效时间区间集合，且p i r ( i = l ，2 ，刀) ，r s ( p z ) 代表起始端点， t e ( p i ) 代表终止端点。 始点比较关系”s ”：p 1 s p 2 s ，s p n t s ( p 1 ) t s ( p 2 ) t s ( p n ) ， 若乃( 只) = r s ( p j ) ，按t e ( p i ) ，t e ( e j ) “小前，大后 排序。另外 ( 风) + = p ip i sp ) ，( e s ) - = p ip sp i 。 终点比较关系”e ”： p 1 e p 2 e ，e p nc ，r e ( p 1 ) t e ( p 2 ) t e ( p n ) ，若t e ( p i ) = r e ( e j ) ，按 t s ( p i ) ，t s ( e j ) “小前，大后排序。另外，( r ) + = e ji 巧e p ) ， ( p e ) - = p jl 尸ee j ) 。 定义3 - 6 前序集合和后序集合 由时态包含关系，我们引出了前序集合和后序集合的概念：对于有效时间段 p ，p 的前序集合尺+ ( p ) 和后序集合r 一( p ) 分别为：尺+ ( 竹= p ip i p ) ， r 一( p ) = p ii 尸p i 即有：r 一( 尸) = ( p s ) + n ( 凡) 一 尺+ ( p ) = ( p s ) 一n ( 尸台) + 定理3 2 连通等价类的时态属性 用 u ， 1 ，】代表两个连通等价类，玎( “ ) 代表等价类 “ 中所有时间区间的 并集，阿( v 】) 代表等价类 1 ， 中所有时间区间的并集。有定理：如果 “ v 】， 则玎( 陬】) n 玎( 1 ，】) = a 。 证明：我们需证明：若阿( “ ) n 玎( v 】) o ，则 比 - v 。证明过程如下： 如果玎( “ ) n 刀( 1 ，】) a ，则j 口“ ，b y ，使得a 与b 存在时态 连通关系，即a 与b 在同一个等价类中( u _ 1 ， ) ，定理得证。 2 0 中山大学硕上学位论文 基于有效时间的时态索引查询技术研究 例3 - 2 ： 设时间期间拟序集合q = p 1 ，p 2 ，p i1 ) ，如图3 - 1 所示。 p i 0 ，1 0 ) 八 p 2 o ，5 】p 3 p 6 1 6 ，7 ) p 7 1 7 ，9 ) 图3 - 1 拟序关系集合 解： 按”s ”排序： p 4 s p 2 s p l s p 5 s p 9 s p ll s p 3 s p 6 s p 7 s p 8 s p l 0 按”e ”排序： 尸4 e p 2 e p 5 e p 6 e p 9 e p 7 e p l e p 3 e p 8 b p l1 e p l 0 根据上面的定义知：r - ( p 3 ) = p 3 ，p 1 ，p 11 ) r + ( p 3 ) = p 3 ，尸6 ，尸7 ，用) 3 3 有效时间时态索引查询模型 时态连通关系可以导致连通等价类的形成，由时态包含关系引出的前序集合 和后序集合可以形成拟序关系集。在本节我们会看到时态连通关系和时态包含关 系是建立时态索引查询模型的理论基础，连通等价类和拟序关系集是时态索引查 询模型的核心支柱。根据前面提到的定义以及相关定理得到了下面的有效时间时 态索引查询模型。 定义3 7 有效时间索引查询模型v t i q m 基于有效时间数据模型( v t d m ) 的v t i q m 可以设计为一个具有根结点、 内结点和叶结点的三层树型结构，如图3 2 所示。其中： 1 根结点：由有效时间数据库中的关系表v t r 确定。 2 内结点：由v t r 中各元组有效时间区间所形成的连通等价类组成，每 一个连通等价类 甜】的有效时间期间阿( “ ) = u ve u l t ( v ) ，然后就用 阿( “ ) 来标志相应的内结点。 2 l b 州 八 中山大学硕士学位论文基于自效时间的时态索引盘询技术研究 3 叶结点：由连通等价类中每个元素的拟序关系集组成，每个拟序关系 集结点的有效时间定义为该关系类元组中的最大时间期间。 图3 2 有效时间索引查询模型 我们建立该索引查询模型的初衷就是想通过连通等价类和拟序关系集来缩 小查询搜索范围，从而提高查询效率。从图3 2 可知，模型首先将表中的元组分 配在区间互不相交的若干个连通等价类中，因此在进行搜索的时候，首先需要确 定目标等价类，找到目标等价类后，就不需要对其它连通等价类中的元素进行遍 历，从而我们在模型的第二层上初步达到了缩小搜索范围的目的，之后再根据目 标等价类中前序集合和后序集合的概念来减少一些不必要的遍历，从而在模型的 第三层上我们进一步缩小了查询搜索范围，因此从总体上提高了查询效率。 前面提到，本文的有效时间查询只针对“c o n t a i n m e n t ”和“i n c l u s i o n ”这两 种形式。因此结合这两种查询的定义，我们还需要在模型的连通等价类层( 第二 层) 对等价类中元素进行排序形成两个有序版本，使得不同的查询形式对应不同 的有序版本。这里之所以要对等价类中元素进行排序是因为：当一个大的等价类 成为搜索空间时，由于等价类中的元素是杂乱无章( 无序) 的，因此只能采用依 次遍历的方法来查找目标进入点，这就一定会影响查询效率，因此我们可以通过 使元素有序来加速搜索速度。此外我们还需要在模型的拟序关系集层( 第三层) 针对不同查询形式来选用不同的拟序关系，即前序集合或后序集合，这在后面时 态查询算法中会具体体现。因此在实际的操作上我们根据有效时间查询本身的特 点对这个索引模型做了进一步扩充，以期望它能很好进行索引工作。 后面关于时态查询算法以及第四章关于时态更新算法的分析讨论都是在有 效时间时态索引查询模型的基本框架中进行的。 中山大学硕士学位论文 基于有效时间的时态索引查询技术研究 3 4 有效时间时态查询基本思想 我们已经知道建立索引模型的初衷就是想通过连通等价类和拟序关系集来 缩小查询搜索范围，从而提高查询效率。有效时间索引模型形成的基本思路如下： 如果仅仅由时态连通关系引出的连通等价类来建立时态索引结构，则由于有效时 间区间的不确定性和随机性以及连通等价类有效时间区间是各个元素期间并集 的特点，最后得出的等价类有效时间期间可能会“很大且最后的索引结构也会 过于“粗放”，从而会带来索引效率低下和效果不够理想等问题。因此我们需要 考虑基于连通等价类索引结构进一步“分层细化”，本文采用的方法就是在连通 等价类上建立拟序子结构，即划分前序集合和后序集合。 时间期间包含关系作为拟序关系，在索引过程中可以体现出其特点。如果查 询目标q 的有效时间期间v t ( q ) 被元素a o 的有效时间期间v t ( a o ) 所包含，则 v a j r 一( a i ) ，都有v t ( q ) v t ( a j ) ：同理如果v t ( q ) 互v t ( a j ) ，则v a j r + ( 以f ) 都有v t ( q ) w ( a j ) ，由此避免了遍历搜索，体现了索引的基本思路。 总结上述思想，有效时间索引查询模型能够提高查询效率的理论根据是通过 连通等价类和拟序关系集来缩小遍历范围，从而减少遍历结点数。通过图3 2 不 难知道，基于该索引模型进行遍历的过程为：首先遍历根结点，然后遍历目标等 价类结点，对于目标等价类的一个查询结果或非查询结果，其通过三层结点代表 的拟序关系集都是或都不是查询结果，直到等价类中结点搜索完毕。 按照上述考虑，基于v t i q m 的查询算法主要由两个基本步骤组成：首先， 搜索目标连通等价类；其次，在等价类中基于拟序关系集进行结果查询。其中查 询的关键在第二步。 3 5 索引查询模型的算法实现 在算法实现上，由于拟序关系不满足对称性质，结点的拟序关系集可能会相 交，而且对于等价类情形来说，由于一个连通等价类中的元素具有不规则型和随 意性，且一个等价类可能会很大( 包含有很多元素) ，这样如果要求得等价类中 每个元素的拟序关系集来建立索引模型需要非常大的工作量。所以从索引效率角 度考虑，不能直接从建立等价类中元素的拟序关系集入手，即对于结点连通等价 中山人学顾：i ：学位论文基于有效时间的时态索引查询技术研究 类来说，本文将研究其基于拟序结构但不通过直接或全面建立拟序关系集的搜索 算法。 上一章提到有效时间有多种查询形式，本文采用了“c o n t a i n m e n t ”和 “i n c l u s i o n ”两种常用形式，而其它查询形式还有待在今后的工作中通过对算法 加以完善来完成。不同的查询形式在算法实现上会稍有不同，下面具体介绍基于 这两种形式的索引查询算法实现。 3 5 1 索引查询模型的算法具体实现 在算法实现中，对v t d m 元组建立索引模型的过程实际上就是对元组建立 连通等价类的过程。根据时态连通关系把元组分布在若干个不相交的连通等价类 d l ，d 2 ，中，并对各个等价类d f 中的元素按照有效时间起始时间从小到大和从大 到小的顺序分别排列( 如果两个元素相应的有效时间起始时间相同，则按照结束 时间从小到大的顺序排列) 得到两种有序版本d n ，d i 2 ；然后把每个等价类d f 中 元素的有效时间并起来得到该连通等价类d ，相应的有效时间区间v t ( d i ) 。这里 先要对等价类中的元素进行起始时间端点排序的目的也是提高搜索效率。 基于索引通用模块进行查找的过程根据有效时间具体的查询形式而稍有不 同。具体步骤如下： s t e pl ：用户输入查询语句 s t e p2 ：解析查询语句，得到查询形式和查询目标阿( q ) 等关键信息。根据 查询形式分为两种情况： ( 1 ) 查询形式是“c o n t a i n m e n t ”时，判断哪一个等价类d 的有效时间区间 包含v r ( q ) ，即r r ( q ) v r ( o ) 。这里假定找出的目标等价类为d f ，我们取d f 的 d i 2 有序版本。设d i 2 = a l ，a 2 ，a 。) ，其中用v t s ( a ，) 代表元组相应起始端点， v t e ( a f ) 代表元组相应终端端点，查询目标阿( q ) 的起始端点为v r s ( o ) ，终端端 点为v t e ( q ) 。查询步骤如下： 开始：在 z t s ( m ) ，v t s ( a 2 ) ，v t s ( a 。) ) 中用折半查找算法找到不大于 “v t s ( q ) 的最大者z t s ( a i _ ) ，a i 是v t s ( a _ ) 对应的元组结点。这样的结点可能有 多个，只需确定其中之- - 最r j 可( 因为在一个时态连通等价类中，相交的两个结点 中山大学硕士学位论文基于有效时问的时态索引查询技术研究 有可能起始端点相等) 。对于找到的元素a i ，相应于查询目标v t ( q ) ，存在两种 情况： c a s ei ：v t ( q ) v t ( a _ f ) ，即a i 是一个查询结果。则在d - a i + l ，a 一) 中 递归地求出a i 的后向关系类j r 一( 口f ) ，尺一( 以f ) 中的所有结点都是相应于v t ( q ) 的 查询结果。如果等价类中元素未搜索完毕，就继续在d ”= d 一r 一( 口f ) 中，从“开 始 处按照类似的步骤进行搜索。 c a s ei i ：玎( q ) 刀f ) ，即a i 不是一个查询结果。则从端点集合 d i 一 a i + l ，a 一) 中“向后”搜索，直到找到一个元素a k ，使得v t ( q ) v t ( a k ) ， 则可以跳跃到c a s ei 的步骤进行搜索判断，否则仍按照c a s ei i 进行搜索判断直 到搜索完毕。 ( 2 ) 查询形式是“i n c l u s i o n 时，判断哪一个等价类d 的有效时间区间与 阿( q ) 相交，即v t ( q ) n v t ( d ) o 。这里假定找出的目标等价类为d f ，我们取 d f 的d l 有序版本。设d i l = 也l ，a 2 ，a 月) ，查询步骤如下： 开始：在 v t s ( m ) ，v t s ( m ) ，v t s ( a 一) ) 中折半查找到不小于“v t s ( q ) 的最小者v t s ( a i ) ，a i 是v t s ( a j _ ) 对应的元组结点。对于找到的元素a i ，相应于查 询目标v t ( q ) ，存在两种情况： c a s el ：y t ( a i ) v t ( q ) ，即a i 是一个查询结果。则在d = a i + 1 ，a n 中 递归地求出a i 的前向关系类尺+ ( a i ) ，r + ( a i ) 中的所有结点都是相应于v t ( q ) 的 查询结果。如果等价类中元素未搜索完毕，就继续在d k d 一r + ( a i ) 中，从“开 始 处按照类似的步骤进行搜索。 c a s ei i ：v t ( a i ) v t ( q ) ，即a i 不是一个查询结果。则从端点集合 d t _ a i + l ，a n 中“向后”搜索，直到找到一个元素a k ，使得y t ( a k ) v r ( q ) ， 则可以跳跃到c a s ei 的步骤进行搜索判断，否则仍按照c a s ei i 进行搜索判断直 到搜索完毕。 基于以上对索引查询模型算法实现的讨沦，我们知道对于查询目标玎( q ) 来 说，不管是哪种查询形式，用户都不需要在所有的元组中一个个进行比较搜索( 遍 历查询) ，很显然算法利用连通等价类初步缩小了搜索范围的同时，紧接着又利 中山大学硕上学位论文基于有