求候选码的方法

1、第五章第五章 关系关系数据理论数据理论 数据库系统概论数据库系统概论26.2.2 码码(参见参见P173.P173.)定义定义5.45.4 设设K K为关系模式为关系模式RR的属性的属性( (组组) )， 若若K UK U，则称则称K K为为R R的的候选码。候选码。 f主码主码：若：若RR有多个候选码，则可以从中选定一个作为有多个候选码，则可以从中选定一个作为R R的主码。的主码。主属性主属性：包含在任一个候选码中的属性，称作主属性。：包含在任一个候选码中的属性，称作主属性。非主属性非主属性：不包含在任一个候选码中的属性，称作非主属性：不包含在任一个候选码中的属性，称作非主属性(或或非码属性

2、非码属性)。全码全码：关系模式的码由全部属性构成。：关系模式的码由全部属性构成。3码码: 例例n关系模式关系模式 S(S# , SN , SD , DEAN , C# , G) 码的确定码的确定(1) (1) 首先根据实际背景数据约束的语义确定关首先根据实际背景数据约束的语义确定关系模式系模式RR。(2) (2) 然后应用然后应用函数依赖的公理系统，验证函数依赖的公理系统，验证F F中中每一个函数依赖的决定因素或其组合每一个函数依赖的决定因素或其组合K K，是是否有否有: : K U K U。 f fn主码主码( (S#S#，C#)C#)，因为因为(S#(S#，C#) C#) 所有属性所有属性

3、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

4、(已知已知), ABC(已知已知), AB E(传递传递) 于是于是 AB ABCDE(合并合并)f5码的确定码的确定: 例例(续续)n验证验证ABAB是否码是否码? ? 前面已得到前面已得到 AB ABCDE， 又又, 显然显然 AABCDE, BABCDE, 故所以故所以AB ABCDE。得证得证AB是一个候选码。是一个候选码。n同理可证：同理可证：AC也是一个候选码。也是一个候选码。n说明：如果每一个说明：如果每一个FD的决定因素都不是码，的决定因素都不是码，则要考虑这些决定因素的组合是否构成码；则要考虑这些决定因素的组合是否构成码；除了码的定义外，有候选码的求解理论和算除了码的定义外，

5、有候选码的求解理论和算法，在后面可以补充介绍更好的求码方法。法，在后面可以补充介绍更好的求码方法。f6码的确定码的确定: 练习练习n根据码的定义，求关系模式根据码的定义，求关系模式R的所有候的所有候选码。选码。U= A , B , C , D ， F=A B, CB 答：答：ACD7关于关于2NF的结论的结论n1. 不存在非主属性的关系模式属于不存在非主属性的关系模式属于2NF。 n没有非主属性没有非主属性n2. 全码关系模式属于全码关系模式属于2NF。 n没有非主属性没有非主属性n3. 码只由一个属性组成的关系模式属于码只由一个属性组成的关系模式属于2NF。n不会有部分依赖不会有部分依赖n4

6、. 二目关系模式属于二目关系模式属于2NF。 n码或是一个属性，或是全码码或是一个属性，或是全码n5. 若若R属于属于1NF，但但R不一定属于不一定属于2NF。 n例如例如, 关系模式关系模式 S(S#, SN, SD, DEAN, C#, G)8关于关于3NF的结论的结论n1. 不存在非主属性的关系模式属于不存在非主属性的关系模式属于3NF。 n没有非主属性没有非主属性n2. 全码关系模式属于全码关系模式属于3NF。 n没有非主属性没有非主属性n3. 二目关系模式属于二目关系模式属于3NF。 n不会存在传递依赖不会存在传递依赖n4. 若若R属于属于3NF，那么那么R也属于也属于2NF。 n可

7、证明，反证可证明，反证n5. 若若R属于属于2NF，但但R不一定属于不一定属于3NF。 n例如，关系模式例如，关系模式 S_SD(S#, SN, SD, DEAN)9BCNF: 定义定义n定义定义5.85.8 关系模式关系模式R R 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一步步检查，也不一步步检查，也不涉及完全、部分和传递函数依赖等概念

8、，可涉及完全、部分和传递函数依赖等概念，可以以直接判断一个直接判断一个1 1NFNF的关系是否属于的关系是否属于BCNFBCNF。nBCNF的定义排除了任何属性的定义排除了任何属性(不管是主属性不管是主属性还是非主属性还是非主属性)对码的传递和部分依赖。对码的传递和部分依赖。由由BCNF的定义得到的结论的定义得到的结论n由由BCNF的定义，非平凡的的定义，非平凡的FD: X Y非主属性非主属性主属性主属性含码含码K，或或X即码即码n可以证明下述结论可以证明下述结论, 一个满足一个满足BCNF的关系模式有的关系模式有:n1. 所有非主属性对每一个码都是完全函数依赖，所有非主属性对每一个码都是完全

9、函数依赖， 即即, 若若R BCNF, 则则R 2NF。n2. 所有的主属性对每一个不包含它的码也是完全所有的主属性对每一个不包含它的码也是完全函数依赖。函数依赖。n3. 没有任何属性完全函数依赖于非码的任何一组没有任何属性完全函数依赖于非码的任何一组属性。属性。n4. 若若R BCNF, 则必有则必有R 3NF; 反之不一定成立。反之不一定成立。11BCNF：例例1n关系模式关系模式SCO(S#, C#, ORDER)，表示学生，表示学生(S#)选修课程选修课程(C#)的名次的名次(ORDER)。n每一个学生选修每门课程的成绩有一定的名每一个学生选修每门课程的成绩有一定的名次，每门课程中每一

10、名次只有一个学生，于次，每门课程中每一名次只有一个学生，于是有函数依赖：是有函数依赖： (S#，C#) ORDER (C#，ORDER) S#n思考思考: 关系模式关系模式SCO的码是的码是? 属于属于BCNF吗？属于吗？属于3NF吗吗? 为什么为什么?12关于关于BCNF的结论的结论n1. 全码关系模式属于全码关系模式属于BCNF。n没有以非码属性作为决定因素的函数依赖没有以非码属性作为决定因素的函数依赖n2. 二目关系模式属于二目关系模式属于BCNF。n如果有函数依赖如果有函数依赖, 则其左部一定含码则其左部一定含码n3. 不存在函数依赖的关系模式属于不存在函数依赖的关系模式属于BCNF。

11、n没有函数依赖没有函数依赖n4. 若若R属于属于BCNF，那么那么R也属于也属于3NF。 n5. 若若R属于属于3NF，但但R不一定属于不一定属于BCNF。 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的传递依赖：的传递依

12、赖： ABC , CAB , CE, E C nR 2NF 存在非主属性存在非主属性D对码对码AB的部分依赖的部分依赖 AB D。nR 1NFP14范式：综合例范式：综合例(续续) 关系模式关系模式 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) BCNF155.2.8 4NFn定义定义5.1

13、0 关系模式关系模式R 1NF，如如果果 对 于对 于 R 的 每 个 非 平 凡 多 值 依 赖的 每 个 非 平 凡 多 值 依 赖XY(Y X)，X都含有码都含有码，则称，则称R 4NF。n说明：说明：1. 定义中的定义中的F是数据依赖集是数据依赖集, 包括包括FD和和MVD; 当当F只只包含包含FD时时, 4NF的定义就是的定义就是BCNF的定义。的定义。2. 4NF是是BCNF的推广的推广, 适用于具有多值依赖的关系适用于具有多值依赖的关系模式。模式。3. 4NF的定义就是限制关系模式的属性之间不允许的定义就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖的存在。有非平凡

14、且非函数依赖的多值依赖的存在。164NF定义的说明定义的说明4. 由定义可知由定义可知, 若若XY 是平凡的多值依赖是平凡的多值依赖, 则不则不要求要求X包含码包含码。5. 由定义可知由定义可知, 若若R 4NF, 则必有则必有R BCNF; 反之反之不成立不成立(因为函数依赖是多值依赖的特例因为函数依赖是多值依赖的特例)。n思考思考: 1. 任何一个二目关系模式任何一个二目关系模式R(A, B)属于属于4NF吗？吗？2. 全码关系模式属于全码关系模式属于4NF吗？吗？是是否，如否，如 WSC关系关系 17非非4NF转为转为4NFn例例2的关系模式的关系模式 WSC，有有WS，WC，码为码为(

15、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，因为因为只有平凡的多只有平凡的多值依

16、赖值依赖WS和和WC，满足满足4NF的定义。的定义。18范式盘点范式盘点 1. 一个全是主属性的关系模式一定可以达到一个全是主属性的关系模式一定可以达到3NF。 2. 一个全码的关系模式一定可以达到一个全码的关系模式一定可以达到BCNF。 3. 一个二目关系模式一定可以达到一个二目关系模式一定可以达到4NF。 4. 函数依赖和多值依赖是两种重要的数据依赖。函数依赖和多值依赖是两种重要的数据依赖。在函在函数依赖的范畴内数依赖的范畴内, BCNF是最高级别的范式。是最高级别的范式。如果考如果考虑多值依赖虑多值依赖, 则则4NF是最高的范式级别。是最高的范式级别。 5. 除除FD和和MVD外，还有其

17、他数据依赖，如外，还有其他数据依赖，如连接依赖连接依赖，在连接依赖的概念上还可以定义在连接依赖的概念上还可以定义5NF的范式级别。的范式级别。19范式之间的关系范式之间的关系1 1NFNF2 2NFNF消除非主属性对码的消除非主属性对码的部分函数依赖部分函数依赖4 4NFNF消除非平凡且非函数消除非平凡且非函数依赖的多值依赖依赖的多值依赖消除主属性对码的部消除主属性对码的部分和传递函数依赖分和传递函数依赖BCNFBCNF3 3NFNF消除非主属性对码的消除非主属性对码的传递函数依赖传递函数依赖消除非消除非平凡且平凡且非非FDFD的的MVDMVD消除决消除决定因素定因素非码的非码的非平凡非平凡的

18、的FDFD205.2.9 规范化小结规范化小结n1. 规范化的目的规范化的目的 n有些关系模式存在有些关系模式存在“插入异常插入异常, 更新异常更新异常, 删删除异常除异常, 数据冗余大数据冗余大”的问题的问题 - 不好的模式不好的模式n寻求解决这些问题的方法寻求解决这些问题的方法 - 规范化的目的规范化的目的n2. 规范化的基本思想规范化的基本思想 n概念的单一化概念的单一化n逐步消除数据依赖中不合适的部分逐步消除数据依赖中不合适的部分, 使关系模式达使关系模式达到某种程度的分离到某种程度的分离, 即即“一事一地一事一地”的模式设计原的模式设计原则则n3. 各种范式及规范化的过程各种范式及规

19、范化的过程n1NF 2NF 3NF BCNF 4NF21规范化小结规范化小结(续续)n4. 关系模式的规范化过程是通过对关系模式的关系模式的规范化过程是通过对关系模式的投影分投影分解解来实现的来实现的, 把低一级的关系模式分解为若干高一级把低一级的关系模式分解为若干高一级的关系模式的关系模式, 分解不是唯一的。分解不是唯一的。后面还介绍分解算法。后面还介绍分解算法。n5. 规范化理论为数据库模式设计提供了理论指南和工规范化理论为数据库模式设计提供了理论指南和工具具, 但仅仅是指南和工具。但仅仅是指南和工具。并不是规范化程度越高越并不是规范化程度越高越好。好。n规范化程度高规范化程度高, 可解决

20、更新异常和冗余大的问题可解决更新异常和冗余大的问题, 但但会失去检索查询方便快速的优点会失去检索查询方便快速的优点, 增加增加(自然自然)连接连接运算的开销。运算的开销。n必须结合应用环境和具体情况合理选择必须结合应用环境和具体情况合理选择DB模式模式, 经经常用于检索查询的系统常用于检索查询的系统, 宁肯规范化程度低些。宁肯规范化程度低些。22补充：候选码的求解算法补充：候选码的求解算法 设关系模式设关系模式RRn(1) (1) 将将R R的所有属性分为的所有属性分为 L L、 R R、NN和和 LRLR四类，四类，并令并令X X代表代表L L、NN两类，两类，Y Y代表代表LRLR类。类。

21、 L类类: 仅出现在仅出现在F的函数依赖左部的属性；的函数依赖左部的属性； R类类: .右右； N类类: 在在F的函数依赖左右两边都不出现的属性；的函数依赖左右两边都不出现的属性； LR类类: 都出现的属性都出现的属性 。 n(2) (2) 求属性集闭包求属性集闭包X X+ +，若若 X X+ +包含了包含了R R的全部属的全部属性则性则X X即为即为R R的唯一候选码的唯一候选码, , 转转(5);(5);23候选码的求解算法候选码的求解算法(续续) (3) (3) 否则否则, , 在在Y Y中取一属性中取一属性A A，求求属性集闭包属性集闭包( (XA)XA)+ +，若，若( (XA)XA

22、)+ +包含了包含了R R的全部属性，则转的全部属性，则转(4)(4)；否则，调换一属性反复进行这一过程，直到否则，调换一属性反复进行这一过程，直到试完所有试完所有Y Y中的属性。中的属性。 (4) (4) 如果已找出了所有的候选码，则转如果已找出了所有的候选码，则转(5)(5)；否；否则在则在Y Y中依次取中依次取2 2个、个、3 3个、个、属性，求属性，求X X与它与它们的属性集闭包，直到其闭包包含们的属性集闭包，直到其闭包包含R R的全部属的全部属性。性。 (5) (5) 停止，输出结果。停止，输出结果。24候选码的求解：例候选码的求解：例1n设关系模式设关系模式R(A, B, C, D

23、), 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的唯一候选的唯一候选码。码。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