（计算机应用技术专业论文）基于时态摘要的对象关系数据索引研究.pdf

基于时态摘要的对象关系数据索引研究摘要 基于时态摘要的对象关系数据索引研究 专业：计算机应用技术专业 硕士生：杨博量 指导老师：叶，j 、平副教授 摘要 随着数据库的应用技术的不断发展，许多新的数据类型不断出现，如多媒 体数据，空间数据，科学数据，地理数据等，传统数据库在支持复杂数据类型、 长事务、嵌套事务等方面存在缺陷，已不能很好地满足新的应用需求。对象关系 数据库继承了关系数据库系统本身成熟的技术，同时又将面向对象技术引入到关 系数据库系统中，使得它具有处理复杂对象数据等方面的能力。 索引是提高数据库查询性能的重要技术。但还没有一种普遍应用于所有需 求环境且高效的时态数据索引，对象关系数据库时态索引技术是一个新的研究， 在国内外都取得了一些成果，但这些索引技术都有以下的一些缺点：如在结构上 比较复杂，导致空间复杂度较高，时态查询效率较低，维护代价也比较高，通用 性不强。因此对象关系数据时态索引技术的应用研究有比较大的意义。 针对对象关系数据自身的特征，本文借鉴了中山大学数据库与协同软件实 验室基于线序时态的对象数据建立时态索引的思想，有效地利用时态数据的相似 性，压缩原始数据，利用时态信息的包含关系和结构相当关系专门针对有效时间 对时态对象关系数据建立索引模型t o r i n d ，实现时态对象关系数据的查询，并 且改进了由于时态结点插入或者删除而导致的时态线序分枝发生变化的增量式 更新算法，解决了之前的无法实现完备增量式更新的问题；此外，本文提出的 冗埭i n d 索引结构，具有基本数学支撑，可以适用于比较广泛的对象关系数据应 用领域；同时本文还设计了基本实验，并通过大量数据的模拟仿真实验，验证了 索引模型t o r i n d 的可行性和有效性，提高了时态对象关系数据查询的效率。 关键词：时态对象关系数据索引，有效时间，时态摘要，时态线序分枝完备更新 算法 基于时态摘要的对象关系数据索引研究a b s t r a c t r e s e a r c ho nt e m p o r a lo b je c t - r e l a t i o n a ld a t ai n d e x b a s e do i lt e m p o r a ls u m m a r y m a j o r ： n a m e ： c o m p u t e ra p p l i c a t i o nt e c h n o l o g y y a n gb o l i a n g 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 t ht h es u s t a i n a b l ed e v e l o p m e n to fd a t a b a s et e c h n o l o g y , m a n yn e wd a t at y p e s e m e r g e ，s u c ha sm u l t i m e d i ad a t a ，s p a t i a ld a t a ，s c i e n t i f i cd a t a ，g e o g r a p h i cd a t a ，e t e b u tt h e r ea r ed e f e c t si nt r a d i t i o n a ld a t a b a s e s u p p o r t i n gc o m p l e xd a t at y p e s ，l o n g t r a n s a c t i o na n dn e s t e dt r a n s a c t i o n s ，i tc a nn o tm e e tt h en e e d so ft h e s en e w a p p l i c a t i o n s o r d be m e r g e s ，i ti n h e r i t st h em a t u r et e c h n o l o g yo fr e l a t i o n a ld a t a b a s e s y s t e ma n da d d so b j e c t o r i e n t e dt e c h n o l o g yi n t or e l a t i o n s d a t a b a s es y s t e m st o e n h a n c ei t sp r o c e s so fc o m p l e xo b j e c td a t a i n d e x i n gi st h ei m p o r t a n tt e c h n o l o g yf o ri m p r o v i n gt h eq u e r y i n gp e r f o r m a n c eo f d a t a b a s e b u tt h e r ei sn oe f f i c i e n tt e m p o r a ld a t ai n d e xc a nm e e tt h en e e d so fa l lt h e c i r c u m s t a n c e s t h ei n d e x i n gt e c h n o l o g yo ft e m p o r a lo b j e c t - r e l a t i o n a ld a t ai sn e w t h e r ea r es o m ed i s a d v a n t a g e si nt h ea c h i e v e m e n t so f t e m p o r a lo b j e c t - r e l a t i o n a li n d e x ， s u c ha s ：t h es t r u c t u r e so ft h e s ei n d e x e sa r ec o m p l i c a t e da n dt h es p a c ec o m p l e x i t i e sa r e h i g h ，o rt h eq u e r yp e r f o r m a n c ei sl o w , o rt h em a i n t e n a n c ec o s ti sh i g l l ，o rl a c ko f g e n e r a l i t y i ti si m p o r t a n tt om a k er e s e a r c ho nt h ei n d e x i n gt e c h n o l o g yo ft e m p o r a l o b j e c t r e l a t i o n a ld a t a f o rt h ec h a r a c t e r i s t i c so ft h eo b j e c t r e l a t i o n a ld a t ai t s e l f , a n dw i t ht h er e f e r e n c e t ot h ei d e ao ft e m p o r a lo b j e c t o r i e n t e dd a t ai n d e xb a s e do nl i n e a ro r d e rw h i c hc o m e s f r o mc o - s o f tr & dc e n t e r ，s u ny a t - s e nu n i v e r s i t y , t h ed i s s e r t a t i o nc o m p r e s so r i g i n a l d a t au s e st h es i m i l a r i t yt ot h er e a l i t yd a t aa n dt h er e l a t i o no fs a m es t r u c t u r e ，c o n s t r u c t t e m p o r a lo b j e c t - - r e l a t i o n a ld a t ai n d e xm o d e l - - t o r i n du s i n gt h ec o n t a i n m e n tr e l a t i o no f t e m p o r a li n f o r m a t i o nb 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 a n dt h e i i i 基于时态摘要的对象关系数据索引研究 a b s t r a c t d i s s e r t a t i o nh a sa l s om a d ei m p r o v e m e n t si nt h ec o m p l e t eu p d a t i n ga l g o r i t h mo f t e m p o r a ll i n e a ro r d e rb r a n c h ，w h i c hw i l lb ec h a n g e dw h e nn e wn o d e si sa d d e di n t oo r d e l e t e df r o mt h ed a t a b a s e t h es t r u c t u r eo fm o d e l - t o r i n di s s u p p o r t e db y m a t h e m a t i c a lt h e o r y , c a nb ew i d e l yu s e d i nt h ee n d ，t h ed i s s e r t a t i o nd e s i g n ss o m e s i m u l a t i o nt oe v a l u a t et h ei n d e xm o d e l r o r i n d , a n dt h er e s u l t so ft h ee x p e r i m e n t s s h o wt h ew o r ki sf e a s i b l ea n de m c i e n t k e yw o r d s ：t e m p o r a lo b j e c t - r e l a t i o n a ld a t ai n d e x ，v a l i dt i m e ，t e m p o r a ls u m m a r y , c o m p l e t eu p d a t i n ga l g o r i t h mo ft e m p o r a ll i n e a ro r d e rb r a n c h i v 本人郑重声明： 论文原创性声明 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 论文作者签名：柄谚鼍 日期：砂l o 年月z h 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：杨壤暹 日期：列。年6 月2e l 导师签名：蚪9 早 1 日期：加加年6 月弓日 基于时态摘要的对象关系数据索引研究第- 一章引言 1 1 研究背景 第一章引言 近年来，一些新的应用领域包括c a d ( 计算机辅助设计) ，c a m ( 计算机 辅助工程) ，c i m ( 计算机集成制造) ，c a s e ( 计算机辅助软件工程) ，o i s ( 办 公信息系统) ，g i s ( 地理信息系统) 等对数据库技术提出了许多新的要求，比 如工程对象的构成关系较复杂，要求存储和管理复杂的对象数据。这些领域中的 数据类型较多，要求具有用户自定义数据类型的可扩展能力，支持新应用领域中 的数据类型，如多媒体数据，空间数据，科学数据，地理数据等，传统的关系数 据库技术已经不能满足这些要求，而随后出现的面向对象数据库( o o d b ) 尽管 能适应非传统应用的需要，但缺少一个共通的数据模型，且纯粹的面向对象的数 据库不支持s q l 数据库的标准查询，这些缺陷阻碍了它的广泛应用。此时对象 关系数据库( 0 r d b ) 应运而生，它通过在关系数据库上通过引入新的数据类型 突破了1 n f 限制，吸取了面向对象技术的基本概念，通过“引用”，“继承等 技术增添了面向对象过程的部分功能。在当时，m s t o n e b r a k e r 认为它是数据库 技术发展的下一个大浪潮【l 】。 时间是自然界无所不在的客观属性，所有的信息都具有相应的时态属性【2 】。 人们在分析问题，进行决策的时候，不但需要现在的数据信息，还需要过去甚至 将来的信息，在信息时代，时间更加显示了它的重要性它是“信息 的基本 属性，时态数据管理技术已经成为现代数据库理论与应用的重要课题之。自从 上个世纪八十年代以来，计算机学术界对时态数据库的研究给予了非常大的关 注，此后十年学者发表了数以千计的论文，提出了上百种时态数据库模型和时态 信息处理方式。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 【3 1 ，是该时期的标志性成果。 迄今为止，时态数据库的研究从未间断过。由于研究人员持续不断的创新研 究，时态数据库理论越来越成熟，并成功应用到地理信息系统( g i s ) ，数据仓库 与数据挖掘，以及时空( s p a t i o t e m p o r a l ) 信息技术和多媒体信息技术等众多领 基于时态摘要的对象关系数据索引研究第。章引言 域当中。对象关系数据库作为面向对象方法与传统关系数据库结合的产物，提供 了对于复杂数据进行复杂查询的支持，从而能更好地满足迅速发展的多媒体应 用、时空信息技术应用、w e b 应用以及新的商业应用的需求。目前已经有若干个 具有o r d b 特性的数据库产品推出，i b m 的d b 2 ，o r a c l e 公司的o r a c l e8 之后 的系列产品。因此将时态的概念引入到o r d b ，构造具有时态信息的对象关系数 据模型具有现实和重要的意义。 一直以来，如何从数据库的海量数据中进行有效的查询都是人们所密切关心 的内容，而索引技术可以通过对关键字段或者其他有效的信息进行建立索引有效 地解决查询性能的问题，因此建立良好、简洁、高效的对象关系时态索引必不可 少。 而在时态索引研究方面，早期阶段的学者的关注点主要集中在如何基于事务 时间建立索引方面。由于事务时间表示数据实体历史版本信息，其本身具有索引 性质，因此可以非常自然地用于索引时态数据【4 】【5 】【6 】。事务时间是事务提交的系 统时间，用户不能对其进行更新，因此相应的索引不需要进行更新管理，基于事 务时间的索引结构主要分为基于传统索引结构的t s b t 7 ，w o b t i s ，o b + t r e e 9 】 和基于独立索引结构的a p t r e e 1o 】 1 1 】，a d t r e e 12 1 ，s n a p s h o ti n d e x 13 1 ，a r c h i v a l e t i m ei n d e x 【1 4 1 。 随后，相关方面研究的学者逐渐将研究的重点转向基于有效时间的索引，有 效时间虽然由数据库系统来解释，但它可以被更新，有效时间的提供和更新是由 用户来完成的，另外实际应用中许多数据实体有效时间本身会随时间的推进而发 生不断地变化，比如具有有效时间变量n o w 情形。因此相对基于事务时间的数 据索引，有效时间的索引应当具有必要的动态管理和操纵约束。随着研究的不断 深入，国际上许多学者提出了许多基于有效时间的索引模型，大概可以分为两种， 一种是扩展传统的支持动态管理机制的索引结构( 如b + 树) 来实现时态索引功 能，主要包括t i m ei n d e x 1 5 】【1 6 】【17 1 、改进t p i n d e x 18 1 、m a p 2 1 1 9 】【2 0 1 、i b + 一讹e 【2 l 】； 另外一种是独立构造的符合时态索引的结构，主要包括i n t e r v a l t r e e 【2 2 1 、 c h e c k p o i n ti n d e x 2 3 1 、i s t r e e ( i n t e m a ls e g m e n t t r e e ) 【2 4 1 、e s t r e e ( e x t e r n a ls e g m e n t t r e e ) 【2 5 】、t p i n d e x 2 q 和r i 一仃e e 【2 7 】。不过由于时态数据本身的特点，通常诸如 b + 树等一些方法比较难以有效用于时态数据索引，尤其是带有时态变元的各种 2 基于时态摘要的对象关系数据索弓l 研究第章引言 时态运算【2 8 1 。 若需要同时考虑有效时间和事务时间两个方面，建立双时态索引，现有的工 作主要借鉴空间数据库r 树技术，引入g r 树( g e n e r a l i z e dr t r e e ) 及其4 r 树等时 态索引方法【2 9 】【3 0 】【3 l 】【3 2 1 。 1 2 研究出发点和意义 在2 0 世纪9 0 年代，开始有学者对时态对象关系数据研究进行工作。带有时 态信息的数据本身是一种比较复杂的数据实体，面向对象方法可以为其提供合适 的描述和有效的操作。时态对象关系数据库技术研究主要集中在时态对象关系建 模和时态对象关系查询方面，时态对象关系数据索引方面工作并不多见，k r i e g e l 等人在2 0 0 0 年提出将r i t r e e 的思想引入到对象关系数据库中来有效地管理有效 时间【3 3 】，x i a o p i n gy e 在2 0 0 7 年提出了基于时态变量的对象关系模型【蚓。时态 数据管理的基本问题是为数据元素添加时间标签。在本文提出的时态对象关系数 据模型中，其实现方式是在对象关系数据模型的基础上，添加引用对象实例时间 标签( i n s t a n c et i m e s t a m p i n g ) 3 5 】【3 6 】和属性时间标签( a 嘶b u t et i m e s t a m p i n g ) 3 7 】【3 8 】 【3 9 】 o 现有的时态索引工作主要集中在时态关系和时态x m l 数据方面，对象关 系数据模型中最大的特点是“嵌套和“引用”，数据的结构形式与时态x m l 有一定的相似性。时态x m l 数据是时态数据管理与应用的新领域，x m l 数据 具有半结构化性质，这使得数据索引更具有必要性。和常规x m l 索引相比，时 态x m l 索引工作较少。现有的工作基本是通过对常规的x m l 索引进行时态扩 充，通过直接加入时态信息实现常规索引的时态细化 4 0 l 4 1 】 4 2 】。除此以外，还有 通过精细分析，研究能够体现x m l 和时态本身特征的索引技术 4 3 】m 】。 因此，针对对象关系数据自身的特征，本文借鉴了中山大学数据库与协同 软件实验室提出的基于线序时态的对象数据建立时态索引的思想，将有效时间作 为时间标签加入对象关系数据模型的边中，在此基础上利用时态数据的相似性， 建立对象关系数据的时态摘要树t o r s u m ，压缩原始数据，然后利用时态信息的 包含关系和结构相当关系在时态对象关系数据时态摘要树模型的基础上通过引 入时态线序分枝建立索引模型t o r i n d ，从而实现时态对象关系数据的快速查询， 3 基于时态摘要的对象关系数据索引研究第一一章引言 并且改进了由于时态数据结点插入或者删除而导致时态线序分枝发生分裂或者 合并的增量式更新算法，解决了之前的无法实现完备增量式更新的问题；此外， 本文提出的t o r i n d 索引结构，具有基本数学支撑，可以适用于比较广泛的对象 关系数据应用领域；同时本文还设计了基本实验，并通过大量数据的模拟仿真实 验，验证了索引模型m r 砌c ，的可行性和有效性，提高了时态对象关系数据查询 的效率。 1 3 论文组织结构 本学位论文共分为六部分。内容组织安排如下： 第一章，阐述论文的研究背景、研究的出发点和意义，以及论文的组织架构； 第二章，介绍相关理论与技术基础知识，包括时态数据库的基本知识，对象 关系数据库的基本知识，以及建立对象关系数据模型o r q d m ： 第三章，在对象关系数据模型的基础上引入有效时间，将其扩展为时态对象 关系数据模型t o r q d m ，并讨论时间拟序和时态线序分枝的概念，为本论文所提 出的索引模型的建立提供基本的数学框架，并进一步建立基于时态摘要t o r s u m 的对象关系索引结构孔职觑以 第四章，讨论索引模型结构t o r i n d 中的数据查询算法，并介绍索引中时态 线序分枝完备的增量式更新维护算法； 第五章，对时态对象关系索引模型t o r i n d 进行实验验证，并给出实验结果 与分析，对本论文得出的索引模型的可行性和有效性进行评估； 第六章，对全文进行总结，分析本文研究成果及意义，并阐述下一步的工作。 4 基于时态摘要的对象关系数据索引研究第二章相关理论与技术基础 第二章相关理论与技术基础 时态对象关系数据模型是以时态数据库的理论为基础的，本章首先介绍时 态数据库中的一些比较重要的概念，然后介绍对象关系数据库的相关概念，最后 对对象关系数据建立模型o r q d m 。 2 1 时态数据库基础 本节首先会介绍一些时态基本元素的概念，如时间区间、时间跨度、两个特 殊的时间元素n o w 和u c ，以及一些基本的关于时态数据库概念，包括用户自定 义时间，有效时间，事务时间，4 种时态数据库【4 5 1 。 2 1 1 时态基本元素的概念 ( 1 ) 时间点：基于点的时间元素。时间点又称为时刻。这种描述方法是把时， 间看成一个个离散的时间点。时间点是时间轴上的一点，它是和时间粒度相关的。 例如时间点2 0 1 0 年3 月2 9 日，时间粒度精确到“天”。 ( 2 ) 时间区间：指一段时间，有固定的起止时间点。例如2 0 0 8 2 0 1 0 年。时 间区间的表示方法根据两端时间点是否封闭分为4 种： 限，吲，孵，呦，僻，e j ，僻，乃) 在上述表示方式中，b ，弓分别表示两个时间点；“【】”表示左闭右闭区间；“ ) 表示左闭右开区间：“( 】”表示左开右闭区间；“( ) 表示左开右开区间。在这四 种区间的表达方式中，一般采用前端封闭，尾端开放的形式，主要是考虑时间区 间兼容时间点的表示方式和时间区间的比较谓词的缘故。 a l l e n 在其1 9 8 3 年发表的论文【4 6 】中指出了1 3 种时间区间之间的关系，为时 态关系的研究做出了开创性的工作。这1 3 种关系可以在时间轴上表示如下，其 中t ，和勿表示两个时间区间： 5 基于时态摘要的对象关系数据索引研究 第- 章棚关理论与技术摹础 表2 - 1a l l e n 的1 3 种时问区问的关系【4 5 】 时态区间关系图示说明 tl|2 t ，在幻之前发生 b e f o r e ( o ，t 2 ) 1 _ j i j a f t e r ( t ，r e ) f2| ，在勿之后发生 jt _ j t | t ，的区间范围包含在 d u r i n g ( t 1 ，t 2 ) 。 ，2 幻内-i 如 f 2 的区间范围包 c o n t a i n s ( t 1 ，t 2 ) f ， 含在t j 内i t l t ，比勿早开始且 o v e r l a p s ( t l ，幻) r 2 两个区司有相交 i 如 t 2 比t l 早开始且 o v e r l a p p e d b y ( 0 ，t z ) 幻 两个区司有相交 li t l t 2 开始于t l 的结 m e e t s ( t 1 ，幻) l _ t z 束点 l 如t j 开始于t z 的结 m e t - b y ( 0 ，t 2 )- - - - - - - - - - 一t l 束点 l t l乃和t 2 有共同的 s t a r t s ( 0 ，t 2 )卜j如 起点，t t 比t z 先结束。 ii t l t ，和t z 有共同的 s t a r t e d - b y ( 0 ，t a ii ； 幻 起点，t z 比t l 先结束。 t l t ，和t 2 有共同的 f i n i s h e s ( 0 ，t 2 ) 如 ! 结束点，t l 比t 2 晚开 i 始。 t l t j 和t 2 有共同的 f i n i s h e d - b y ( 0 ，幻) i- 结束点，t z 比t j 晚开 1 2 ； 始。 e q u a l s ( 0 ，t 2 )tt t ，和t z 在时间轴 i t z i 上重合 6 基于时态摘要的对象关系数据索引研究 第_ 章干h 关理论与技术雉础 在这1 3 种关系中，其中6 对关系可以互相转换【4 5 1 ，如下： b e f o r e ( t t ，勿) = a l t e r ( r e , t 1 ) d u r i n g ( t ，t 2 ) = c o n t a i n s ( t z , t i ) s t a r t s ( t t ，r e ) = s t a r t e d b y ( t 2 , t 1 )f i n i s h e s ( h ，幻) = f i n i s h e d b y ( t 2 ，t ) o v e r l a p s ( o ，t 2 ) = o v e r l a p p e d b y ( t 2 , t o m e e t s ( t t ，t 2 ) = m e t b y ( t 2 , ，) e q u a l s ( t 1 t 西= e q u a l s ( t 2 , t t ) ( 3 ) 时间跨度：指持续的一段时间，表示时间的长度。例如：“两年零三个 月”、“3 0 天”、“2 7 个小时”等。与时间区间类似，时间跨度表示一段时间； 但不同的是，时间跨度没有时间起点，也没有时间终点。 ( 4 ) 时间元素n o w ：n o w 的中文意思是当前时间，是一个时间变元，随着当 前时间的变化而变化，记录了随时间变化的信息，它的有效值依赖于当前时间。 n o w 的引入给时态数据库带来便捷的同时也带来了n o w 语义失真等问题。 ( 5 ) 时间元素u c ( u n t i lc h a n g e d ) ：主要用于事务时间中的一种时间变元， 表示一直到该元组发生改变的时间，在应用于事务时间中它有比n o w 更精确的 解释语义，并与有效时间中的时间变元n o w 相区别，但与n o w 具有类似的含义。 2 1 2 时态数据库基本概念 本节将介绍时态数据库里面的3 种基本时间和4 种数据库。 ( 1 ) 在时态数据库里，3 种基本时间分别指的是：用户自定义时间、有效时 间和事务时间，下面分别介绍： 用户自定义时间：指用户根据自己的需要或理解定义的时间。这种时间 的属性值一般是时间点，用户本身会解释自身所给出的时间信息，数据 库系统不需要解释其含义，只需将时间域等同其他一般的属性来理解， 对其的操作和对普通字符串的操作几乎没有什么区别。用户自定义时间 是和应用相关的，不在时态数据库处理的范围之内。 有效时间：指一个对象或事件在现实世界中发生并保持的那段时间，即 该对象在现实世界中语义为真的时间。有效时间包含v a l i d f r o m 和 v a l i d t o 两个值。有效时间可以反映过去，现在和将来的时间，可以是时 间点、时间点的集合、时间区间或者时间区间的集合，或者是整个时间 域。有效时间由时态数据库系统解释并处理，在查询的过程中对用户透 7 基于时态摘要的对象关系数据索引研究 第二章棚关理论与技术摹础 明。用户也可以显式地查询和更新有效时间。 事务时间：指一个数据库对象发生操作的时间，是一个事实存储在数据 库、或者在数据库中发生改变的时间，包含t r a n s a c t i o n f r o m 和 t r a n s a c t i o n t o 两个值。当用户对数据库状态进行更改时，会产生各种操 作历史，事务时间真实地记录了数据库状态变更的历史。有时也称事务 时间为系统时间。事务时间由数据库来解释和处理的，但是它对用户是 透明的，用户不能对事务时间进行操作。 ( 2 ) 按表示时态信息的方式，可以将数据库分成基本的4 个类型：快照数据 库( s n a p s h o td a t a b a s e ) 、回滚数据库( r o l l b a c kd a t a b a s e ) 、历史数据库( h i s t o r i c a l d a t a b a s e ) 和双时态数据库( b i t e m p o r a ld a t a b a s e ) ，通常将后3 种数据库称为时 态数据库( t e m p o r a ld a t a b a s e ) 。但是从广义的角度来看，这4 种数据库都应该 称作时态数据库，它们在数据库的发展历史中扮演了不同的角色，其发展变化反 映了时态数据库的进化历程【4 5 1 。 快照数据库( s n a p s h o td a t a b a s e ) ：快照数据库是反映现实世界某一瞬间 情况的数据模型。它记录了特定时刻的数据库状态。从时态数据库的观 点来看，快照数据库不区分事务时间和有效时间，它采用这样的假定： 一个存储在数据库中的元组，一定是真实世界中的有效事实【4 5 1 。 历史数据库( h i s t o r i c a ld a t a b a s e ) ：由“历史关系”组成，每一个元组 记录了数据的一个“历史”的状态。通常我们将只支持有效时间的数据 库称为历史数据库【4 5 1 。 回滚数据库( r o f l b a c kd a t a b a s e ) ：支持事务时间，它按事务时间进行编 址，保存了过去每次事务提交、状态演变之前的状态【4 5 1 。 双时态数据库( b i t e m p o r a ld a t a b a s e ) ：结合了回滚数据库与历史数据库 的优点，既保存了数据库变迁的是谁，又保存了现实世界的真实的数据 属性。双时态数据库既支持事务时间又支持有效时间，它集成了前面三 种类型数据库的功能特性，存储了数据库和现实世界两者发展的历史 【4 5 1 。 8 基于时态摘要的对象关系数据索引研究第- 章丰h 关理论与技术基础 2 2 对象关系数据库基础 随着计算机应用领域的扩展和深入，关系数据模型难以有效适应于新领域 需求。这主要表现在关系中数据取值的数据类型主要有整数、实数、字符串、时 间型等简单( 原子) 数据类型，在现实中较为复杂的实体缺少必要模拟和表现能 力。因此在2 0 世纪9 0 年代面向对象数据库( o o d b ) 的研究兴起，在数据库中 引入了面向对象的数据模型和方法，增强了管理数据内在动态联系的能力，对复 杂数据对象的表达能力更强，能够很好地支持多种非常规数据库的应用。但是由 于面向对象数据库产品缺乏统一的标准，在程序设计接口、实现方法( 手段) 、 对查询的支持等方面都存在许多差异。而且应用开发工具不足。由于上述原因， 对象关系数据库( 0 r d b ) 应运而生，它是面向对象技术与数据库技术的结合走 向成熟的产物。对象关系数据库本质上还是一种关系数据库，其特征是在关系数 据库上通过引入数据类型突破了i n f 限制，同时通过引入“引入”、“继承” 等技术增添了面向对象过程部分功能。 对象关系数据库系统采用对象关系数据模型，而对象关系数据模型是在经典 关系数据模型上进行扩充得来的，其基本特征有以下几个： ( 1 ) 首先引入了新的数据结构和数据类型，即表现的属性值可以是另一个关 系，从而实现了嵌套关系结构，表示数据对象之间更广泛联系的结构数据类型和 聚集数据类型，突破了1 n f 限制。 ( 2 ) 对象关系数据库中的这种突破实质上是将关系表中数据项( 属性值) 看 作具有自身结构的对象或类型，因此在引入面向对象程序设计方法的某些基本理 念与思想的时候就会显得非常的自然。例如，引入类型间继承概念以体现重用性， 引入引用数据类型( 指针类型) 以实现对象标识和完成数据递归嵌套定义，引入 抽象数据类型以体现对象的封装性等。 ( 3 ) 由于对象关系数据库具有基于对象方法的基本特征，使其更加接近客观 现实世界中的实体对象，因此，在对象关系数据模型中，e e r 模型中的许多概 念，例如实体标识、多值属性、泛化、细化等，不需要经过变换转化就可以可直 接使用。 下面分别介绍对象关系数据模型中的结构数据类型，抽象数据类型，聚集数 9 基于时态摘要的对象关系数据索引研究第二章相关理论与技术基础 据类型以及引用和继承的概念。 2 2 1 结构类型 在平面关系模型中，允许其中的属性值可以是一个元组( 结构或行) ，而且 可以多次交替、规则出现，则称该属性值的数据类型为结构数据类型( s t r u c t u r a l d a t at y p e ) 。结构数据类型表现为元组或行记录，因此也称为行数据类型( r o w d a t at y p e ) 、元组类型( t u p l ed a t at y p e ) 和对象类型( o b j e c tt y p e ) 。 结构数据类型的定义可以表示如下： c r e a t er o wt y p en a m e ( ) ( 1 ) 结构类型的基本描述 结构数据类型具有下述特征： 类型中元素具有不同数据类型结构类型数据中的各个元素具有不同的 数据类型值( 可以是合法的各种数据类型值，特别还可以是另一个结构类型值) 。 由于结构数据类型是传统关系模型中元组概念的推广，所以基本要素是其中元素 的属性名和相应属性域。 类型元素可为另一关系元组的集合就是关系，结构类型中某个元素取值 可以是另外一个关系，此时整个关系称之为嵌套关系( n e t e s t e dr e l a t i o n ) 。嵌套 关系通常具有“关系属性值元组( 关系) 属性值元组( 关 系) ”的链条形式。嵌套关系模式如图2 1 所示。 图2 - 1 嵌套数据模型结构 l o 基于时态摘要的对象关系数据索引研究 第二章棚关理论与技术基础 ( 2 ) 引用和继承 结构类型作为面向对象方法在数据库系统应用的一个重要体现就是具有引 用和继承的内在机制。下面分别讨论这两个问题。 引用类型 数据类型如果直接用于表示递归结构，就可造成无穷嵌套，带来语义上混 乱，甚至成为不可知。例如，有下面两个关系： d e p a r t m e n t r e l ( d n o ，d n a m e ，s t a f f ( e m p l o y e e t u p ) ) e m p l o y e e r e l ( f n o ，f n a m e ，r a g e ，w o r k s - f o r ( d e p a r t m e n t t u p ) ) 上述关系定义中分别涉及到结构类型d e p a r t m e n t t u p 和e m p l o y e e t u p ( 本身 是一个关系) ，即在关系d e p a r t m e n t r e l 的元组( d e p a r t m e n t t u p ) 中包含关系 e m p l o y e e r e l 的成分；而关系e m p l o y e e r e l 的结构类型( e m p l o y e e t u p ) 中有包 含了结构类型为d e p a r t m e n t t u p 的成分，此时的类型构造示意如图2 2 所示。由 于会引发无穷嵌套，这种递归类型构造通常禁止使用。 后来学者采用“引用”( r e f e r e n c e ) 技术解决数据类型中的递归问题，这就 提出了“引用( 数据类型) ”概念。引用相当于程序设计中的指针概念，在面向 对象技术中其称为“对象标识”。引用类型概念可以将数据类型定义中的实例 映射扩充到类型值域中的实例映射，从而提供有关细节的抽象。通过“引用类 型”的实现方式避免了“无穷嵌套”。 前述关系中的结构类型d e p a r t m e n t t u p 中有一个属性s t a f f 是关系类型 e m p l o y e e r e l ，在实现时不采用原有的嵌套方式，而采用“引用方式” ( 指针方 式) ，用指针指向关系类型e m p l o y e e r e l 中各个与之相关联的职工。元组 e m p l o y e e t u p 中有一个属性是结构类型d e p a r t r n e n t t u p ，实现时也不采用嵌套方 式，而是采用“引用方式 。图2 3 是采用“引用 类型后的类型构造示意图。 l 姗m e n t r e i 图2 - 2 递归引发无穷嵌套 l l e r a p l o y e e t u p 甚于时态摘要的对象关系数据索引研究第二章棚关理论与技术基石：l ； 图中的虚线表示“引用”类型，实线则表示类型与元组成分相连。 d c p a r t m e n t r c l 图2 - 3 采用“引用”概念的类型构造 e m p l o y c c r c l e m p l o y c c t u p 由此可知，如果类型中一个对象的属性取值为引用，则该属性值就是被引 用对象的o l d 而非该对象的实际取值。引用数据类型通常用r e f ( r e f e r e n c e ) 表 示，也称为引用类型，其取值为相应的o l d 。需要注意，在面向对象方法中， o i d 对于用户来说透明，是一种系统码。但在对象关系数据库系统中，允许用户 以引用类型r e f 访问o l d ，但仅可以访问，不能修改。 类型继承 结构类型是“类 概念在数据库中应用，需要讨论“类”概念重要机制“继 承”在结构类型上的实现。 数据泛化和细化数据的泛化和细化( g e n e r a l i z a t i o na n ds p e c i a l i z a t i o n ) 是概念之间联系进行抽象的一种方法。当较低层面上抽象表达了与之联系的较高 层面上抽象的特殊情况时，则称较高层面上抽象是较低层面上抽象的“泛化”， 而较低层面上抽象则是较高层面上抽象的“细化 。这种细化联系是一种“是” ( i sa ) 的联系。 在具有泛化和细化的对象类型之间，较高层面上的对象类型称为“超类型” ( s u p e r t y p e ) ，较低层面上的对象类型称为“子类型”( s u b t y p e ) 。 继承与多重继承子类型应当具有继承性，即继承其超类型的特征，而 子类型本身还具有其他的特征。 比如，我们有人p e r s o n 的类型，而我们还希望除了基本的人的信息外，高 校中学生s t u d e n t 和教师t e a c h e r 还具有自己的特定信息，这样在数据库中，p e r s o n 就是s t u d e n t 和t e a c h e r 的父类，而s t u d e n t 和t e a c h e r 则是p e r s o n 的子类，他们继 承了p e r s o n 的基本特征( 属性和方法) ，也具有自身的特征。在高校中，助教 1 2 基于时态摘要的对象关系数据索引研究 第二章 1 l 关理论与技术基础 图2 - 4 继承与多重继承 a s s i s t a n t 作为教师t e a c h e r ，通常由研究生( s t u d e n t ) 担任，因此，a s s i s t a n t 就同 时作为s t u d e n t 和t e a c h e r 的子类，具有多重继承( m u l t i p l ei n h e r i t a n c e ) 。继承与 多重继承示例如图2 - 4 所示。 在结构类型中引入继承机制，就可以在涉及到演化问题的数据库系统中避免 重复定义，提高系统效率。 2 2 2 聚集数据类型 如前所述，如果实际应用中出现的属性取多个值的情形，则可以通过聚集 数据类型( c o l l e c t i o nt y p e ) 实现非1 n f 。聚集类型是由一组相同类型元素组成 的满足一定要求的集合。聚集类型具体可以分为数组、列表、多集和集合四种情 形，而s q l 3 中的聚集类型为数组，而s q l 2 0 0 3 中聚集类型为多集( 包) 。 ( 1 ) 数组数据类型 数组类型( a r r a yt y p e ) 是相同类型元素的有序集合，一般而言，数组的大 小预先设置。在实际应用中，相同类型数据值的排序往往是必要的，例如一本出 版物的如果有多名作者，则第一作者、第二作者等的区分具有重要意义。例如一 本著作的作者名可以以数组【j h o n ，r a u l ，m a r y ，w h i t e 】形式表示，这使得我们