求候选码的方法PPT学习课件.ppt

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