（计算机软件与理论专业论文）时态数据库数据依赖理论研究.pdf

哈尔滨理工大学工学硕士学位论文 时态数据库数据依赖理论研究 摘要 一个好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异 常。对于时态数据库也是如此。论文提出了时态初等函数依赖、时态初等关 键字、时态初等主属性、时态简单关键字、时态简单主属性等概念，在此基 础上利用具有多时间粒度的时态函数依赖( t f e 、约束对时态数据库进行了规 范化研究，提出了规范程度高于时态三范式低子时态b o y c e c o d e 范式的时 态初等关键字范式( t e k n f ) 及时态简单范式( t s n f ) ，并研究了时态初等关 键字范式和时态简单范式的分解问题，给出了相关分解算法，并对算法的可 终止性、正确性进行了证明，对时间复杂度进行了分析。 根据关系数据库规范化的过程，基于时态函数依赖和关系数据库多值依 赖理论提出了多时间粒度约束的时态多值依赖( t m v d ) 等概念，并给出了时 态多值依赖的推导规则，对其有效性、完备性进行了证明。由于包含有限个 t m v d 的t m v d 集通常蕴含着无限个t m v d ，给出了t m v d 的有限推导 规则，对其有效性、完备性进行了证明。 对于具有t f d 和t m v d 混合集约束的时态模式来说，由于多时间粒度 的使用使成员籍问题的解决变得更加复杂。但成员籍问题的解决对设计有效 的模式分解算法必不可少，由此论文定义了时态类型集的强封闭集、属性集 的有限闭包、属性集在给定时态类型上的有限依赖基、属性集的有限依赖基 及特殊有限依赖基等概念，给出了求属性集的有限闭包、有限依赖基和特殊 有限依赖基的算法，对算法的可终止性、正确性进行了证明，并对时间复杂 度进行了分析。在此基础上，给出了解决时态混合集成员籍问题的算法，并 对算法的可终止性、正确性进行了证明，对时间复杂度进行了分析。 最后，基于t f d 和t m v d 混合集提出了时态第四范式( t 4 n f ) ，并给 出了时态模式的t 4 n f 的无损分解算法，对算法的可终止性、正确性进行了 证明，对时间复杂度进行了分析。 关键词时态数据库；时态初等关键字范式；时态简单范式；时态多值依 赖；时态第四范式 堕查堡堡三查兰三茎璺圭兰堡耋兰 s t u d yo nd a t ad e p e n d e n c yt h e o r yd q t e m p o r a ld a t a b a s e a b s t r a c t t h ep u r p o s eo fag o o dd a t a b a s el o g i c a ld e s i g ni st oe l i m i n a t ed a t a r e d u n d a n c ya n di n s e r t i o n ，d e l e t i o na n du p d a t ea n o m a l i e s t e m p o r a ld a t a b a s ei s t h es a m ec a s e i nt h i sp a p e r ，t h en o t i o n so ft e m p o r a le l e m e n t a r yf u n c t i o n a l d e p e n d e n c y ，t e m p o r a le l e m e n t a r yk e y , t e m p o r a le l e m e n t a r ym a i na t t r i b u t e ， t e m p o r a ls i m p l ek e ya n dt e m p o r a ls i m p l em a i na t t r i b u t ea r ei n t r o d u c e d o ni t s b a s e ，t h en o r m a l i z a t i o no ft e m p o r a ld a t a b a s ei ss t u d i e db yu s i n gc o n s t r a i n t so f t e m p o r a lf u n c t i o n a ld e p e n d e n c y ( t f d ) w i t hm u l t i p l e t i m eg r a n u l a r i t i e s ；t h e c o n c e p to ft e m p o r a le l e m e n t a r yk e yn o r m a lf o r m ( t e k n f ) a n dt e m p o r a ls i m p l e n o r m a lf o r m ( t s n f ) i si n t r o d u c e d ；t h ep r o o ft h a tt h en o r m a l i z a t i o nd e g r e eo f b o t hn o r m a lf o r mi sb e t w e e nt 3 n fa n dt b c n fa n dt h en o r m a l i z a t i o nd e g r e eo f t e k n fi sl o w e rt h a nt h a to ft s n fa r eg i v e n d e c o m p o s i t i o na l g o r i t h m st h a t g i v el o s s l e s s ，d e p e n d e n c y _ p r e s e r v i n g ，t e k n fd e c o m p o s i t i o n sa n dl o s s l e s s ， d e p e n d e n c y _ p r e s e r v i n g ，t s n fd e c o m p o s i t i o n sa n dt h ep r o o ff o ri t st e r m i n a t i o n a n dc o r r e c t i o n & r eg i v e n o nt h eb a s eo ft h ep r o c e s so fn o r m a l i z a t i o no fr e l a t i o n a ld a t a b a s e ，t h e c o n c e p t so ft e m p o r a l m u l t i v a l u e dd e p e n d e n c y ( t m v d ) w i t hm u l t i p l et i m e g r a n u l a r i t i e sb a s e do nt e m p o r a lf u n c t i o n a ld e p e n d e n c y a n dt h et h e o r yo f m u l t i v a l u e dd e p e n d e n c yo fr e l a t i o n a ld a t a b a s e & r ei n t r o d u c e d a na x i o m a t i z a t i o n f o rt m v di sg i v e n b e c a u s eaf i n i t es e to ft m v d su s u a l l yi m p l i e sa ni n f i n i t e n u m b e ro ft m v d s ，w ei n t r o d u c et h en o t i o no fa n dg i v ea na x i o m a t i o nf o ra f i n i t ec l o s u r et o e f f e c t i v e l yc a p t u r eaf i n i t e s e to fi m p l i e dt m v d st h a t & r e e s s e n t i a lt ot h el o g i c a ld e s i g n f o rt e m p o r a ls c h e m ew i t ht e m p o r a lf u n c t i o n a ld e p e n d e n c i e sa n dt e m p o r a l m u l t i v a l u e dd e p e n d e n c i e sc o n s t r a i n s ，t h eu s a g e so fm u l t i p l et i m eg r a n u l a r i t i e s m a k ei tm o r ed i f f i c u l tt os o l v em e m b e r s h i pp r o b l e m h o w e v e r , t h es o l v eo f m e m b e r s h i pp r o b l e mi se s s e n t i a lt od e s i g na na v a i l a b l ea l g o r i t h mo fs c h e m e i i 堕玺堡塞三查兰三兰霎圭兰堡鎏兰 - d e c o m p o s i t i o n ，t h u si nt h i sp a p e r , s t r o n gc l o s es e to fs e to ft e m p o r a lt y p e s ，f i n i t e c l o s u r eo fa t t r i b u t i o ns e t s ，f i n i t ed e p e n d e n c yb a s eo fa t t r i b u t i o ns e t sb a s e do na c e r t a i nt e m p o r a lt y p e ，f i n i t ed e p e n d e n c yb a s eo fa t t r i b u t i o ns e t sa n ds p e c i a l f i n i t ed e p e n d e n c yb a s eo fa t t r i b u t i o ns e t sa r ei n t r o d u c e d ；t h ea l g o r i t h mo ff i n i t e c l o s u r e ，f i n i t ed e p e n d e n c yb a s eo fa t t r i b u t i o ns e t sa n ds p e c i a lf i n i t ed e p e n d e n c y b a s eo fa t t r i b u t i o ns e t s ，a n dt h ep r o o ff o ri t st e r m i n a t i o na n dc o r r e c t i o ni sg i v e n o ni t sb a s e ，t h ea l g o r i t h mo fm e m b e r s h i pp r o b l e ma n dt h ep r o o ff o r i t s t e r m i n a t i o na n dc o r r e c t i o ni sg i v e n f i n a l l y , t e m p o r a lf o r t hn o r m a lf o r l i lw i t hr e s p e c tt ot f d sa n dt m v d s i s g i v e n ，d e c o m p o s i t i o na l g o r i t h mw h i c hi st e r m i n a la n dc o r r e c t i sp r e s e n t e dt h a t g i v el o s s l e s st 4 n fd e c o m p o s i t i o n s k e y w o r d st e m p o r a ld a t a b a s e ；t e m p o r a le l e m e n t a r yk e yn o r m a lf o r m ；t e m p o r a l s i m p l en o r m a lf o r m ；t e m p o r a l m u l t i v a l u e dd e p e n d e n c y ；t e m p o r a l f o r t hn o r m a lf o r m - i i i 哈尔滨理工大学工学硕士学位论文 第1 章绪论 1 1 时态数据库产生的背景及特性 1 1 1 时态数据库产生的背景 出于现实世界是不断演变进化的，时闻是那些反映现实世界信息的基本组 成部分，因而大多数数据库应用程序都有时态的特性，例如：会计，银行等财 经类的应用程序，人事、培训、酒店预订、项目管理等记录性应用程序，天气 监测等科学类应用程序。传统的数据库管理系统对时态信息的存储、处理和操 作都十分有限，正因为传统数据库缺乏对时态数据的支持，因而在很多方面产 生了很多问题，例如：它把时间数据作为一个字段的值进行存储和管理，只反 映了对象某一个时刻或当前时刻的信息和状态，不联系对象的历史、现在和将 来，无法将对象的历史、现在和将来作为对象的一个发展过程来看待，而这样 做有助于解释事物发展的本质规律，抓住事物的发展趋势( 这一点对于决策支 持系统这类的应用程序来说是很基本、很重要的) ；同时要求管理数据库系统 中元事件的时态信息，例如数据库被查询修改的时刻，时间区间。多用户系统 中对锁定排队以及资源竞争协调的时标等。这些时态数据也有助于提高数据库 系统的可靠性和效率。随着数据库技术的不断发展，人们开始逐渐意识到必需 为时态数据建立时态数据库的模型，或者在现有的数据库模型上加以改造，于 是提出了时态数据库的概念。 目前，对时态数据库已进行了大量的研究。at a n s e l 收集了当前时态数 据库几乎所有的重要成果【1 】。唐常杰对时态数据库技术前2 0 年的发展做出了系 统回顾【2 】吼汤庸介绍了几种具有代表性的时态数据模型【4 ) 【5 】。 1 ，1 2 时态数据库的特性 所谓时态数据库，指能够处理时间信息的数据库。传统数据库只记录了数 据的当前状态，在现实情况改变时，数据库也发生变化。而时态数据库不仅存 放对象的现状，而且存放对象过去的一切状态，并且可以根据对象现在和过去 的状态推测其未来可能的状态。 时态数据库技术已成为一个诱人且活跃的研究领域。时态数据库有下列几 哈尔滨理工大学工学硕士学位论文 个方蕊的特性： 1 动态性：传统的数据库系统对数据进行静态或准动态的数据库管理。在 数据更新时，过时的数据将从数据库中删除，这就不能反映出现实世界的动态 过程，例如，李明的专业技术职务是：1 9 9 1 5 至1 9 9 4 3 为助教，1 9 9 4 4 至 2 0 0 1 6 为讲师，2 0 0 1 7 至今为副教授。在时态数据库中，过时的数据不再从数 据库中删除，对历史数据也可以进行更新，使系统和现实世界直保持着全方 位的动态交换。 2 全面性：由于时态数据库是所有数据的集合体，可以提供任何时刻和时 问段的数据，这是传统数据库无法比拟的。时态数据库为历史、当前和将来进 行对比、分析、监测和预测预报提供了丰富的数据，从而为预测预报系统、决 策支持系统和其他分析系统服务。 1 2 时态数据库数据依赖理论国内外的发展现状及趋势 对于传统关系数据库，一般用函数依赖、多值依赖和连接依赖表示关系模 式满足的属性问固有的约束，并且基于它们对关系数据库进行的规范化问题已 有大量的研究口2 i i ”1 1 “】。对于时态数据库，借鉴传统关系数据依赖理论，许多研 究人员为寻找合适的数据依赖约束也做了大量的工作。v i a n u 提出了动态函数 依赖( d f d s ) t ”1 的概念。而w 日s e n 定义了4 种类型的依赖：快照函数依赖 ( s f d s ) ，动态函数依赖( d f d s ) ，时态函数依赖( t f d s ) ) 及t 间隔依赖( i d s ) 1 1 6 1 1 ”l 。 j e n s e n 讨论了基于b c d m 模型的时态函数依赖b l l l 9 忙。上述的数据依赖虽然 在一定程度上反映出数据的动态约束，但都无法处理多时间粒度的问题，而现 实世界的大部分数据都涉及多时间粒度问题1 2 l 】。w a n g 基于多时间粒度给出了 另一个时态函数依赖( t f d ) 的定义【2 2 】，由于w a n g 的t f d 能较好地反映客观世 界，w 日s e n 又将其扩展到复杂对象的依赖约束。 w a n g 基于t f d 系统地讨论了具有多时间粒度的时态数据库的逻辑设计问 题，定义了时态第三范式( t 3 n f ) 及时态b o y c e c o d d 范式( t b c n f ) ，并提出了 相应的分解算法。但w a n g 的算法在实际的数据库设计中却很难使用，这主要 是由于三方面的原因：时态类型集所具有的偏序特性使得算法中的一些时态类 型间的操作无法实现；w a n g 的算法涉及到对时态类型执行g l b 操作，而对于 任意时态类型集，g l b 操作可能会产生新的时态类型，这使得计算机难以处 理；w a n g 的算法是以范式判定为基础的，而对于范式判定至今没有有效的算 法。为了解决以上问题，姚春龙等人建立了一个对于g l b 操作封闭的时态类型 哈尔滨理工大学工学硕士学位论文 集掣】；讨论了时态函数依赖集的成员籍算法 2 5 l ：对具有全序时悉类型集的时态 函数依赖集进行了深入研究l 。 一。个好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异 常，丽要设计一个好的数据库必须研究数据依赖理论。结合目前的研究成果可 知将来的发展趋势是： 1 寻找低于时态b o y c e c o d d 范式高于时态第三范式的时态范式，并且将 一个时态模式分解成该时态范式时能同时满足保持函数依赖和无损连接性； 2 类似于关系数据库中的多值依赖，寻找时态多值依赖，并根据时态多值 依赖定义时态第四范式，研究其分解算法。 1 3 本课题的主要研究内容 1 3 1 时态初等关键字范式 1 基本概念：时态初等函数依赖；时态初等关键字；时态初等主属性；时 态初等关键字范式 2 规范程度：证明时态初等关键字范式的规范程度高于时态第三范式低于 时态b y o y c e c o d d 范式。 3 分解算法：时态初等关键字范式的分解算法 4 算法的证明：证明算法能将一个时态模式分解成满足时态初等关键字范 式定义的若干个对态模式的集合，并且保持函数依赖和无损连接性，对算法的 时间复杂度进行了分析。 1 3 2 时态简单范式 1 基本概念：时态简单关键字：时态简单主属性：时态简单范式 2 规范程度：证明时态简单范式的规范程度高于时态初等关键字范式低于 时态b y o y c e c o d d 范式。 3 分解算法：时态简单范式的分解算法 4 算法的证明：证明算法能将一个时态模式分解成满足时态简单范式定义 的若干个时态模式的集合，并且保持函数依赖和无损连接性，对算法的时间复 杂度进行了分析。 一： 竺玺篓堡三查兰三兰堡圭兰竺丝兰 1 _ 3 3 基于t f d s 和t m v d s 混合集的时态模式的规范化 1 3 3 1 时态多值依赖 1 基本概念：强细于关系；集强细于关系：时态多值依赖 2 时态多值依赖的推导规则和有限推导规则 3 时态多值依赖推导规则的有效性和完备性证明，有限推导规则的有效性 和完备到继承性的证明。 13 3 2 成员籍问题 1 基本概念：有限闭包：有限依赖基；特殊有限依赖基 2 求有限闭包、有限依赖基和特殊有限依赖基的算法及其证明 3 成员籍问题的算法及其证明。 1 3 3 - 3 时态第四范式 1 基本概念：时态第四范式 2 分解算法：时态第四范式的分解算法 3 算法的证明：证明算法能将个时态模式分解成满足时态第四范式定义 的若干个时态模式的集合，并且保持无损连接性，对算法的时间复杂度进行分 析。 1 4 本文结构 第2 章介绍了时态数据库涉及的基本概念和时态查询语言；第3 章定义了 时态初等关键字范式和时态简单范式并给出了相应的分解算法，对算法的可终 止性、正确性进行了证明，对时间复杂度进行了分析；第4 章提出了时态多值 依赖的概念，给出了有效和完备的推导公理系统，定义了有限闭包、有限依赖 基和特殊有限依赖基等概念并给出了相应的求解算法，从而解决了成员籍问 题，最后提出了时态第四范式及把时态模式分解成时态第四范式的分解算法。 哈尔滨理工大学1 二学硕士学位论文 第2 章时态数据库简介 2 。l 时态数据库的一些术语 2 1 1 三种时间 时态数据库涉及三种时间： 1 有效时间( v a l i dt i m e ) ：是指一个对象在现实的世界中发生并保持的时 问，或者该对象在现实世界中为真的时间段。 2 事务时间( t r a n s a t i o nt i m e ) ：是指一个对象录入数据库系统的时间，有 时候也称它为系统时间( s y s t e mt i m e ) 。一 3 用户定义的时间( u s e rd e f i n e dt i m e ) ：是指用户根据需要而输入的时 间，数据库管理系统将它与数据库中其他一般数据等同对待。 例如一个员工关系( 名字，级别，提升对间) ，则元组( 张三，副教授， 1 9 9 7 年1 月1 曰) 于1 9 9 7 年1 月2 7 日录入数据库，则这里提升时间“1 9 9 7 年1 月1 日”是用户定义的时间类型，它表示的是提升管理委员会同意提升的 时间，有效时间就是提升生效的时间，在这个例子中( 1 9 9 7 年1 月1 日，下一 次提升的时间) 就是有效时间，而事务时间就是将提升的信息存储至数据库的 时间，即是“1 9 9 7 年1 月2 7 目”。 2 1 2 四种数据库 已经建立的数据库有如下四种： 1 快照数据库( s n a p s h o td a t a b a s e 九使用数据更新操作象删除、替换、 插入等对一个数据库的状态进行次系统活动，它导致数据库的过去状态丢失 并忘却，这种数据库称为快照数据库。它仅仅反映现实中的一个片断。 2 回滚数据库( r o l l b a c kd a t a b a s e ) ：根据事务时间在系统中保持数据库 的所有过去状态并能对过去的任意状态进行删除操作。这类数据库称为回滚 数据库。 3 历史数据库( h i s t o r yd a t a b a s e ) ：根据有效时间在系统中保持对象的所 有过去历史，并能对库中任何数据做更新操作。这种数据库称为历史数据库。 4 时态数据库( t e m p o r a ld a t a b a s e ) ：根据有效时间和事务时间在系统中 哈尔滨理工大学工学硕上学位论文 分别保存对象历史和数据库状态。 2 1 3 三种时态数据类型 时态数据库涉及如下三种时态数据类型： 1 瞬时( i n s t a n t ) ：是时间轴上的固定点。例如：王三转正定级的时间是 1 9 9 9 年7 月1 日。这种类型是时态领域中最基本的类型，其他类型可以通过瞬 时来实现或者在某种程度上通过瞬时来模拟。除了瞬时类型之外，大多数的数 据库管理系统并没有提供其他类型的时态数据类型。 2 时区( i n t e r v a l ) ：是时问轴上段时间的长度，是时闻轴上不固定的但 连续的部分，即两个瞬时之间的距离。时区的概念是相对的，且具有方向性， 正区间表示未来，负区问表示过去。 3 期间( p e r i o d ) ：是时间轴上段固定的时间区间，例如1 9 9 9 年7 月至 2 0 0 0 年7 月就是一个期间的例子。在商业上广泛应用的d b m s 和s q l 9 2 标准 中都不支持这种数据类型。但是我们可以通过它们支持的瞬时数据类型来模拟 期间类型。方法是用一对瞬时数据类型( t 】，t 2 ) 来表示，前者1 】表明期间的开 始，后者t 2 表明期间的结束。 2 2 时态查询语言 目前基于不同的时态数据模型有4 0 多种查询语言，其中g a d i “1 9 8 8 ) 基于 s q l 体系提出了一种支持双时间数据库的查询语言t e m p s q l 。但最著名的是 s n o d g r a s s 于1 9 8 7 年设计的时问数据库级查询语言( t q u e l ) 。t q u e l 语言在理论 和原形上都很成功，但其基于的语言q u e l 不是工业标准，t e m p s q l 标准性 好，但又不如t q u e l 成功。 t q u e l 语言是一个著名的基于1 n f 方法的时态查询语言。他是r s n o d g r a s s 在1 9 8 4 年完成的q u e l 的一个扩充询问语言。 功能上，t q u e l 包含了q u e l ，即q u e l 中的语句在t q u e l 中有效。而t q u e l 具有询问历史和回滚操作的功能。t q u e l 是通过扩充q u e l 来提供询问、数据定 义和数据操作能力以达到支撑以上介绍的四种类型的数据库操作的这样一种时 态查询语句。由于t q u e l 被设计成q u e l 的一个最小扩充，这种设计仅需要在 q u e l 语句中增加一个处理时间的子句即可。例如，r e t r i e v e 语句有w h e n 谓词， w h e n 指定参与的元组中的时态关系。其一般形式为： r a n g e o f f ii s r i 堕堡堡兰三查兰三兰璺土兰堡篁塞 r a n g eo f f 2 i s r 2 r a n g e o f f o i s r n r e t r i e v e ( ) w h e r e p v d h e n q 除w h e n 子旬外的部分与它在q u e l 中一致。假定这部分操作的结果是a ， 则w h e n 子句是对a 的进一步限制，也就是说，a 中满足q 条件的所有元组就 是查询结果。w h e r e 和w h e n 也可以缺省，它保证了q u e l 语句在t q u e l 的合 法性。 这里，q 是时间表达式，它是由a l l e n t 2 8 1 定义的十三种时间关系运算符与时 间区间的连接而组成的。其中时间t 可以看成是一个区间【t ，t 】。 当然，r e t r i e v e 语句中也可以含有v a l i d 子句和a so f 子句。v a l i d 子句指定 怎样为结果元组计算蕴涵有时间的属性。a so f 为回滚数据或时态数据库指定 回滚操作。v a l i d 子句和a so f 子句的形式和地位与w h e n 子旬一样，这三令子 句和w h e r e 予句都可以同时出现在r e t r i e v e 语句中，也可以缺省。 t q u e l 中的a p p e n d 、d e l e t e 和r e p l a c e 语句以r e t r e i v e 语句一样的方式拥有 v a l i d 子句和w h e n 子句。 r s n o d g r a s s 还根据他设计的1 7 个比较标准将当时存在的t a n s e l 、h q u e l 、 h t q u e l 、m h m 、l e g o l 、t o s q l 、t r v l 、t s q l 、h r d m 十个询问语句与 t q u e l 徽了比较。从比较情况看，t q u e t 是最好的。但这些标准有其局限性和 偏见性，只能说明部分问题。因为s k g a d i a 和c y e u n g 指出t q u e l 功能不完 全，有些询问不能用t q u e l 提供的r e t r i e v e 语句表达。 当然，一些学者仍然在讨论1 n f 方法，象n l s a r d a t 3 0 l 3 q 等人，这些研究 结果与t q u e l 相比，在功能上大多一致，还没有取得一些突破。 2 3 本章小结 本章介绍了时态数据库涉及的一些基本概念 1 三类时间：有效时间、事务时问、用户自定义的时间 2 四种数据库：快照数据库、历史数据库、回滚数据库和时态数据库 3 三种时态数据类型：瞬时、时区、期间 4 。对时态查询语言t q u e l 语言做了一个简单的介绍。 篁查鎏堡三奎兰三耋罂圭兰堡丝兰 第3 章时态初等关键字、简单范式分解问题研究 3 1 引言 对于传统关系数据库，一般用函数依赖、多值依赖和连接依赖表示关系模 式满足的属性间固有的约束，并且基于它们对关系数据库进行的规范化问题已 有大量的研究。对于时态数据库，c s j e n s e n ，j w i j s e n ，xs w a n g 分别提出了 时态函数依赖( t f d ) 的概念。由于xs w a n g 的t f d 能较好地反映客观世界， 1 9 9 9 年j w i j s e n 又将其扩展到复杂对象的依赖约束。 基于t f d ，xs w a n g 提出了时态三范式( t 3 n f ) 和时态b o y c e c o d e 范式 ( t b c n f ) 的概念并给出了相关模式分解算法。但是，在时态函数依赖环境下， 把一个时态模式分解成属于t b c n f 的时态子模式时，并不能同时保持函数依 赖又同时具有无损连接性。甚至对很简单的时态模式进行分解时也是如此。例 如，对态模式( a b ，d a y ) ，t f d 集f = a 一。毗b ，a 一。o n l h b 。显然( a b ，d a y ) 不属 于t b c n f ，根据t b c n f 分解算法得 ( a ，d a y ) ，( a b ，m o n t h ) ) ，分解后a 一。k b 丢失。于是，就使我们不能不考虑规范程度高于t 3 n f 而低于t b c n f 的新范 式研究问题。基于关系数据库中的初等关键字范式及简单范式1 ，本章提出了 时态初等关键字范式和时态简单范式的基本概念并研究了时态初等关键字范 式、时态简单范式的分解问题，给出了相应的分解算法，对算法的可终止性、 正确性进行了证明，并对时测复杂度进行了分析。 3 2 基本概念 w a n g 给出了时态模式及时态函数依赖等相应的描述【2 2 】。现将本章在讨论 中涉及的相应概念描述如下。为描述时态类型，设全体实数集代表时间，记吼 为实数集，2 “表示瑕的幂集。 定义3 1 ( 时态类型) 时态类型是一个从确定的整数( 时刻) 集合到2 ” ( 绝对时唰集合) 的投影“，使得对所有确定的整数i j ( i 1 ) 。 定义3 2 ( 细于关系) i x l 和是时态类型，如果对每一个确定的整数 i ，存在整数j 满足扯l ( i ) c 斗2 0 ) ，则称l 细于“2 。记作i 。 在本文中，经常把r t l ( i ) _ c i t 2 0 ) 描述为：的时刻j 覆盖p l 的时刻i 。若 h v ，咿v ，则称蚌严格细于v ，记作：w l ，有： 哈尔滨理工大学工学硕士学位论文 f q ( f ) = 【d o ( j ) u ( f ) = 庐 一习，使v i ( i ) ( - ，) 事，使得u ( f ) ( 歹) 定义3 - - 2 4 ( m a x s u b 函数) 肚为一时态类型，p 为分解的模式，i 为一整 数，贝um a x s u b ( p _ ( i ) ，p ) = ( r ，v ) p l | j ，p ( i ) v 0 ) 。 定义3 2 5 ( 时刻无损性) p 是( r ) 关于f 的分解模式，k 为的任一非 空时刻，m a x s u b ( i ，t ，p ) = ( r l ，九1 ) ，f r 2 ，如) ，( r 。，h ) ) 。若对任意时态模型 m = ( r ，i t , m ) 及相应的投影m i = ( r i ，p ，m 。) = d o w n ( u p ( t ( m ) ，九。) ，“) ( 1 i m ) 有 o ( k ) = o l ( k 1 ) 睁卸2 ( k 2 ) 闻，扭曲。( k m ) ，其中p ( ”九( 1 【) ，则称p 具有时刻无损性。 定义3 2 6 ( 保持函数依赖) p = ( ( r 1 ，1 1 1 ) ，( r 2 ，2 ) ，( r 。，) ) 是( r ) 关 于f 的一个分解，m 为( r ，曲的任一时态模型。若命题( 若u p ( t ，( m ) ，p i ) 满足 t c r ( f ) 则m 满足f ) 成立，则称p 保持函数依赖。 引理3 1 设( u ) 为一时态模式，f 是仅包含r 中属性的t f d 集。 x e r ，a g x ，若x j a 舒文m i n c o v 叮) ) ，则f 逻辑蕴涵的t f d ：x f a ( 对任 意时态类型) 对于f 是初等函数依赖。 证明：( 反证法) 假设f 逻辑蕴涵的x _ 。t a 对于f 不是初等函数依赖，则 存在x c x 使得x ，_ 。a 被f 逻辑蕴涵，则x 寸a 被尢一f ) 逻辑蕴涵。又因为 x 斗a 兀d m i n c o v ( f ) ) ，由m i n c o v ( f ) 的定义可知啾m i n c o v ( f ) ) 是 c 文f ) 的最小覆 盖集，则x _ a 是兀文f ) 的最小覆盖集中的元素，这与x 斗a 被7 c 文f ) 逻辑蕴涵 相矛盾。证毕。 引理3 2 设( 凡，九。) 是( r ，) 的分解p 中的一个模式，其中r i = x a ， x 斗a 丌文m i n c o v ( f ) ) ，k 是算法中通过r a i s e ( ) 运算而得到的时态类型，则x 是( r ，丸) 的时态初等关键字。 证明：考虑一个一般性的模式f x a ，九7 ) ，”= r a i s e ( x ，f ) “a ) ，k = p r k d u 。 根据算法3 一l 可知：对任意p - i ( 鹾i s ) ，存在t f d ：x 斗，i a e f x a 且u i 的某时刻 被v l 的某时刻覆盖。由于是肛的一个划分，所以肛i 的每一时刻都被v i 的某时刻 覆盖( 否则u i 将会被进一步划分) ，则九的每一时刻被v 。的某一时刻覆盖。由于 每个t f d ：x 斗。；a f x _ ，a 被f 逻辑蕴涵，所以x 一心被f 逻辑蕴涵。再根据 r a i s e ( ) 定义得：x 斗”a 被f 逻辑蕴涵。根据x a 兀羽“i n c o “f ) ) 及引理3 1 可得：x -