求候选码的方法

第五章关系数据理论《数据库系统概论》26.2.2码(参见P173.)定义5.4设K为关系模式RU,F的属性(组)，若KU，则称K为R的候选码。f主码：若RU,F有多个候选码，则可以从中选定一个作为R的主码。主属性：包含在任一个候选码中的属性，称作主属性。非主属性：不包含在任一个候选码中的属性，称作非主属性(或非码属性)。全码：关系模式的码由全部属性构成。3码:例关系模式S(S#,SN,SD,DEAN,C#,G)码的确定(1)首先根据实际背景数据约束的语义确定关系模式RU,F。(2)然后应用函数依赖的公理系统，验证F中每一个函数依赖的决定因素或其组合K，是否有:KU。ff主码(S#，C#)，因为(S#，C#)所有属性4码的确定:例求出关系模式RU,F的所有候选码：U={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}注:码或者是某一函数依赖的左部,或是一个属性组。验证AB是否码,须证明ABABCDE是否成立?∵AB→C(已知),而AB→AB(自反),∴AB→ABC(合并)∵B→D(已知),∴AB→AD(增广),∴AB→ABCD(合并)∵C→E(已知),AB→C(已知),∴AB→E(传递)于是AB→ABCDE(合并)f5码的确定:例(续)验证AB是否码?前面已得到AB→ABCDE，又,显然A→ABCDE,B→ABCDE,故所以ABABCDE。得证AB是一个候选码。同理可证：AC也是一个候选码。说明：如果每一个FD的决定因素都不是码，则要考虑这些决定因素的组合是否构成码；除了码的定义外，有候选码的求解理论和算法，在后面可以补充介绍更好的求码方法。f6码的确定:练习根据码的定义，求关系模式RU,F的所有候选码。U={A,B,C,D}，F={A→B,C→B}答：ACD7关于2NF的结论1.不存在非主属性的关系模式属于2NF。没有非主属性2.全码关系模式属于2NF。没有非主属性3.码只由一个属性组成的关系模式属于2NF。不会有部分依赖4.二目关系模式属于2NF。码或是一个属性，或是全码5.若R属于1NF，但R不一定属于2NF。例如,关系模式S(S#,SN,SD,DEAN,C#,G)8关于3NF的结论1.不存在非主属性的关系模式属于3NF。没有非主属性2.全码关系模式属于3NF。没有非主属性3.二目关系模式属于3NF。不会存在传递依赖4.若R属于3NF，那么R也属于2NF。可证明，反证5.若R属于2NF，但R不一定属于3NF。例如，关系模式S_SD(S#,SN,SD,DEAN)9BCNF:定义定义5.8关系模式RU,F1NF，对于属性组X和Y，若XY且YX时X必含有码，则RU,FBCNF。注意到：BCNF的定义更简单，不需要从1NF到2NF再到3NF再到BCNF一步步检查，也不涉及完全、部分和传递函数依赖等概念，可以直接判断一个1NF的关系是否属于BCNF。BCNF的定义排除了任何属性(不管是主属性还是非主属性)对码的传递和部分依赖。由BCNF的定义得到的结论由BCNF的定义，非平凡的FD:X→Y非主属性主属性含码K，或X即码可以证明下述结论,一个满足BCNF的关系模式有:1.所有非主属性对每一个码都是完全函数依赖，即,若RBCNF,则R2NF。2.所有的主属性对每一个不包含它的码也是完全函数依赖。3.没有任何属性完全函数依赖于非码的任何一组属性。4.若RBCNF,则必有R3NF;反之不一定成立。11BCNF：例1关系模式SCO(S#,C#,ORDER)，表示学生(S#)选修课程(C#)的名次(ORDER)。每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生，于是有函数依赖：(S#，C#)ORDER(C#，ORDER)S#思考:关系模式SCO的码是?属于BCNF吗？属于3NF吗?为什么?12关于BCNF的结论1.全码关系模式属于BCNF。没有以非码属性作为决定因素的函数依赖2.二目关系模式属于BCNF。如果有函数依赖,则其左部一定含码3.不存在函数依赖的关系模式属于BCNF。没有函数依赖4.若R属于BCNF，那么R也属于3NF。5.若R属于3NF，但R不一定属于BCNF。13范式：综合例设有关系模式RU,FU={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}要讨论范式，首先确定码。R的候选码:AB,AC;主属性:A,B,C;非主属性:D,E。RBCNF∵EC→B的决定因素EC不包含码。R3NF∵存在非主属性E对码AB的传递依赖：ABC,CAB,CE,ECR2NF∵存在非主属性D对码AB的部分依赖AB→D。R1NFP14范式：综合例(续)关系模式RU,FU={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}R的候选码:AB,AC。R1NF。将R规范化(分解)为BCNF模式集：R1(A,B,C;AB→C,AC→B)BCNFR2(B,D;B→D)BCNFR3(B,C,E;C→E,EC→B)BCNF155.2.84NF定义5.10关系模式RU,F1NF，如果对于R的每个非平凡多值依赖XY(YX)，X都含有码，则称R4NF。说明：1.定义中的F是数据依赖集,包括FD和MVD;当F只包含FD时,4NF的定义就是BCNF的定义。2.4NF是BCNF的推广,适用于具有多值依赖的关系模式。3.4NF的定义就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖的存在。164NF定义的说明4.由定义可知,若XY是平凡的多值依赖,则不要求X包含码。5.由定义可知,若R4NF,则必有RBCNF;反之不成立(因为函数依赖是多值依赖的特例)。思考:1.任何一个二目关系模式R(A,B)属于4NF吗？2.全码关系模式属于4NF吗？是否，如WSC关系17非4NF转为4NF例2的关系模式WSC，有WS，WC，码为(W,S,C),所以WSC4NF,但WSCBCNF。如果仓库Wi有n个保管员，存放m件商品，则关系中分量为Wi的元组共有m×n个，每个保管员重复存储m次,每种商品重复存储n次,数据冗余非常大。增删也不便,增加商品,取消保管员都必须增删若干元组。分解改造:将WSC分解为WS(W，S)和WC(W，C)分解后的关系模式都属于4NF，因为只有平凡的多值依赖WS和WC，满足4NF的定义。18范式盘点1.一个全是主属性的关系模式一定可以达到3NF。2.一个全码的关系模式一定可以达到BCNF。3.一个二目关系模式一定可以达到4NF。4.函数依赖和多值依赖是两种重要的数据依赖。在函数依赖的范畴内,BCNF是最高级别的范式。如果考虑多值依赖,则4NF是最高的范式级别。5.除FD和MVD外，还有其他数据依赖，如连接依赖，在连接依赖的概念上还可以定义5NF的范式级别。19范式之间的关系1NF2NF消除非主属性对码的部分函数依赖4NF消除非平凡且非函数依赖的多值依赖消除主属性对码的部分和传递函数依赖BCNF3NF消除非主属性对码的传递函数依赖消除非平凡且非FD的MVD消除决定因素非码的非平凡的FD205.2.9规范化小结1.规范化的目的有些关系模式存在“插入异常,更新异常,删除异常,数据冗余大”的问题---不好的模式寻求解决这些问题的方法---规范化的目的2.规范化的基本思想概念的单一化逐步消除数据依赖中不合适的部分,使关系模式达到某种程度的分离,即“一事一地”的模式设计原则3.各种范式及规范化的过程1NF2NF3NFBCNF4NF21规范化小结(续)4.关系模式的规范化过程是通过对关系模式的投影分解来实现的,把低一级的关系模式分解为若干高一级的关系模式,分解不是唯一的。后面还介绍分解算法。5.规范化理论为数据库模式设计提供了理论指南和工具,但仅仅是指南和工具。并不是规范化程度越高越好。规范化程度高,可解决更新异常和冗余大的问题,但会失去检索查询方便快速的优点,增加(自然)连接运算的开销。必须结合应用环境和具体情况合理选择DB模式,经常用于检索查询的系统,宁肯规范化程度低些。22补充：候选码的求解算法设关系模式RU,F(1)将R的所有属性分为L、R、N和LR四类，并令X代表L、N两类，Y代表LR类。L类:仅出现在F的函数依赖左部的属性；R类:………………………...右…………；N类:在F的函数依赖左右两边都不出现的属性；LR类:…………………………都出现的属性。(2)求属性集闭包X+，若X+包含了R的全部属性则X即为R的唯一候选码,转(5);23候选码的求解算法(续)(3)否则,在Y中取一属性A，求属性集闭包(XA)+，若(XA)+包含了R的全部属性，则转(4)；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。(4)如果已找出了所有的候选码，则转(5)；否则在Y中依次取2个、3个、…属性，求X与它们的属性集闭包，直到其闭包包含R的全部属性。(5)停止，输出结果。24候选码的求解：例1设关系模式R(A,B,C,D),其函数依赖集：F={D→B,B→D,AD→B,AC→D}求R的所有候选码。解:L类:A,CR类:N类:LR类:B,D因为(AC)F+=ACDB，所以AC是R的唯一候选码。25候选码的求解：例2设关系模式R(A,B,C,D,E,P),其函数依赖集：F={A→D,E→D,D→B,BC→D,DC→A}求R的所有候选码。解:L类:C,ER类:N类:PLR类:A,B,D因为(CEP)F+=CEPDBA，所以CEP是R的唯一候选码。26候选码的求解：例3设关系模式R(S,D,I,B,O,Q),其函数依赖集:F={S→D,I→B,B→O,O→Q,Q→I}求R的所有候选码。解:L类(S);R类(D);N类(无);LR类(I,B,O,Q)因为S+=SD,所以S不是R的候选码；因为(SI)+=SIDBOQ，所以SI是一个候选码；因为(SB)+=SBDOQI，所以SB也是一个候选码；因为(SO)+=SODQIB，所以SO也是一个候选码；因为(SQ)+=SQDIBO，所以SQ也是一个候选码。第5章补充作业题1.设关系模式RU,F,U={A,B,C,D,E,H},F={AD→BC,BE→C,C→H}求出R的所有候选码。2.判断下面的函数依赖集是否最小。F={AD→BC,BE→C,C→H}3.设关系模式RU,F,U={A,B,C,D},F={A→C,C→A,B→AC,D→AC,BD→A}(1)求R的所有候选码；(2)确定R的范式级别；(3)求Fmin；(4)将R分解为3NF的模式集。4.判断下面分解的无损连接性：R(A,B,C,D),F={AB→C,C→A,CD}，ρ={ACD,BC}。