《《求候选码的方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《求候选码的方法》PPT课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、候选码的确定方法,第五章 关系数据理论 数据库系统概论,6.2.2 码(参见P173.),定义5.4 设K为关系模式R的属性(组)，若K U，则称K为R的候选码。,主码：若R有多个候选码，则可以从中选定一个作为R的主码。主属性：包含在任一个候选码中的属性，称作主属性。非主属性：不包含在任一个候选码中的属性，称作非主属性(或非码属性)。全码：关系模式的码由全部属性构成。,码:例,关系模式 S(S#,SN,SD,DEAN,C#,G),码的确定(1)首先根据实际背景数据约束的语义确定关系模式R。(2)然后应用函数依赖的公理系统，验证F中每一个函数依赖的决定因素或其组合K，是否有:K U。,主码(S#
2、，C#)，因为(S#，C#)所有属性,码的确定:例,求出关系模式R的所有候选码：U=A,B,C,D,E F=ABC,BD,CE,ECB,ACB 注:码或者是某一函数依赖的左部,或是一个属性组。,验证AB是否码,须证明 AB ABCDE是否成立?ABC(已知),而ABAB(自反),AB ABC(合并)BD(已知),ABAD(增广),AB ABCD(合并)CE(已知),ABC(已知),AB E(传递)于是 AB ABCDE(合并),码的确定:例(续),验证AB是否码?前面已得到 AB ABCDE，又,显然 AABCDE,BABCDE,故所以AB ABCDE。得证AB是一个候选码。同理可证：AC也是
3、一个候选码。说明：如果每一个FD的决定因素都不是码，则要考虑这些决定因素的组合是否构成码；除了码的定义外，有候选码的求解理论和算法，在后面可以补充介绍更好的求码方法。,码的确定:练习,根据码的定义，求关系模式R的所有候选码。U=A,B,C,D，F=A B,CB,答：ACD,关于2NF的结论,1.不存在非主属性的关系模式属于2NF。没有非主属性2.全码关系模式属于2NF。没有非主属性3.码只由一个属性组成的关系模式属于2NF。不会有部分依赖4.二目关系模式属于2NF。码或是一个属性，或是全码5.若R属于1NF，但R不一定属于2NF。例如,关系模式 S(S#,SN,SD,DEAN,C#,G),关于
4、3NF的结论,1.不存在非主属性的关系模式属于3NF。没有非主属性2.全码关系模式属于3NF。没有非主属性3.二目关系模式属于3NF。不会存在传递依赖4.若R属于3NF，那么R也属于2NF。可证明，反证5.若R属于2NF，但R不一定属于3NF。例如，关系模式 S_SD(S#,SN,SD,DEAN),BCNF:定义,定义5.8 关系模式R 1NF，对于属性组X和Y，若XY且Y X时X必含有码，则R BCNF。注意到：BCNF的定义更简单，不需要从1NF到2NF再到3NF再到BCNF一步步检查，也不涉及完全、部分和传递函数依赖等概念，可以直接判断一个1NF的关系是否属于BCNF。BCNF的定义排除
5、了任何属性(不管是主属性还是非主属性)对码的传递和部分依赖。,由BCNF的定义得到的结论,由BCNF的定义，非平凡的FD:X Y,可以证明下述结论,一个满足BCNF的关系模式有:1.所有非主属性对每一个码都是完全函数依赖，即,若RBCNF,则R2NF。2.所有的主属性对每一个不包含它的码也是完全函数依赖。3.没有任何属性完全函数依赖于非码的任何一组属性。4.若RBCNF,则必有R3NF;反之不一定成立。,BCNF：例1,关系模式SCO(S#,C#,ORDER)，表示学生(S#)选修课程(C#)的名次(ORDER)。每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生，于是有
6、函数依赖：(S#，C#)ORDER(C#，ORDER)S#思考:关系模式SCO的码是?属于BCNF吗？属于3NF吗?为什么?,关于BCNF的结论,1.全码关系模式属于BCNF。没有以非码属性作为决定因素的函数依赖2.二目关系模式属于BCNF。如果有函数依赖,则其左部一定含码3.不存在函数依赖的关系模式属于BCNF。没有函数依赖4.若R属于BCNF，那么R也属于3NF。5.若R属于3NF，但R不一定属于BCNF。,范式：综合例,设有关系模式 R U=A,B,C,D,E F=ABC,BD,CE,ECB,ACB 要讨论范式，首先确定码。R的候选码:AB,AC;主属性:A,B,C;非主属性:D,E。R
7、 BCNF EC B的决定因素EC不包含码。R 3NF 存在非主属性E对码AB的传递依赖：ABC,CAB,CE,E C R 2NF 存在非主属性D对码AB的部分依赖 AB D。R 1NF,P,范式：综合例(续),关系模式 R U=A,B,C,D,E F=ABC,BD,CE,ECB,ACB R的候选码:AB,AC。R 1NF。,将 R规范化(分解)为 BCNF 模式集：R1(A,B,C;AB C,AC B)BCNF R2(B,D;B D)BCNF R3(B,C,E;C E,EC B)BCNF,5.2.8 4NF,定义5.10 关系模式R 1NF，如果对于R的每个非平凡多值依赖XY(YX)，X都含
8、有码，则称R4NF。说明：1.定义中的F是数据依赖集,包括FD和MVD;当F只包含FD时,4NF的定义就是BCNF的定义。2.4NF是BCNF的推广,适用于具有多值依赖的关系模式。3.4NF的定义就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖的存在。,4NF定义的说明,4.由定义可知,若XY 是平凡的多值依赖,则不要求X包含码。5.由定义可知,若R 4NF,则必有R BCNF;反之不成立(因为函数依赖是多值依赖的特例)。思考:1.任何一个二目关系模式R(A,B)属于4NF吗？2.全码关系模式属于4NF吗？,是,否，如 WSC关系,非4NF转为4NF,例2的关系模式 WSC，有W
9、S，WC，码为(W,S,C),所以 WSC4NF,但 WSC BCNF。如果仓库Wi有n个保管员，存放m件商品，则关系中分量为Wi的元组共有mn个，每个保管员重复存储m次,每种商品重复存储n次,数据冗余非常大。增删也不便,增加商品,取消保管员都必须增删若干元组。分解改造:将WSC分解为WS(W，S)和WC(W，C)分解后的关系模式都属于4NF，因为只有平凡的多值依赖WS和WC，满足4NF的定义。,范式盘点,1.一个全是主属性的关系模式一定可以达到3NF。2.一个全码的关系模式一定可以达到BCNF。3.一个二目关系模式一定可以达到4NF。4.函数依赖和多值依赖是两种重要的数据依赖。在函数依赖的范
10、畴内,BCNF是最高级别的范式。如果考虑多值依赖,则4NF是最高的范式级别。5.除FD和MVD外，还有其他数据依赖，如连接依赖，在连接依赖的概念上还可以定义5NF的范式级别。,范式之间的关系,1NF,5.2.9 规范化小结,1.规范化的目的 有些关系模式存在“插入异常,更新异常,删除异常,数据冗余大”的问题-不好的模式寻求解决这些问题的方法-规范化的目的2.规范化的基本思想 概念的单一化逐步消除数据依赖中不合适的部分,使关系模式达到某种程度的分离,即“一事一地”的模式设计原则3.各种范式及规范化的过程1NF 2NF 3NF BCNF 4NF,规范化小结(续),4.关系模式的规范化过程是通过对关
11、系模式的投影分解来实现的,把低一级的关系模式分解为若干高一级的关系模式,分解不是唯一的。后面还介绍分解算法。5.规范化理论为数据库模式设计提供了理论指南和工具,但仅仅是指南和工具。并不是规范化程度越高越好。规范化程度高,可解决更新异常和冗余大的问题,但会失去检索查询方便快速的优点,增加(自然)连接运算的开销。必须结合应用环境和具体情况合理选择DB模式,经常用于检索查询的系统,宁肯规范化程度低些。,补充：候选码的求解算法,设关系模式R(1)将R的所有属性分为 L、R、N和 LR四类，并令X代表L、N两类，Y代表LR类。L类:仅出现在F的函数依赖左部的属性；R类:.右；N类:在F的函数依赖左右两边
12、都不出现的属性；LR类:都出现的属性。(2)求属性集闭包X+，若 X+包含了R的全部属性则X即为R的唯一候选码,转(5);,候选码的求解算法(续),(3)否则,在Y中取一属性A，求属性集闭包(XA)+，若(XA)+包含了R的全部属性，则转(4)；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。(4)如果已找出了所有的候选码，则转(5)；否则在Y中依次取2个、3个、属性，求X与它们的属性集闭包，直到其闭包包含R的全部属性。(5)停止，输出结果。,候选码的求解：例1,设关系模式R(A,B,C,D),其函数依赖集：F=DB,BD,ADB,ACD 求R的所有候选码。解:L类:A,C R类:N
13、类:LR类:B,D因为(AC)F+=ACDB，所以AC是R的唯一候选码。,候选码的求解：例2,设关系模式R(A,B,C,D,E,P),其函数依赖集：F=AD,ED,DB,BCD,DCA 求R的所有候选码。解:L类:C,E R类:N类:P LR类:A,B,D因为(CEP)F+=CEPDBA，所以CEP是R的唯一候选码。,候选码的求解：例3,设关系模式R(S,D,I,B,O,Q),其函数依赖集:F=SD,IB,BO,OQ,QI 求R的所有候选码。解:L类(S);R类(D);N类(无);LR类(I,B,O,Q)因为S+=SD,所以S不是R的候选码；因为(SI)+=SIDBOQ，所以SI是一个候选码；
14、因为(SB)+=SBDOQI，所以SB也是一个候选码；因为(SO)+=SODQIB，所以SO也是一个候选码；因为(SQ)+=SQDIBO，所以SQ也是一个候选码。,第5章 补充作业题,1.设关系模式 R,U=A,B,C,D,E,H,F=ADBC,BEC,CH 求出R的所有候选码。2.判断下面的函数依赖集是否最小。F=ADBC,BEC,CH 3.设关系模式 R,U=A,B,C,D,F=AC,CA,BAC,DAC,BDA(1)求R的所有候选码；(2)确定R的范式级别；(3)求Fmin；(4)将R分解为3NF的模式集。4.判断下面分解的无损连接性：R(A,B,C,D),F=ABC,CA,CD，=ACD,BC。,
