（计算机应用技术专业论文）强全序时态模式下函数依赖多值依赖混合集问题研究.pdf

哈尔滨理工大学工学硕士学位论文 强全序时态模式下函数依赖多值依赖 混合集问题研究 摘要 与时间相关的数据库应用需求的不断增长，使得时态数据库设计成为非常 重要的问题。在数据库的设计中，要充分考虑对数据依赖的处理，数据依赖是 指数据之间存在的各种联系，数据冗余的产生和数据依赖有着密切的联系。数 据依赖是数据库设计理论中的一个核心概念，通过它可以规范属性之间满足的 固有的语义约束。 为了更有效的研究时态数据库中各种依赖以及各属性之间的关系，以便将 关系进一步规范化，本文提出了时态左部属性、时态右部属性、时态双部属 性、时态函数依赖图等概念。并分别利用图论法和吸收法给出了求时态候选关 键字集的算法，并证明其正确性。 时态函数依赖( 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 ) 和时态多值依赖 ( t e m p o r a lm u l t i v a l u e dd e p e n d e n c y , t m v d ) 是时态数据库中最重要的两种数据 依赖。对于具有t f d 和t m v d 混合集约束的时态模式来说，由于多时间粒度的 使用使成员籍问题的解决变得更加复杂。但成员籍问题的解决对设计有效的模 式分解算法必不可少，本文基于强全序时态模式以及全序时态函数依赖和规则 时态多值依赖( r t m v d ) 理论提出了给定时态类型上的混合依赖基、强全序模 式混合依赖基、t f d 和r t m v d 混合集闭包、强全序模式混合闭包等概念，并 给出了求混合混依赖集中属性的依赖基、属性集的闭包的算法，对算法的可终 止性、正确性进行了证明，并对时间复杂度进行了分析。在此基础上，给出了 解决强全序模式混合集成员籍问题的算法，并对算法的可终止性、正确性进行 了证明，对时间复杂度进行了分析。 同时，本文提出了强全序时态模式中冗余依赖、混合无冗余覆盖、规范混 合依赖集等概念，并给出了求强全序时态模式混合依赖集的无冗余覆盖和规范 覆盖的算法。 以上理论和算法的研究，很好的解决了强全序混合依赖集中依赖的判定的 处理问题，为解决强全序时态模式规范化问题以及时态数据库设计提供了理论 哈尔滨理工大学工学硕士学位论文 基础。 关键词时态数据库；强全序时态模式；时态函数依赖；时态多值依赖；成员 簦 布日 哈尔滨理工大学工学硕+ 学位论文 r e s e a r c ho nm i x - s e to ff u n c t i o n a ld e p e n d e n c y m u l t i - v a l u e dd e p e n d e n c yo fs t r o n g - t o t a l l yo r d e r e d t e m p o r a ls c h ( 1e m p o r a lc i i e m e a b s t r a c t t h eo v e ri n c r e a s i n go fd a t a b a s er e l a t e dt ot i m em a k e sd e s i g n i n gt 锐n p o r a l d a t a b a s ev e r yi m p o r t a n t i nt h ed e s i g no ft e m p o r a ld a t a b a s e , i ti sn e c e s s a r yt og i v e f u l lc o n s i d e r a t i o nt ot h ed a t ad e p e n d e n tt r e a t m e n t d a t ad e p e n d e n c ym e a n sa l lk i n d s o fc o n n e c t i o n sa m o n gd a t a t h eh a p p e n i n go fd a t ar e d u n d a n c ei sc o n n e c t e dw i t hd a t a d e p e n d e n c y d a t ad e p e n d e n c yi sac e n t r a ln o t i o ni nd a t a b a s ed e s i g nt h e o r yt h r o u g h w h i c hw ec a nn o r m a l i z ei n t r i n s i cs e m a n t i cr e s t r i n c t i o na m o n ga t t r i b u t e s i no r d e rt om a k et h es t u d y , t h er e l a t i o no fa l lt h ed e p e n d e n c e sa n da l lt h e a t t r i b u t e s , m o r ee f f i c i e n t ，t h e nn o r m a l i z er e l a t i o n a ld a t a b a s eo n em o r es t e p ，i nt h i s p a p e r , t h en o t i o n so ft e m p o r a ll e f ta t t r i b u t e s ，t e m p o r a lr i g h ta t t r i b u t e s ，t e m p o r a lb o t h - r l a t t r i b u t e s ，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 yg r a p h a r ei n t r o d u c e d a n dt h e a l g o r i t h m sf o rt e m p o r a lc a n d i d a t ek e y w o r ds e t si sg i v e nu s eg r a p ht h e o r ym e t h o d a n da b s o r p t i o nm e t h o dr e s p e c t i v e l y , i t sc o r r e c t i o na r eg i v t 孔 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 yo f d ) a n dt e m p o r a lm u l t i - v a l u e dd e p e n d e n c y o m v d ) a r et h et w om o s ti m p o r t a n td a t a - d e p e n d e n ti nt e m p o r a ld a t a b a s e f o r t e m p o r a ls c h e m ew i t l lt 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 lm u l t i v a l u e d d 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 sm a k ei tm o r e d 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 u t i o no fm e m b e r s h i p p 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 ed e c o m p o s i t i o n o n t h eb a s eo ft h es t r o n gt o t a l l yo r d e r dt e m p o r a ls c h e m ea n dt o t a l l yo r d e r dt e m p o r a l f u n c t i o n a ld e p e n d e n c ya n dt h et h e o r yo fr e g u l a rt e m p o r a lm u l t i - v a l u e dd e p e n d e n c y ( r t m v d ) o f r e l a t i o n a ld a t a b a s e , i nt h i sp a p e r , t h ec o n c e p t so fm i xd e p e n d e n c yb a s e o ng i v e nt e m p o r a lt y p e , m i xd e p e n d e n c yb a s ei ns t r o n gt o t a l l yo r d e r ds c h e m e , t f d a n dr t m v dm i xc l o s es e to fs t r o n gt o t a l l yo r d e r ds c h e m ea r eg i v e n a n dt h e i 哈尔滨理工大学工学硕士学位论文 a l g o r i t h m so f d e p e n d e n c yb a s e o fa t t r i b u t i o ns e t s ，c l o s u r eo fa t t r i b u t i o ns e t sa l eg i v e n , t h e nt h ep r o o ff o ri t st e r m i n a t i o n , c 舱r r e c t i o na n dt i m ec o m p l e x i t ya r eg i v e n o nt h i s 慨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 mo fm i xs e ti ns t r o n gt o t a l l yo r d e r di s g i v e n , a n dt h ep r o o ff o ri t st e r m i n a t i o n , c o r r e c t i o na n dt i m ec o m p l e x i t y a r og i v e n a sw e l la s ，c o n c e p t so f r e d u n d a n td e p e n d e n c y , m i x e dn o n - r e d u n d a n tc j c l v e i a n d c a n o n i c a lm i x e dd e p e n d e n c ys e to fs t r o n g - t o t a l l yo r d e rt e m p o r a ls c h e m e 锄g i v e n c o r r c - s p o n d i n ga l g o r i t h m s ，n o n - r e d u n d a n tc d v e ra n dc a n o n i c a lc o v e r , a l ep r o p o s e d w h i c hc a ns o l v et h ec o v e rp r o b l e mo fm i x e dd e p e n d e n c ys e ti ns t r o n g - t o t a l l yo r d e r d t e m p o r a ls c h e m e t h ea b o v er e s e a r c ho ft h e o r ya n da l g o r i t h mi sa g o o d s o l u t i o nt ot h ep r o b l e mo f d e p e n d e n c yj u d g e m e n ti nas t r o n g - t o t a l l ym i x - s e to fd e p e n d e n c y , a sw e l la s , i t p r o v i d et h e o r yb a s e m e n tf o rr e s o l v i n gt h ep r o b l e mo f n o r m a l i z a t i o nw h i c hi ns t r o n g - t o t a l l yo r d e r e dt e m p o r a ls c h e m ea n dt h ed e s i g no ft e m p o r a ld a t a b a s e k e y w o r d st e m p o r a ld a t a b a s e , s t r o n gt o t a l l yo r d e r e dt e m p o r a ls c h e m e , t e m p o r a l f u n c t i o n a ld e p e n d e n c y , t e m p o r a lm u l t i v a l u e dd e p e n d e n c i e s , m e m b e r s h i p i v 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文强全序时态模式下函数依赖 多值依赖混合集问题研究。是本人在导师指导下，在哈尔滨理工大学攻读硕 士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部 分外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：玉嘴吼跏7 年弓月纱日 哈尔滨理工大学硕士学位论文使用授权书 强全序时态模式下函数依赖多值依赖混合集问题研究是本人在哈尔滨 理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究 成果归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。 本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留 并向有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨 理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部 或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 | 不保密叼。 ( 请在以上相应方框内打) 作者签名：骑 日期：卅年g , 9 刀e t 导师签名： 7 韬 e t 期：乒嘲年弓月切e l 哈尔滨理工大学工学硕士学位论文 第1 章绪论 1 1 课题来源和研究的背景 本课题来源于黑龙江省自然科学基金( f 2 0 0 6 0 1 ) 高维时空数据库中移动对象 的查询技术研究。 随着数据库技术的发展，信息系统面临许多新的应用和新的需求，对时态 信息处理的需求越来越迫切。人们意识到，在关系数据库中正确的加入时态元 素，以及正确定义各元素之间的关系对研究时态数据库技术以便使其更好的应 用有着重要的现实意义。时态信息应用领域越来越广阔，时态信息需求多元 化，时态信息的应用也多元化。从传统的时态数据处理到时态知识的应用，从 传统的文本数据库到时空数据库、多媒体数据库系统，应用领域也渗入到科学 实验信息系统、多媒体信息系统、地理信息系统、市政信息系统、电信信息系 统、电子政务、数据仓库等各个方面n 1 。时态信息需求与处理越来越复杂，完 全“统一 的时态数据模型难以实现，仍然会有多种领域范围内“统一 的时 态数据模型。 出于现实世界是不断演变进化的，时间是那些反映现实世界信息的基本组 成部分，因而大多数数据库应用程序都有时态的特性，例如：会计，银行等财 经类的应用程序，人事、培训、酒店预订、项目管理等记录性应用程序，天气 监测等科学类应用程序。传统的数据库管理系统对时态信息的存储、处理和操 作都十分有限，正因为传统数据库缺乏对时态数据的支持，因而在很多方面产 生了很多问题，例如：它把时间数据作为一个字段的值进行存储和管理，只反 映了对象某一个时刻或当前时刻的信息和状态，不联系对象的历史、现在和将 来，无法将对象的历史、现在和将来作为对象的一个发展过程来看待，而这样 做有助于解释事物发展的本质规律，抓住事物的发展趋势( 这一点对于决策支 持系统这类的应用程序来说是很基本、很重要的) ；同时要求管理数据库系统 中元事件的时态信息，例如数据库被查询修改的时刻，时间区间。多用户系统 中对锁定排队以及资源竞争协调的时标等，这些时态数据也有助于提高数据库 系统的可靠性和效率。随着数据库技术的不断发展，人们开始逐渐意识到必需 为时态数据建立时态数据库的模型，或者在现有的数据库模型上加以改造，于 是提出了时态数据库的概念瞳1 。 哈尔滨理工大学工学硕士学位论文 目前，对时态数据库已进行了大量的研究，t a n s e la 收集了当前时态数 据库几乎所有的重要成果嘲。唐常杰对时态数据库技术前2 0 年的发展做出了系 统回顾h 一。汤庸介绍了几种具有代表性的时态数据模型啪。 1 2 本课题研究的目的和意义 一个好的数据库设计应该是尽可能的消除数据冗余以及插入、删除和更新 异常伸1 ，同传统的数据库一样，良好的时态数据库逻辑设计可以消除数据冗余 和减少插入、删除等异常，在很大程度上改善系统的性能，因此如何有效地进 行时态数据库设计成为近年来数据库研究的热点之一嘲。 时间维的引入致使数据库中的数据存储量急剧增加，极易产生存储异常和 数据冗余，因此，有效地进行时态数据库设计显得尤为重要。关系数据库设计 理论主要包括三方面内容：数据依赖、范式和模式设计方法。其中数据依赖 起着核心的作用。数据依赖是指数据之间存在的各种联系，譬如键就是一种依 赖。数据冗余的产生和数据依赖有着密切的联系，在数据依赖中，函数依赖 ( f u a c t i o n a ld e p e n d e n c y , f d ) 1 是最基本的一种依赖，实际上，它是键概念的推 广。f d 能有效地表达属性之间的多对一联系，它是现实世界中广泛存在也是 最基本的一种数据依赖。但f d 还不足以刻画现实世界中所有的依赖。例如 f d 就不能刻画属性值之间的一对多联系，多值依赖n 2 1 能刻画一部分一对多联 系。 近年来许多研究人员在时态数据库规范化问题上做了大量的研究n ”蚰，将 时态数据库规范到了t 3 n f 、t b c n f ，但是由于多值依赖的存在，t b c n f 范 式并不能完全消除冗余问题，这就需要将关系进一步规范化。 由于全序时态模式n 5 1 具有更好的特性，所以目前对于规范化问题的研究大 多是基于全序时态模式的，同时，函数依赖和多值依赖的同时存在使得对数据 库规范化的研究变得更加复杂，这就要求在以后的研究中，要很好的解决函数 依赖和多值依赖的混合集问题。如果一个数据库的函数依赖集和多值依赖集都 处于全序状态下，将更好的解决时态数据库中的规范化相关的问题，这就是本 文应用到的强全序时态模式n 引，即以拥有全序时态类型集的函数依赖集和全序 时态类型集的多值依赖集为前提的时态模式。 本课题将基于时态数据库中多值依赖的存在，在强全序时态模式下，对时 态数据库中函数依赖和多值依赖及它们的混合集的相关问题进行研究，在强全 序时态模式中进一步解决规范化的问题。 哈尔滨理工大学工学硕士学位论文 1 3 国内外数据依赖理论发展的现状 对于传统关系数据库，一般用函数依赖、多值依赖和连接依赖表示关系模 式满足的属性间固有的约束n 7 1 引，并且基于它们对关系数据库进行的规范化 问题已有大量的研究。对于时态数据库，许多研究人员为寻找合适的时态数据 依赖约束也做了大量的工作。 数据依赖是数据库设计理论中的一个核心概念，通过它可以规范属性之间 满足的固有的语义约束。在关系数据库设计中，最常见的依赖约束是函数依赖 ( f u n c t i o n a ld e p e n d e n c y , f d ) 和多值依赖( m u l t i - v a l u ed e p e n d e n c y , m v d ) ，对这 两种依赖以及基于它们的关系数据规范化理论已有大量的研究。在f d 和m v d 环境下，可以将关系模式规范化到第三范式( t h i r dn o r m a lf o r m , 3 n f ) 、b o y c o - c o d d 范式( b o y c e - c o d dn o r m a lf o r m , b c n f ) 和第四范式( f o r t hn o r m a lf o r m ， 4 n f ) 啪3 ，以消除数据冗余和各种异常现象。对于时态数据库，传统的数据依赖 不能很好地适应时态数据的动态性。为了能够刻画属性之间满足的动态的语义 约束，已经提出了多种时态数据依赖。下面分别介绍一些主要的时态数据依赖 以及基于它们的范式理论。 v i a n u 提出了动态函数依赖( d y n a m i cf u n c t i o n a ld e p e n d e n c i e s ，d f d s ) 口的 概念。而w i j s e n 定义了4 种类型的依赖：快照函数依赖( s n a p s h o tf u n c t i o n a l d e p e n d e n c i e s ，s f d s ) ，动态函数依赖( d y n a m i cf u n c t i o n a ld e p e n d e n c i e s , d f d s ) ，时态函数依赖( 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 i v s , t f d s ) 及间隔依赖 ( i n t e r v a lf u n c t i o n a ld e p e n d e n c i e s 。m s ) 陇砘巩龉】。j e n s e n 讨论了基于b c d m 模型 的时态函数依赖吼2 7 1 。上述的数据依赖虽然在一定程度上反映出数据的动态约 束，但都无法处理多时间粒度的问题，而现实世界的大部分数据都涉及多时间 粒度问题啪1 。w a n g 基于多时间粒度给出了另一个时态函数依赖( t f d ) 的定义 啪1 ，基于t f d 系统地讨论了具有多时间粒度的时态数据库的逻辑设计问题，定 义了时态第三范式( t e m p o r a lt h i r dn o r m a lf o r m ，t 3 n f ) 及时态b o y o v - c o d d 范式 ( t i m p o r a lb o y c c - c o d dn o r m a lf o r m ，t b c n f ) ，并提出了相应的分解算法啪1 。由 于w a n g 的t f d 能较好地反映客观世界，w i j s e n 又将其扩展到复杂对象的依 赖约束口。 1 v i n a u 提出了动态函数依赖( d f d s ) 的概念，他把时态关系看作在时间 上的快照关系的序列，每一个新的快照关系是从前一个快照关系通过同时影响 一些( 或全部) 属性的全局更新得到的。 哈尔滨理工大学工学硕士学位论文 2 n a v a t h e 和a h m e d 基于t r m 模型通过时态独立属性的概念提出了另 一种时态数据依赖。任意两个时间变化属性是时态独立的，如果它们的值不总 在相同的时间改变。n a v a t h e 和a h m e d 提出的时态范式中认为一个时态关 系中不应该包含时态独立属性，这样可以减小数据冗余。 3 j e n s e n 等人提出了一种依赖理论，他们认为数据冗余存在于时态关系 的快照中，他们把时态关系看成任快照关系的集合。由于每个快照是一个传统 的关系，因此可以把传统的函数依赖( f d ) 、多值依赖( m v d ) 和范式的概念应用 于每个快照。这样通过传统的关系模式的规范化方法可以减少每个快照的数据 冗余和各种异常。实际上j e n s e n 等人提出的时态函数据依赖就是传统f d 的直 接扩展。 4 结合v i n a u 和j e n s e n 的依赖理论，w i j s e n 定义了四种类型的依赖： 快照函数依赖( s f d s ) 、动态函数依赖( d f d s ) 、时态函数依赖( t f d s ) 和间隔依赖 ( d s ) 。与j e n s e n 的时态函数依赖相同，s f d s 是时态关系中的一个快照满足的 依赖，而其余的三种依赖是快照序列间的依赖约束；与v i n a u 的动态函数依赖 相同，d f d s 约束相邻的两个有效时间状态：t f d s 和i d s 约束一个多有效时间状 态的序列。另外，w i j s e n 在这四种依赖中都集成了对象标识。基于所提出的 依赖理论，w u s e n 给出了相应的时态范式的定义并提出了分解策略。 5 w a n g 等人基于多时间粒度提出了一个新的时态函数依赖( t f d s ) 概念。 w a n g 的t f d s 能够灵活地捕捉时间变化属性信息，并通过时态类型的概念，在 一定程度上能约束属性值的变化率和支持用户定义的时间类型。例如对于某个 时态模式的两个属性e # ( 员工号) 和s a l a r y ( 薪水) 及时态类型m o n t h ( 户 ) ，若该时 态模式满足t f de 撑一m 。劬s a l a r y ，则表明每个员工的薪水在一个月内有唯一的 薪水。基于t f d ，w a n g 对多时间粒度下的时态数据库的逻辑设计问题进行了 系统研究，系统地提出了时态模式的规范化理论，并定义了时态第三范式 ( t 3 n f ) 和时态b o y e e - c o d d 范式( t b c n f ) ，并给出了相应的时态模式的分解算 法。 6 l i u 提出了一种称作稳定性约束的动态依赖的概念m 1 ，反映了属性间的 变化快慢关系。对于稳定约束a - , b ，表明不存在这种情况，属性b 的值变化而 属性a 的值不变，即属性a 的值要比属性b 更稳定。 与其它的时态数据依赖相比，w a n g 基于所提出的t f d s 系统地讨论了多 时间粒度下的时态规范理论，分别提出了满足t 3 n f 和时态t b c n f 的时态模式 的分解算法。w a n g 的t f d s 具有更丰富的语义、可以在更大程度上消除数据 冗余并具有较为完备的规范化理论。鉴于此，w i j s e n 对t f d s 在支持对象标识 哈尔滨理工大学工学硕士学位论文 等方面进行了进一步的扩充，使其具有更丰富的约束表达能力，但从数据库的 设计方面没有进一步的研究，仍采用w a n g 提出的逻辑设计方法。另外， w a n g 的t f d s 是基于时态模块提出来的。时态模块模式可以按照其它的时态 数据模型直接地进行转换。因此，只要得到规范化的时态模块模式，经过转换 就可以直接得到满足实际数据模型所需要的数据库模式。时态模块为访问不同 的时间信息系统提供了一个统一的接口。 但w a n g 的算法在实际的数据库设计中却很难使用，这主要是由于三方面 的原因：时态类型集所具有的偏序特性使得算法中的一些时态类型间的操作无 法实现；w a n g 的算法涉及到对时态类型执行g l b 操作，而对于任意时态类型 集，g l b 操作可能会产生新的时态类型，这使得计算机难以处理。为了解决以 上问题，姚春龙等人建立了一个对于g l b 操作封闭的时态类型集嘲，对时态类型 的处理进行了讨论m 1 ；讨论了时态函数依赖集的成员籍算法；对具有全序时 态类型集的时态函数依赖集进行了深入研究；并提出了基于多时间粒度的 t 3 n f 的分解算法船7 1 。李艳娟等人提出了基于混合依赖的有限依赖基算法啪1 以及 基于此的成员籍算法。这些算法是时态数据库进一步规范化的基础，为找到 更有效的时态数据库的规范化方法开辟了新路。 在日常生活和实际的生产应用中，系统用来记录数据有效和事件发生的时 间的粒度通常是秒、小时、日、月和年等，这种多粒度常常同时存在于时态数 据库中，而这些粒度满足一种全序关系。一个具有全序的时态类型集的时态模 式，将比具有一般的时态类型集的时态模式有更多更好的特性，解决时态数据 库中多时间粒度的问题，是解决全序及强全序时态模式覆盖及成员籍等问题基 础，近几年来，也有很多学者在多时间粒度问题上进行了研究呱札朋1 ，并得出 了一定的成果，建立了基于多时间粒度的数据模型，进行了多时间粒度下模 式分解及多值依赖问题的研究m ，。 1 4 本课题的主要内容 1 在传统的关系数据库候选码的思想基础上，结合w a n g 论文中关于时 态候选码的定义，给出求时态候选关键字的方法。 2 基于强全序时态模式，为了解决强全序时态模式中规范化的相关问题， 在以前学者们给出的全序时态函数依赖、全序时态多值依赖等概念的基础上， 结合强全序时态模式下函数依赖和规则的多值依赖的混合推导规则，提出强全 序时态模式下的混合依赖基、闭包等概念，给出求强全序时态模式下混合依赖 哈尔滨理工大学工学硕士学位论文 基的算法和属性集闭包的算法，并进行证明。在求依赖基和闭包的基础上，结 合成员籍的概念，给出求强全序时态模式下混合依赖集成员籍问题的算法，并 进行相应的证明。 3 在以上工作的基础上，对强全序时态模式混合依赖集覆盖问题进行分 析，给出强全序时态模式下混合依赖集规范覆盖和无冗余覆盖的算法，并进行 相应的证明。 1 5 本文的结构 第l 章分析本课题研究的背景及意义，国内外在数据依赖理论方面的研究 现状，并介绍课题研究的主要内容。 第2 章简要介绍时态数据库出现的背景及其基本理论和时间粒度等相关内 容。 第3 章介绍时态候选关键字，给出了求时态模式中候选关键字的两个算 法，并证明其正确性。 第4 章是关于强全序时态模式中时态函数依赖和时态多值依赖混合集的规 范化相关问题的研究，给出了强全序时态模式的定义、规则时态多值依赖的定 义及其推导规则，给出了强全序模式的两种时态依赖混合集中依赖基、属性集 的闭包、成员籍问题的解决算法，并给出了正确性证明。然后提出了强全序模 式依赖集覆盖的概念，提出了解决冗余的覆盖算法并加以证明。 哈尔滨理工大学工学硕士学位论文 第2 章时态数据库简介 2 1 时态数据库出现的背景 传统的数据库技术能反映现实世界中的数据，但是它仅仅能体现现实世界 中数据的当前状态，只反应了一个对象在某一个时刻的状态( 快照) ，不联系其 过去和未来。这就是人们常说得快照数据库( s n a p s h o td a t a b a s e ) 。现代的信息流 包含事件的时态信息( t e m p o r a li n f o r m a t i o n ) ，其中有时刻信息( i n s t a n t i n f o r m a t i o n ) ，时间区间信息( i n t e r v a li n f o r m a t i o n ) 和相对时间信息( 之前、之后、 重叠) 等等。 日益广泛的数据库应用要求了管理被处理事件的历史性信息，和系统中元 事件的时态信息。需要迫切解决两个问题：一是要求管理被处理事件的历史性 信息，如与人事、财务、金融和自然灾害等有关的历史资料，从中可看出事物 发展的本质规律；二是要求管理数据库系统中元事件的时态信息，如增查，删 改的时刻和时间区间、在多用户系统中对锁定排队及资源竞争协调的时标等， 这些数据有助于提高数据库系统的可靠性和效率，因此引入时态数据库。 2 2 时态数据库的分类 时态数据库t d b ( t e m p o r a ld a t a b a s e ) ，是在传统的数据库基础上加上时间 维，不仅能刻画某个时刻的数据，还能反映出其历史和揭示其未来。按 s p i p a d a 和s n o d g r a s s 的意见，时态数据库按其功能可分为历史数据库、事 务数据库和双时态数据库n 钉。 1 历史数据库被管理对象的生命周期称为有效时间( v a l i dt i m e ) ，对象的 历史由d b m s 内部机制处理； 2 事务数据库数据库本身被查删改的时间称为事务时间( t r a n s a c t i o n t i m e ) ，事务数据库支持事务时间，他按事务时间编址，保存了所有状态演变 中过去的状态。事务的关系是一种三维结构，由元组、属性和事务时间三维构 成。 3 双时态数据库既能管理对象的历史，又能管理数据库本身被查增删改 的历史。他具有前两者的优点，支持事务时间和有效时间。时态关系是一个四 哈尔滨理工大学t 学硕士学位论文 维结构，由元组、属性、事务时间和有效时间构成。 下面介绍双时态数据模型中所涉及的三种时间体系：有效时间、事务时间 和用户自定义时间。 1 有效时间( v a l i dt i m e ) 一个事实( 事件) 的有效时间就是在建模的现实世 界中它为真( 存在) 的时间，有效时间可用单一的时间点、时间区间来表示，或 者表示为多个时间点和时间区间的有限集的有效时间元素，即一个事实可以联 系任意个时间点和时间区间，以单一时间点和时间区间作为重要的特例。 有效时间对应于应用或者现实世界变化历史，它是应用依赖的，即它的值 来自应用，或由用户或由应用提供。有效时间可以是“未来 时间( 一个事实 在未来的某时刻为真) 。 2 事务时间( t r a n s a c t i o nt i m e ) 一个数据库事实( 数据) 在某一时间点存储 到数据库中，此后它就是“现行 的，直至被逻辑地删除。一个数据库事实的 事务时间就是它在数据库中存在( 现行) 的时间。 事务时间对应于现有事务或现有数据库状态变迁的历史。它是应用独立 的，即其值仅根据系统时钟导出，因而它是应用不可操纵的。事务时间不能晚 于当前事务时间( 因为它对应于现有历史) ，也不能改变( 因为不能改变过去历 史) 。 3 用户定义的时间( u s e r - d e f i n e dt i m e ) 用户定义的时间就是一个不解释 的日期和时间属性域，就像“整数弦、“实数一、“金钱 等域一样，用户根 据需要而输入的时间，系统不作任何特殊处理，不要专门的语言支持( 这不像 有效时间和事务时间) 。与有效时间一样，用户定义的时间值是完全应用依赖 的，由用户应用以常规方式存取。 双时态数据模型不仅记录了现实世界中事件发生的有效时间，而且记录了 这个事件存储到数据库中的事务时间，既反映了现实世界的历史，又反映了数 据库的历史，可以满足人们对时态数据操作的各种要求。 2 3 时态信息模型 传统数据库在在添加了时间属性后，相应的概念、性质、基本原理、基本 方法发生了变化。时间元素在时态数据库中是记录和标识无限时间属性的基本 原子，因为没有时间元素的有效准确标识，时态信息的记录是不的，所以时态 元素模型是时态数据库基础之基础。 - 8 哈尔滨理工大学工学硕士学位论文 2 3 1 时态信息 时态信息需要用数据进行记录，这些用于记录时态信息的数据就是时态数 据( t 豇n p o r a ld a t a ) 。时态数据在计算机系统中的一般保存在数据库系统中，记 录和管理时态信息的数据库，有别于传统的关系数据库，记录在的元组部分属 性带有时变的特性，这就导致这种数据库的数据模式与传统的关系数据库数据 模式差别较大，由此而产生了数据库一些基本概念、理论、性质方面的改变， 这种记录时态数据反映时态信息的数据库就是时态数据库。 表2 1 中，表示了一个花店中的各种花的级别和售价随月份变化的情况。 因为级别是变化的，所以时变属性级别和售价的记录是分段的。在这里，用表 格的方式记录该花店的花种级别和工资的数据就是时态数据，这些时态数据所 反映出来的该花店花种的级别和售价情况就是时态信息。表中的闭区间，如 【1 ，7 】代表的是时间区间段，表示l 7 月的时间区间。 表2 - i 销售价格表 t a b l e2 it a b l eo f s a l e s - v a l u e 花名级别 售价( 元) 二级【l ，3 】 6 ，【i ，3 】 玫瑰 一级【4 ，7 】8 ，【4 ，7 】 百合 一级【l ，7 】8 ，【1 ，7 】 满天星 三级【2 ，9 】4 ，【2 ，9 】 2 3 2 时间模型 在自然界中，时间是每时每刻都存在、连续发生且一去不复返的，它在时 间轴上是连续存在的。从计算机科学的角度来看，如何量化时间和确定某个时 间点或者时间段，这关系到如何确定时间模型。如果按照现实世界的本来面目 来记录时间，则数据量过于庞大，而且人们往往并不需要获取现实世界所有的 时问的状态。解决这一问题的方法是建立合适的时间模型，使得它不仅能应用 到数据模型中，而且能满足不同应用场合的要求。 基于对时间轴结构的选择，时间模型可以划分为如下几种模型： 1 连续模型( c o n t i n u o u sm o d e l ) 连续模型把时间看作同构于实数，每一个 实数对应于一个时间点。因此，在时间轴的两个时间点之间，可以存在其它的 哈尔滨理工大学工学硕士学位论文 时间点。这种模型能够最精确地为时间建模，但是由于现代计算机基于数字逻 辑的工作方式，所以不可能无失真地记录时间。在许多实时控制场合中，例如 工业控制领域，需要记录大量随时间不断变化的数据，在这种情况下，往往采 取采样的方式记录数据变化，对相邻时间点之间的数据采取插值的方法得到。 2 步进模型( s t e p w i s em o d e l ) 步进模型把数据的状态看成是时间的函数。 当时间点上的数据状态发生变化时才记录状态变化，否则保持不变。在这种模 型下，时间序列上任一点上数据的值对应于上一次数据改变时保持的状态，如 果要查询当前数据的取值，则需要回溯。例如，表2 1 是采用步进模型登记的 某个花种级别的变动信息。 3 离散模型( d i s c r e t em o d e l ) 离散模型把时间和整数映射起来，且在相邻 的两个时间点之间不存在另一个时间点。任一时间点有前驱和后继时间点。在 实际应用中，该模型适用于记录那些在关键时间点上才有意义的数据。例如， 考虑某单位的人员工资发放总额，1 - - - 3 月的工资发放总额分别为1 9 万元、1 8 万元和2 0 万元。可以看到这组数据有如下特点。 ( 1 ) 在相邻的两个月份之间不存在另一个月份，如1 月和2 月。 ( 2 ) 相隔的两个时间点中间月份的数据，用插值的方法会得到无效数据， 通过1 月和3 月的数据无法确定2 月数据。 ( 3 ) 采取步进模型描述可能得出错误信息。假如现在为4 月和l o 日，当月 的工资尚未发放，如果回溯，就会得出4 月工资发放总额为2 0 万元的错误数 据。 4 恒定模型( n o nt e m p o r a lm o d e l ) 有些数据是不随时间变化的，例如，籍 贯、出生地等。这些数据只有其本身固有的属性。但是大部分数据在一种情况 下没有时态属性，但在另一种情况下往往会有时态属性。例如，住址、身份、 工作单位等。在一般情况下，在建模时通常没有充分考虑值随时间变化的情 况。如果发生变化时，就采用最新值进行替换。 2 4 时间粒度 由于计算机的数字化特点，不可能将时间存贮为一个连续的实体，而必须 用离散形式来表示。时间粒度是对离散化程度的度量，当以固定时间粒度对实 体状态采样时，粒度越小表示越精确，但太小的粒度又会导致内存的增加。实 际实现时，往往在两者间折中权衡，当系统以状态改变来记录信息的方式时， 时间粒度是变化的，或者时间粒度的语义由不同应用的需要而定。在实际应用 哈尔滨理工大学工学硕士学位论文 中，用户可根据具体情况来选择不同的粒度，而且不同的粒度间可以实现互相 转换机制。 2 4 1 基本概念 以下是与时间粒度有关的一些概念1 。 定义2 1 ( 时间粒度t i m ec , r a n u l a f i t y ) 时间粒度是指描述时间数据的最小时 间单位。它是表示时间点之间离散化程度的因素，它反映了时态信息系统中时 间点描述的最小单位，时间粒度越小，离散的时间点越多，描述的事件变化的 信息越精细准确；反之，描述的事件变化的信息越粗糙。 定义2 2 ( 时间域) 时间域是一个满足排序关系 l ， 若( d = = i z l ，贝l j 烈d d 。 考虑银行交易关系a c c o u n t s ( a c c t n o ，a m o u n t , b a l a n o e , a c c t m l h l t , t u n e ) ，其中，a e e t n o 为账号，a m o u n t 为交易数额，b a l a n c e 为账户余额， a c c u m i n t 为月累积利率，t u n e 为交易时间。a c c u m i n t 的计算方法是每天的开 始累加年利率的5 ，但是只在月末进行总体计算，由此可以看出，a c 贮u m i n t 的对应值不是每天都有变化。t i m e 即为时间戳，在这个例子中，它包含月、 日、年、小时、分钟、秒。我们假设每一个账户在做一笔交易时都有一个唯一 的时间戳。表3 1 为关系a c c o u n t s 的一组数据。 对于关系a c c o u n t s ，其时态模式即为( a c c o u n t s ，s e c o n d ) ，其中 r - -