为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

属性集的有限闭包和有限依赖基算法

2017-12-07 10页 doc 27KB 19阅读

用户头像

is_531654

暂无简介

举报
属性集的有限闭包和有限依赖基算法属性集的有限闭包和有限依赖基算法 第10卷第2期 2005年4月 哈尔滨理工大学 J0URNALHARBINUNIV.SCI.&TECH. Vol_10No.2 Apr.,2005 属性集的有限闭包和有限依赖基算法 李艳娟,郝忠孝 (哈尔滨理工大学计算机与控制学院,黑龙江哈尔滨150080) 摘要:本文定义了时态类型集的强封闭集,属性集的有限闭包,属性集在给定时态 类型上的 有限依赖基,属性集的有限依赖基等概念.给出了求属性集的有限闭包和有限依赖 基的算法,并对 算法的可终止性,正确性进行了证明...
属性集的有限闭包和有限依赖基算法
属性集的有限闭包和有限依赖基算法 第10卷第2期 2005年4月 哈尔滨理工大学 J0URNALHARBINUNIV.SCI.&TECH. Vol_10No.2 Apr.,2005 属性集的有限闭包和有限依赖基算法 李艳娟,郝忠孝 (哈尔滨理工大学计算机与控制学院,黑龙江哈尔滨150080) 摘要:本文定义了时态类型集的强封闭集,属性集的有限闭包,属性集在给定时态 类型上的 有限依赖基,属性集的有限依赖基等概念.给出了求属性集的有限闭包和有限依赖 基的算法,并对 算法的可终止性,正确性进行了证明,对时间复杂度进行了. 关键词:时态数据库;有限闭包;有限依赖基;成员籍 中图分类号:TP311文献标识码:A文章编号:1007—2683(2005)02—0019—04 AlgorithmofFiniteClosureandFiniteDependencyBase ofAttributionSets l,n—juan.HAOZhong—xicto (Computer&ControlCollege,HarbinUniv.Sci.Tech.,Harbin150080,China) Abstract:Inthispaper,strongclosesetofsetoftemporaltypes,finiteclosureofattributionsets, finitede— pendencybaseofattributionsetsbasedonacertaintemporaltypeandfinitedependencybaseo fattributionsetsare introduced;thealgorithmoffiniteclosureandfinitedependencybaseofattributionsetsandth eproofforitstermi— nationandcorrectionaregiven. Keywords:temporaldatabase;finiteclosure;finitedependencybase;membership 近年来,对于时态数据库有了相当多的研 究,文[1,5]提出了各自的时态函数依赖(TFD)的 概念,其中文[5]提出的时态函数依赖能够较好地 反映客观世界,文[6]又将其扩展到复杂对象的依 赖约束. 文[7,8]对时态函数依赖集的成员籍算法及具 有全序时态类型集的时态函数依赖集进行了深入研 究.本文讨论了时态类型的一些特性,定义了时态类 型集的强封闭集,属性集的有限闭包,属性集在给定 时态类型上的有限依赖基,属性集的有限依赖基及 属性集的特殊有限依赖基等概念,给出了求属性集 的有限闭包和有限依赖基的算法,对算法的可终止 性,正确性进行了证明.' 2004—1O一15 收稿日期: 作者简介:李艳娟(1979一),女,哈尔滨理工大学硕士研究生 1基本概念 文[5]给出了时态类型,细于关系,严格细于关 系,集细于关系的定义及任何时态类型集相对于细 于关系存在一个最小下界和最大上界,分别记作 B.和T.,任意一对时态类型和相对于细 于关系分别存在一个最大下界和最小上界,分别记 作glb(/x1,2)和lub(/x1,2). 定义1(强细于关系).,是两个时态类 型,若对每一个满足(i)?咖的正整数i,存在满 足(i)=(),则称强细于,记作s. 任何时态类型集相对于强细于关系都存在一个 哈尔滨理工大学第9卷 最小下界,记作.它的定义为:对每个i,/x(i)= (b.这里规定一个特殊的时态类型=,使得任 何时态类型都强细于,则任何时态类型集相对于 强细于关系都存在一个最大上界.由上述描述可 知任一对时态类型(.,),相对于强细于关系存 在最小上界和最大下界,分别记作lubs(/x,/x)和 glbs(~1,/x2). 定义2(集强细于关系).{.,,…,}是一 个时态类型集,是一个时态类型.如果对于每个满 足l,(i)?的正整数i,存在1??凡和某一个正整 数J_,使得(i)=(),则称集强细于{.,,…, },记作s{/xl,/x2,…,}. 文[9]中给出了封闭时态类型集和时态类型的 封闭集的定义. 定义3(强封闭时态类型集).一个时态类型 集是强封闭的,当且仅当对于任何时态类型/x, ?T,一定有glb(,)?T,glbs(~,)? 定义4(时态类型集的强封闭集).一个时态 类型集r的一个强封闭集r'定义为:r'是强封闭 的,并且rr'. 定理1一个时态类型集的封闭集也是它的强 封闭集. 证明在时态数据库中,用时态类型表示时间 粒度,并且具有一定现实意义.基于时态类型的特性 有:若两个时态类型/x,相对于强细于关系存在不 等于空的最大下界glbs(~,),则这两个时态类型相 对于细于关系也一定存在不等于空的最大下界glb (/x,),且glb(~L,)=glbs(~,).证毕. 文[9]中给出了求时态类型集的封闭集的算 法,根据定理1可知,可以利用该算法求时态类型集 的强封闭集. 定义5(有限闭包).TFD和TMVD混合集D 的有限闭包,是由D应用有限规则推导出的所有 TFD和TMVD的集合,记为:={YIDI——r X6,Y,6是"一"或""}. 定义6(属性集的有限闭包).D是一个TFD 和TMVD的混合集,对每个有限属性集,关于D 的有限闭包定义为:={(B,)I一口?且 不存在一B?D,,使得<}. 定义7(在给定时态类型上的有限依赖基). 设D是一个TFD和TMVD的混合集,R是范属性 集,是有限属性集,是某时态类型,定义G={yI 存在l,?I,使得DI—_,y或存在, },MB(G)为G的最小 ?,使得DI——,一一Y 基集,则在时态类型上关于D的依赖基DE ()={(y,)IY?MB(G)}. 定义8(属性集的有限依赖基).设D是一个 TFD和TMVD的混合集,对每个有限属性集,关 于D的有限依赖基DEP[列=DE(),其中T=… {IDI—_ry}. 对于任意时态依赖d:y,其中6是"一"或 " 一" ,称作d的时态类型,记作Tr(d);X称作 d的左部,记作LH(d);Y称作d的右部,记作RH (d);NT(d)是d对应的非时态版本,即若d是一个 TFDy,则NT(d)=—y;若d是一个TMVDX 一y,则NT(d)=一一y.设D是一个TFD和 TMVD混合集,D的时态类型集TTS(D)={TT(d)I d?D},7r(D)={NT(d)Jd?D}. 2属性集有限闭包和有限依赖基算法 算法1T—FMCLOSURE(求属性集的有限闭 包和有限依赖基算法) 输入:属性集,泛属性R,TFD和TMVD的混 合集D及TTS(D)的一个强封闭集r 输出:关于D的有限闭包CLOS和有限依赖 基DEP T—FMCLOSURE(X,D) Begin 1)For每个?Tdo {pre(~)={I<,?T}; pres()={ul/x?,?,?T}; Countf_l:1pre()I; TFDC={yIY?D}; TMVDC】={—yI—Y?D};} 2)Count=ITI; While(Count>0)do For每个?Tdo ifCount[]0then {SetC]=TFDCuTMVD~]u{一yI_y ErFD[],?pre()}u}一一yI_一Y?TM— VDr1,?pres(~)}; TFD={yI仃(Se)I=y}; TMVD~]={一yI仃(Set[])I=一一 Y}; 计算关于7r(se[])的属性闭包?X,令 []={(A,)IA?X一X}; 第2期李艳娟等:属性集的有限闭包和有限依赖基算法21 计算关于7r(se[】)的依赖基mDEP',令 ]={(1,,)Il,?DEP'}; Count=Count一1; T=T一{}; For每个?Tdo If?pre()thenCount~]=Count[】一1;} 3)CLOS=u; 删除CLOS中所有这样的(A,),存在<, 使得(A,)?CLOS; 4)CLOS=CLOSU{(A,)IA?X}; 5)DEP=u[】; 6)DEP=DEPU{(A,)IA?X}u{(R—, )}; 7)return(CLOS,DEP); End. 引理1设D是一个TFD和TMVD混合集, 是rrs(o)的一个强封闭集.若DI——,则Tr(d) ?TU{T0}. 引理2设D是一个TFD和TMVD混合集,若 DI_rd,贝07r(SetETr(d)])I=NT(d). 引理3若Set[]中的每个TFDx一l,,满足存 在?使得DI——r一,l,,每个TMVDx一 一l,,满足存在?使得DI——,一一l,或 存在",?",使得DI——,一一,,l,,则:若 仃(se[])l_XSY,如果是"一",那么一定存在, ?,使得DI——r一l,;如果是"",那么一 定存在,?,使得DI——,一一l,或存在 ?使得DI——r一 引理4设淞l,是Set[]中的任意一个时态依 赖.若是"一",则一定存在?,'使得DI—, l,;若是"一",则一定存在?使得D I——rl,或存在",?",使得DI—_r 引理5若(A,)?,则一定不存在(A,), <,使得7r(SetEv])I=一. 证明(反证法)设存在(A,),<,使得7r (Set)l_—A.则由定理4和定理3得:一定存 在?使得DI——,一,这与(A,)?, 相矛盾.证毕. 引理6若存在?T,使得7r(se[】)l—— A,且不存在?T,<,使得7r(se)l=—A, 则(A,)?r. 证明(反证法)设(A,),由定理4,定 理3及引理1可知:一定存在?T,<,使得DI —— r一A,.根据定理2,一定有7r(Se)l_ . 这与题设矛盾,证毕. 定理2对于给定属性集X,TFD和TMVD混 合集D,算法1正确求得关于D的有限闭包CLOS 和有限依赖基DEP.其时间复杂度超不过Of印' ., r +?(2n+2n)+|l}(n一九)),其中n是范 属性个数,P是D中的时态依赖的个数,|l}是中时 态类型的个数,h是中的属性个数,P是算法第二 步对中的第i个时态类型(不妨设为)求Set[】 时,Set1中的时态依赖的个数. 证明算法仅涉及到有限的f0r循环,显然算法 是可终止的. 正确性: 1)首先证明对于任意(A,)?,当且仅当 (A,)?CLOS; 充分性对于每个(A,)?CLOS.若A?X,算 法只有在第4)步将(A,T.)加到CLOS中,于是 =/xT0,显然(A,T0)?;若AX,根据算法第 2)步,必然存在(A,)?X[](?T),且不存在? ,<,使得(A,)?X;即7r(Set)I=_?A, 且不存在?T,<,使得7r(Set[】)l_—A.根 据定理6,(A,)?. 必要性对每个(A,)?,即DI——r A,由定理2一定存在?T,使得(Set[])I= ,~Jl(a,)?X.根据定理5得:不存在?T, <,使得7r(Set)l_A,即(A,)?XE】_因 此在算法第3)中将(A,)加入到CLOS中后,并没 有把(A,)从CLOS中删除,即(A,)?CLOS. 2)其次证明对于任意(1,,)?DEP…,当且仅 当(1,,)?DEP. 充分性对于每个(1,,)?DEP.若=,算 法只在第5)步将(A,)(A?X)和(R—,)加入 到DEP中,于是Y?{(A,)IA?X}u{(R—, )},显然(1,,)?DEP[];若?,?T,则根据 DEP儿()的定义及定理4,定理3,得:(1,,)?DE ().再由DEP…的定义得(1,,)?DEP[],证毕. 必要性对于每个(1,,)?DEP…,根据 DEPf】的定义有DI——r一一l,或存在,?, 使得DI——r一一对于前者DI——r一 一l,,根据定理2可知,一定存在?T,使得 (set[】)l_—一l,,则(1,,)?],根据DEP的求 22哈尔滨理工大学第9卷 法有(1,,)?DEP;对于后者,DI——r一l,,则 仃(TFD【])I=-+由?得仃(Set[])I= l,,则一定有(1,,)?],根据DEP的求法有 (y,)?DEP.证毕. 时间复杂度:算法第1)步对每个时态类型求 TFD[】和pre(/z)时需对D和分别扫描一遍,故算 法第1)步的时间复杂度为O(k+);算法第2)步 中求关于仃(Set)的属性闭包的时间复杂度为 o(pn),依赖基为O(n),则求TFD[]和TMVD[] 的时间复杂度分别为O(2n)和0(2"n),故算法 . r 第2)步的时间复杂度为O(?(2n+2"n)); 算法第3)步中CLOS中的元素至多为k(n—h)个, 故算法第3)步的时间复杂度为O(k(n—h));算 法第4)一6)步的时间复杂度分别为O(h),O(), O(h+1).故算法总的时间复杂度为:O(k+)+ , r, O《?(2"Pn+2"n))+o(k(n一))+D() +D(后)+O(h+1),超不过D(印+(2n+ 2nn4)+后(一)1.证毕. 3结语 本文定义了时态类型集的强封闭集,属性集的 有限闭包,在给定时态类型上的有限依赖基,属性集 的有限依赖基及特殊有限依赖基等概念,给出了求 属性集的有限闭包,有限依赖基和特殊有限依赖基 的算法,对算法的可终止性,正确性进行了证明,对 时间复杂度进行了分析.最后,给出了解决时态混合 集成员集问题的算法,并对算法的可终止性,正确性 进行了证明,对时间复杂度进行了分析,下一步的主 要工作是:首先解决成员籍问题;然后寻找时态第 四范式及其分解算法, 参考文献: [1]JENSENCS,CLIFFORDJ.AGlossaryofTemporalDatabaseConcepts[J].ACMSIGMODRecord,1994,23(1):52—64. [2]JENSENCS,SNODGRASSRT,SOOMD.ExtendingExistingDependencyTheorytoTemporalDatabases[J].IEEETransactionsOilKnowledge andDataEngineering.1996,8(4):563—582. [3]JENSENCS,SNODGRASSRT.SemanticsofTime— varlngInformation[J].InformationSystem,1996,21(4):311—352. [4]WIJSENJ.DesignofTemporalRelationalDatabasesBasedDynamicandTemporalFunc tionalDependencies[J].In:ProcoftheInternational WorkshoponRecentAdvancesinTemporalDatabases.Springer— Verlag.NewYork,NY,1995.25(2):61—76. [5]WANGXS,BETHNIC,JAJODIAS.1ogicalDesignforTemporalDatabaseswithMultip leGranularities[J].ACMTransactionsOnDatabasesrs— tem.1997,22(2):115—170. [6]WHSENJ.TemporalFDsonComplexObjects[J].ACMTransactionsonDatabaseSyste m,1999,24(1):127—176. [7]姚春龙,郝忠孝.一个具有多时间粒度时态函数依赖集的成员籍算法[J].计算机 研究与发展,2002,39(3):342—347. [8]姚春龙,郝忠孝.具有全序时态类型集时态函数依赖集的研究[J].软件,2003,l4(2):247—252. [9]姚春龙,郝忠孝.时态类型集的封闭集[J].计算机工程,2003,29(2):35—37. [10]刘惟一.数据模型[M].北京:科学出版社,2001. (审稿:陈德运教授,孙立镌教授;编辑:付长缨)
/
本文档为【属性集的有限闭包和有限依赖基算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索