（计算机应用技术专业论文）时态数据库中不确定时态信息的处理研究.pdf

哈尔滨理t 大学工学硕士学位论文 时态数据库中不确定时态信息的处理研究 摘要 在研究不断变化着的现实世界时，时间是一个非常重要的因素。我们常 以时间为依据来解释各种事实和数据，因为各种事件和实体间的潜在关系常 常蕴涵在时态信息中。目前对时态信息处理的研究多集中于确定时态，然而 在现实的许多情况下，事件的时间往往很难精确判定，所以，建立一个能全 面且方便地描述各类事件的不确定时态信息、又具备一定时态推理能力的不 确定时态信息表达模型，具有十分重要的意义。 本文是对不确定时态信息表达模型的理论研究。本文的研究始终以不确 定时态信息处理为主线，结合概率论的方法，提出了基本概率的不确定时态 信息表达模型，并基于此模型提出时态信息不确定关系的表示及推理。本文 的研究沿如下思路进行：首先，仔细研究表示不确定时态信息的方法，结合 概率论，提出一个基于概率的表示不确定时态信息的统一模型，分析模型的 各类性质和时态推理能力；其次，讨论了模型中各种时态信息的不确定关 系，给出了基于a l l e n 区间关系的概率表示，并提出了基于概率的时态信息 不确定关系的推理，有助于解决不确定关系间的传递问题。最后，提出t e p r 网络，用来表示时态信息之间的不确定关系，并给出了基于t e p r 网络 的路径一致性算法，可以对时态信息不确定关系网络中的时态约束关系进行 筛选，有助于解决网络的约束满足问题。 关键词时态数据库；不确定时态；时态表达；不确定推理 哈尔滨理工大学工学硕士学位论文 r e s e a r c ho nu n c e r t a i n t yt e m p o r a li n f o r m a t i o n 。7 一m o o r a ld a t a b a s e s i nl e mo r a la t aa s e s a b s t r a c t t i m ei sav e r yi m p o r t a n tf a c t o rw h i l er e s e a r c h i n go nt h ec h a n g i n gw o r l d w ea l w a y se x p l a i na l lk i n d so fr e a l i t i e sa n dd a t ab yt i m e ，b e c a u s et h ep o t e n t i a l r e l a t i o n s h i p sa m o n ge v e n t sa n de n t i t i e sa r eo f t e ni m p l i c a t e di nt h et e m p o r a l i n f o r m a t i o n u pt on o w , m o s tr e s e a r c h e so nt e m p o r a li n f o r m a t i o nf o c u so n c e r t a i n t yt e m p o r a li n f o r m a t i o n h o w e v e r , i ti sh a r dt od e t e r m i n et h ep r e c i s et i m e o fe v e n t si nm o s tp r a c t i c a ls i t u a t i o n s i ti s n e c e s s a r yt ob u i l da nu n c e r t a i n t y t e m p o r a lr e p r e s e n t a t i o nm o d e l ，w h i c hc a nb e u s e dt o d e s c r i b eu n c e r t a i n t y t e m p o r a li n f o r m a t i o no fe v e n t sg e n e r a l l ya n dc o n v e n i e n t l y t h i sd i s s e r t a t i o nw a sa b o u tu n c e r t a i n t yt e m p o r a lr e p r e s e n t a t i o nm o d e li n t h e o r y i tf o c u s e do nu n c e r t a i n t yt e m p o r a li n f o r m a t i o nm a n a g e m e n t c o m b i n e d w i t ht h et h e o r yo fp o s s i b i l i t y , ap o s s i b i l i t yt h e o r y b a s e du n c e r t a i n t yt e m p o r a l r e p r e s e n t a t i o nm o d e lw a sp r e s e n t e d b a s e do nt h i sm o d e l ，t h er e p r e s e n t a t i o na n d r e a s o n i n go fu n c e r t a i nr e l a t i o n sb e t w e e nt e m p o r a li n f o r m a t i o nw a sp r e s e n t e d t h ec o n t e n t so ft h i sd i s s e r t a t i o ni n c l u d e d ：f i r s t l y , b a s e do nt h ea n a l y s i so f t e m p o r a li n f o r m a t i o nm a n a g e m e n t ，au n i f i e dp o s s i b i l i t yt h e o r y b a s e dt e m p o r a l r e p r e s e n t a t i o nm o d e lw a sp r e s e n t e d t h ep r o p e r t ya n dc a p a b i l i t yf o rt e m p o r a l r e a s o n i n go ft h i sm o d e lw a sa l s oa n a l y z e d ；s e c o n d l y , t h eu n c e r t a i nr e l a t i o n so f t e m p o r a li n f o r m a t i o nw e r ed i s c u s s e d ，w h i c hc a nb er e p r e s e n t e dw i t h t h e p o s s i b i l i t yv a l u e sd e n o t i n gt h ep r o b a b i l i t yo ft h eb a s i cr e l a t i o n sd e f i n e db ya l l e n t h er e a s o n i n gw i t hu n c e r t a i nr e l a t i o n sb e t w e e nt h et e m p o r a li n f o r m a t i o nw a s r e p r e s e n t e d i tc a nb eu s e dt os o l v et r a n s i t i v i t yp r o b l e mo fu n c e r t a i n ；l a s t l y , a t e m p o r a le l e m e n tp r o b a b i l i s t i cr e l a t i o n ( t e p r ) n e t w o r kw a sd e f i n e d ，w h i c h c a n r e p r e s e n tt h eu n c e r t a i nr e l a t i o n sb e t w e e n t h et e m p o r a li n f o r m a t i o n b a s e do n t h et e p rn e t w o r k ，t h ep a t hc o n s i s t e n c ya l g o r i t h mw a sp r o p o s e d ，w i t c hc a nb e u s e dt os o l v et h ec o n s t r a i n ts a t i s f a c t i o np r o b l e m ，a sw e l la st ot e s tat e p r i i n e t w o r kf o rc o n s i s t e n c y 哈尔滨理t 大学工学硕士学位论文 k e y w o r d st e m p o r a ld a t a b a s e s ，u n c e r t a i n t yt e m p o r a l ，t e m p o r a lr e p r e s e n t a t i o n ， u n c e r t a i nr e a s o n i n g 1 1 1 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文时态数据库中不确定时态信息 的处理研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中 以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：) 日照 日期：为年弓月，口日 哈尔滨理工大学硕士学位论文使用授权书 时态数据库中不确定时态信息的处理研究系本人在哈尔滨理工大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理 工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔 滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论 文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密留。 ( 请在以上相应方框内打) 作者签名：j 司巫 日期：m 莒年弓月，口日 导师签名：善能芬日期：t 谚年多月，。日 哈尔滨理t 大学工学硕士学位论文 1 1 研究的背景及意义 第1 章绪论 时间是现实生活中的一个重要因素，是解释生活中各种事实和数据的主要 依据n 一1 。随着信息技术的深入发展，对时态信息处理的要求越来越迫切。目 前，时态信息处理技术已经成为许多新一代数据库与信息系统的关键技术，尤 其在电子商务、财经系统、医疗系统、土地规划系统、地理信息系统和预约系 统中扮演日益重要的角色n 瓢引。r s n o d g r a s s 指出，在应用系统中平均每5 0 行 代码就涉及到一个有关时间的语句8 1 。时态数据库就是为了满足时态数据管 理的要求而产生并发展起来的。 时态数据库的先前工作，主要建立在有效时间的开始、终止都十分清楚的 基础上。然而，在许多实际情况中，事件的时间界限并不十分清楚。我们常常 无法很明确地知道事件发生的时间，只知道事件大概是什么时候发生的。例 如，我们大概知道这件事发生在“下午2 点到4 点之间 、“上周的某个时 间”、“大概在四月的中旬”。一般来说，不确定时态信息的产生主要有以下 几种原因。 时间粒度。在大多数情况下，记录数据时间的粒度与事件发生的确切时间 粒度不一致。比如一个事件发生在某秒内，然而由于系统的时间粒度只是精确 到天，所以最终在系统中该事件发生的时间是以天作为标记。 时间测定技术。许多时间测定技术本身就不精确，导致测出的时间数据有 误差，例如采用c a r b o n - 1 4 来测定时间。 未来计划时间。项目计划完成的时间往往都是不确定的。例如，这个项目 将会在三到六个月之后完成。 未知或不精确的事件时间。一般来说，事件发生时间可以是未知或者不精 确的。例如，假设我们不知道某人出生的时间，那么在数据库中，该人的出生 时间就会被记录为未知( 出生时间是从时间开始到现在之间) 或不精确( 出生 时间是从5 0 年前到现在) 。 由于不确定时态信息的广泛存在，时态数据库管理系统有必要支持不确定 时间。然而，表示不确定时间信息是时态数据库中目前仍缺少的一个重要的功 能，这一缺陷极大地约束了时态数据库的应用范围，影响了时态数据库的进一 哈尔滨理工大学t 学硕十学位论文 步推广。因此，如何表示不确定时态信息，是进行更深层次的时态推理和完善 时态数据库的一个重要前提条件。 现在的文献中有大量的有关时态数据库的研究报道，国内时态数据库的研 究和应用也越来越受到关注，一般的问题都是建立在时态属性为确切数据的假 设条件下。但在现实世界的环境中，一些重要的数据信息( 例如事件的有效时 间) 通常不是一个非常确切的量值，往往是一个时间段或是一个空值，因此， 把确切数据的条件扩展到不确定或是空值的条件是时态数据库中一个急需解决 的问题，这就产生了时态数据库中不确定信息的研究。 在时态属性确切的时态数据库问题研究中，把一些时态变量描述成不确定 时态信息，这样产生的数据库更接近人类认识的直觉性，也更加符合现实世界 的情况。因此，时态数据库中的不确定信息问题是当今数据库技术发展的必然 趋势，具有极其广泛的应用价值和实际背景。 1 2 国内外研究现状 1 2 1 时态数据库的研究现状及发展 数据库是现今存储信息的重要手段。传统的数据库只能体现现实世界中数 据的当前状态，只反映了一个对象在某个时刻的状态，与过去和未来无关。这 就是常见的快照数据库( s n a p s h o td a t a b a s e ) 。时态数据库t d b ( t e m p o r a l d a t a b a s e ) 是在传统( 快照) 数据库的基础上增加时间维，来刻画某个时刻的数 据，反映历史并揭示未来。时态数据库由于其动态性( 过时的数据不再从数据 库中删除，对历史数据也可以进行更新，使系统和现实世界一直保持着全方位 的动态交换) 和全面性( 可以提供任何时刻和时间段的数据) ，因此被称为真正 意义上的数据库阻1 。 时态信息的研究始于2 0 世纪7 0 年代。1 9 7 0 年，g w i e d e r h o l d 和j f f r i i e s 研 制的医疗信息处理系统在处理时态信息方面做了最早的尝试n 引。时态数据库 t d b 技术的研究始于2 0 世纪8 0 年代，在这期间，t d b 的理论、模型、查询语言 以及标准化都取得了丰硕成果。国内外出现了大量的关于时态数据模型和时态 查询语言的文献。计算机学术界对时态数据库的研究给予了极大关注，时念数 据库的理论研究得到了发展，取得了许多科研成果，并实现了一些原型系统， 基本完成了奠基工作n 。 在国外，时态数据库技术的发展过程可分为开创期、发展期和应用期三个 哈尔滨理工大学工学硕上学位论文 阶段引。 1 开创期j b e n z v i 和j c l i f f o r d 在1 9 8 2 年完成的博士论文标志着时态数据 库的研究进入开创期。j b e n z v i 提出了以时问区间作为字段值的时态数据库模 型年d n i n f 时态数据库t d b ，引入了t i m ep e r i o d ( 又称t i m ei n t e r v a l ) 的概念，双 时态概念( 即用有效时间表示被管理对象的生命周期，事务时间表示数据库本 身的历史) ，以及时态索引结构，突破了数据库字段值只能是一个数或串的概 念。j c l i f f o r d 引入了历史数据库模型，研究了在关系、原组和字段值上加入时 态信息的技术细节。 2 发展期从1 9 8 3 年到1 9 9 4 年为发展期。这一时期产生了许多时态数据 库模型和方法。9 0 年代初期，国际时态数据库权威学者t a n s e l 等出版的 “t e m p o r a ld a t a b a s e ：t h e o r y , d e s i g na n di m p l e m e n t a t i o n ”是时态数据库发展过程 中具有代表意义的产物n 引。此书收录了1 3 种最有影响力的时态数据模型。这些 模型从不同的需求和观点出发，各自独立的建立了一套概念、术语和时态关 系，并形成了各自独立的理论体系。 3 应用期从1 9 9 4 年到现在为应用期。这一时期的主要特征是将时态数 据模型标准化以及将其应用到不同的领域。但是，由于还没有时态信息的产品 形成，这一时期的应用基本上是借用时态数据库的一些概念，在传统的关系数 据库上实现时态管理和时态操作n 4 。 在国内，时态数据库的研究和应用也越来越受到关注，出现了许多相关的 书籍n5 1 6 1 ，如唐常杰设计实现了对象历史模型o b j e c th i s t o r y 盯8 。与国外相比， 国内对时态数据模型以及时态数据库的研究还比较少。主要集中在时态数据库 的一般性技术方面。比如，多媒体和地理信息系统等专业信息系统中涉及到的 时态信息处理，其它主要为时态数据库理论和数据模型的阶段性研究n 2 1 。 近年来有关时态表示和时态推理的研究越来越多，并涉及到许多不同的学 科，比如计算机科学、哲学、心理学和语言学等。在计算机科学领域，时间是 人工智一匕( a r t l f i c l a li n t e l l i g e n c e ，简称a d 、数据库管理、多媒体系统、历史管 理系统和医疗信息系统等的核心问题之一。目前对时态信息的研究主要来自两 个领域，分别为人工智能领域和数据库领域，研究的核心是时态数据模型和时 态推理。在时态信息表示和推理方面，主要集中在时间模型和时态属性上n 引。 在实际应用中，需要根据具体的研究目的来考虑使用哪一种或几种时间表示模 犁。 哈尔滨理t 大学工学硕上学位论文 1 2 2 时态不确定性的研究及发展 在历史或双时态数据库中，一个事实的有效时间可能是不确定的。不确定 性有许多来源。比如，时态粒度的不匹配、日期的测定技术、计划的不确定 性、未知或不精确事件以及时钟测量技术等n 引。无论哪种原因都需要处理有效 时间不确定的数据。下面总结数据库中不确定时间的处理方法。 在国外，g a d i a 等人提出了包含不完全信息的时态关系数据库模型n 引。另 外，g a d i a 还提出了三值逻辑t r u e ，f a l s e $ l l u n d e f i n e d 。d y r e s o n 和s n o d g r e s s 提出 了用上下界以及概率聚集函数表示不确定时间n 引。k o u b a r a k i s 用约束数据库来 解决时态不确定性问题幢训。一个约束数据库是一个扩展的关系数据库，元组由 变量和相关约束组成。g r i f f i t h s 等人提出了在元组之间表达时态关系。 o c o n n o r 等人开发了系统c h r o n u si i 来解决不确定时态信息的查询问题，并将 其与一种时态提取系统相结合，构成r e s u m e ，它是处理医疗数据库中时态不 确定性和时态提取的简单有力的工具瞳引。c o w l e y 等人提出了新的不确定时间戳 表示方法，并扩展了a l l e n 的1 3 种区间关系来表示不确定的时间区问，还提供了 相应的运算符操纵这些确定的和不确定的时间区间瞳引。c a m p o s 等人提出了将模 糊时态推理与现有数据库系统d b m s 结合的方法瞳制。s c h o c k a e r t 等人扩展了 a l l e n 的1 3 种区间关系，用f u z z y 集方法表示不确定时间之间的确定关系和不确 定关系心射。 在国内也有一些学者对不确定时间的表示进行了研究。主要有二种方法， 分别为f u z z y 集理论和r o u g h 集理论。比如张师超提出了基于间断区间的时态知 识表示心引。林嘉宜等人给出了不确定时态信息的表示方法乜7 。莫孙冶等采用 f u z z y 集的方法表示不确定时间及时态关系幢引。 为了更好的反映现实世界时态信息的变化，需要考虑各种不确定时态数据 并给出相应的表示方法。除此之外，其它相关的问题也需要重新研究。这些问 题主要包括不确定时态数据的操作、语法和语义的定义、一致性和完整性约 束、合适的不确定时态关系代数的构造、不确定时态数据模型的集成和实现问 题等。其中时态数据建模是表示和推理时态信息的基础砼9 。 1 3 存在的不足 目前，时态信息技术仍处于研究和发展阶段，人们从不同的观点提出了各 种时态数据库模型。另一方面，由于实际应用的需求，时态信息处理的应用领 哈尔滨理丁大学t 学硕十学位论文 域越来越宽，在应用中也提出了许多方法和技术。同时在对时态信息各方面的 研究中也存在着以下不足。 现有的时态数据模型中主要存在的不足是：时态数据运算体系不完备，没 有系统和有力的数学理论支持。现有的时态数据模型一般都是传统关系数据库 的扩展，并将传统关系数据库作为特例。主要方法是在t d b 中增加a f t e r 、 b e f o e 和o v e r l a p 等运算；扩展时态选择、时态投影、时态连接等操作。目 前大部分时态数据查询语言是通过扩展当前的查询语言女i s q l 或者q u e l ，时态 数据查询功能有限，效率比较低。由于种种原因，数据库厂商难以下决心选用 t d b 技术用于产品。目前时态数据库研究取得了相当的进展，但是大多研究局 限在数据库的时态属性，而忽视了其他信息的时态属性，例如知识库的时态特征 和应用。时态数据技术目前还停留在“数据”处理上，关于时态逻辑和推理方 面的研究，主要优点是符号演算和推理能力强，但是信息处理能力弱，与时态数 据库和时态信息处理研究相脱离。关于时态知识与逻辑方面主要包括时问区间 逻辑运算的扩充等，没有涉及时态知识数据库模型。 对于时态信息研究方面，先前的时态数据模型大部分都建立在有效时间的 开始和结束点均精确的基础上。而由于现实世界的动态变化，经常不能准确的 确定事件发生的时间及其时态关系，有时只知道事件大概发生在什么时间。由 于这类时态信息的广泛性，使得研究不确定时间以及相应的时态数据模型是很 有必要的。因此，不确定时态数据的表示、操作以及查询是目前时态数据库不 可忽视的发展方向之一啪一。 不确定时态信息数据的研究存在以下两个值得注意的问题。一是数据模型 采用的时态原语。具体来讲是模型所支持的时态原语( 时间点、时间区间、持 续时间还是时态元素) 、这些时态原语的时间域( 密集的还是离散的) 、时态原 语的确定性以及时态原语的排序( 线性还是分支) 。二是时态数据的表示方法和 操作。 对于不确定时态数据建模的问题，近年来已经有许多方法被提出口引，但是 在不确定时态数据方面仍有一些问题有待解决，主要有以下几个方面： 1 如何将自然语言表达式转化为数据库可操作的表示形式。 2 有效时间的不确定性如何表示。 3 如何构造一种通用的支持确定和不确定时间的时态数据模型，且适应 不同的应用需求。 哈尔滨理工人学工学硕士学位论文 1 4 本文研究思路及主要内容 本文首先仔细研究已有的时态信息表达模型和不确定时态信息的处理方 法，包括时间点、时间区间等的表达方法和定性、定量约束的表示方法。综合 利用已有的各类模型的理论和技术，结合概率论，提出一个基于概率的表示不 确定时态信息的统一模型，可用于描述各种具有确定或不确定性时态信息的事 件，具备一定的时态推理能力。本文涉及的主要研究内容如下： 首先，提出了一个基于概率的时态信息表示模型，不仅可以表示确定和不 确定的时态信息，而且还能描述定性和定量的时态关系。在模型中，不确定时 态元素分为时间点、时间区间和时距三种，能描述各种类型的不确定时态信 息。该模型将时区和事件两个概念分离出来，并在此基础上定义了时间点的3 个关系、时间区间的1 3 个关系。对模型不进行复杂的约束，以保证模型在描述 不确定时态信息方面的通用性。在模型中，确定时态是不确定时态的一种特殊 情况。该模型是全文研究的基础。 其次，在理论上对本文提出的不确定时态信息表示模型进行分析，讨论了 模型中各种时态信息的不确定关系。给出了基于a l l e n 区间关系的概率表示，并 提出了基于概率的时态信息不确定关系的推理算法，可以对不确定关系进行推 理，有助于解决不确定关系间的传递问题。针对本文提出的时态信息的不确定 关系推理，分析了各种推理运算所具有的数学性质。 再次，提出t e p r 网络，用来表示时态信息之间的不确定关系，并给出了 基于t e p r 网络的路径一致性算法，可以对时态信息不确定关系网络中的时态 约束关系进行筛选，有助于解决网络的约束满足问题。 最后，通过一个简单的实例说明了时态信息不确定关系的定性和定量推 理。 哈尔滨理丁大学t 学硕十学位论文 2 1 引言 第2 章现有时态信息模型分析 在计算机科学研究中，时态信息表达和时态推理是信息系统、人工智能和 其它过程建模等领域的核心问题。例如在人工智能的规划问题中，给定某时刻 的世界状态描述和一系列动作( a c t i o n ) ，规划者要设计一组动作序列，使得世界 能从初始状态变迁到目标状态，如移动积木、绕开障碍等。在整个规划过程 中，规划者就需要一些基于时间的信息表达方法，在此之上进行推理，从而得 到解决问题的方案。总之，时间在我们的现实生活中扮演着一个十分重要的角 色，对推理、信息处理、知识发现等的研究不可避免要涉及到时态信息。在进 入本课题之前，本章先介绍与课题研究内容有关的一些基本理论。 2 2 时态基本元素模型 理论物理学家在宇宙的大爆炸的假说中，指出时间开始于大爆炸的那一瞬 间；至于时间是否有终点，他们并没有给出答案。时间的概念就像一个被压缩 的橡皮筋，随着宇宙的爆炸在不断地扩展。 2 2 1 时态信息的概念 在现实世界中，时间无时不有，无处不在，客观世界中的事物都带有时间 的属性。描述现实世界的带有时间属性的信息系统，称为时态信息系统。例如 金融方面的会计、银行系统；档案管理方面的人事档案、医疗记录系统；行程 安排中的飞机、火车、旅店等项目的管理系统；科学应用方面的气候、地理系 统等。这些系统中记录的信息是随时间变化的，这种随着时间变化的信息称为 时态信息( t e m p o r a li n f o r m a t i o n ) 。 2 2 2 时间基本元素单位 时间元素就是指表示时间属性值的元素，时间元素在时态信息系统中有着 基础的地位，它对于正确有效的表达记录的时间属性有着重要的意义。对于时 哈尔滨理工大学工学硕十学位论文 间元素来说，出于表达的需要，它有许多具体的形式，有的是离散的时间点， 有的是连续的时间区间，当然还有较为复杂的情形一集合形式。 对于离散的时间点，属性的时变特性是离散的，每个时间点都对应记录中 的属性值；对于时间段，属性的变化具有某些连续的特性，用连续时间区间记 录元组的属性节省了大量的空间；对于复杂的集合形式，时间元素的描述更为 复杂。时间元素主要有三种基本的表现形式： 1 时间点时间点是时间轴上的一点，它是和时间粒度相关的。选择适 当的时间粒度，就可以准确的描述现实世界事件发生及变化的状况。例如， 2 0 0 7 年6 月1 日，时间粒度精确到“天”。如果系统使用的最小时间粒度是 “秒”，则该时间点在系统内的表示必须换算成2 0 0 7 年6 月l 同0 时o 分0 秒。 2 时间区间时间区间是通过描述时间段的起始和终止点来描述一段时 间。时间区间是指一段时间，有固定的起止时间点，例女n 2 0 0 5 年至2 0 0 7 年。时 间区间的表示方法根据两端时间点是否封闭分为4 种，如图2 1 表示。 四种区间 ( 1 ) 【只，p j 】 ( 2 ) b ，p s ) ( 3 ) ( 只，p j 】 ( 4 ) ( 只，马) 区间含义 a f p j p i t p j p t tsp j p t t p j 图例 j _ 。 o j o _ 。 a ，p j ：分别表不两个时i 司点； 【】：分别表示左右闭区间； ( ) ：分别表示左右开区间。 图2 - 1 基于时间区间的时间描述方法 f i g 2 - 1a p p r o a c ho f t i m er e p r e s e n tb a s e do ni n t e r v a l 时间点和时间区间是可以转化的。例如：在 b ，p j ) 中，令b = p ，这时的时 间区间可以理解为延续时间为0 的一段时间，即时间轴上的某个时间点。同 样，时间区间可以用时间点的集合表示，当确定了时间粒度的时候，每个时间 区间都是可以用时间点的集合来表示的。 在这四种区间的表达方式中，一般采用前端封闭，尾端开放的形式，主要 考虑的是时间区间兼容时间点的表示方式和时间区间的比较谓词的缘故，而事 实上，它与前端开放尾端封闭的时间区间的表达方式在表达能力上是等价的。 3 时间跨度时间跨度是指持续的一段时间，表示时问的长度。例如： “2y e a r3m o n t h ”、“1 0 天”、“4 小时”等。在数据库系统内，一般用一个 哈尔滨理t 大学t 学硕十学位论文 整数表示时间跨度。 与时间区间类似，时间跨度也是表示一段时间，所不同的是，时间跨度没 有时间起点，也没有时间终点。从这个意义上来说，时间区间是一个矢量，而 时间跨度是一个标量。 2 3 时态数据库简介 2 3 1 时态数据库的分类 时态数据库t d b ( t e m p o r a ld a t a b a s e ) 是在传统的数据库基础上加上时间 维，不仅能刻画某个时刻的数据，还能反映出其历史和揭示其未来。时态数据 库按其功能分为历史数据库、事务数据库和双时态数据库。 1 历史数据库( h i s t o r i c a ld a t a b a s e ) 历史数据库只支持有效时间，每个关 系记录一个“历史的”状态。它记录现实世界在有效时间内发生的事件，或者 现实世界的状态变化。 2 回滚数据库( r o l l b a c kd a t a b a s e ) 回滚数据库只支持事务时间，因此又 称事务数据库。它记录了数据库自身的变化，沿事务时间轴记录数据，按照事 务时间排序，保留了所有状态演变中过去的状态。 3 双时态数据库( b i t e m p o r a ld a t a b a s e ) 双时态数据库同时支持有效时间 和事务时间。它既能够处理管理对象的历史，又能管理数据库本身被删改的历 史。 2 3 2 双时态数据库 双时态数据建模要涉及多种时间系统，特别是在现实世界中事件发生的真 实时间于将它记录到数据库的时间可能不一样。数据库管理可能涉及三种时间 体系：有效时间、事务时间和用户自定义时间。 1 有效时间一个事实( 事件) 的有效时间( v a l i dt i m e ) 就是在建模的现 实世界中它为真( 存在) 的时间。有效时间可用单一的时间点、时间区间来表 示，或者表示为多个时间点和时间区间的有限集的有效时间集合，即一个事实 可以联系任意个时间点和时间区间，以单一的时间点和时间区间作为重要的特 例。 有效时间对应于应用或者现实世界变化历史，它是应用依赖的，即它的值 哈尔滨理t 大学工学硕上学位论文 来于应用，或由用户经由应用提供。，有效时间可以是“未来”时间( 一个事实 在未来的某时刻为真) 。 2 事务时间一个数据库事实( 数据) 在某一时间点存储到数据库中， 此后它就是“现行”的，直至被逻辑地删除。一个数据库事实的事务时间就是 它在数据库中存在( 现行) 的时间。 事务时间对应于现有事务或现有数据库状态变迁的历史。它是应用独立 的，即其值仅根据系统时钟导出，因而它是应用不可操纵的。事务时间不能晚 于当前事务时间( 因为它对应于现有历史) ，也不能改变( 因为不能改变过去 历史) 。 3 用户自定义时间用户自定义时间就是一个不解释的日期和时间属性 域，就像“整数”、“实数、“金钱 等域一样，系统不作任何特殊处理， 不要专门的语言支持( 这不像有效时间和事务时间) 。与有效时间一样，用户 自定义时间的值是完全应用依赖的，由用户应用以常规方式存取。 双时态数据库模型不仅记录了现实世界中事件发生的有效时间，而且记录 了这个事件存储到数据库中的事务时间，既反映了现实世界的历史，又反映了 数据库的历史，可以满足人们对时态数据操作的各种要求。 2 4 时态信息研究相关理论 目前时态数据库研究取得了相当的进展，但是大多研究局限在数据库的时 态属性，而忽视了其他信息的时态属性，例如知识库的时态特征和应用。下面介 绍在人工智能领域中时态信息研究相关理论。 对时态逻辑的研究大约起于二十世纪5 0 年代末6 0 年代初。这一问题开始并 未引起人工智能领域研究者们的重视，后来被证实，人工智能的倡导者们想要 达到他们所宣称的目标，必须结合时间的表示并使用某种形式的时态逻辑协引。 因为大多数人工智能应用中的推理都是基于逻辑的，所以研究者们采用在逻辑 框架中加入时问概念的方法进行时态推理。时态推理是将时间观念形式化并提 供对时态信息进行表示和推理的方法制。一般认为，在人工智能领域，对时态 信息的处理有三种逻辑口引：一阶逻辑( f i r s to r d e rl o g i c ) ，模态时态逻辑( m o d a l t e m p o r a ll o g i c ) 和具体化时态逻辑( r e i f i e dt e m p o r a ll o g i c ) 。 1 一阶逻辑在数学和物理学中，一般用一个附加的变量来表示时间， 通常为一个实数或整数。这种表示方式下的推理方法属于一阶谓词演算( f i r s t o r d e rp r e d i c a t ec a l c u l u s ) 。一阶谓词演算在人工智能的许多方面得到广泛应 哈尔滨理t 大学r t 学硕上学位论文 用，人们提出了在一阶逻辑框架内对时间进行推理的很多方法，这些方法并没 有对时间进行特殊的处理，所以它们仍然属于应用在事件上的经典逻辑，只不 过在逻辑中，事件的描述都包括了时间因素。例如事件“在时间t 内，灯是亮 着的 可以表示为( o n ( 1 a m p ) ，0 。 。 一阶逻辑将时间作为谓词的一个参数，主要用于物理过程和一些数学应用 的推理，如果用于动作( a c t i o n ) 和自然语言理解( n a t u r a ll a n g u a g eu n d e r s t a n d i n g ) 的推理则显得远远不够。例如在一阶逻辑中，我们经常用的“现在”、“接 着”、“当、“直到”等表示时间概念的词语是无法表示的，这是因为一阶 逻辑仅仅将时间表示为一个数值。但是对于那些仅需将时间看成一个变量的实 际问题，一阶逻辑仍然十分有用。一阶逻辑的优点在于计算量少，而且建立于 一系列坚实的理论基础之上，其缺点在于表达能力较差，将时问作为一个参数 处理使其无法表示一些特定的时间概念，限制了其在时态推理中的应用。 2 模态时态逻辑相对一阶逻辑而言，模态时态逻辑采用了相对时间的 方法，所有的语句在时态上都是相对于现在或者其它事件的时间的，如模念时 态逻辑中的“将来总是 、“过去是 等模态词都是相对“现在而言的。模 态时态逻辑是在模态逻辑的基础上发展而来的，其表达能力和符号演算的效率 使其在自然语言理解方面应用得十分广泛引。在程序理论方面，模态时态逻辑 经常用于推导程序的特性，如程序正确性判断，程序终止性判断和程序死锁可 能性判断等，并已经应用于串行和并行程序中的自动证明和自动推理过程。时 态逻辑本身也已经发展成编程语言，女1 t e m p u r a 语言。 然而，模态时态逻辑的定理证明比一阶逻辑要困难得多。时态模态逻辑的 应用很大程度上还要依赖于这些定理证明技术的进展，不少文献提出了针对模 态时态逻辑定理的一些有效证明方法曲7 1 。 3 具体化时态逻辑时态具体化有很多优点。一方面，它给予了时间一 个特殊的状态；另一方面，它又允许人们在命题项上进行判断和量化。因此， 我们可以在更高层次上对命题项之间的时态关系进行表示和讨论。基于这些优 点，时态推理中具体化的方法用得很广泛，时态推理中最有影响的工作大部分 都是基于具体化方法的。具体化时态逻辑将其它元语言( 如经典一阶逻辑或模 态逻辑) 的标准命题具体化为表示命题项的对象啪1 。虽然具体化时态逻辑在许 多方面如公理的完备性等降低了要求，但由于具有较强大的表达能力，所以将 其用于智能活动的问题求解( 如规划等) 是相当有效的旧9 1 。 总之，具体化时态逻辑在一阶逻辑的框架内，通过具体化命题，大大提高 了对时态信息的表达能力，吸引了人工智能领域的许多研究者们。 哈尔滨理工大学工学硕十学位论文 在这些逻辑中又有三种方法来表示时间的结构引：一是基于事件的时态逻 辑( e v e n t b a s e dt e m p o r a ll o g i c ) ，即以事件作为时间的基本单元；二是基于区 间的时态逻辑( i n t e r v a l b a s e dt e m p o r a ll o g i 曲，即以时间区间作为时间的基本 单元；三是基于点的时态逻辑( p o i n t b a s e dt e m p o r a ll o g i c ) ，是以时刻为时间 单元。显然，以上这三种时间结构可以相互转换，因为任何事件总是在一定的 时间区问中发生，而时间区间又可用其开始和结束的时间点来表示。这三种方 法都是在二十世纪八十年代提出来的，在某种程度上已成为时态逻辑研究的基 本框架。 2 5 不确定性推理 本文主要讨论的是用概率的方法分析时态不确定性问题，所以有必要了解 不确定推理与概率推理的基本知识。 不确定性推理是一种建立在非经典逻辑基础上的基于不确定性知识的推 理，它从不确定性的初始证据出发，通过运用不确定性知识，推出具有一定程 度的不确定性的和合理的或近乎合理的结论。概率推理是不确定性推理的方法 之一，从知识的表示角度看，自从1 9 3 3 年k o n m o p ob 提出概率公理以来，概率 论成为一门严谨的数学分支。在人工智能领域，以概率论为基础的不精确推理 方法得到了广泛的应用。 2 5 1 概率逻辑的概念 不同随机事件发生的可能性的大小是不同的，概率就是人们用来表示随机 事件发生的可能性大小的一个量。 对于概率，一般是从统计学的角度来研究的，我们也可以从逻辑的角度来 研究，用逻辑推理的方法解决因随机性引起的不确定性推理问题。所以，概率 逻辑就是应用数理逻辑或非经典逻辑和概率理论对归纳推理进行形式化研究的 逻辑学。因此，它有许多演绎系统所具有的重要特征。 概率逻辑的提出至今已有多年，并且在许多数学家、逻辑学家与一些学者 的努力下，取得了一定的成果。其产生与发展可以从不同角度来分析，这里从 概率定义和知识表示两个角度来解释。 从概率定义的角度来看，最早的概率是与赌博联系在一起的1 ，数学家对 概率的兴趣是由赌博所引起的，帕斯尔、费尔马、惠更斯都对赌博问题作题 解。第一个给概率下定义的是数学家、天文学家拉普拉斯( l a p l a c e ) ，他将概率 哈尔滨理工大学工学硕上学位论文 定义为尸( 4 ) = m n 。这一定义可以用摸球模型作形象化的解释，因而也可以被 称为古典概型。从此定义出发，许多概率的计算相当困难却又富有技巧，它有 着多方面的应用，产品抽样检验就是其中之一。古典概率的方便之处也恰恰是 它的不足之处，其一它处理的是有限个基本事件，其二它处理的事件都是等可 能的。因此，古典定义适用的范围过于狭小。从古典概率的缺陷出发，开始了 对概率的更进一步的研究。 从知识的表示角度看，自从1 9 3 3 年k o n m o p ob 提出概率公理以来，概率论 成为一门严谨的数学分支。在人工智能领域，以概率论为基础的不精确推理方 法得到了广泛的应用。例如，m y c i n 专家系统中，其确定性因子，就是以概 率论为基础表示的。另一方面，逻辑作为思维的法则，是人类认识世界和改造 世界的准绳，是研究知识表示和推理的基本工具。把概率在推理方面的巨大功 能和逻辑在知识表示方面的优势结合起来，便出现了概率逻辑，即用逻辑的表 示来进行概率推理n ，它集中了概率与逻辑的优点于一身，如图2 2 所示，形 图2 - 2 概率逻辑中概率与逻辑的关系 f i g 2 - 2r e l a t i o n s h i pb e t w e e np r o b a b i l i t ya n dl o g i ci np r o b a b i l i t i cl o g i c 象地表明了在真实世界的应用中概率与逻辑的关系。从这个角度来进行概率逻 辑的研究中，已有许多学者取得一定的成果，例如n i l s s o n ，h a l p e m ，与 s u b r a h m a n i a n ，与p o o l e 等人，为概率逻辑的发展起到了推动作用。 2 5 2 不确定性的算法 1 不确定性的匹配算法推理是一个不断运用知识的过程。为了找到所 需的知识，需要在这一过程中用知识的前提条件与己知证据进行匹配，只有匹 哈尔滨理工人学工学硕上学位论文 配成功的知识才有可能被应用。 在确定性推理中，知识是否匹配成功是很容易确定的。但在不精确推理 中，由于知识和证据都具有不确定性，而且知识所要求的不确定性程度与证据 实际具有的不确定性程度不一定相同，因而就出现了“怎样才算匹配成功”的 问题。对于这个问题，目前常用的解决方法是：设计一个用来计算匹配双方相 似程度的算法，再指定一个相似的限度，用来衡量匹配双方相似程度是否落在 指定的限度内。如果落在指定的限度内，就称它们是可