（计算机应用技术专业论文）双时态数据库中间件的研究与实现.pdf

中山人学硕i ：学位论文 双时态数据库中问件的研究，。j 实现 双时态数据库中间件的研究与实现 专业：计算机应用技术 硕士生：陈莉莉 指导教师：汤庸教授 摘要 时间是事物固有的客观属性。随着信息技术的发展，在信息与时间尤其紧密 相关的许多应用领域，信息系统对时态信息处理的需求变得越来越迫切。传统的 数据库系统已经不能满足这种需求，于是时态数据库就成为了新一代数据库研究 领域。 虽然经过几十年的发展，时态数据库理论研究取得了丰富的成果。但由于技 术和标准化等多方面原因，一种完整的时态数据库管理系统产品至今未能出现。 为了解决当前应用需求，并为时态数据库的进一步研究积累实践经验，中山大学 数据库与协同软件实验室选择在应用层和关系数据库之间构建时态信息处理构 件的现实方案，将一系列时态理论成果应用于实践，实现了基于a t s q l 2 时态 查询语言的t e m p d b 数据库中间件。 t c ：i l l p d b 研发过程分阶段进行，在现阶段暂只支持有效时间，实现了三种时 态数据库当中的历史数据库。而记录数据存储历史的事务时间在理论研究和应用 方面都存在与有效时间不同的现实意义，因此本文认为有必要进一步研究三种时 态数据库中的另外两种：支持事务时间维的回滚数据库和支持双时间维的双时态 数据库。 本着最大化发挥时态数据库优秀特性的目的，本文结合关系模型建立了双时 态关系数据模型：提出了双时态区间的1 0 种关系，给出了其与灿l e i l 的1 3 种关 系之间的转换策略：明确定义了双时态数据结构和双时态完整性规则；扩展了 a t s q l 2 的事务时间单时态和双时态的数据定义、数据操作、数据查询的语法、 语义。其次，根据双时态关系数据模型研究了双时态归并策略、双时态数据定义 语言处理算法、双时态数据操作语言处理算法和双时态数据查询语言处理算法。 最后，将双时态关系数据模型的各种算法应用到t e m p d b 2 1 版本中，实现了集 中山大学硕上学位论文 双时态数据库中问件的研究与实现 非时态数据库、历史数据库、回滚数据库和双时态数据库为一体的双时态数据库 中间件t 锄p d b 2 x 。 关键词：双时态数据库，数据库中间件，时态数据处理构件，回滚数据库， a t s q l 2 中山大学硕1 ：学位论文 双时态数据库中间件的研究j 实现 r e s e a r c ha n di m p l e m e n t a t i o no nb i t e m p o r a ld a t a b a s e m i d d l e w a r e m 旬o r ：c o m p u t e ra p p l i c 撕o nt e c h n o l o g y n 锄e ：l i l ic h c i i s u p e i s o r ：p r o 慨s o ry o n gt 狮g a b s t r a c t t i m ei san a 咖l 卸do b j e 鲥v ea t t r i b u t eo f o b j e c t s w i t hi n f o 】彻a t i o n 溉h n o l o g ) ， d e v e l o p i n 岛t h ei i l f o m a t i o ns y s t e mr c q u i r e sf o rt 锄p o r a li n f o 锄a t i o np r o c e 踌i n g m o r e 锄dm o r e 苫e n t l yi l ll o t so f a p p l i c a t i o nf i d d sw h e r ei l l f 0 m a t i o ni sc o r r d a t e d e s p 撕a l l yc l o s e l yw i m t i m e t r a d i t i o n a lr d b m sc 锄tm e e tt h i sr e q u i r e i l l e n ta l r e a d 弘 t l l u st e m p o r a ld a t a b a s eb e c o m e st h en e wg e n e m t i o nd a t a b 嬲e e s e a r c hf i e l d 廿l o u g l lt l l e 0 d r 燃h t 锄p 响l 语法分析一 语义分析的分析过程来处理，整个解析过程增加了 时态语法的处理，对含时态语义的语句根据相应的时态数据结构进行了恰当的转 换工作。a t s q l 2 语句的解析结果是一个标准s q l 语句集，数据访问模块使用这 些s q l 语句访问关系数据库得到返回结果之后，需要经过结果包装模块的处理， 用时态数据模型的表现形式将数据展示给用户界面【2 。 由于a t s q l 2 并没有形成最终的标准版本，正不断地接受改进和完善，本文 的研究和开发就是a t s q l 2 的一个演变过程，在未来也可能会不断地变化。所以 结合目前的时态数据库技术现状，整个系统的模块保持高度的独立性。尤其是语 法处理和语义转换作为核心部分，被设计为分离的两个模块，以便于日后进行扩 中山大学硕i ：学位论文双时态数据库中间件的研究与实现 展和修改，并且也更有利于时态信息处理方法的变动和优化【4 l ，【2 0 l 。 2 4 本章小结 本章首先介绍了与本文研究相关的时态数据库基本知识，阐述了有效时间和 事务时间两个时间维，u c 和n o w 两个时间变元，快照数据库、历史数据库、回 滚数据库和双时态数据库四种数据库这些概念的涵义。接着本章还讲述了 a t s q l 2 的特点和设计思想，以此说明t e m p d b 采用a t s q l 2 作为时态查询语言的 理由。为了读者更好地理解双时态t 鲫p d b 的流程结构和主要算法，本章最后给 出了t e m p d b 的总体框架，介绍了其对a t s q l 2 语言的处理流程设计思想。 中山人学硕一i ：学位论文双时态数据库中问件的研究j 实现 第3 章双时态关系数据模型 模型是对现实世界的抽象，描述数据库的结构与语义，能表示实体类型及实 体间联系。数据模型的种类很多，主要分为两种类型。一种称为“概念数据模型”， 以著名的“实体联系模型一为代表。另一种称为“结构数据模型”，它是直接面 向数据库的逻辑结构。例如层次、网状、关系、面向对象等模型2 5 1 。 本文主要是研究基于关系数据库的双时态逻辑数据模型，以下简称双时态关 系数据模型。完整的逻辑数据模型包括数据结构、数据操作和数据完整性约束三 个部分【2 习，本章将对这三方面分别做出详细的研究。 3 1 双时态数据结构 数据结构指现实世界的实体类型和实体间的联系在数据库中如何表达和实 现【2 6 】。双时态t 伽p d b 中间件处理的数据都存储在关系数据库中，因此使用关系 模式表示实体类型，二维表格表示实体集，实体间的联系通过键引用来实现。这 些都与非时态数据结构相同，不同的是时态数据具有时效属性。如何表示时态数 据数据本身的时态语义，并保证数据存储的合理性以最大程度减少时间标签给底 层数据库系统增加的负担，这是接下来本节要研究的问题。 3 1 1 事务时间维的存储表示 t e m p d b 2 1 只支持有效时间维，数据库的时态关系结构如下表： 表3 1 有效时间单时态t e m p d b 的关系结构 部门号名称员工人数有效时间 开始时间结束时间 0 0 l 研发部 3 0 0l9 9 5 0 3 - 2 02 0 0 2 0 4 0 9 0 0 2财务部1 0 0l9 9 4 0 4 一0 6l9 9 9 0 6 0 7 0 0 3 行政部 8 51 9 9 6 - 1 l 0 3n o w 有效时间单时态关系表的主键是用户自定义主键加上两个有效时间属性构 成的联合主键。对于具有特殊语义的有效时间点，比如时态变量n o w 在后台数据 库被表示成d a t e t i m e 类型字段，赋值为“9 9 9 9 一o 卜0 10 0 ：0 0 ：0 0 一【7 1 【2 7 1 。 1 3 中山人学硕：i ：学位论文双时态数据库中间件的研究与实现 事务时间维的意义在于记录数据在数据库的存储历史，数据发生的任何插 入、更新、删除动作都需要记录下来。因此，事务时间维的存在无疑会使得数据 量急剧增长，给数据库管理系统带来巨大的压力，进而带来操作性能的问题【2 8 l 。 t e m p d b 双时态的扩展必然需要为数据增加事务时间标签，所以很有必要为事务 时间寻找一种合理、高效的表达方式。 事务时间的存储表示可分为时间点和时间区间两种形式，它们各有利弊，因 此需要从用户性能和数据库系统的负担两方面去衡量它们，选择一种最佳方案。 一种考虑是采用时间点的方式存储事务时间维数据，事务时间属性值记录的 是一系列离散的时间点。一个时间点对应一个数据库状态，以接近自然的方式记 录了数据库的操作历史，形式简单，意义清晰。但是这种方式不利于反映数据存 储状态的持续性和阶段性，将给数据查询带来效率上的负担，增加应用程序处理 数据的复杂性。 另一种考虑是采用时间区间的方式存储事务时间，事务起始时间属性记录了 每一个新事务发生的时间，事务结束时间属性记录了下一个事务发生的时间，而 这两个属性值构成的时间区间也代表了每一个数据库状态的持续时间。数据库发 生任何变化，都将以 新的事务时间点，u c ) 时间区间把新的数据库状态记录下来， 并把上一个数据库状态的结束时间改成当前系统时剐冽删。 表3 - 2 事务时间区间存储方案的关系结构 部门名称员工有效时间事务时间 号 人数开始时间结束时间开始时间结束时间 0 0 l 研发部 3 0 0 1 9 9 5 0 3 2 02 2 - 0 蝴1 9 s 1 5 - 0 蝴31 9 9 6 彤2 1 0 0 2 财务部 1 0 01 9 9 4 o 蜥l 钙吟鲫 1 9 9 5 0 4 旬31 9 9 6 加5 - 2 l 0 0 3 行政部 8 51 9 9 6 1 l 旬3n o w 1 9 9 5 - 0 1 4 旬31 9 9 锄5 - 2 l 0 0 l 研发部 3 0 01 9 9 5 旬3 2 02 0 0 2 - 0 4 _ 0 1 91 9 9 6 0 5 2 lu c 0 0 _ 2 财务部 1 0 01 9 9 4 o 伽6 l 舛1 9 m 每0 71 9 9 6 d 5 2 lu c 3 行政部 8 51 9 9 6 i l l 奶1 9 9 7 1 l - 2 41 9 9 6 0 5 - 2 lu c 0 0 3 行政部 8 519 9 8 1 2 2 5n o w 1 9 9 1 6 0 5 2 lu c 1 4 中山大学硕，j ：学位论文 双时态数据库中问件的研究与实现 这种方案清晰地反映了数据库的阶段性状态，对于查询要求，只需要考察每 一元组的时间区间和查询时间区间的关系。因此用时间区间表示事务时间维的方 案是比较可行的，但是，这种方案也有欠缺之处，那就是数据冗余问题。一状态 的事务结束时间与另一状态的事务起始时间是重复存储的，更严重的冗余在于即 使是毫无变化的元组数据也将和少数变化的记录一起用新的事务时间添进数据 库表示新的状态。 3 1 2 双时态扩展的存储优化 数据库添加了事务时间维，就意味着数据操作包括建立、修改、删除在事务 提交之后，都将产生一个新的数据库状态，新状态不会覆盖旧的状态，因此没有 数据会从数据库中被物理删除，数据在不断地增加。而且即使数据的改变甚小， 也需要进行所有数据的重新输入及储存，这样数据增长的速度是非常快的，冗余 问题将异常严重，有必要作适当的存储优化。 我们仔细观察表3 2 ，研发部和财务部在两个数据库状态都没有发生任何改 变，它们的事务时间区间为 1 9 9 5 0 4 0 3 ，1 9 9 6 0 5 2 1 ) 和 1 9 9 6 0 5 2 1 ，u c ) ，既 然除事务时间之外的实体属性都是相同的，而且元组前后状态的事务时间区间是 连续的，那么我们实际上可以把连续区间的两条记录合并成一条【2 9 】，f 3 0 1 ，合并之 后的数据库表如下图： 表3 3 合并后的数据库表 部门名称员工有效时间 事务时间 号人数开始时间 结束时间开始时间结束时间 0 0 l 研发部 3 0 0l9 9 5 0 3 - 2 02 0 0 2 0 晖j d 9l9 9 5 - 0 4 彤3u c 0 0 2 财务部 1 0 01 9 9 4 司1 4 0 61 9 9 9 0 6 0 哆19 9 5 0 4 一。3u c 0 0 3 行政部 8 51 9 9 6 1 l 钙n o w l9 9 5 - 0 4 国3 19 9 6 - 0 5 - 2 l 0 0 3 行政部 8 51 9 9 6 - l l 躬1 9 9 7 1 l - 2 41 9 9 淌- 2 lu c 0 0 3 行政部8 51 9 9 8 1 2 2 5n o w1 9 9 6 0 5 - 2 lu c 我们可以看到，归著之后最终数据库表中添加的新记录只是针对部分被执行 操作的记录，存储了它们的新状态，而其它未作任何改变的记录则没有重新存储。 1 5 中山大学硕士学位论文双时态数据库中间件的研究与实现 可以说明，这种方法大大减少了数据量，消除了部分冗余。 事实上，我们不需要以先存储再合并的方式来达到这样的存储优化效果，而 可以一步到位。u c 是事务时间中的时间变元，具有特殊的意义，表示直到该元 组改变的时间。当插入一个新的记录时，假设t s t a r t 为插入时的时间，那么把 此记录的事务时间设为 t s t a r t ，u c ) ，则此记录自动具备了状态延续的意义，当 其不发生任何改变时系统无需对其作出任何处理【3 1 1 。 这里需要特别说明的两点是，第一、采用时间区间的存储方案，处于当前数 据库状态的元组，事务结束时间都是用u c 来表示，可以对任意事务时间的记录 进行查询，但是更新和删除操作只对当前状态的数据有效，即只能对u c 为事务 结束时间的元组进行操作。第二、时态变量u c 在数据库中与一样记录为 “9 9 9 9 一o 卜0 10 0 ：o o ：0 0 ”，但在用户界面上却显示为“u c 一，这就需要t e m p d b 对结果集进行包装。 冗余数据量的减少实际上也加快了数据库系统对元组查找的速度，进而为用 户提高数据查询、更新、删除等操作的效率。 3 1 3 时态实体和实体间联系 实体都存在某些特征使它区分于别的实体，当实体表达在关系数据库中时， 我们可以选用它的某个属性或属性组合即主键来惟一标识该实体的元组。例如， 工资表( 职工号，职工名称，工资) ，用户可以选用职工号作为主键。如果一记 录是( 0 0 2 ，李明，2 0 0 0 ) ，那么该表就不能存在第二条职工号为0 0 2 的记录。假 如李明辞职了，这0 0 2 的职工号就不能再被他人所用了，或者就只能把李明的这 条记录从表格中永远地删除。前者造成了资源的空闲浪费，后者造成了信息的流 失。 时态实体所具有的时间属性表明了该实体存在于现实世界或数据库中的时 间。根据前面讨论并选择的时间属性表达形式，时态实体的时态属性和非时态属 性都包含在同一张二维表格的列集合里面。比如同样是工资表，就变成( 职工号， 职工名称，工资，起始时间，结束时间) 。假设用户依然选择职工号作为主键， 职工号为0 0 2 的记录是( 0 0 2 ，李明，2 0 0 0 ，2 0 0 5 0 2 0 3 ，2 0 0 6 0 6 1 9 ) ，那么这 条记录的生效时间到2 0 0 6 0 6 1 9 就结束了所以从时态语义上来讲，如果李明 1 6 中山人学硕：仁学位论文双时态数据库中间件的研究与实现 从单位辞职，这个0 0 2 的职工号是可以继续被第二个人所用的，那么在关系数据 库中职工号就不能再按照用户的选择单独作为主键。事实上，作为时态实体组成 部分的属性都是跟实体一样跟存在于某生效时间内，包括被用户选作主键的属性 或属性集合也是具有时效性的【3 2 】。带有时间属性的主键才能唯一标识时态实体， 因此，时态实体在关系数据库中的完整表达应该如下： a ) 有效时间单时态实体：( 围皇自庭塞圭毽! 查夔盟闻，其它属性) b ) 事务时间单时态实体：( 题应自宣塞圭毽：蔓釜盟闷，其它属性) c ) 双时态实体：( 周应自定望圭键：直熟时间! 童箜盟间，其它属性) 时态实体间的联系在关系数据库中可通过外键形式来实现，同类实体的联系 体现在关系内的引用关系，不同类实体的联系体现在不同表之间的引用关系。我 们知道，外键首先是作为它所在关系的主键，因而外键与主键一样需要包含时间 属性。为了做到与单时态、非时态数据模型的兼容性，本文的双时态数据模型需 要考虑双时态关系、有效时间单时态关系、事务时间单时态关系和非时态关系任 何同类或异类两者之间发生的引用关系。外键的引用应该遵守两个原则：一、能 够反映参照关系的时态特性；二、保持依赖关系的时态特性。简单地说，参照关 系的时间属性都应该包含在外键里面被依赖关系引用，但前提是依赖关系本身已 拥有这些时间属性，否则这种引用关系不会发生。基于这种思想，两表之间的外 键形式如下表，其中r l 是依赖关系，r 2 是参照关系。 表3 4 双时态关系数据模型的外键结构 r l 时态特性r 2 时态特性外键形式 非时态 非时态 用户自定义外键 非时态有效时间或者事务 不允许 时间或者双时态 双时态或者有效有效时间 用户自定义外键+ 有效时间属性 时间 双时态或者事务事务时间 用户自定义外键+ 事务时间属性 时间 有效时间或者事双时态 不允许 物时间 有效时间事务时间不允许 事务时间有效时间 不允许 双时态双时态用户自定义外键+ 有效时间属性+ 事务 时间属性 有效时间或者事非时态用户自定义外键 1 7 中山大学硕1 j 学位论文双时态数据库中间件的研究与实现 l 物时问萎者双时 3 2 双时态完整性约束 数据库中“完整性一的含义是指数据的正确性、一致性和有效性。所谓“完 整性约束”就是为了保证数据库完整性数据应该满足的条件。“数据完整性约束一 是一个数据模型不可或缺的重要方面，如果没有一套完整性规则和一种机制保证 数据正确地存储在数据库，并正确地被输入输出，这数据库系统是没有意义的。 数据库的完整性关系到数据库系统能否真实地反映现实世界，因此当前流行的几 大数据库管理系统o r a c l e 、s q ls e r v e r 等都提供了比较完善的完整性约束定义 功能和执行完整性检查的。完整性子系统【2 5 1 。 同样地，时态数据库也需要一套完整性机制来保证时态数据的完整性。虽然 本文研究的双时态t e m p d b 是基于底层关系数据库的中间件，普通的数据完整性 控制完全可交由底层d b m s 执行，然而时态数据库涉及到关系数据库所没有的许 多时态元素，使得完整性规则内容增加了时态约束条件，完整性约束控制也因而 更加复杂【2 4 】。为了保证时态数据的合法性，具有正确的时态语义与及时态一致 性，本节对双时态数据模型的时态完整性规则作明确的定义。 时态完整性规则可参照关系模型的完整性规则分为时态实体完整性规则、时 态参照完整性规则和用户自定义的完整性规则三类【2 4 】。其中用户定义的完整性 规则是用户与系统交互的时候对数据自定义的约束条件，它属于列级或表级的约 束，不具有通用性，因而不是本节讨论的内容。 3 2 1 双时态实体完整性规则 时态实体完整性规则： a ) 组成用户自定义主键的属性上不能有空值； b ) 时态元组的时间区间不能为空值； c ) 时态元组在同一时间维的起始时间属性值必须小于等于结束时间属性 值。 这是为了保证每个时态元组能够在时态表中被惟一标识，没有时间标签或者 1 8 中山人学硕l j 学位论文双时态数据库中间件的研究j 实现 时间标签不完整、不合法的元组不能称为是时态数据，不应该跟其它时态元组同 属一个关系。事务时间属于系统时间，不需要考虑，但是对有效时间时态表或者 双时态表插入数据的时候，则必须要求用户赋予正确的有效时间区间。另外在修 改时态表的时候，不允许用户把时问区间修改为空或者没有意义的时间区间。 3 2 2 双时态参照完整性规则 关系模型下传统的参照完整性规则是组成外键的属性不能为空值或者外键 值等于参照关系中某个元组的主键值。经本文3 1 3 节讨论，如果参照关系是时 态表，那么依赖关系的外键包含着时间区间，也即是说只能引用外键指定的时间 区间内有效存在的实体。如果这种时态参照完整性规则完全交由底层关系数据库 系统处理，这种规则就变成了用户自定义外键值和时间区间值要么为空，要么都 等于被引用元组的用户自定义主键值和时间区间值。根据双时态实体完整性规 则，时间区间值不能为空。另外我们知道，只要在实体生存周期内的区间，该实 体都是有效的，而并不需要完全等于实体的生存周期。因此，双时态参照完整性 规则应该如下： a ) 用户自定义外键值等于参照关系中被引用元组的主键值 b ) 如果参照关系是有效时间单时态关系，那么依赖关系的引用元组有效时 间区间在参照关系的被引用元组有效时间区间范围内；如果参照关系是 事务时间单时态关系，那么依赖关系的引用元组事务时间区间在参照关 系的被引用元组事务时间区间范围内；如果参照关系是双时态关系，那 么依赖关系的引用元组任一时间维的时间区间在参照关系的被引用元组 相同时间维的时间区间范围内【2 4 】【3 3 1 。 以上规则所表达的一个时间区间在另一时间区间范围内的涵义包含了两个 时间区间的e q u a l s 、s t a r t s 、f i n i s h e s 关系。假设有两个时间区间t 1 ( s t a r t ，e n d ) ，t 2 ( s t a r t ，e n d ) ，如果t 1 在t 2 范围内，则t 1 s t a r t = t 2 s t a r t 并且t 1 e n d = t 2 e n d 。 双时态参照完整性规则与关系模型的参照完整性规则有所不同，涉及到了时 间区间关系的判断。因此，双时态参照完整性规则的检查并不能直接交由底层关 系数据库系统，而需要双时态t e m p d b 中间件系统作相应的操作。 1 9 中山大学硕 ：学位论文双时态数据库中间件的研究与实现 3 3 双时态区间关系的探讨 双时态的数据模型必然涉及到双时态元素之间的关系，而双时态区间关系的 研究是双时态数据处理构建数据处理的基础。本节在单时态区间关系的基础上， 探讨了双时态区间之间的若干种关系，并给出了双时态区间关系和单时态区间关 系之间的转换策略。 3 3 1 双时态区间的1 0 种关系 a 1 1 e n 在1 9 8 3 年发表的论文中明确指出了1 3 种时态区间的关系，为时态关 系研究做出了开创性工作【1 1 。然而这1 3 种关系主要针对单时态时间区间，下面 讨论双时态区间关系。 双时态区间关系的研究具有非常重要的现实意义，双时态t e m p d b 的很多核 心处理模块都涉及到双时态区间关系的判断，从而进一步作出相应的数据处理， 典型的操作有双时态元组归并和双时态元组分裂。单时态区间关系主要围绕两时 间区间起始和结束点的先后发生顺序而产生，而双时态区间在示意图中通常表现 为矩形，两个双时态区间之间并没有明确的先后顺序之分。双时态区间关系分析 的方法是把双时态区间抽象为一个矩形图形，那么两个双时态区间之间的关系就 可以抽象为两张矩形图形之间的平面位置关系另外，矩形图形可以进一步看做 是平面上某一区域点的集合，从而根据两矩形拥有的点集之间的关系，把双时态 区间关系分为以下几种类型，其中t 1 和t 2 是双时态区间。 表3 51 0 种双时态区间关系 双时态区间关系图示等价关系说明 j t l 和1 2 两个点 o u t s i d e 仃l 皿) 田皂e 洲d 贸r 2 ，t 1 ) 集中没有任何共 同的点 中山人学硕i ：学位论文双时态数据库中回件的研究与实现 j v a l i d t i m e p 0 i i l t ( t 2 t 1 ) 有一个共同点。 p o i l l t ( t l ，t 2 ) t l 和t 2 有且仅 l t 1 l 一： lm 1 1 s a c t l 蚀u m e t l 和t 2 有多于1 个的共同点并 v 矾i d t i m e 且这组共同点的 ，r r m t s ( t i ，t 2 ) 1 r m e t - b y ( t 2 ，t 1 ) 事务时间都相同 l t - 除共同点之外， t l 点集的事务时 间都早于t 2 点集 lr 锄s a c u ( 婴i l m e 的事务时间。 t l 和配有多于1 n h l i d t i m e 个的共同点，并 且这组共同点的 有效时间都相 、呵m t s ( t 1 皿)冈、仃m e t - b y ( t 2 ，t 1 ) 同。除共同点之 t 1 外，t l 点集的有 l - 一一二一二一一 效时间都旱于t 2 王r a n s a c u 凹脏e 点集的有效时 间。 t l 和眨有多于1 个的共同点，并 且这组共同点至 少有2 个不同的 0 魄一a p s ( t lm ) 龌 o 闻r l a p 文t 2 t 1 ) 有效时间和2 个 不同的事务时 间。但这组共同 点并不是t l 或 t 2 的全部点。 jl v d i d t i m e 他包含t l ，即t l d i i l l 通g ( t l ，t 2 ) t 2 c 0 n t a i n s ( ，r 2 ，t 1 ) 点集是t 2 点集的 子集。 t l t r a n s a c t i o n t i m e 2 l 中山大学硕上学位论文双时态数据库中间件的研究与实现 从上图可知，双时态区间关系大致可以分成l o 种：o u t s i d e ，p o i n t ，1 v r m e e t s ， t t m e t b y ，v t m e e t s ，v t m e t b y ，o v e r l a p s ，d u r i n g ，c o n t a i n s ，e q u a l s 。这1 0 种关系之间可作如下转换： t r m e e t s 仃l ，1 2 ) = 1 眦c t - b y ( 1 r 2 ，t 1 ) v 喇e e t s 口l ，1 r 2 ) = v 1 m c t b y ( 1 2 ，t 1 ) d l l r i n g 口l ，t 2 ) = c 伽t 血s ，t 1 ) o u t s i d e ( 1 l ，1 r 2 ) = o l l t s i d e ( t 2 ，t 1 )p o i n t ( t l ，t 2 ) = p o 硫，t 1 ) 洲a p s ( t l ，均= 帅( 他，t 1 ) e q i l a l s ( t l ，t 2 户刚s m ，t 1 ) 这l o 种双时态区间关系的意义包括了任何两个双时态区间之间关系的所有 情况。当然，有些关系类型还可继续细分为不同的可能性，上表图示的只是这种 类型的其中一种代表性情况。比如0 、，e r l a p s 关系其实还细分为很多可能的情况， 下图就是其中的几种。 ee 图3 1 几种0 、r e r l a p s 关系细分情况 中山人学硕 ：学位论文双时态数据库中问件的研究与实现 3 3 2 双时态区间关系与单时态区间关系的转换 单时态区问关系是双时态区间关系研究的基础。在实际应用当中，往往也需 要将多维的单时态区间关系转化为双时态区间关系，或者将双时态区问关系转换 成单时态区问关系来处理，本文研究的双时态t e m p d b 系统就是在现实条件下采 用这种操作方式的例子。因此，本节将对双时态区问关系与单时态区间关系之间 的联系和转换方法进行研究。 根据a 1 1 e n 给出的单时态区间关系，每一维的关系类型有1 3 种，那么从理 论上来讲，考虑有效时间和事务时间两个维度合并成的双时态区间关系则有 1 3 术1 3 = 1 6 9 ( 种) 类型。这是一个非常庞大的数字，单时态和双时态关系的转换 处理将会很复杂。但从3 3 1 节给出的双时态区间关系类型来看，事实上并不需 要细分成这么多种。因为在很多情况下，一维单时态区间关系的类型可以决定性 地得出本文给出的双时态区间关系类型之一。设双时态区间t 1 ( v t l ，t t l ) 和 t 2 ( v t 2 ，t t 2 ) ，其中，v t l 和t t l 是双时态区间t 1 的有效时间区间和事务时间区 间，v t 2 和t t 2 是双时态区间t 2 的有效时间区间和事务时间区间。详细转换关 系如下推论： 推论一：双时态区间关系o u t s i d e ( t 1 ，t 2 ) 成立，只需要以下任意一种关系 成立。 a )b e f o r e ( v t l ，v t 2 ) b )a f t e r ( v t l ，v t 2 ) c )b e f o r e ( t t l ，t t 2 ) d )a f t e r ( t t l ，t t 2 ) 也即是说只要以上四种关系任意一种成立，都可成为充分条件推导出关系 o u t s i d e ( t l ，t 2 ) 。 推论二：双时态区间关系p o i n t ( t l ，t 2 ) 成立，只需要以下任意一种关系成 立。 a ) m e e t s ( v t l ，y t 2 ) a n dm e e t s ( t t l ，t t 2 ) b )m e e t s( v t l ，v t 2 ) a n dm e t b y ( t t l ，t t 2 ) c )m e t b y( v t l ，v t 2 )a n dm e e t s ( t t l ，t t 2 ) d )m e t b y( v t l ，v t 2 ) a n dm e t b y( t t l ，t t 2 ) 也即是说只要关系( v t l ，v t 2 ) 和( t t l ，t t 2 ) 都是m e e t s 和m e t b y 中任意一种， 则可成为充分条件推导出关系p o i n t ( t l ，t 2 ) 。 中山大学硕士学位论文双时态数据库中间件的研究与实现 推论三：双时态区间关系t t m e e t s ( t 1 ，t 2 ) 成立，只需要以下任意一种关系 成立： a )m e e 土s ( t t l ，t t 2 )a n dd u r i n g ( v t l ，v t 2 ) b )m e e t s ( t t l ，t t 2 ) a n dc o n t a i n s ( v t l ，v t 2 ) c ) m e e t s ( t t l ，t t 2 ) a n d0 v e r l a p s ( v t l ，v t 2 ) d )m e e t s ( t t l ，t t 2 ) a n d0 v e r l a p p e d b y ( v t l ，v t 2 ) e ) m e e t s ( t t l ，t t 2 ) a n ds t a r t s ( v t l ，v t 2 ) f )m e e t s ( t t l ，t t 2 ) a n ds t a r t e d b y ( v t l ，v t 2 ) g )m e e t s ( t t l ，t t 2 ) a n df i n i s h e s ( v t l ，v t 2 ) h )m e e t s ( t t l ，t t 2 ) a n df i n i s h e d b y ( v t l ，v t 2 ) i )m e e t s ( t t l ，t t 2 )a n de q u a l s( v t l ，v t 2 ) 也即是说，当m e e t s ( t t l ，t t 2 ) 关系成立的时候，v t l 和v t 2 只要是除了 b e f o r e ，a f t e r ，m e e t s ，m e t - b y 之外的任意一种关系，就可推导出t ，i m e e t s ( t 1 ，t 2 ) 推论四：双时态区间关系t t m e t - b y ( t 1 ，t 2 ) 成立，只需要以下任意一种关系 成立： a )m e t b y ( t t l ，t t 2 )a n dd u r i n g ( v t l ，v t 2 ) b )m e t b y ( t t l ，t t 2 ) a n dc o n t a i n s ( v t l ，v t 2 ) c )m e t b y( t tl ，t t 2 )a n d0 v e r l a p s ( v t1 ，v t 2 ) d )m e t b y ( t t l ，t t 2 ) a n do v e r l a p p e d b y ( v t l ，v t 2 ) e ) m e t - b y ( t t l ，t t 2 ) a n ds t a r t s ( v t l ，v t 2 ) f )m e t b y ( t t l ，t t 2 ) a n ds t a r t e d b y ( v t l ，v t 2 ) g )m e t b y ( t t l ，t t 2 ) a n df i n i s h e s ( v t l ，v t 2 ) h )m e t b y ( t t l ，t t 2 ) a n df i n i s h e d b y ( v t l ，v t 2 ) i )m e t b y ( t t l ，t t 2 ) a n de q u a l s( v t l ，v t 2 ) 也即是说，当m e t b y ( t t l ，t t 2 ) 关系成立的时候，v t l 和v t 2 只要是除了 b e f o r e ，a f t e r ，m e e t s ，m e t - b y 之外的任意一种关系，就可推导出 t ，r m e t - b y ( t 1 ，t 2 ) 。 推论五：双时态区间关系1 i t m e e t s ( t l ，t 2 ) 成立，只需要以下任意一种关系 成立： a ) m e e t s ( v t l ，v t 2 ) a n dd u r i n g ( t t l ，t t 2 ) b ) m e e t s ( v t l ，v t 2 ) 鲫dc o n t a i n s ( t t l ，t t 2 ) c )m e e t s ( v t l ，v t 2 ) a n do v e r l a p s ( t t l ，t t 2 ) d )m e e t s ( v t l ，v t 2 ) a n do v e r l a p p e d b y ( t t l ，t t 2 ) e )m e e t s ( v t l ，v t 2 ) a n ds t a r t s( t t l ，t t 2 ) f )m e e t s ( v t l ，v t 2 ) a n ds t a r t e d b y ( t t l ，t t 2 ) 中山人学硕f ：学位论文双时态数据库中间件的研究与实现 g ) m e e t s( v t l ，v t 2 )a n df i n i s h e s( t t l ，t t 2 ) h )m e e t s( v t l ，v t 2 ) a n df i n i s h e d b y ( t t l ，t t 2 ) i )m e e t s( v t l ，v t 2 )a n de q u a l s( t t l ，t t 2 ) 也即是说，当m e e t s ( v t l ，v t 2 ) 关系成立的时候，t t l 和t t 2 只要是除了 b e f o r e ，a f t e r ，m e e t s ，m e t 咄y 之外的任意一种关系，就可推导出v t m e e t s ( t 1 ，t 2 ) 。 推论六：双时态区间关系v t m e t - b y ( t l ，t 2 ) 成立，只需要以下任意一种关系 成立： a )m e t b y( v t l ，v t 2 ) a n dd u r i n g ( t t l ，t t 2 ) b ) m e t 咄y ( v t l ，v t 2 ) a n dc o n t a i n s ( t t l ，t t 2 ) c )m e t b y ( v t l ，v t 2 ) a n do v e r l a p s ( t t l ，t t 2 ) d )m e t b y( v t l ，v t 2 ) a n do v e r l a p p e d b y ( t t l ，t t 2 ) e ) m e t - b y ( v t l ，v t 2 ) a n ds t a r t s ( t t l ，t t 2 ) f ) m e t b y( v t1 ，v t 2 )a n ds t a r t e d b y( t tl ，t t 2 ) g )m e t b y ( v t l ，v t 2 ) a n df i n i s h e s ( t t l ，t t 2 ) h )m e t b y( v t l ，v t 2 ) a n df i n i s h e d b y( t t l ，t t 2 ) i )m e t b y( v t1 ，v t 2 ) a n de q u a l s ( t t l ，t t 2 ) 也即是说，当m e t b y ( v t l ，v t 2 ) 关系成立的时候，t t l 和t t 2 只要是除了 b e f o r e ，a f t e r ，m e e t s ，m e t - b y 之外的任意一种关系，就可推导出v t m e t - b y ( t 1 ，t 2 ) 。 推论七：双时态区间关系o v e r l a p s ( t 1 ，t 2 ) 成立，只需要以下任意一种情 况成立： a ) o 、，e r l a p s ( v t l ，v t 2 ) 并且关系( t t l ，t t 2 ) 是除 b e f o r e ，a f t e r ，m e e t s ，m e t _ b y 之外的九种关系之一。 b ) o 、，e r l a p p e d _ b y ( v t l ，v t 2 ) 并且关系( t t l ，t t 2 ) 是除 b e f o r e ，a f t e r ，m e e t s ，m e t - b y 之外的九种关系之一。 c ) o 、r e r l a p s ( t t l ，t t 2 ) 并且关系( v t l ，v t 2 ) 是除 b e f o r e ，a f t e r ，m e e t s ，m e t b y 之外的九种关系之一。 d ) o v e r l a p p e d b y ( t t l ，t t 2 ) 并且关系( v t l ，v t 2 ) 是除 b e f o r e ，a f t e r ，m e e t s ，m e t b y 之外的九种关系之一。 e ) 关系( v t l ，v t 2 ) 是s t a r t s ，d u r i n g ，f i n i s h e s 三种关系当中的一种， 并且关系( t t l ，t t 2 ) 是s t a r t e d - b y ，c o n t a i n s ，f i n i s h e d - b y 三种关 系当中的一种。 f ) 关系( t t l ，t t 2 ) 是s t a r t s ，d u r i n g ，f i n i s h e s 三种关系当中的一种， 并且关系( v t1 ，v t 2 ) 是s t a r t e d b y ，c o n t a in s ，f in is h e d _ b y 三种关 系当中的一种。 中山人学硕上学位论文 双时态数据库中间件的研究与实现 推论八：双时态区间关系d u r i n g ( t 1 ，t 2 ) 成立，只需要以下任意一种关系 成立： a ) s t a r t s ( v tl ，v t 2 ) a n df i n is h e s ( t t l ，t t 2 ) b ) s t a r t s ( v t l ，v t 2 ) a n dd u r i n g ( t t l ，t t 2 ) c )s t a r t s ( v t l ，v t 2 ) a n de q u a l s ( t t l ，t t 2 ) d )s t a r t s ( v t l ，v t 2 ) a n ds t a r t s ( t t l ，t t 2 ) e ) f ) g ) h ) i ) j ) k ) 1 ) f i n i s h e s f i n i s h e s f i n i s h e s f i n i s h e s d u r i n g d u r i n g d u r i n g d u r i n g ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) ( v t l ，v t 2 ) a n ds t a r t s( t tl ，t t 2 ) a n dd u r i n g ( t tl ，t t 2 ) a n de q u a l s( t tl ，t t 2 ) a n df i n i s h e s ( t t