（计算机软件与理论专业论文）在时变类表示数据模型上的时态关联挖掘研究.pdf

山东大学硕士学位论文 摘要 随着数据挖掘技术的发展，人们对时态信息的关注日益提高。时态数据库中 既反映被处理事件的历史信息又体现系统中元事件时态信息的双时态数据库日 益受到人们的重视。随着双时态数据库的不断发展，双时态数据库的模型、索引 等技术趋于成熟。 通常情况下，在时态数据库的一个元组中只有若干属性与时间紧密相关。随 着人们对时态信息的重视，这些与时间紧密相关的属性越来越多地成为了研究热 点。传统的双时态关系模型虽然标记了有效时间和事务时间，但其有效时间和事 务时间是约定在整个元组上的，不能唯一地约束某一属性。人们无法区分哪些属 性与时间紧密相关、哪些无关；在属性随时间变化时，规模过大的元组会带来更 多的i o 压力，影响效率的提高。要在传统时态模型之上进行一些时态数据挖掘 的话，工作往往变得复杂、甚至难以进行。 本文提出一种改进的表示数据模型。改进的表示数据模型基于属性的时变 性，将双时态关系分为多个时间粒度关系，引入分类关系来实现对多关系的管理。 使得与时间相关属性的数据分析工作更具针对性和灵活性。此外，文章详细阐述 了模型之上的查找、更新等操作。 为验证模型在时态数据挖掘中的性能，以时态关联规则挖掘为例，使用 a p r i o r i 改进算法，在表示数据模型和改进的表示数据模型上进行了测试。测试 数据表明改进表示数据模型在该应用领域的有效性。模型的不足之处是过于简 单，没有考虑索引技术和对t s q l 2 语言的支持。这些都是今后努力的方向。 关键字：时态数据库；时变属性：时态关联规则：a p r i o r i 算法 i ij 东大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t am i n i n gt e c h n o l o g y ，t e m p o r a li n f o r m a t i o ni s g e t t i n ga t t e n t i o ni n c r e a s i n g l y ，e s p e c i a l l yt h eb i t e m p o r a ld a t a b a s ew h i c h r e f l e c t sn o to n l yt h eh i s t o r i c a li n f o r m a t i o no ft h ei n c i d e n t sb u ta l s o t h et e m p o r a li n f o r m a tio no fm e t ae v e n t si nt h es y s t e m t e c h n o l o g i e so f b it e m p o r a ld a t a b a s em o d e la n di n d e xh a sb e i n gm a t u r e i nm o s tc a s e s ，n o ta 1 1t h ea t t r i b u t e si no n er e c o r di st i m er e l a t e d a s m o r ea t t e n t i o no nt i m ei n f o r m a t i o n ，m o r ea n dm o r er e s e a r c h e sh a v eb e i n g c a r r i e do nt i m er e l a t e da t t r i b u t e s a l t h r o u g ht h ec l a s s i cb i t e m p o r a l d a t a b a s em o d e ls e tt h ee f f e c t i v et i m ea n de v e n tt i m e ，t h ee f f e c t i v et i m e a n de v e n tt i m ea r eb o u n dt ot h er e c o r db u tac e r t a i na t t r i b u t e so ft h e r e c o r d i nt h i ss i t u a t i o n ，w h i c ha t t r i b u t e sa r et i m er e l a t e di sh a r dt o f i n g e r o u t w h e nt i m e c h a n g i n g c a u s e st i m e r e l a t e da t t r i b u t e s c h a n g i n g ，l a r g er e c o r dw i1 1g e tl a r g e ri op r e s s u r e ，w h i c hi sn e g a t i v et o e f f i c i e n c y i naw o r d ，t e m p o r a ld a t am i n i n gi sh a r dt oc a r r yo ni nc l a s s i c t e m p o r a ld a t a b a s em o d e 1 d u et ot h ea b o v er e a s o n s ，a ni m p r o v e d r e p r e s e n t a t i o n a lr e l a t i o n s h i pm o d e l i sp r o p o s e di nt h i sp a p e r i m p r o v e dr e p r e s e n t a t i o n a lr e l a t i o n s h i pm o d e l s p l i t eu pt h ep r e v i o u sb i t e m p o r a lr e l a t i o n s h i pi n t om u l t i p l et i m et a b l e b a s eo nt h et i m eo ft h ea t t r i b u t e s i n t r o d u c e dc a t e g o r yr e l a t i o n s h i p m a n a g em u l t i p l et i m et a b l ei ni m p r o v e dm o d e l i nt h i sw a yt h et i m e r e l a t e d d a t aa n a l y s i sw o r k si sm o r ed i r e c t l ya n df e x i b l e i na d d i t i o n ，i nt h i s p a p e r ，w ed e s c r i b et h ef i n d ，u p d a t eo p e r a t i o n si nd e t a i lf o rt h en e wm o d e l ， i n c l u d i n g ：a d dan e wo b j e c t ，m o d if ya t t r i b u t e s ，d e l e t eao b j e c ta n ds o 0 n i no r d e rt ov e r i f yt h es u p e r i o r i t yo ft h i sn e wm o d e li nd a t aa n a l y s i s ， t h ep a p e rf o c u s e so nt h ea p p li c a t i o no ft e m p o r a la s s o c i a t i o nr u l e si nd a t a l i i 东大学硕士学位论文 m i n i n g f i r s t l y ，w eg i v eo u tt h ec o n c e p t so fc o m m o na s s o c i a t i o nr u l e sa n d t h ec l a s s i c a la p r i o r ia r i t h m e t i c s e c o n d l y 。o nt h e s eb a s e s ，w ed e s c r i b e h o wt oo p e r a t et h et e m p o r a la s s o c i a t i o nr u l e sa r i t h m e t i co nt h i si m p r o v e d n e wm o d e la n dw eh a v ea no p e r a t i o np r o c e d u r ei nd e t a i1a n dg i v eo u tt h e e x p e r i m e n td a t a t h ee x p r i m e n t ss h o wt h a tt h en e wm o d e lh a ss u p e r i o r i t y i nt h ea p p l i c a t i o na r e a s t h ei n a d e q u a c i e so ft h en e wm o d e li st h a tt h e m o d e ld o e s n tt a k ei n d e x i n gt e c h n o l o g ya n dt s q l 2l a n g u a g es u p p o r t ，w h i c h w il lb er e s e a r c h e dint h ef u t u r e k e y w o r d s ：t e m p o r a ld a t a b a s e ；t i m e - v a r y i n gc a t e g o r y ；t e m p o r a la s s o c i a t i o n r u l e s ；a l g o r i t h ma p r i o r i h i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：塑垒盗 e t期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：唯塑套躲师签 期： 东大学硕士学位论文 1 1 研究背景 第一章绪论 信息是对现实事物、事件的刻画与描述，对信息的记录构成了数据。数据 质量影响着人们对事实的认识。对信息的描述越完整越精确其质量越高，越便 于人们使用。关系数据库技术的广泛应用极大地方便了人们对信息的管理，相 比之前的管理方式提高了效率和准确性。在传统的关系数据库之中着重研究了 事实在某一时刻的状态，满足了多数事务处理的需要。随着对事实认识的深入， 尤其是为了揭示事实随时问变化的规律，迫切需要在数据信息之中增加对时间 的记录与刻画。时间是物质存在的一种客观形式，由过去、现在、将来构成，是 物质运动、变化的持续性表现。在对事实的描述中如果缺少了时间要素的话， 这种描述就是是不完整、不精确的。对时间要素的要求反映在数据库领域，就 是提出了时态关系和对时态数据库的需要。 传统的数据库管理系统n 叫对时态数据未做专门处理，只把它作为一个普通 属性来对待，都是把它作为用户定义时间进行存储和管理。因此，关系数据库中 只反映、存储了事实的瞬时状态，即只反映一个对象在某一个时刻的状态。 随着数据挖掘瞄1 技术的发展，人们对时态信息的关注日益提高。既反映被 处理事件历史性信息又体现数据库系统中元事件时态信息的双时态数据库引起 了很多专家学者的重视。经过2 0 多年的努力，双时态数据库的研究取得了丰硕 成果，模型、索引方面的技术日臻完善。 传统的双时态关系模型虽然标记了有效时间和事务时间，但其有效时间和 事务时间是约束在整条记录上，不能专一地约束单一属性。用户无法区分哪些 属性与时间紧密相关、哪些无关；在属性随时间变化时，规模过大的元组操作 会带来更大的1 0 压力，影响系统效率的提高。要在传统时态模型之上进行一些 时态数据挖掘的话，工作往往变得复杂、甚至难以进行。如，在表示数据模型 之上进行关联规则挖掘时遇到的一个问题：在属性间时间粒度不一致时，通常 采用最小时间粒度来约束所有属性。带来的结果是，属性的时态信息满足需要， 数据冗余膨胀，对存储需求急剧增加；或者会出现相反的现象。 l i l 东大学硕士学位论文 基于以上所述，本文提出一种改进的表示数据模型。改进的表示数据模型 基于属性的时变性，将双时态关系分为多个时间粒度关系，分别对应主体关系 和实例关系，引入分类关系实现对多粒度关系的管理，从而实现时间相关属性 分类管理。使得与时态相关的数据分析工作更具针对性和灵活性。此外，文章 详细阐述了改进模型之上的查找、更新等操作。 1 2 国内外研究现状 1 2 1 时态数据库技术的研究现状 文献【6 9 】阐述了到目前为止时态数据库技术的发展现状。概括起来是，自上 世纪八十年代初时态数据库技术产生以来，经过专家学者的大量研究和实践， 时态数据库在基础理论、数据模型、数据库语言、应用技术等方面都取得了丰 硕成果，时态信息技术目前仍处在不断的研究和发展阶段。现有的时态数据库 研究及问题可以归纳如下。 1 、在现有的时态数据模型中，对时间数据的描述主要是依照j b e n z v i 于 1 9 7 9 1 9 8 2 年提出的时间点时间区间模型、有效时间( v a l i dt i m e ) 、事务时间 ( t r a n s a c t i o nt i m e ) 以及双时态( b i - t e m p o r a l ) 【10 】等概念；时态数据演算主要是基于 j f a l l e n 于1 9 8 4 年提出的十三种时间区间演算( 或其扩展) 。 2 、时态数据模型多，各种模型都还存在一些不足，还没有形成较完整的国 际性或行业性标准。时态数据模型一般都是关系数据模型的扩展，并将关系数 据库作为特例。主要扩展方法是在关系数据库中增加一些时态运算，如a f t e r , b e f o i 咂和o v e r l a p 等；扩展一些时态操作，例如时态选择，时态投影、时 态连接等。目前大部分时态数据查询语言是通过扩展当前的查询语言实现的， 如在s q l 或者q u e l 的基础之上扩展而成。这样的时态数据查询语言功能有限。 3 、在应用方面，由于上世纪八十年代数据库技术迅速发展，特别是九十年 代后多媒体技术、网络技术的大发展，时态信息的应用呈现出巨大需求。在地 理信息系统、农业信息系统，电信信息系统，电子商务，电子政务，智能决策 支持系统，数据仓库与数据挖掘方面，尤其是时空( s p a t i o t e m p o r a l ) 信息技术和 多媒体信息系统方面，时态信息处理技术经历了空前的探索和发展。由于还没 2 山东大学硕士学位论文 有成熟的时态模型和软件产品，大部分与时态相关的应用，只是借鉴当前一些 时态数据模型在关系数据库中实现。文献 9 a o 谈到，到二十世纪九十年代初，人 们提出的时态数据模型及其查询语言己多达四十余种。目前，对时态数据库的 各种特征基本上都进行了探索，面临的问题应该是总结成果，研究技术实现。 文献中还指出，任何一种时态数据模型要满足所有要求是很难的。现有各种时 态数据模型在用途上都各有侧重，t s q l 2 中提出的二种时态数据模型，分别是 双时态概念数据模型( b i t e m p o r a lc o n c e p t u a ld a t am o d e l ，b c d m ) 和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 ，r d m ) 。b c d m 存在着 明显的不足，它的时间标签占用存储空间过大，直接用b c d m 形式存储时态数 据不够理想。用表示数据模型表示时态数据，可以节省存储空间，但这种模型 使得数据的表现形式具有很大的随意性，不利于时态数据的有效处理。 4 、虽然传统的双时态关系模型标记了有效时间和事务时间，但其有效时间 和事务时间约束在整条记录上，不能唯一地约束单一属性。这样，用户无法区 分哪些属性与时间紧密相关、哪些无关；在属性随时间变化时，规模过大的元 组操作会带来更大的1 0 压力，影响效率的提高。要在传统时态模型之上进行一 些时态数据挖掘的话，工作往往变得复杂、费解。 1 2 2 关联规则挖掘的研究现状 与关联规则挖掘相比，时态关联规则挖掘能更好地反映数据中所隐藏的与 时间相关的知识。近年来，国内外许多学者对此进行了研究，而且已成为k d d 的热点之一。 时态关联挖掘就是要发现事件与时间之间的关联以及基于时域的事件与事 件之间的关系等，我们将这种带有时间属性的关联规则称为时态关联规则。研 究时态关联规则首先要弄清楚时态约束问题。在现实中，附加上某种时态约束 的知识将可以更好地描述事实，也更有价值。面对大容量的时态数据集，用户 关心的往往是某一时间区域的数据而不是整个时域的数据，而特定时间区域的 数据又可能导致特定的数据间的关联。时态约束可以应用到数据挖掘和知识发 现中，并起到过滤过时数据、聚焦用户目标以及加速知识模式生成等作用。文 献 6 j 给出了时态区间代数的概念，定义了时态区间变量的交与并操作，挖掘用 山东大学硕士学位论文 户给定时态区间内的时态约束规则。 时态关联规则研究主要集中在关联规则成立的时间和时态关联规则模型的 建立两个问题上。 1 、关联规则成立的时间 关联规则挖掘很少考虑关联规贝蝴时间适用性，然而每个关联规则都有其 成立的时间区域。如在购物篮分析中，对各商品项目的购买时间加以考虑，就 会得出在某段时间内成立的关联规则。文献【1 1 】提出了时间区间的延展概念及方 法、时间区间的归并概念及技术。 在文献 1 2 】中，引入了交易项目集的生命期概念，规则的支持度只在其生命 期内考察。该文献所介绍的时态关联规则是对一般的非时态关联规则的扩展， 这种方法主要是针对商品交易数据库进行的，它的基本思想是将频繁项集的搜 索限制于其生命期内。这种对项目集赋予生命期的方法可以发现一般关联规则 挖掘方法所不能发现的新知识。文献【1 1 - 1 7 】主要是针对交易发生的时间区域来扩 展项目集，在连接操作上考虑了项目的时间属性，以决定规则成立的时间域。 这些研究的重点是事件与时间之间的关联，考虑了一定时间段内的阶段性关联 规则，未涉及到事件之间的时态约束。 已有的这些研究主要是对数据库的每个元组考虑其发生时间，强调的是关 联规则成立的时间特征，以标明所发现的知识何时有效。在未考虑时间特征时， 所得到的规则存在一个前提，这个前提就是：“规则是永远有效的。 考虑了 时间特征后，所得到的规则将可以更好地描述客观事实，因而也就更具针对性 和价值。 2 、时态关联规则模型的建立 由于时态关联规则挖掘是在带有时间属性的数据上进行的，因而有关时态 数据的表示也需进行研究，以便于建立事件和时态规则模型。对于这方面的深 入研究还不多。如，对于时间的表示及相应的性质的深入研究还很少，而且也 各有特点。 文献【1 6 1 8 1 9 2 1 】对有关时间的概念及性质从数学理论上进行了定义和证明， 如时态型、时态因子的定义及性质，仅建立了简单时态事件模型，对部分特殊 情况下的时态关联规则的挖掘思想进行了简单介绍，却没有深入的算法研究。 4 山东大学硕士学位论文 对于复杂的时态关联规则以及通用的时态关联规则模型没有进行相关的讨论。 相对于文献【2 2 - 2 5 ，在文献【1 9 五1 】中时间的定义更具广泛性、更直观，也更易于理 解。尽管如此，文献中提出的模型还是可以描述企业当前发展的现状和规律， 也可以用来实现预测和辅助决策。 1 3 文章内容及组织结构 作者提出了一种改进的双时态关系模型，并给出模型之上的插入、修改等 相关操作。该模型依据属性的时变特征对属性进行区分，以期满足数据挖掘工 作中对时间相关事件处理的需要。通过减小元组的长度，改善时态数据操作性 能，提高系统效率。同时，结合该模型提出了一种时态关联规则挖掘的实现方 法，并给出相关实验数据予以验证。 论文的结构如下： 第1 章绪论。简述论文所研究问题的背景、现状和论文的内容结构安排。 第2 章时态数据库基础。介绍了论文研究所涉及到的时态数据库基础知 识。 第3 章基于时变类的双时态改进模型。叙述了双时态关系数据模型建立和 更新过程，阐述了如何建立双时态关系数据模型，在此基础上提出一种基于属 性时变类的改进模型，并详细给出模型结构以及模型上的更新和查找操作。 第4 章时态关联挖掘实现。在描述关联规则的基本概念和经典a p r i o r i 算 法的基础上，结合第三章提出的改进模型，给出该模型之上的时态关联规则挖 掘实现方法，并实验证明模型在该应用领域的优越性。 第5 章总结。总结论文的主要工作结果，分析不足，并提出对下一步研究 工作的展望。 山东大学硕士学位论文 第二章时态数据库 时间是物质存在的一种客观形式，由过去、现在、将来构成，是物质运动、 变化的持续性表现。任何事件的发生发展都离不开具体的时间因素。在对事实的 描述中，缺少了时间要素的描述都是不完整、不准确的。反映在数据库中就是： 所有记录都具有时态属性。随着数据库应用范围的扩大，在很多问题中出现了过 去和将来的信息与现在的信息同等重要的情况，对时态信息处理的需求越来越迫 切，特别是在电子政务、电子商务、数据仓库等信息系统中，时态信息处理技术 已成为提高应用水平的关键。 传统数据库管理系统对时态数据未做专门的处理，只作为一个普通属性来对 待，以用户定义时间方式存储和管理。在传统数据库中只能反映、存储事实的瞬 时状态。为满足对时态信息处理的应用需求，对数据库管理系统提出了如下新要 求。 l 、要求管理被处理事件的历史性信息。如：与自然灾害( 地震、洪涝等) 事件有关的历史资料，人事、财务、金融应用中的历史资料。这些数据客观上反 映了事物发生发展的内在规律。 2 、要求管理数据库系统中元事件的时态信息。如：数据库被查、删、改的 时间等。这些数据有助于改善数据库系统的可靠性和效率。 为满足这些新需求，人们提出了时态数据库概念，并不断探索、完善相关的 技术。 2 - 1 时态数据库的发展 关于时态数据库的发展历史，国际时态数据库权威学者t m n s e l 等在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 ”收录了此 前时态数据库的所有重要成果。唐常杰对时态数据库技术前2 0 年的发展也在文 献【3 1 中做了系统回顾。汤庸先生等在文献【4 ，6 ，刀中将时态信息处理技术的发展划 分为三个时期。 1 、开创期( 1 9 8 2 年以前) 6 山东大学硕士学位论文 加州大学洛杉矶分校b e n z v i 和纽约大学的c l i f f o r d 在1 9 8 2 年的博士论文 是时态数据库技术开创期的两个标志性成果。j b e nz v i 于1 9 7 9 - - - 1 9 8 2 年对时 态数据库作了开创性研究，他的博士论文( t h et i m er e l a t i o n a lm o d e l 总结 了他的一系列工作。b e nz v i 的贡献突出表现在下列几点。 ( 1 ) 他提出了时态数据库模型，引入了时间间隔( t i m ep e r i o d ) 概念，后来被 学术界改称为时间区间。 ( 2 ) 在1 9 7 9 - - - 1 9 8 2 这个关系规范型研究的热点时期，b e nz v i 突破思想禁 区，提出并研究了非1 n f 的t d b 。 ( 3 ) 以时间区间作字段值，刷新了人们认为数据库字段值只能是一个数或 串的观念。 ( 4 ) 引入了后来被称为双时态的概念，即用有效时间表示被管理对象在库 中生命周期，用事务时间表示数据库本身的历史。 ( 5 ) 引入了时态索引结构。 1 9 8 2 年j c l i f f o r d 在纽约大学完成了博士论文“al o g i c a lf r a m ew o r kf o r t h et e m p o r a ls e m a n t i c sa n dn a t u r a ll a n g u a g eq u e r y i n go f h i s t o r i c a ld a t a b a s e 及 相关的一组文章，对历史数据库的开创性作了重要贡献。它注意到了被管理对 象的生命周期( l i f e s p a n ) ，研究了在关系、元组、字段值上加时态信息的技术细 节，引入了历史关系模型，历史关系代数，研究了历史数据库中投影、选择、 连接的特殊要求和特殊规律，研究了历史关系模型与传统关系模型的兼容性， 即当把区间缩小为一点( n o w , n o w ) 时历史数据库即退化为传统快照数据库， 且相应的时态代数运算退化为传统快照关系运算。 2 、发展期( 1 9 8 3 1 9 9 3 年) 这个时期标志性成果是t a n s e l 等在1 9 9 3 年共同编辑出版的( t e m p o r a l d 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 。该书被称为“世界上第 一本关于时态数据库的专著。该书对此前国际时态数据库技术的研究给出了 全面的总结。其中收录了十三种公认的时态数据模型，每个模型从不同的需求、 观点出发，各自独立地建立了一套术语、概念、数学模型，并形成了一套各自 独立的理论体系。 3 、应用期( 1 9 9 3 年至今) 7 【i i 东大学硕士学位论文 1 9 9 4 年后，如何将时态数据模型“标准化”和“产品化”是这个时期重要 目标，广泛应用和实践则是这个时期重要特征。在这个阶段的突出成果有 g i e d r i u s 等提出的时态中间件上查询优化和评估，时态归并算法，时态连接操 作，以及使用时态逻辑查询时态数据库等。在“产品化”方面的代表是瑞士 t i m e c o n s u l t 组织于1 9 9 8 年推出的t i m e d b 。 尽管国内外学者们在时态数据库领域提出了很多创新的理论，但是目前并 没有一个像传统关系数据库一样具有成熟功能( 数据定义、存储、完整性控制 等) 的时态数据库管理系统。 2 2 时态数据库的基本概念 信息系统中的数据通常是保存在数据库中，记录时态数据反映时态信息的 数据库就是时态数据库( t e m p o r a ld a t a b a s e ) 。从对事务时间和有效时间的支持 的角度来说，通常将支持事务时间和有效时间的数据库称为时态数据库。相对 于传统数据库而言，时态数据库中增加了时间概念、时间的关系和运算等内容。 2 2 1 时间的概念 1 、时间粒度 时间粒度( g r a n u l a r i t y ) 是在应用中选择的时间单位，用来描述时间点之 间离散化程度的大小。时间粒度有很多，生活中常用的就有年、月、日、时、分、 秒等。时间粒度越小，离散的时间点越多，描述事件的信息越精细准确，反之， 描述事件的信息越粗糙。如，描述雇员工资信息的时间粒度使用月，描述航空飞 行班次使用分，在科学研究中要使用微秒甚至更小的时间粒度。在实际应用中选 择怎样的粒度，应该根据应用领域需要和系统的承受能力来确定。不同的时间粒 度之间存在进制关系，在度量时可以进行相互转换。 2 、时间元素 时间元素( t i m ee l e m e n t s ) 是事实或事件的时间特征，在数据库中就是元 组或者属性的时间特征描述，它是时态信息系统正确有效的表达时间属性的基 础。时间元素有多种表示形式，可以是离散的时间点，也可以是连续的时间区间， 还可以是离散点或时间区间的集合形式。最基本的三种时间元素是：时间点、时 1 i i 东大学硕士学位论文 间区间和时间跨度。 ( 1 ) 时间点 时间点( t i m ei n s t a n t ) 是离散的时间元素，又称时刻( t i m ep o i n t ) 。这 种描述是把时间轴看成由一个个离散的点组成的。这些离散化的时间点的间隔大 小适度时，也就是说选择的时间粒度合适时，就可以准确地描述现实世界中事件 发生发展的状态。时间点是时间轴上的一个点，在使用中它和时间粒度是密切相 关的。如：2 0 0 5 年1 0 月1 日是以“天”为时间粒度来描述的时间点，9 点2 1 分3 5 秒是以“秒 为时间粒度来描述的时间点。使用的时间粒度越小描述的事实就越 精确。 ( 2 ) 时间区间 时间区间( t i m ei n t e r v a l ) 是区间化的时间元素。表示时间轴上有起点和 终点的一段时间，时间区间的两个端点分别叫做时间区间的起始时间和终止时 间。指明两个时间点，即一个时刻二元组，就可以完整地描述一个时间区间。如： 2 0 0 0 年1 月2 0 0 0 年3 月就指明了一个时间区间。根据起始、终止时间点的封闭 情况，时间区间存在四种类型，表示方法和语义如表2 一l 所示。 表2 - 1四种时间区间描述方法 时间区间类型时间区间语义 p 。，p 。开始于p l 时间点终止于时间点p 2 ，包含p l s n p 2 。 p 。，p ：) 开始于p l 时间点终止于时间点p 2 ，包含p 1 。 ( p 。，p ：开始于p l 时间点终止于时间点p 2 ，包含p 2 。 ( p 。，p ：)开始于p 1 时间点终止于时间点p 2 。 使用时间区间来表示时间元素能够兼容时间点元素的表示。当时间区间的的 起始点和终止点相同时就表示了一个时间点。当然，时间点是离散的，时间区间 是连续的。 ( 3 ) 时间跨度 时间跨度( t i m es p a n ) ：是描述一段连续的、具有固定长度的、没有明确的 起止点的时问元素，用来指明时间的长度。如，“三年半 ，“3 6 小时”都是 9 山东大学硕士学位论文 时间跨度。在数据库系统内，一般用一个整数表示时间跨度。时间跨度和时间 区间都表示一段连续的时间，不同之处在于：时间跨度没有明确的时问起点和 时间终点，时间区间有着明确的时间起点和时问终点。 2 2 2 时态区间和时间点的关系 a l l e n 在其论文中指出了1 3 中时态区间的关系，为时态关系研究做出了开 创性的工作。这1 3 种关系可以在时间轴上表示如表2 - 2 ，其中t 1 和t 2 是时态 区间。 1 0 i i i 东大学硕士学位论文 表2 - 2 时态区间关系 时态区间关系图示说明 b e f o r e ( t l 。t 2 ) t lt 2 t 1 在t 2 之前发生 l 一1 一 a f t e r ( t 1 ，t 2 ) t 2t 1 t l 在t 2 之后发生 i 一- 一 t l d u r i n g ( t l ，t 2 ) 心 t 1 的区间范围包含在t 2 内 - t 2 c o n t a i n s ( tl ，t 2 )- t l t 2 的区间范围包含在t l 内 t l t 1 比t 2 早开始且两个区间有 o v e r l a p s ( t l ，t 2 ) t 乜 相交 乜 t 2 比t 1 早开始且两个区间有 o v e r l a p p e d - b y ( t l ，t 2 ) - t l 相交 - t 1 m e e t s ( t l ，t 2 ) i 亿t 2 开始于t 1 的结束点 ii t 2 m e t - b y ( t l ，t 2 ) i 一一 t 1 t 1 开始于t 2 的结束点 ii t l t 1 和t 2 有共同的起点，t l s t a r t s ( t l ，t 2 ) ! i t 2 ；t比t 2 先结束。 t l t 1 和t 2 有共同的起点，t 2 s t a r t e d b y ( tl ，t 2 ) 一 - ； u 比t l 先结束。- t 1 t 1 和t 2 有共同的结束点，t l f i n i s h e s ( t l ，t 2 ) t 比t 2 晚开始。 t 1 t 1 和t 2 有共同的结束点，t 2 f i n is h e d b y ( tl ，t 2 ) _ l 二 比t 1 晚开始。 i t 1 e q u a l s ( t l ，t 2 ) tl t 1 和t 2 在时间轴上重合 配 i i i 东大学硕士学位论文 2 2 3 三种基本时间类型 1 、用户定义时间( u s e r d e f i n e dt i m e ) 用户自定义时间是用户根据应用领域需要或理解定义的时间。传统数据库 中提供了用户定义时间的机制，允许用户把某个元组的属性值设为时间类型。 这种时间一般取值为时间点。如李清的出生日期为1 9 8 0 年2 月8 日，那么在数 据库里，与张清相应的元组记录里的b i r t h d a y 属性的值就为1 9 8 0 0 2 0 8 。一 般来说，用户自定义时间的值都是固定不变的。 在时态数据库中也支持用户自定义时间，系统不对它进行任何特殊处理， 不需要专门的语言支持。用户自定义时间是完全应用依赖的，由用户和系统以 常规的方式进行存取，不在时态数据库处理的范围之内。 2 、有效时间( v a l i dt i m e ) 有效时间是指被管理对象的生命周期，是一个事实或事件在现实世界中发 生并保持为真的那段时问。还经常被叫做现实世界时间( r e a l - w o r l dt i m e ) 、逻 辑时间( 1 0 9 i c a lt i m e ) 或者数据时间( d a t at i m e ) 。有效时间可以真实地反映事 实在过去、现在和将来的状态。例如，考虑事实“张三峰从2 0 0 3 年到2 0 0 7 年 是大学生”，那么时间区间 2 0 0 3 ，2 0 0 7 3 是事实“张三峰是大学生”的有效时间 区间，该事实在该时间区间内为真。有效时间可以是时间点、时间点的集合、 时间区间或者时间区间的集合，或者是整个时间域。有效时间由时态数据库系 统解释并处理，在查询的过程中对用户透明。用户也可以显式地查询和更新有 效时间。它的确切语义依赖于应用领域，取值是否有效和具体应用场合密切相 关，对应于实际应用的需要或现实世界变化的历史，在数据库中涉及到数据的 时间约束问题。 3 、事务时间( t r a n s a c t i o nt i m e ) 事务时间是对一个数据库对象进行操作的时间。还经常被叫做注册时间 ( r e g i s t r a t i o nt i m e ) 、外在时间、物理时间( p h y s i c a lt i m e ) 或数据库时间 ( d a t a b a s et i m e ) 。它记录着对数据库进行修改或更新的各种操作所发生的时间 信息，对应着数据库状态变迁的历史。如对象录入数据库的时间、修改的时间、 删除的时间等都是事务时间，标记着数据库状态的变迁。事务时间的值由系统 时钟给出，它独立于应用，用户不能修改事务时间。处理事务时间的方法是存 【i j 东大学硕士学位论文 储所有数据库的状态，即每处理一个事务就存储一个数据库状态。修改只能对 最后一个状态进行，但可以查询任意一个状态。 事务时间与有效时问是互相正交的两个概念。有效时间一般由用户显式指 定，事务时问由数据库系统在更新数据库状态时自动生成。因而，相对于有效 时间来说，事务时间的语义单一，进行数据库更新操作时，只需把系统当前时 间绑定到当前事务的事务时间上即可。 2 2 4 两种时间变量 在数据库时态信息的描述中，人们经常采用 v s ，v e ) 、 t s ，t e 这样的区 间形式来分别表示有效时间和事务时间。假定一个事实的有效时间是 a ，b ) ( a = b ) ，用时间标签描述为“f r o mat ob ”。当对应与上述事实的数据记录从 进入数据库以后，直到事实在现实世界无效之前，为了体现数据在时间上的连 续性和事实在现实世界中的有效性，有效时间标签“t o ”后面的数据必须按照 数据库更新的时间粒度( 如“日”) 来进行更新；否则就会出现时间不连续或者 事实的有效时间区间得不到正确表达的问题。显然，这种大量更新非常费时费 力，也是难以实现的的。为了高效正确地解决这个问题，引入时间变量就成为 有效手段。 当有效时间的起止时间不能确定为某个时刻的时候，人们用“n o w ”来描述 有效时间的起l e 值。“n o w ”作为一个时间变元，表示现实世界的当前时间。它 随着当前时间的变化而变化，有效地记录了时间的变化。当系统时间和现实世 界时间一致时，它的有效值也等效与系统的当前时间。随着时间的流逝，f l o w 的值也跟着改变来准确体现不同的当前时间。 类似地，“l i e ”是事务时间变量，用来表示事务时间中的当前时间。它随 着数据库系统的时问变化而变化，i i c 的每次改变对应着数据库状态的一次改变。 随着数据库状态的历史化进程，1 1 c 都准确地刻画着数据库的当前时间。假设一 个事实的事务时间区间是 a ，u c ) ，就表示该事实对应的数据在时间点a 开始提 交到目前为止还没有完成，事务一直处于提交的过程之中。 东大学硕士学位论文 2 2 5 两个时间维 传统的关系数据库是二维结构，一个是属性维，另一个是元组维，分别构 成了关系的横向和纵向结构。时态数据库中，要反映事实变化的历史信息增加 了有效时间维，为了反映数据库状态的变化增加了事务时间维。这样一来，时 态数据库就构成了一个四维结构，其中的两个时间维就是有效时间维和事务时 间维。所以，双时态数据库的状态空间是一个四维空间，关系数据库的状态空 间是一个二维的空间。 2 3 时态数据库的分类 按照对时态信息的支持能力对数据库进行分类，可以将数据库分成四种类 型，分别是快照数据库( s n a p s h o td a t a b a s e ) 、回滚数据库( r o ll b a c kd a t a b a s e ) ， 历史数据库( h i s t o r i c a ld a t a b a s e ) 和时态数据库( t e m p o r a ld a t a b a s e ) 。它们 的出现和发展反应了时态数据库的发展历程。 2 3 1 快照数据库 快照数据库是反映现实世界特定时刻的瞬间情况的数据模型，反映了现实 世界连续变化中某一瞬间的状态。快照数据库的前提假设：一个存储在数据库 中的元组一定是真实世界中的有效事实。快照数据库只支持用户定义时间类型， 由静态的二维关系组成，分别是属性维和元组维。数据库的状态变迁由事务触 发实现，一旦事务提交，其状态变迁立即生效，原来的数据库状态就完全被丢 弃和遗忘。相应的，现实世界的原来状态也一样被丢弃和遗忘。快照数据库无 法表示属性的时间约束关系，没有维护数据库状态变迁的能力，只能进行当前 数据库状态之上的查询、更改或删除活动。它反映的是数据的当前状态，随着 时间的推移，数据库状态在不断的改变，新状态将覆盖旧状态，状态之间的转 变是通过事务的提交实现的。状态之间转变的确切时刻是发生c o m m i t 的时刻。 从时态数据库的观点来看，快照数据库不区分事务时间和有效时间。 为了更好地了解快照数据库，我们给出快照数据库的二维结构图。 1 4 山东大学硕士学位论文 图2 一l 快照数据库的二维结构图 目前，正被广泛应用的数据库，如d b 2 、o r a c l e 等，都是快照数据库系统。 2 3 2 回滚数据库 回滚数据库( 又叫事务数据库) 是一种支持事务时间的数据库。除了支持 用户定义时间类型外，还支持事务时间，把被管理对象的生命周期限定在事务 时间之上。对数据库的变迁状态按事务时间进行编址，它保存了所有的状态演 变过程。这种数据库由回滚关系组成。 回滚关系是一个三维结构，可看作是一个按时间编址的瞬象的序列。这个 三维结构是这样的：x 轴是属性轴，y 轴是元组轴，z 轴是事务时间轴。在z 轴 的时间点上作垂直切割，每一个时间点都对应于一个二维的快照数据库，反映 了在那一时间点上的数据库建立、修改、删除及数据库的定期重写( 里面可能 没有数据的变更) 活动。三维结构图示在图2 - 2 中。 东大学硕士学位论文 图2 2 回滚数据库的三维结构图 回滚数据库保持了数据库变迁的历史，每个事务都产生一个新的回滚关系 附着在事务时间轴上。回滚数据库的不足之处是：第一，它记录的是数据库活 动的历史，而不是现实世界事实变化的历史。现实世界中元组属性已经随着时 问变化了，但是因为数据库的事务时间没有改变，元组属性的改变在数据库中 根本没有得到体现。第二，历史状态中的元组错误无法更正。对于历史状态中 的元组可以查看，一旦发现元组有错误并且事务已经提交的话，我们所能做的 工作只能是在下次系统事务时间进行新的更正。改动的只是提交前的数据库状 态，更早的数据库状态是无法再改变的。 2 3 3 历史数据库 历史数据库与回滚数据库类似，区别是历史数据库支持有效时间，不支持