（计算机系统结构专业论文）时态数据库有效时间不确定性研究.pdf

中山大学硕十学位论文时态数据库有效时问不确定性研究 时态数据库有效时间不确定性研究 计算机系统结构 硕士生：周汉达 指导教师：叶小平副教授 摘要 在永恒发展的现实世界中，时间是信息的一个重要属性，大量数据都要在一 定的时间背景下解释才有意义。随着计算机应用技术的深入和发展，人们对时态 信息处理的需求也越来越迫切，时态数据库正是处理时态数据的重要技术。 在时态数据处理技术的研究过程中，我们发现有效时间不确定性会引起数据 的时态不确定性，这里不确定性的含义有二：其一、仅知时间区间的起始时间点 和终止时间点均取自于某个时间域子集，而具体取值并不确定；其二、时间区间 的终止时间点随当前时间的演进而不断改变，但最终的取值同样不能确定。显然， 传统的数据库技术无力处理这样的数据。通过研究，我们将时态变量n o w 和概 率不确定时态数据模型引入数据库并由此形成一种变量概率数据库技术。实践证 明，采用这种方式可以有效地解决不确定性数据的操作问题。 本文基于时态数据库技术，对上述两类不确定性数据引起的查询结果的不确 定性作了深入的探讨并由此提出相应的处理方法。首先，给出时态变量和概率不 确定性的概念并分析引入两者所产生的问题。然后，借助概率理论对不确定性进 行了定性和定量的研究，在此基础上建立了所谓“n o w 相关一概率不确定时态 数据模型。基于该模型，本文对时态数据查询中最核心的不确定时间点之间的 概率序关系b e f o r e i 操作作了深入的语义分析并提出其实现算法，进而对传统 s q l 中的查询语句s e l e c t 进行了时态扩展。最后，通过一个模拟实验原型系 统的设计和实现证明了本文工作的可行性和价值。 关键词：时态数据库，有效时间，不确定性，概率 中山人学硕一i j 学位论文时态数据库有效时间不确定性研究 s t u d yo fi n d e t e r m i n a t ev a l i dt i m ei n t e m p o r a ld a t a b a s e c o m p u t e ra r c h i t e c t u r e n a m e ：z h o uh a n d a s u p e r v i s o r ：y ex i a o p i n g a s s o c i a t ep r o f e s s o r a bs t r a c t e v e r y t h i n gh a si t st i m ea t t r i b u t e ! i ti su n a v o i d a b l et oo p e r a t et i m ei n f o r m a t i o n w h e nw ed e a lw i t hd a t a t e m p o r a ld a t a b a s e ，a sa na d v a n c e dt e c h n o l o g y , p l a y sa n i m p o r t a n tr o l ei ns u c hf i e l d ! d u r i n go u r r e s e a r c ho nt e m p o r a ld a t a b a s e ，w ef o u n dt h a ti n d e t e r m i n a c yo fv a l i d t i m ea l w a y sc a u s e st h ed a t at ob ei n d e t e r m i n a t e h e r ei n d e t e r m i n a c yc a nb e c o m p r e h e n d e da s2a s p e c t s ：f i r s t ，t h ee x a c tt i m eo ft h e2e n d so fa ni n t e r v a l ( c a l l e d s t a r t i n ga n dt e r m i n a t i n gi n s t a n t s ) i si n d e t e r m i n a t ei fw ej u s tk n o wt h e yc o m ef r o ma c e r t a i ns u b s e to ft i m ed o m a i n s e c o n d ，s i n c et h ee n dp o i n to fa ni n t e r v a lm a yc h a n g e s a st h et i m ee l a p s e s ，a sw e l l ，t h ee x a c tt i m eo fi ti si n d e t e r m i n a t e a p p a r e n t l y , i ti s p o w e r l e s st op r o c e s ss u c hd a t aw i t ht r a d i t i o n a ld a t a b a s et e c h n o l o g y i no u rr e s e a r c h ， w ei n t r o d u c ea ni m p o r t a n tv a r i a b l ec a l l e dn o w , a sw e l la sap r o b a b i l i t y - b a s e d i n d e t e r m i n a t et e m p o r a ld a t am o d e li n t od a t a b a s e i ti sp r o v e dt h a ti nt h i sw a y , w ec a n p r o c e s si n d e t e r m i n a t ed a t ae f f e c t i v e l y i nt h i st h e s i s ，b a s e do nt e m p o r a ld a t a b a s e ，w ew i l lh a v eai n - d e p t hd i s c u s so n t h e2t y p e so fi n d e t e r m i n a t ed a t as t a t e da b o v ea n dh e n c ep r o p o s et h es o l u t i o no ft h e m a tt h eb e g i n n i n g ，t h ec o n c e p to fp r o b a b i l i t y - b a s e di n d e t e r m i n a c yt o g e t h e rw i t ht h e v a r i a b l en o ww i l lb e 酉v e n a n dt h e nw ew i l la n a l y z et h ep r o b l e mt h e yb r i n g a f t e r w a r d s ，r e s o r t i n gt ot h et h e o r yo fp r o b a b i l i t y , w ew i l lh a v eaq u a l i t a t i v ea n d q u a n t i t a t i v e r e s e a r c ho n i n d e t e r m i n a c y am o d e l n a m e d“n o w r e l a t e d m p r o b a b i l i t y - b a s e di n d e t e r m i n a t et e m p o r a ld a t am o d e l w i l lt h e nb eb u i l to i l t h i s a st h em o s ti m p o r t a n tp a r to ft h i sp a p e r , w ew i l le x p a n ds e l e c ts t a t e m e n ti n t r a d i t i o n a ls q la f t e rt h ea n a l y s i so n b e f o r e ，o p e r a t i o n a tl a s t ，as i m u l a t e ds y s t e m w i l lb eg i v e nt ov a l i d a t et h ef e a s i b i l i t ya n dv a l u eo fo u rr e s e a r c h k e yw o r d s ：t e m p o r a ld a t a b a s e ，v a l i dt i m e ，i n d e t e r m i n a c y , p r o b a b i l i t y 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：i 裔弧透y 日期：犷o g 年s 月g 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 导师签名：计_ 平 日期：加p 弓年s 月6 日 中山大学硕上学位论文时态数据库有效时间小确定件研究 第1 章绪论 本章概括地论述了数据库技术研究领域中不确定时态信息的处理，关于有效 时间不确定性的国内外研究背景和应用现状，简要地综述了本文的研究内容、方 法和意义，并介绍了本文的组织结构。 1 1 引言 时间是自然界无所不在的客观属性，所有信息都隐式或显式地具有相应的时 态特征。随着计算机应用技术的深入和发展，人们对时态信息处理的需求也越来 越迫切，时态数据库正是处理时态数据的重要技术【1 1 。 很多数据库应用程序都反映出数据相关的时态特性，例如证券管理、会计和 银行存储等财务应用程序，人事管理、医疗记录和投资管理等应用程序，飞机航 班、火车班车等调度应用程序，数据仓库、数据挖掘、人工智能和决策支持系统 等信息系统，天气监测等科学类应用程序【2 1 。 随着数据库技术的深入发展，信息系统对时态信息处理的需求越来越迫切。 时态信息处理已成为许多新一代数据库与信息系统的关键技术。例如，在工资智 能决策系统中，不仅数据有时态特性，而且知识也有时态特性。一个人员的工资 需要根据他的学历、职务及其获得时间等信息( 时态性数据) ，依据相应时期的工 资政策( 时态性知识) 来确赳l 引。 人们对时态数据库的研究起始于二十世纪八十年代初，迄今已近三十年，有 几百名专家学者参与研究，并已有数千篇相关论文和著作发表，在理论研究和应 用开发方面都取得很大的进展【2 1 。时态数据库中有两个最重要的概念：有效时间 和事务时间。有效时间是指事件或对象在现实世界中为真的时间，反映事物变化 发展本质规律；事务时间是指一个数据对象进入系统的时间，是对数据进行插入、 删除、修改等基本操作的时间，反映系统中“元事件”的时态信息，有助于提高 数据库系统的可靠性和使用效掣4 , 5 1 。 时态数据库中引入有效时间和事务时间的概念，带来了有关时态变量引入和 中山人学硕j ：学位论文时态数据库有效时间不确定性研究 使用的基本问题以及有效时间不确定性的问题。通常，在常规数据之后加上一个 称为时间标签( t i m e s t a m p ) l 拘属性来表示数据成立的有效时间，为了便于表示，时 间标签的形式常为由两个时间点乜和b 作为上下界的时间区间ia , bi 。例如，如果 需要记录d a v i d 自2 0 0 7 年0 6 月0 1 日起在s 大学担任副教授这一事实，当数据 于2 0 0 7 年0 6 月1 0 日写入数据库时，则有效时间标签就是“2 0 0 7 0 6 0 1 2 0 0 7 0 6 1 0 ”。假设数据库系统的时间粒度为“天”，此后只要d a v i d 没有被解聘， 上述时白】标签的终止时间就需要按“天”更新一次。由此会出现以下2 个问题： 1 导致数据库性能低效，每天更新大量数据必然会造成系统承担巨大的丌 销，即使是每周或每月更新一次，对于大型信息系统来说，也要浪费不 必要的资源，从而降低了整个系统的性能，负载过重时可能造成系统崩 溃。 2 造成数据混淆，人们很难分清数据库中哪些元组的有效时间需要每天更 新，哪些元组的有效时间不需要每天更新； 为了解决这些问题，人们引入“变量”来表示这种随当前时间而改变的有效 时间。通常考虑问题都是“截至”到当前时间( c u r r e n t t i m e ) ，人们选择了英语单 词n o w 作为这样的变量【3 ，6 ，8 1 ，其基本含义就是“当前时间”。对于事务时间，人 们选择了u c 作为相应的时态变量。 时态变量n o w 的引入有助于对问题的表示，但也带来了新的问题，这主要 表现在具体数据的操作( 例如查询与更新) 过程中，系统需要根据n o w 的具体语义 确定其的真实取值。由事务时间的定义，时态变量u c 的语义比较简单，只需将u c 绑定为当前时间即可。时态变量n o w 的语义比较复杂，因为在实际应用中除了 可以取“当前时间”语义之外，由于数据库系统机制和具体应用需要，时态变量 d w 还可能表示“过去”时间或“将来”时间的语义【9 , 1 0 l ，其取值绑定比较复杂， 由此产生了不少研究课题。 在时态数据库中，有效时间可能不随当前时间而改变，但它的起始时间点与 终止时间点可能在一个集合中取值，然而取集合中的哪个元素却是未知的 1 1 1 , 1 2 , 1 3 , 1 4 , 1 5 】。例如，古埃及法老t u t a n k h a m e n 的统治时间是不确定的，有入说是 1 3 4 7 b c 一1 3 3 9 b c ，有人则认为是1 3 3 4 b c 一1 3 2 5 b c ，还有人说是1 3 3 6 b c - - 2 中山人学硕十学位论文时态数据库自效时问4 i 确定性研究 1 3 2 7 b c 。所以t u t a n k h a m e n 统治的有效时间区间的起始时间点在1 3 4 7 b c - - 一 1 3 3 4 b c 之间取值，终止时间点在1 3 3 9 b c 1 3 2 5 b c 之间取值1 1 3 】。这种有效时间 不确定的数据会带来查询结果的不确定性，如何表示、处理和控制有效时间的不 确定性是时态数据库中重要的研究课题。 1 2 国内外研究现状 1 2 1 时态数据库技术 文献【1 ，2 ，1 6 ，1 7 ，1 8 ，1 9 1 论述了时态数据库技术近3 0 年来的发展状况，概括地 说，上个世纪八十年代初时态数据库技术产生以来，经过大量学者的研究与实践， 时态数据库技术在基础理论、数据模型、数据库语言、应用技术等方面都取得了 巨大的成果，时态信息技术目前仍处于不断研究和发展阶段。现有的时态数据库 研究现状及不足可以归纳如下： 1 时态数据模型一般都是传统关系数据模型的扩展，与传统的关系数据模 型有较好的兼容性。已提出了二十多种数据模型，每一种时态数据模型 都有各自的优点和不足，还没有形成较完整的国际标准。对时间的描述 主要是依照j b e nz v i 提出的时间点与时间区间模型、有效时间、事务 时间以及双时态等概念；时态数据关系演算主要是基于j e a l l e n 提出的 1 3 种时间区间演算，仍没有系统、有力的数学理论支持，时态数据运算 体系不够完备。 2 对时态数据查询语言的扩展基于传统的s q l ，目前人们基于各自的数据 模型已定义了四十多种时态查询语言，时态数据查询功能有限，效率较 低。最近提出一个称为t s q l 2 的时态查询语言，很多第一代时态查询语 言的设计者将它作为第二代的时态查询语言来发展。然而，目前对时态 数据查询语言中很多重要研究课题，如时态谓词演算、时态关系表和视 图修改、整体性约束等，都是分开研究的，没有综合地考虑它们之间的 关系和影响，所以目前还没有一个通用的时态查询语言。 3 在实际应用方面，由于数据库技术的迅速发展，尤其是网络与多媒体技 术的发展，时态信息的应用得到了很大的发展。在地理信息系统、农业 3 中山大学硕上学位论文时态数据库有效时问1 i 确定性研究 信息系统，电信信息系统，电子商务，智能决策支持系统，数据仓库与 数据挖掘，特别是时空信息技术和多媒体信息系统方面，时态信息处理 技术得到空前的重视和应用1 1j 。由于没有成熟的时态数据模型和时态查 询语言，大部分与时态相关的应用，在具体实现中仍然采用传统的关系 数据库技术，对应时态操作的解释由应用程序而非数据库系统来处理。 文献 2 0 ，2 1 研究了基于时间点和基于时间区间的时态数据模型以及两者之 间的区别，文献【2 2 】试图用一种统一的数据模型来描述时态信息，而文献【2 】指出 任何一种时念数据模型要满足所有的要求是不可能的，现有的各种时态数据模型 在用途上都各有侧重并介绍了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 j 咖a ld a t am o d e l ，r d m ) 。其中b c d m 的时间标 签空间复杂度很大，直接用b c d m 形式存储时态数据不可行。表示数据模型可 以节省存储空间，却使得数据的表示具有很大的随意性，不利于处理多变且运算 操作复杂的时态数据。 1 2 2 不确定时态信息处理 在时态数据库中，有效时间可能是不确定的，在文献1 1 1 中s n o d g r a s s 指出 了有效时间的不确定性主要表现为有效时间区间的端点为集合的情况，分析了有 效时间不确定性产生的原因主要在于时间粒度不匹配、年代测定技术、不确定计 划、未知或不精确的事件时问和计时器本身的误差等等，有效时间不确定性的处 理是时态数据库技术研究领域中的一个基本课题。 文献【6 ，8 ，9 ，1 0 ，2 3 1 对时态变量n o w 进行了深入的研究，讨论了在时态数据中 引入变量的必要性，分析了时态变量n o w 带来问题以及n o w 的“过去 、“现在”、 “将来”不确定语义，并给出了相应的绑定算子。 对不确定时间区间，a l l e n i 2 4 l 提出了时间区间的1 3 种关系，国内学者张师超 2 5 1 对间断区间提出的2 0 种关系可看作是其的推广。在文献 1 1 d p ，s n o d g r a s s 针 对有效时间不确定性，扩展了传统的关系数据模型和s q l 查询语言以支持这种 不确定性，并在此框架内，深入地探讨了不确定有效时间的语义问题。 4 中山大学硕上学位论文时态数据库有效时间不确定性研究 为了定量的刻画这种有效时间的不确定性，文献【7 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，2 6 给出了 基于概率的不确定时间点模型。文献【1 1 】并用其作为端点来定义时间区间，分析 了不确定语义，研究了有效时间不确定性的度量，最后给出了一个比较高效的实 现算法。文献【7 】研究了时态概率关系的语法和多种时态概率代数。文献【1 4 】对有 效时间不确定性表现为有效时间区问的端点为集合值的情况进行了相关扩展，深 入地分析了不确定时间区间的表示方法和它们之间相互关系。 文献【2 3 】则对由时间粒度不匹配和时间信息不完备性所产生的有效时间的 归并( c o a l e s c e ) i 司题进行了详细研究，由于在时态数据库中进行插入和投影等操 作，都需要进行时态归并运算，作者提出的对于不确定时问区间的归并算法和相 应的关系代数运算对于本文的基于有效时间的不确定时态信息查询操作的算法 设计与实现具有重大的启发。 对于数据的不确定时态推理，国内学者王家廒1 1 5 j 提出了一个具有不确定性的 时态模型，彭宏f 1 2 】则提出了一个统一的时态模型，不仅可以定性和定量地表示时 态信息，还能用于描述不确定时态信息。 1 3 本文的研究思路和意义 在前面对时态数据库技术和不确定时态信息处理的有关研究和应用的分析 基础上，本节对论文的主要工作进行概述，包括论文的主要目标、研究思路和意 义等等。 1 3 1 问题的提出 由前文的论述可知，不确定时态信息的研究主要针对有效时间。有效时间不 确定性主要有两类：一类是与当前时间不相关的不确定性，主要是原始数据的时 间信息本身是不精确或不完全的信息；另一类是与当前时间相关的不确定性，这 一类不确定信息不仅是因为原始数据的时间信息本身是不精确或不完全的信息， 还与人们计划的不确定性有关，是系统运行机制和实际应用需求造成的数据不确 定性。 在时态数据库中，这两类有效时间不确定性都有很广泛的应用背景。第一类 中山人学硕e 学位论文时态数据库自效时问不确定性研究 对时间粒度不匹配和事件的发生时间有争议的领域特别适合，例如前面所述，古 埃及法老t u t a n k h a m e n 的统治时间是不确定的，其有效时间区间的起始时间点在 1 3 4 7 b c 1 3 3 4 b c 之间取值，终止时间点在1 3 3 9 b c 1 3 2 5 b c 之间取值1 1 3 j 。第 二类适用于有效时间区间终点随着当前时间不断增长的数据，但不能事先确定这 种终止时问点的增长在何时结束。例如，一个试验性科研项目从2 0 0 4 年6 月起 开始实施，但什么时候终止不明确。人们发现，处理这种情况下的时态信息最有 效的方法就是引入时态变量n o w 来表示有效时间区间的终止时间点【6 , 8 , 1 0 】。 这两种有效时间不确定性已有不少学者作过研究，取得了一定成果。如何统 一地处理这两类有效时间不确定性带来了新的难题，这主要体现在具体数据模型 的表示，时态变量n o w 带来的问题与复杂语义，数据之间不确定性度量与控制， 时态查询语言的语义，与传统s q l 的兼容性等方面。 1 3 2 本文的主要目标和意义 按照上述考虑，本文主要研究时态数据库有效时间不确定性的表示和时态查 询结果不确定性的度量与控制，据到目前为止掌握的资料来看，这种有效时间不 确定性的研究工作还比较少。 本文的具体工作主要表现为： 1 讨论了引入时态变量的应用背景，深刻地分析引入时态变量n o w 所带来 的问题和复杂语义，并研究了相关问题的解决方案。还研究了概率不确 定数据模型的基本概念和相关理论，最后结合n o w 相关不确定时态数据 模型和概率不确定时态数据模型提出了一种新的数据模型d w 相 关一概率不确定时态数据模型； 2 在n o w 相关一概率不确定时态数据模型的基础上，对s q l 查询语句 s e l e c t 进行时态扩展，提出两个重要的概念：关联可信度和预定似真 性，并分析了时态查询语句的指称语义和操作语义。 3 针对有效时间的不确定性，给出了相应的时态变量n o w 的绑定算法，改 进了时态谓词演算中核心操作晓归，巳操作的实现算法。 4 通过扩展s q l 查询语句，设计和完成了一个模拟实验系统，在关系数据 6 中山大学硕j ：学位论文时态数据库有效时间升i 确定性研究 库平台上实现了本文的研究成果，证明了本文工作的合理性与可行性。 有效时间不确定性是时态数据库中数据处理技术的一个必须解决的基本课 题，而目前，将概率与时态变量n o w 相结合的处理方法研究较少，而本文提出 数据模型和时态变量n o w 的绑定算法以及时态查询操作的实现算法对于进一步 的研究工作具有普遍的指导意义。 1 4 本文的组织结构 本文共由六个章节组成，具体如下： 第1 章概要地论述了在数据库研究与技术领域中不确定信息的处理，关于有 效时间不确定性的国内外研究背景和应用现状，简要综述了论文的研究内容，方 法和意义，同时介绍了本文的组织结构。 第2 章介绍了论文所涉及到的一些时态数据库的最基本的理论，以期读者对 时态知识有个基本的了解。 第3 章分析了概率不确定时态数据模型与n o w 相关不确定时态数据模型， 将两者结合并提出新的数据模型d w 相关一概率不确定时态数据模型； 第4 章对s q l 中的查询语句s e l e c t 进行时态扩展，分析语义，讨论其与 经典s q l 语言的兼容性，对时态连接操作和时态选择操作给出操作语义，并改 进其中最核心的操作b 咖厂白操作的实现算法。 第5 章通过时态查询的仿真实验，证明了n o w 相关一概率不确定时态数据 模型在描述有效时间不确定信息时具有其自身的优越性和兼容性，同时也证明了 本文所提出的理论的合理性和可行性。 第6 章主要是总结了所做的工作和指明进一步努力的方向。 7 中山人学硕上学位论文时态数据库有效时间小确定性研究 第2 章时态数据库基本概念 时态数据库是记录和管理时态信息的数据库技术，是在传统关系数据库的基 础上添加时态信息的处理发展而成的。时态数据库有丰富的理论知识，本章只是 介绍关于时态数据库技术已有的一些基本理论和概念。 2 1 时间的概念 时间有一个标准的几何表示轴线，有连续的表示方式和离散的表示方 式，鉴于在计算机科学上的应用，我们选择离散的表示方式。 2 1 1 时间粒度 时间粒度( g r a n u l a r i t y ) 是指描述应用系统中时间的最小单位，表示时间点之 间的离散程度。表示时间粒度的单位有很多，常用的有年、月、日、时、分、秒 等。时间粒度越小，离散的时间点越多，描述对象的时态信息越精确，反之，描 述的对象时态信息越粗糙。具体应用系统中时间粒度由应用需求和系统负载能力 来决定，不同的时间粒度可以相互转换【2 3 ，2 刀。与时间粒度相关的一个重要的概念 是时间元，时间元( c h r o n o n ) 是系统实现时所能表示的最小时间单位，例如目前 大部分计算系统的时间元是毫秒。 2 1 2 时间元素 时间元素( t i m ee l e m e n t s ) 是指表示时间标签的元素，主要有三种基本的表现 形式： 1 时间点( t i m ei n s t a n o 时问点是时间轴上的一点，与时间粒度相关。适当的时间粒度既能够准确地 反映对象发展变化的状况又能节省系统开销。例如，时间点“2 0 0 7 年6 月1 日 ， 其时间粒度为“天”；如果系统的时间粒度为“秒 ，则该时间点表示为“2 0 0 7 年6 月1 日0 时0 分0 秒” 1 1 , 2 1 】。 中山人学硕一l 二学位论文时态数据库自效时间f i 确定性研究 2 时间区间( t i m ei n t e r v a l ) 时间区间是带有起始时间点与终止时间点的一段时间，通常起始时间点记为 v t s ，终止时间点记为v t e ，例如2 0 0 5 年至2 0 0 7 年。时间的区间的表示方法根 据两端时间点是否封闭分为4 种，如图2 1 所示【1 , 2 4 , 2 8 】。 在这四种区间的表达方式中，一般采用前端封闭，尾端开放的形式，主要考 虑的是时间区间兼容时间点的表示方式和时间区间的比较谓词的缘故，事实上， 它与前端开放尾端封闭的时间区问的表达方式在表达能力上是等价的。 四种区间区间含义图例 1 ) 1 j ，i i js ts i ， 一一 2 ) 卧i ，) i fs t i ， 一一o 3 ) ( i f ，i 】 i f tsi o 一 4 ) ( i f ，i ，)i f ，其中s e d ru u o w ， e e 珥u n o w ，且有ss e ，当s = e 时，就为一个确定时间点。不确定时间点，是 在s 和e 之间取值，但具体取哪个值不确定。 我们现以不确定时态数据模型为基础，对n o w 相关时态数据模型进行扩展， 得到一个优于上述两种模型的数据模型，称其为n o w 相关不确定时态数据模型， 定义在形式上仍与上面的定义一样： t ；( 置，x 2 ，x 。，v t s ，v t e ) 其中，x i ( 1 s is 咒) 为非时态属性，l e t s 属性为元组丁有效时间区间的起始 时间点，v t e 属性为元组r 有效时间区间的终止时间点，并且有 l e t s 岛，i t e e 珥u n o w ) u l f = a s ，e e 珥u n o w ，其中，珥为时间 域，料为不确定时间点集合，n o w 为时态变量。 例3 3 用n o w 相关不确定时态数据模型表示的s 大学中d a v i d 元组信息如 图3 2 所示，假设该大学有强制的退休制度，不妨设d a v i d 的退休时间最迟为 2 0 2 8 0 1 0 1 。 v f l i dt i m e n a m e r a n k v t se 图3 2d a v i d 信息 假设今天是2 0 0 7 0 7 0 9 ，d a v i d 仍被聘用，且数据库中更新操作的最大延迟 为三天，则d a v i d 在数据库中的元组如图3 2 ( a ) 所示。d a v i d 在2 0 0 7 0 7 1 0 的信 1 9 中山大学硕十学位论文 时态数据库有效时问小确定性研究 息如图3 2 ( b ) 所示。 用n o w 相关不确定时态数据模型表示当前d a v i d 的信息如图3 - 2 ( c ) 所示。注 意v t e 属性所表示的终止时间点不确定性已经减少到很微小了，在2 0 0 7 0 7 1 0 这 一天查询，d a v i d 在2 0 0 7 0 7 0 7 是被聘用的，在2 0 0 7 0 7 0 7 与2 0 2 8 0 1 0 1 之间有 可能被聘用。 在图3 2 中，我们可以肯定d a v i d 从2 0 0 7 0 6 0 1 丌始是一名副教授，但不再 是副教授的时间是不确定的，我们所能确定的是直到三天前，他一定是名副教授， 并且一直到2 0 2 8 0 1 0 1 退休有可能仍是副教授。v t e 时间标签使我们能够准确地 抓住这一点，n o w 相关不确定时态数据模型不需要连续不断的更新操作，但却 能准确地描述d a v i d 什么时候被s 大学聘用。 n o w 相关不确定性数据模型提供了一个能够准确描述不确定的、与当前时 间相关事件有效时问的信息的且非常灵活的方法，能够很好地解决时态变量 n o w 带来的问题。n o w 相关不确定时态数据模型中的终止时间点通常由可变的 下界和一个基本上界组成，下界不超过时间点的上界，所以上界经常表示时间点 中可能或不确定信息的极限。查询n o w 相关不确时态数据模型表示的数据，可 能得到不确定的结果，也可能得确定的结果，主要依赖于我们考察数据库的参考 时间r t 与当前时间c t 。 例3 3 中，d a v i d 聘用元组表示的可能或确定信息不能超过2 0 2 8 0 1 0 1 ，尽管 今天是2 0 2 8 0 1 0 1 之后的某一天。如果今天是2 0 0 7 0 5 0 6 ，则下界是2 0 0 7 0 5 0 6 ， 元组表示d a v i d ( 可能) 从2 0 0 7 0 6 0 1 到2 0 2 8 0 1 0 1 之间被聘用。如果今天是 2 0 5 0 0 1 0 1 ，则上界是2 0 2 8 0 1 0 1 ，元组表明d a v i d 从2 0 0 7 0 6 0 1 到2 0 2 8 0 1 0 1 真的被聘用。简言之，n o w 相关不确定数据模型符合了预更新的语义。n o w 相 关不确定数据模型还可以描述时态数据库进化的特征，元组的不确定值随着当前 时间的推移逐渐进化为确定值。 3 2 概率不确定时态数据模型 3 2 1 不确定时间点 一个时间点( i n s t a n t ) 是确定的如果它定位在某一特定的时间元( c h r o n o n ) c 中山人学硕。i ：学位论文时态数据库有效时间不确定性研究 上，记为a = c ，其中，c e d ，珥为时间域，例如2 0 0 7 - 1 2 2 0 。 如果一个时间点定位于一个由多个时间元组成的集合上，称这个时间点为不 确定时间点，仍用符号a 表示。 一个不确定时间点口由下界( l o w e rs u p p o a ) ，记为口，上界( u p p e rs u p p o r t ) ， 记为口，和一个概率分布函数( p r o b a b i l i t ym a s sf u n c t i o n ) 只表示。 上下界约束了不确定时间点在时间轴上的取值范围，即不确定时间点不早于 它的下界，不晚于它的上界。在上下界之间存在一个称为不确定性间隔的时间段， 它是由连续时间元组成的集合，不确定时间点就定位在这个集合中某个的时间元 上，但具体哪一个时间元是未知的，我们记这个集合为口口。 尽管不确定时间点在一个时间元集合中取值，但不是所有的时间元都是等可 能的。例如，一个不确定时间点更有可能定位在不确定性间隔中的最后面的时间 元上。概率分布函数给出了每一个时间元的概率。对不确定时间点a ，对应的概 率分布函数只为 己( f ) = p r a = f 】i e 0 ，1 ，) 其中，p r a = f 】是不确定时间点a 定位于时间元f 的概率。显然，有 p r i 口】= 0 。假设所有的不确定时间点都是相互独立的，则有 p r a = ia 卢= j 】= p r a i 】p r f l = j 】 所以不确定时间点可以记为口= 口，) ，其中，a 珥，口。d r ，只 为口与a 之间元素的概率分布。 例3 4 【2 0 0 0 - 0 8 - 0 1 2 0 0 0 一0 9 3 1 ，踟和册】，其中，洗咖删为等概率分布 函数，表示时间点的取值在闭区域1 2 0 0 0 - 0 8 一o l , 2 0 0 0 一0 9 3 1 】中是等概率的。 不确定时间点实际上是对确定时间点的扩展，如果不确定时间点的下界a 和上界口相等，则该不确定时间点退化为确定时间点，且有口= 仉一口，概率 分布函数只不起作用，可将足定义为常量函数且只= 1 。 2 1 中山人学硕i - 学位论文时态数据库有效时问不确定性研究 3 2 2 不确定时间区间( i n d e t e r m i n a t ei n t e r v a l ) 一个确定的时间区间( d e t e r m i n a t ei n t e r v a l ) 是两个确定时间点之间的时间延 续，记为，= 【l t s ，v t e 】，其中v t s 为，起始时间点，v t e 为，的终止时间点，且v t s 与m 均为确定时间点，如【2 0 0 7 一1 0 1 ，2 0 0 7 1 0 3 1 1 。 一个时间区间两端的时间点是不确定时间点，称这个时间区间是不确定时间 区间( i n d e t e r m i n a t ei n t e r v a l ) ，仍记为，- 【v t s ，m 】，其中v t s 为，的起始时间点， v t e 为，的终止时f b j 点，且v t s 与v t e 均为不确定时间点。一个不确定时间区间 可以起始于它开始的不确定时间点v t s 中的某一个的时间元；结束于它终止的不 确定时间点v t e 中的某一个时i 白j 元。 3 2 3 不确定时间间隔( i n d e t e r m i n a t es p a n ) 一个确定时间间隔是一个被精确认知的时间的持续，如1 0 天。一个不确定 时间间隔是一个不精确的时间持续，表现为不精确的时间元个数，如“从两到三 个时间元”。 3 2 4 概率不确定时态数据模型 t = ( x 1 ，x 2 ，邑，砰) 其中，置( 1 s is 甩) 是关系r 中与时问无关的属性，砰为元组丁的有效时间 的时间区间，且冲= 【v t s ，v t e 】，v t s = ( s ，s ，只) ，v t e = ( e ，e ，) 3 3n o w 相关一概率不确定数据模型 如前面所述，n o w 相关不确定时态数据模型的优点是能准确地描述不确定 的、与当前时间相关的对象有效时间的信息，而且非常灵活，不需要做连续不断 的更新操作。而概率不确定时态数据模型的优点是能够用概率来衡量对象的有效 时间不确定信息，给数据库考察者更详细的信息，帮助其做出相应的决策。 我们将n o w 相关不确定时态数据模型与概率不确定时态数据模型相结合， 得到一个新的时态数据模型，称之为n o w 相关一概率不确定时态数据模型，其形 中山人学硕上| 学位论文时态数据库有效时间不确定性研究 式如下： t = ( 置，x 2 ，x 。，孙俨) 其中，刀7 r p = 【v l s ，m 陀】，j 面v t s = o 8 7 e ) 和y 死= ( p p ，) 中ms ， s ，巳，e d rt o n o w ，d r 为时间域，n o w 为时态变量。 因为，又，s ，己，e 的值可以取时态变量n o w ，则对应的不确定时间点v t s ， v t e 可能随当前时间改变而改变。 例3 4 设不确定时间点石= ( n o w 2 0 0 8 1 2 3 1 ，) ，当当前时间c t 为 2 0 0 8 一0 1 3 1 时，即c t = 2 0 0 8 一0 1 3 1 ，贝0 有 x = ( 2 0 0 8 0 1 3 1 2 0 0 8 1 2 3 1 ，只) 当当前时间c t 为2 0 0 8 0 6 3 0 时，即c t = 2 0 0 8 0 6 3 0 则 x = ( 2 0 0 8 0 6 3 0 2 0 0 8 1 2 3 1 ，) 这样，对应的概率分布函数也是不确定的，因此，我们作如下约定： 1 对不确定时间点a ； 一a ，e o ) ，若口的下界口。和上界口中有一个为 时态变量n o w ，则对应的概率分布函数为等概率分布函数，即 v q ，口sq s a + ，有 p r i = 口，】= _ 一，其中，时态变量n o w 与当前时间 口一o t c t 绑定。 2 当不确定时间点口= ( 0 1 一口+ ，只) 中的下界口和上界口都为时态变量 n o w 时，口与口，都绑定为当前时间c t ，对应的概率分布函数为常量函数且 己= 1 。 中山人学硕士学位论文 时态数据库有效时间小确定性研究 第4 章不确定时态信息的查询 本章根据n o w 相关一概率不确定时态数据模型的框架下，对传统s q l 中的 查询语句s e l e c t 进行时态扩展，分析了对应的时态语义，针对其中出现的一 些基本问题和技术难点提出相应的解决方案，还举例说明了时态查询操作的过 程。最后对时态谓词演算核心操作b 咖，巳算法进行改进。 4 1 查询语句的语法时态扩展 将有效时间不确定性扩展到s q l 中的查询语句s e l e c t 要尽可能地满足： ( 1 ) 所作的语法扩展较小，但应具有较强的表达能力；( 2 ) 所作的扩展是向上兼容 的，即在有效时间确定的情况下，所扩展的查询语句退化为传统s q l 中的查询 语句；( 3 ) 语义应是较简单直接的；( 4 ) 有效时间不确定性对现有的d b m s 的影响 应该很小。 如果查询语句能够利用n o w 相关一概率不确定数据模型中的时间元概率分 布函数，可以对不确定性进行度量和控制从而得到更好的查询结果。下面我们在 w 相关一概率不确定时态数据模型中引入两个概念，可以使用户在查询时态 数据库时对有效时间不确定信息进行控制。 4 1 1 关联可信度( c o r r e l a t i o nc r e d i b i l i t y ) 关联可信度仃是一个整数，且c r e 1 ，1 0 0 】，默认情况下仃= 1 0 0 。关联可信度 实质上是通过用某种过滤( 或筛选) 策略来决定元组有效时间不确定时间点中的 哪些时间元参与时态谓词演算。一个典型的过滤策略是根据时间元的概率大小来 决定该时间元是否参与时态谓词演算，在带有不确定性的时态查询中，可以将 w i t hc r e d i b i l i t y 字段加到f r o m 子句后面来设置关联可信度值。 4 1 2 预定似真性( o r d e r i n gp l a u s i b i l i t y ) 因为在n o w 相关一概率不确定数据模型中，两个时间点之间的先后关系是建 中山大学硕十学位论文时态数据