候选关键字的求解算法

候选关键字的求解算法 第l6卷第1期江西师范大学(自然科学版) 1992年2月JOURNALOFJIANGXINORMALUNIVERSITY Vo1.16N0.1 Feb.1992 候选关键字的求解算法 周定康 (计算机科学系),『t/? 摘要 .本文了属性子集与候选关键字的关系,利用拓扑序结构和集舍理论,导出了求所有候选关 解 依赖;黜关键词堡垄羞壁耋;函数依赖!茎至苎茎;堕;属性闭包,,,压 候选关键字是关系数据库理论中的重要概念,关系的规范化,无损和依赖保持分解算法, 合成算法,以及对关系施行的各种操作等都涉及到候选关键字问题.选择优良性候选关键字, 对关系模式的性能将产生直接的影响.这就要确定给定模式的所有候选关键字.然而这是NP 完全问题.[美]UllmanJD在文献CID中给出了证明,[美]加里MR,约 翰逊DS已经把它收集 在文献C2]的附录A4?3数据库问题中.[美]codeEF,u1aIlJD等对候选关键字给出了精确 定义和求属性闭包算法,从而为我们如何求解候选关键字开辟了一种途径,但是如何具体地确 定候选关键字,特别是给定模式的所有候选关键字,至今尚没有一个行之有效的算法?本文分 析了属性子集的特性,在理论上阐述了它与候选关键字的关联问题;开发了较为理想的,行之 有效的求解所有候选关键字的新算法,为关系模式的优化设计和自动生成提供了帮助. 1基本概念 定义I.1关系模式是一个三元组:,,) 其中(1)R是关系名; (2),,是有限属性集; (3),是定义在c,上的函数依赖集? 定义1.2在关系模式,F)中,为所逻辑蕴舍的函数依赖的全体叫做F的闭包,记 为F或F’. 定义1.3设为属性集U上的一组函数依赖集,盖,,,则X关于F的属性闭包为: 对={Al卫一A?) 其中盖,常简写为X.计算X算法用类PASCAL语言描述如下 FUNCTIONclosul~(盖,F); 收藕日期l99】一】O一04 *本课题为省重点科技项目 中 江西师范大学(自然科学版)1992年 输入:属性子集x和函数依赖集; 输出:x begin OLDDEP:=;NEWDEP:=盖; WHILENEWDEP?OLDDEPD0 hnOLDDEP:~NEWDEP; forevery(W~Z)in,DO ifNEWDEPthen beginNEWDEP:~NEWDEP+{z}; F:=F--{z) end; endI return(NEWDEP) endI 定义1.4对于给定的关系模式R(U,F),如果jKCU.并满足: (1)=c, (2)V?K有(一{))?u 则称为关系模式R(U,F)上的一个候选关键字. 本文约定英文大写字母表示集合,英文小写字母表示集合中元素I用英文小写字符申表示 集合?在上下文不混淆的情况下,英文小写字母也可理解只有一个元素的集合,当易混淆时,常 用”{“和”)”括号标注.在集合运算中,用”+”表示并运算,用×”表示粲合的笛卡尔积. 2确定所有候选关键字算法 对于给定的关系模式(.),不失,般性.假设F是由英文小写字符组成的有限属性集, F是函数依赖小覆盖集,计算的所有候选关键字的算法是: 算法A2.2 A1.[初妊1t]将U中所有可能的属性子集排成表列; A2.[淘汰]淘汰表列中属性闭包不等于U的所有表项} 3.(删除]删除表列中具有多余属性的属{)不是候选关键字,所以(一{d)每81(,我们说(一 {))s?,这是因为若一{})?8N,则jK?8K.,使得KC(W--{)),K一U,即有(?一 {))=U,矛盾于是候选关键字.因此必有(一{))?蹦?{)×蹦.如果W=a,显 然原式为真.即定理得证. 该定理告诉我们,添加一个新属性到中,新的候选关键字只可能落在{)+{a)×8 中.在求解所有候选关键字的过程中,应在{a)+{)×蹁中寻找新的候选关键字,同时生成 &tI+1. 定义2.2如果集合s的每个元素排成一个序列:{s-.sz,…,s.),并且只要i<j(i?1,j ?)就有s.s,则称集台s排成的序列为集合拓扑序序列. 定理2.3设s是u中所有可能的属性子集组成的集合,则s必可以按照”“关系构成 拓扑序序列. 证略. 定理2.4给定关系模式R(U,),s是中所有可能的属性子集组成的集合,?u,每 ,{)+,令s={H一{d)×蹦,并且s构成拓扑序序列:{,sz,…,s.).那末从左 到右,集合s序列中第一个属性闭包等于U的元素必为的候选关键字. 证设甜一U且对?U(j<) (1)当;=i时,有s={),显然当s=U时,s?为候选关键字. (2)当>i时(以下用反证法): 假设s,不是候选关键字,则|?s.满足(s.--z)一. 若=(s.--z)?s屯(岛一.)?u,与假设相矛盾; 若.?d,则(鼠一d—)?(s,一—)?8.4.(s.一)?.由于是拓扑序结构,故|J <,满足母=(s.--z)且对=,与巳知条件相矛盾. 由上分析,S必为候选关键字,定理得证. 根据定理2.4,我们可以导出求给定关系模式所有候选关键字的新算法.算法中使用的数 据结构,过程和函数描述如下: typelink一 ode; , W:setofC]311.r;船一链链 如,,?,,P,p1,2:llnk; 江西师范大学(自然科学版)1992芷 top,head,tail,,f1;link; 豚…SA均采用循环链结构,链中设置 啃兵结点l曲,,,”分别是它们的头尾指 针.其初值如上页右下图 (1)计算{d)+{)×的算法 FUNCTIONeount(w,sa); 周定康候选关键字的求解算法 bee,ln A=A?next;”{=,lA?data {在拓扑序序列中取下一个元素) ifclosure,F)=Uthen bee,ln insert(w,5f);del(1~,top) end else =A?next end; A’nextl—} A?next{=top: l, end end; 倒给定关系模式R(U.F),其中: = 忙,bc,){ F={d6,p6,曲d,p,c) 采用本算法计算步骤如下: (1)初始值 d? 出m哨兵哨兵 (2)取第一个属性{) (3)由于{)?U,则计算{a)+{a)xHA, 结果是 恤n (d)取第二个属性{6) (5)由于{6)?,则计算{6)+{6)×HA 结果是 是 (6)由于{ah)?U,则生成新的蹦,结果 “ (7)取属性{c),{d)皆有{c)一U,{) U,插入船链,结果是: 芭兰 (8)属性取完,结束计算,返回曲所指的 链. 本实例共计算5次属性闭包,存贮属性 子集的结点共5个(不包括哨兵结点). 3结束语 本算法采用逐步扩充属性的生成属 性子集组成的集合.在生成过程中,每步都将 该集合划分为四类.它们是: (1)候选关键字的集合; (2)有可能靠添加属性生成,但当前不是 候选关键字的集合; (3)不可能靠添加属性成为候选关键字 的集合; (d)非确定的集合. 算法的核心就是不断地添加属性生成第 4类集合,同时又将它分解成(1),(2),(3) 类}减少了重复计算.在技巧上,对第4类集 合采用拓扑序结构,从而免除进行算法A2.1 步骤Aa的操作.因此,大大提高了运算速度. 假如U有n个属性,若仅有个单属性 候选关键字,则计算属性闭包的次数?是t NC=+0一+一一+…+=: =m-F一+一+一+…+=: =2…+m—l 江西师范大学(自然科学版)1992盎 对于多属性候选关键字,我们可以通过阶梯多叉树进行分析.若某属性子集为候选关键 字,则在树中保留一条该候选关键字的边,删除其余该关键字的边及其以该候选关键字为祖先 的所有子树.对所有候选关键字都如此进行,结果所得树的边数即为计算属性闭包的次数. 从上面分析说明,关系模式的候选关键字越多,本算法的优越性就越明显.对于不同的模 式,它将以候选关键字的增多而几何级数的下降,这是令人满意的. 参考文献 (1]u~.1,lanJDPrinCipleofDatab~saSystems.Computerscepress,Inc..F.oc kvilleMd.InuS.A..1982 C2J(黄)加里MR,约翰逊DS着,张立昂等译.计算机和难解性——NP 完全性理论导弓『.北京;科学出 版社,1987 (3)MajernTheTheoryofRe~tlonalDatabas~.ComputerScienceh.Inc.,RockvilleMd.InU.&A.. 1987.42,92 (4)Yuc日 1Feng.Al~oFithrnforso?ngCandidateKeyGraphTh~ey.proc.TheInternad帆 aIP砒DB.86 Symposium.1986 C5)冯玉才.候选关键字的图论隶解法.计算机.1988;11:$ (6)萨师煊,王珊.数据库系统概论.北京高等教育出版 社.1983;261~302 (73左孝凌等.离散.上海科学技术文献出版社.1985.8l,170 TheAlgorithmforSolvingAllCandidateKeys ??p’l) Abstract Inthispaper,wediscussedtherelatianbetweenthecandidatekeyandtheattributesub- set.andfounds0metheoryandalgorithmfarslavingallcandidatekeysoftherelatian schema. Keywords:candidatekey;functionaldependencies;relatianschema;databa se;attribute closure (责任编辑;王盎莲)