1、1数据库技术及应用第三章关系数据库的规范化理论第三章关系数据库的规范化理论23.1 关系模式的冗余和异常问题n范式（范式（Normal Form）：）：是指规范化的关系模式。是指规范化的关系模式。n第一范式（第一范式（1NF）：）：由满足最基本规范化的关系模式。由满足最基本规范化的关系模式。n第一范式的关系模式再满足另外一些约束条件就产生了第第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、二范式、第三范式、BC范式等等。范式等等。n一个低一级的关系范式通过模式分解可以转换成若干高一一个低一级的关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的
2、规范化级范式的关系模式的集合，这种过程叫关系模式的规范化（Normalization）。）。3二、二、关系模式规范化的必要性关系模式规范化的必要性1.关系模式应满足的基本要求1)元组的每个分量必须是不可分的数据项。元组的每个分量必须是不可分的数据项。2)数据库中的数据冗余应尽可能少。数据库中的数据冗余应尽可能少。数据量巨增，系统负担过重，浪费存储空间，造成数据的不完整。数据量巨增，系统负担过重，浪费存储空间，造成数据的不完整。3)关系数据库不能因为数据更新操作而引起数据不一致问关系数据库不能因为数据更新操作而引起数据不一致问题。题。（数据冗余）（数据冗余）4)当执行数据插入操作时，数据库中的数
3、据不能产生插入当执行数据插入操作时，数据库中的数据不能产生插入异常现象。异常现象。数据库中的数据因不能满足某种完整性要求而不能正常地插入到数数据库中的数据因不能满足某种完整性要求而不能正常地插入到数据库中。据库中。5)数据库中的数据不能在执行删除操作时产生删除异常问数据库中的数据不能在执行删除操作时产生删除异常问题。题。删除某种信息的同时，把其他信息也删除了。多种信息捆绑在一起。删除某种信息的同时，把其他信息也删除了。多种信息捆绑在一起。4关系中每一个分量都必须是不可分的数据项。v判断是否为关系的标准判断是否为关系的标准v关系的一切数学理论都是基于关系服从关系的一切数学理论都是基于关系服从1N
4、F1NF。姓名所在系成绩C数据库李明计算机6578姓名所在系C成绩数据库成绩李明计算机6578修改后的数据结构：修改后的数据结构：将大大增加关将大大增加关系操作的表达、系操作的表达、优化及执行的优化及执行的复杂度。复杂度。56)数据库设计应考虑数据库设计应考虑查询要求查询要求，数据组织应合理。，数据组织应合理。在数据库设计时，不仅要考虑到自身结构的完整性，还在数据库设计时，不仅要考虑到自身结构的完整性，还要考虑到数据的使用要求。要考虑到数据的使用要求。为了使数据查询方便、数据处理简便，有必要通过为了使数据查询方便、数据处理简便，有必要通过视视图、索引和适当增加数据冗余图、索引和适当增加数据冗余
5、的方法。的方法。62.关系中异常和冗余问题关系中异常和冗余问题数据冗余大；数据冗余大；插入异常；插入异常；删除异常；删除异常；更新异常。更新异常。dwbmdwmcWzbmWzmcRqJldwPriceQlssfs0101一分厂一车间02010125铜管材2002/12/01根90550101一分厂一车间010401锆美合金2002/12/01Kg12001080101一分厂一车间010101铍铜合金2002/12/02Kg80020200101一分厂一车间02010220铜管材2002/12/02根80550101一分厂一车间02010125铜管材2002/12/02根9010100102一分
6、厂二车间010301铅锑合金2002/12/02Kg1000880102一分厂二车间02010125铜管材2002/12/02根90330221二分厂生产科02010125铝管材2002/12/02根70201573.模式分解是关系规范化的主要方法模式分解是关系规范化的主要方法 按“一事一地”的原则分解成“单位”、“物资”和“领料”三个关系，其关系模式为：单位（单位编码单位编码，单位名称，单位名称）物资（物资编码物资编码，物资名称，计量单位，价格，物资名称，计量单位，价格）领料（单位编码，物资编码，领料时间单位编码，物资编码，领料时间，请领量，实，请领量，实发量发量）关系模式:物资领料（单位编
7、码单位编码，单位名称，单位名称，物资编码物资编码，物资名，物资名称，称，领料时间领料时间，计量单位，价格，请领量，实发量）。，计量单位，价格，请领量，实发量）。8学号姓名年龄性别系名系主任课程名成绩98001李华20男计算机系王民程序设计8898001李华20男计算机系王民数据结构7498001李华20男计算机系王民数据库8298001李华20男计算机系王民电路6598002张平21女计算机系王民程序设计9298002张平21女计算机系王民数据结构8298002张平21女计算机系王民数据库7898002张平21女计算机系王民电路8398003陈兵20男数学系赵敏高等数学7298003陈兵20男
8、数学系赵敏数据结构9498003陈兵20男数学系赵敏数据库8398003陈兵20男数学系赵敏离散数学87学生学生(学号，姓名，年龄，性别，系名称学号，姓名，年龄，性别，系名称)；教学系教学系(系名，系主任系名，系主任)；选课选课(学号，课程名，成绩学号，课程名，成绩).93.2 函数依赖函数依赖1.关系模式的简化表示法关系模式的简化表示法关系模式的完整表示是一个五元组：R(U，D，Dom，F).其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。关系模式可以用三元组来为：R(U，F)数据依赖集函数依赖（Functional Dep
9、endency）多值依赖（Multivalued Dependency）连接依赖(Join Dependency)102.函数依赖的概念函数依赖的概念v 设设R R（U U）是属性集）是属性集U U上的关系模式，上的关系模式，X X、Y Y是是U U的子集。若对于的子集。若对于R R（U U）的任意一个可能的关系）的任意一个可能的关系r r，r r中的任一元组中的任一元组在在X X中的属中的属性值确定后性值确定后，则在，则在Y Y中的属性值中的属性值也必确定。则称也必确定。则称X X函数决定函数决定Y Y，或或Y Y函数依赖于函数依赖于X X，记作，记作XYXY。XY，但Y X，则称XY是非平
10、凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。XY，但YX，则称XY是平凡的函数依赖。若XY，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。若XY，YX，则记作XY。若Y不函数依赖于X，则记作X Y。函数依赖是数据依赖的一种，实际上它函数依赖是数据依赖的一种，实际上它描述的是描述的是同一同一关系中属性关系中属性间的联系。间的联系。11例例3，对于教学关系模式：教学（，对于教学关系模式：教学（U，F）；）；U=学号，姓名，年龄，性别，系名，系主任，课程名，成绩学号，姓名，年龄，性别，系名，系主任，课程名，成绩；例1：物资（物资编码物资编码，物资名称，计
11、量单位，价格，物资名称，计量单位，价格）属性“物资编码物资编码”和和“物资名称物资名称”间有函数依赖关系，间有函数依赖关系，物资编码的值确定，物资名称的值也惟一确定。物资编码的值确定，物资名称的值也惟一确定。称称 “物资编码物资编码”函数决定函数决定“物资名称物资名称”或或 “物资名称物资名称”函数依赖于函数依赖于“物资编码物资编码”。例2：领料（单位编码，物资编码，领料时间单位编码，物资编码，领料时间，请领量，实发量，请领量，实发量）F=学号学号姓名，学号姓名，学号年龄，学号年龄，学号性别，学号性别，学号系名，系名系名，系名系主任，系主任，(学号，课程名学号，课程名)成绩成绩.“物资编码物资
12、编码”与与“请领量请领量”间没有函数依赖关系。但间没有函数依赖关系。但12注意：注意：函数依赖是函数依赖是语义范畴语义范畴的概念，我们只能根据数据的的概念，我们只能根据数据的语义来确定函数依赖。例如，语义来确定函数依赖。例如，“姓名姓名所在系所在系”这个函这个函数依赖只有在没有同名人的条件下成立。如果有相同名数依赖只有在没有同名人的条件下成立。如果有相同名字的人，则字的人，则“所在系所在系”就不再函数依赖于就不再函数依赖于“姓名姓名”了。了。13完全函数依赖、传递函数依赖v 在在R(U)中，如果中，如果XY，并且对于，并且对于X的任何一个真子集的任何一个真子集X，都有都有X Y，则称，则称Y对
13、对X完全函数依赖完全函数依赖，记作：，记作：XY；若；若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y对对X部分函数依赖部分函数依赖，记作：记作：XY。例例:在教学关系模式：在教学关系模式：(学号，课程名学号，课程名)成绩，成绩，(学号，课程学号，课程名名)姓名姓名.v 在在R(U)中，如果中，如果XY，(Y X)，Y X，YZ，则称，则称Z对对X传递函数依赖。传递函数依赖记作传递函数依赖。传递函数依赖记作X Z。例如，例如，在教学模式中，因为：学号在教学模式中，因为：学号系名，系名系名，系名系主任；系主任；所以：学号所以：学号 系主任。系主任。PffP传递传递14v码码定义定
14、义：设设K为关系模式为关系模式R(U)中的属性或属性组合，若中的属性或属性组合，若KU，则称，则称K为为R的一个的一个候选码候选码。若关系模式有多个候选。若关系模式有多个候选码，则选定其中的一个做为主码（码，则选定其中的一个做为主码（primary key）。）。主属性主属性：包含在任何一个关键字中的属性。：包含在任何一个关键字中的属性。非主属性非主属性：不包含在任何候选码中的属性。：不包含在任何候选码中的属性。在最简单的情况下，候选码只包含一个属性。在最极在最简单的情况下，候选码只包含一个属性。在最极端的情况下，关系模式的所有属性组是这个关系模式的候端的情况下，关系模式的所有属性组是这个关系
15、模式的候选码，称为选码，称为全码全码。15数据依赖引起的主要问题是插入、删除及更新异常等，解数据依赖引起的主要问题是插入、删除及更新异常等，解决的办法是进行决的办法是进行关系模式的合理分解关系模式的合理分解，也就是对关系模式规，也就是对关系模式规范化。范化。范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。满足最低要求满足最低要求的叫第一范式，简称为的叫第一范式，简称为1NF。在第一范式基础上进一步满足。在第一范式基础上进一步满足一些要求的为第二范式，简称为一些要求的为第二范式，简称为2NF。其余以此类推。显然。其余以此类推。显然各种范式之间存在联各种范式之间存在联系
16、。系。通常把某一关系模式通常把某一关系模式R为第为第n范式简记为范式简记为RnNF。NFNFBCNFNFNFNF54321小知识：从小知识：从19711971年起，年起，E E。F F。CoddCodd相继提出了第一范式、第二范式，第相继提出了第一范式、第二范式，第三范式，三范式，CoddCodd与与BoyceBoyce合作提出了合作提出了Boyce Boyce CoddCodd范式，到目前为止，已范式，到目前为止，已提出了第五范式。提出了第五范式。16如果关系模式如果关系模式R R，其所有的属性均为简单属性，其所有的属性均为简单属性，即每个属性都是不可再分的，则称即每个属性都是不可再分的，则
17、称R R属于第一范式，属于第一范式，记作记作R R 1NF1NF。它不允许属性值为元组、数组或某种复合数据等。它不允许属性值为元组、数组或某种复合数据等。仅满足第一范式是不够的，仍然存在异常和冗余问题，需对关系模式继续规范，使之服从更高的范式，才能得到性能较高的关系模式。17 若关系模式若关系模式RlNF，并且每一个，并且每一个非主属性都完全函数非主属性都完全函数依赖于依赖于R的码的码，则，则R 2NF。2NF就是不允许关系模式的非主属性对码的部分依赖。即：XY，其中X是码的真子集，Y是非主属性。显然，码只包含一个属性的关系模式如果属于1NF，那么它一定属于2NF。18例例1：分析关系模式：分
18、析关系模式R（dwbm，wzbm，rq，dwmc，zgld，zgdz，qls，sfs）中的函数依赖：）中的函数依赖：rqdwbmwzbmqlssfszglddwmczgdz图3.2R中的函数依赖19如对关系模式如对关系模式R分解为两个关系模式：分解为两个关系模式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm，dwmc，zgld，zgdz）rqdwbmwzbmrqrq图3.3R1中的函数依赖dwbmzglddwmczgdz图3.4R2中的函数依赖关系分解实际上是把联系不紧密的属性尽量分开关系分解实际上是把联系不紧密的属性尽量分开。20在教学模式中在教学模式中：属性集属性集=学号
19、，姓名，年龄，系名，系主任，课程名，成绩学号，姓名，年龄，系名，系主任，课程名，成绩.函数依赖集函数依赖集=学号学号姓名，学号姓名，学号年龄，学号年龄，学号性别，学号性别，学号系名，系名，系名系名系主任，系主任，(学号，课程名学号，课程名)成绩成绩.主码主码=(学号，课程名学号，课程名).非主属性非主属性=(姓名，年龄，系名，系主任，成绩姓名，年龄，系名，系主任，成绩)。(学号，课程名学号，课程名)姓名，姓名，(学号，课程名学号，课程名)年龄，年龄，(学号，课程号学号，课程号)性别性别，(学号，课程名学号，课程名)系名，系名，(学号，课程名学号，课程名)系主任；系主任；(学号，课程名学号，课程
20、名)成绩成绩.显然，教学模式不服从显然，教学模式不服从2NF，即：教学，即：教学 2NF。PPPPP非主属性对码的函数依赖：非主属性对码的函数依赖：21根据根据2NF的定义，将教学关系模式分解：的定义，将教学关系模式分解：学生系（学号，姓名，性别，年龄，系名，系主任）。学生系（学号，姓名，性别，年龄，系名，系主任）。选课（学号，课程名，成绩）选课（学号，课程名，成绩）问题：问题：满足满足2NF的关系模式是否还存在异常和冗余问题？的关系模式是否还存在异常和冗余问题？22三三.3NF 关系模式关系模式RU，F中若不存在这样的码中若不存在这样的码X、属性组、属性组Y及及非主属性非主属性Z(Z Y)使
21、得使得XY、Y X、YZ成立，则称成立，则称R（U，F）3NF。可以证明，若可以证明，若R 3NF，则，则每一个非主属性既不部分函数依每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。赖于码，也不传递函数依赖于码。分析下面关系模式的范式：分析下面关系模式的范式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm，dwmc，zgld，zgdz）R1 3NF，R2 3NF，对，对R2分解：分解：R21（dwbm，dwmc，zgld）R22（zgld，zgdz）23例例2：学生：学生_系系（学号，姓名，性别，年龄，系名，系主任）。（学号，姓名，性别，年龄，系名，系主任）。学号学号
22、系名，系名系名，系名系主任。则：系主任。则：传递学号学号 系主任系主任如果分解为：如果分解为：学生学生(学号，姓名，年龄，性别，系名学号，姓名，年龄，性别，系名)；教学系教学系(系名，系主任系名，系主任).显然分解后的各子模式均属于显然分解后的各子模式均属于3NF。学生学生_系系 3NF。24说明：1、3NF范式是一个可用的关系模式应满足的最低范式。2、把关系模式分解到第三范式，可以在相当程度上减轻原关系中的异常和信息冗余，但也不能保证完全消除关系模式中的各种异常和信息冗余。要想使数据库性能得到进一步的改善，就要把关系模式进一步规范化。25四四.BCNF（Boyce Codd Normal F
23、orm）n关系模式关系模式R（U，F）1NF。若。若XY（YX）时）时X必含有必含有码，则码，则R（U，F）BCNF。即：关系模式即：关系模式RU，F中，若中，若每一个决定因素都包含码每一个决定因素都包含码，则则RU，F BCNF。n一个满足一个满足BCNF的关系模式有：的关系模式有：1)1)所有所有非主属性非主属性对每一个码都是完全函数依赖。对每一个码都是完全函数依赖。2)2)所有的所有的主属性主属性对每一个不包含它的码，也是完全依赖。对每一个不包含它的码，也是完全依赖。3)3)没有任何属性完全函数依赖于没有任何属性完全函数依赖于非码非码的任何一组属性。的任何一组属性。26例例1：分析下面的
24、关系是否满足：分析下面的关系是否满足BC范式？范式？S11(学号，姓名，所在系学号，姓名，所在系)S12(所在系，系主任姓名所在系，系主任姓名)S2(学号，课程名，成绩学号，课程名，成绩)答：均满足BCNF范式27例例2：关系模式：关系模式SPC(S，C，P)中，中，S是学生，是学生，C表示课程，表示课程，P表示名次。表示名次。语义：语义：每一个学生选修每门课程的成绩有一定的名次，每门每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生课程中每一名次只有一个学生(即没有并列名次即没有并列名次)。由语义。由语义可得到下面的函数依赖：可得到下面的函数依赖：（S，C）P；(C，P
25、)S候选码：候选码：(S，C)与与(C，P)。SPC3NF，而且除，而且除(S，C)与与(C，P)以外没有其它决以外没有其它决定因素，所以定因素，所以SPCBCNF28例例3：关系模式：关系模式STJ(S，T，J)中，中，S表示学生，表示学生，T表示教表示教师，师，J表示课程。表示课程。语义为：每一教师只能讲授一门课程，每门课程由若语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教干教师讲授；每个学生选修某门课程就对应一个固定的教师。师。由语义可以得到由语义可以得到STJSTJ模式的函数依赖为：模式的函数依赖为：F=(SF=(S，J)TJ)T，TJ
26、TJ显然：显然：(S(S，J)J)和和(T(T，S)S)都是关系的码；都是关系的码；关系的主属性集为关系的主属性集为SS，T T，JJ，非主属性为，非主属性为（空（空集）。集）。P P由于由于STJSTJ模式中模式中无非主属性，所以它属于无非主属性，所以它属于3NF3NF；但因为存；但因为存在在TJTJ，由于，由于T T不是码，故不是码，故STJSTJ BCNFBCNF。29 五、五、BCNF和和3NF的比较的比较 1)BCNF1)BCNF不仅强调不仅强调非主属性非主属性对码的完全的直接的依赖，对码的完全的直接的依赖，而且强调而且强调主属性主属性对码的完全的直接的依赖，故对码的完全的直接的依赖
27、，故R R BCNFBCNF，R R一定属于一定属于3NF3NF。2)3NF2)3NF只强调只强调非主属性非主属性对码的完全直接依赖，这样对码的完全直接依赖，这样就可能出现就可能出现主属性对码的部分依赖和传递依赖主属性对码的部分依赖和传递依赖。301NF2NF3NFBCNF削除削除非非主属性对码的主属性对码的部分部分函数依赖函数依赖削除削除非非主属性对码的主属性对码的传递传递函数依赖函数依赖削除削除主属性主属性对码的对码的部分部分和和传递传递函数依赖函数依赖图1各种范式规范化过程各种范式规范化过程31规范化小结：规范化小结：1、在关系数据库中，对关系模式的基本要求是满足第一范、在关系数据库中，
28、对关系模式的基本要求是满足第一范式。这样的关系模式就是合法的、允许的。但是，人们发现式。这样的关系模式就是合法的、允许的。但是，人们发现有些关系模式存在有些关系模式存在插入、删除异常、修改复杂、数据冗余插入、删除异常、修改复杂、数据冗余等等毛病。人们寻求解决问题的方法，这就是规范化的目的。毛病。人们寻求解决问题的方法，这就是规范化的目的。2、规范化的基本思想是逐步、规范化的基本思想是逐步消除数据依赖消除数据依赖中不合适的部分，中不合适的部分，使模式中的各使模式中的各关系模式达到某种程度的关系模式达到某种程度的“分离分离”，即，即“一事一事一地一地”的模式设计原则。让的模式设计原则。让一个关系描
29、述一个概念、一个实一个关系描述一个概念、一个实体或者实体间的一种联系体或者实体间的一种联系。若多于一个概念就把它。若多于一个概念就把它“分离分离”出去。因此所谓规范化实质上是出去。因此所谓规范化实质上是概念的单一化概念的单一化。323、实际上，在对模式进行分解时，除考虑实际上，在对模式进行分解时，除考虑数据等价和数据等价和依赖等价依赖等价以外，还要考虑以外，还要考虑效率效率。当我们对数据库的操作主要是查询而更新较少时，当我们对数据库的操作主要是查询而更新较少时，为了提高查询效率，可能宁愿为了提高查询效率，可能宁愿保留适当的数据冗余保留适当的数据冗余，让，让关系模式中的属性多些，而不愿把模式分解
30、得太小，否关系模式中的属性多些，而不愿把模式分解得太小，否则为了查询一些数据，常常要做大量的连接运算，把多则为了查询一些数据，常常要做大量的连接运算，把多个关系模式连在一起才能从中找到相关的数据。个关系模式连在一起才能从中找到相关的数据。在实际应用中，对模式分解的要求并不一定要达在实际应用中，对模式分解的要求并不一定要达到到BC范式或更高的范式，有时达到范式或更高的范式，有时达到第三范式第三范式就足够了就足够了。33关系规范化理论研究：关系规范化理论研究：v函数依赖理论的研究函数依赖理论的研究（1）关系模式上的所有依赖通过一些公理系统（）关系模式上的所有依赖通过一些公理系统（Armstrong
31、）而获得关系模式上的所有依赖。基本的由语义获取，其他部分由公理而获得关系模式上的所有依赖。基本的由语义获取，其他部分由公理系统推出。系统推出。（2）最小函数依赖集）最小函数依赖集:等价的函数依赖集中最小者。等价的函数依赖集中最小者。v模式分解的研究模式分解的研究（1）无损连接（无损连接（反映了模式分解的数据等价原则。反映了模式分解的数据等价原则。）当对关系模式当对关系模式R进行分解时，进行分解时，R的元组将分别在相应属性集进行的元组将分别在相应属性集进行投影而产生新的关系。投影而产生新的关系。如果对新的关系进行自然连接得到的元组的集合与原关系完全一如果对新的关系进行自然连接得到的元组的集合与原
32、关系完全一致，则称为无损连接致，则称为无损连接。（2）保持依赖）保持依赖当对关系模式当对关系模式R R进行分解时，进行分解时，R R的函数依赖集也将按相应的模式进的函数依赖集也将按相应的模式进行分解。如果分解后总的函数依赖集与原函数依赖集保持一致，则称行分解。如果分解后总的函数依赖集与原函数依赖集保持一致，则称为保持依赖。为保持依赖。34F1=AB，B C，A C与F2=AB，B C，ABCF3=AB，B C是否等价？353.4 关系模式的分解算法 一、关系模式分解的算法基础1.函数依赖的逻辑蕴含 设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出XY，则称F逻辑蕴
33、含XY，或称XY是F的逻辑蕴含。如：FAB，B C，问A C是否成立？这就需要函数依赖的逻辑隐含知识，用函数依赖的公理系统推出。362.Armstrong公理系统(1)Armstrong公理系统设U为属性集，F是U上的函数依赖集，于是有关系模式RU，F。对R（U，F）来说，有以下的推理规则：1)自反律自反律：若YXU，则XY为F所蕴含。2)增广律增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。3)传递律传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。(2)Armstrong公理的三个推理1)合并规则合并规则：由XY，XZ，有XYZ。2)伪传递规则伪传递规则：由XY，WYZ，有XWZ。
34、3)分解规则分解规则：由XY及ZY，有XZ。由合并规则和分解规则，容易知：X A1A2Ak成立的充分必要条件为X Ai成立。（i=1,2,k）372、指出下列关系属于第几范式？并说明理由。（1）R(X,Y,Z)F=XYZ解：R的候选码为XY，而R中决定因素只有XY，决定因素包含了码。RBCNF。（2）R(X,Y,Z)F=YZ，XZY解：R的候选码为XY或XZ，不存在非主属性对码的部分或传递函数依赖 R3NF。38（3）R(X,Y,Z)F=YZ，YX，XYZ，解：R的候选码为X和Y（单个属性单个属性），XYZ等价于：XY，XZ，故XY，不存在非主属性Z对码的传递函数依赖。又决定因素都是码，RBC
35、NF。（4）R(X,Y,Z)F=XY，XZ 解：R的候选码为X（单个属性单个属性），又每一个函数依赖的左部都是码，RBCNF。39（5）R(X,Y,Z)F=XYZ解：R的候选码为XY，又每一个函数依赖的左部都是码，RBCNF。（6）R(W，X,Y,Z)F=XZ，WXY解：R的候选码为WX，存在非主属性对码的部分函数依赖。R1NF。403.函数依赖集闭包F+和属性集闭包XF+(1)函数依赖集闭包F+和属性集闭包XF+的定义v 在关系模式在关系模式R R（U U，F F）中，为）中，为F F所逻辑蕴含的所逻辑蕴含的函数依赖的全体函数依赖的全体叫做叫做F F的的闭包，记作闭包，记作F+。v设有关系模
36、式设有关系模式R R（U U，F F），），X X是是U U的子集，称所有从的子集，称所有从F F推出的函数依赖集推出的函数依赖集XAXAi i中中A Ai i的属性集为的属性集为X X的属性闭包的属性闭包，记作，记作XF+。即：。即：X XF F+=A=Ai i|A|Ai iUU，XAXAi iFF+(2)属性集闭包XF+的求法1)1)选选X X作为闭包作为闭包X XF F+的初值的初值X XF F(0)(0)。2)X2)XF F(i+1)(i+1)是由是由X XF F(i)(i)并上集合并上集合A A所组成，其中所组成，其中A A为为F F中存在的函中存在的函数依赖数依赖YZYZ，而，而A
37、 A Z Z，Y Y X XF F(i)(i)。3)3)重复步骤重复步骤2)2)。一旦发现。一旦发现X XF F(i)(i)=X=XF F(i+1)(i+1)，则，则X XF F(i)(i)为所求为所求X XF F+。41n【例1】已知关系RU，F，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)F+。设X=AB XF(0)=AB：AB为闭包初值,为本身。XF(1)=ABCD：由ABC，B D可得CD在闭包中。由 XF(2)=ABCDE ：由C E，知E在闭包中。XF(3)=XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E424.函数依赖集的最
38、小化(1)最小函数依赖集的定义最小函数依赖集的定义如果函数依赖集如果函数依赖集F满足下列条件，则称满足下列条件，则称F为一个极小函为一个极小函数依赖集。亦称为数依赖集。亦称为最小依赖集最小依赖集或或最小覆盖最小覆盖。1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与FXA等价。等价。(不含冗余函数依赖。不含冗余函数依赖。)3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真子集有真子集Z使得使得F-XAZ-A与与F等价。等价。(决定因素不含冗余属性。决定因素不含冗余属性。)如如F=AB
39、，B C，A C不是最小函数依赖集。不是最小函数依赖集。43(2)最小函数依赖集的求法最小函数依赖集的求法1)逐一检查逐一检查F中各函数依赖中各函数依赖XY，若，若Y=A1A2Ak，k2，则用，则用XAj|j=1，2，k来取代来取代XY。(右边的属性单值化右边的属性单值化)2)逐一检查逐一检查F中各函数依赖中各函数依赖XA，令，令G=FXA，若，若AXG+，则从，则从F中去掉此函数依赖。中去掉此函数依赖。(去掉冗余函数依赖去掉冗余函数依赖)3)逐一取出逐一取出F中各函数依赖中各函数依赖XA，设，设X=B1B2Bm，逐一检查，逐一检查Bi（i=1，2，m），如果），如果A(X-Bi)F+，则以，
40、则以XBi取代取代X。(左边的属性单值化左边的属性单值化)44【例4-2】设F=ABC，BAC，CA，对F进行极小化处理。解：1)根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。F=AB，AC，BA，BC，CA2)去掉F中冗余的函数依赖。判断AB。设：G1=AC，BA，BC，CA，得：AG1+=AC BAG1+AB不冗余判断AC。设：G2=AB，BA，BC，CA，得：AG2+=ABC CAG2+AC冗余判断BA。设：G3=AB，BC，CA，（去掉AC冗余后）得：BG3+=BCA ABG3+BA冗余判断BC。设：G4=AB，CA，得：BG4+=B C
41、BG4+BC不冗余判断CA。设：G5=AB，BC，得：CG5+=C ACG5+CA不冗余 Fm=AB，BC，CA45【例4-3】求F=ABC，AB，BA的最小函数依赖集Fm。解：(1)去掉F中冗余的函数依赖。判断ABC是否冗余。设：G1=AB，BA，得：(AB)G1+=AB C(AB)G1+ABC不冗余判断AB是否冗余。设：G2=ABC，BA，得：AG2+=A BABG2+AB不冗余判断BA是否冗余。设：G3=ABC，AB，得：BG3+=B ABG3+BA不冗余经过检验后的函数依赖集仍然为F=ABC，AB，BA。(2)去掉各函数依赖左部冗余的属性。本题只需考虑ABC的情况。方法1：在决定因素中
42、去掉B，若CAF+，则以AC代替ABC。求得：AF+=ABC CAF+以AC代替ABC故：Fm=AC，AB，BA方法2：在决定因素中去掉A，若CBF+，则以BC代替ABC。求得：BF+=ABC CBF+以BC代替ABC故：Fm=BC，AB，BA463.4.2 判定分解服从规范的方法1.关系分解的无损连接性关系分解的无损连接性 设关系模式设关系模式R R，如果把它分解为两个（或多个）子模式，如果把它分解为两个（或多个）子模式R R1 1和和R R2 2，相应，相应一个一个R R关系中的数据就要被分成关系中的数据就要被分成R R1 1、R R2 2两个（或多个）子表。两个（或多个）子表。假如将这些
43、子表自然连接，即进行假如将这些子表自然连接，即进行R R1 1RR2 2操作，得到的结果与原来关操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果如果RRRR1 1 R R2 2，则称该分解不具有无损连接性。，则称该分解不具有无损连接性。2.判断分解成两个关系具有判断分解成两个关系具有无损连接性无损连接性的方法的方法定理：RU，F的一个分解=R1(U1，F1)，R2(U2，F2)具有无损连接性的充分必要条件是：(U1U2)(U1-U2F+).或 U1U2U2-U1F+.3.判断分解保持函数依赖
44、的方法判断分解保持函数依赖的方法设U，F的分解=R1U1，F1，R1U2，F2，RkUK，FK，若F+=(Fi)+，则称分解保持函数依赖。47n【例-5】关系模式R=CITY，ST，ZIP，其中CITY为城市，ST为街道，ZIP为邮政编码，F=(CITY，ST)ZIP，ZIPCITY。如果将R分解成R1和R2，R1=ST，ZIP，R2=CITY，ZIP，检查分解是否具有无损连接和保持函数依赖。解：1)检查无损连接性。求得：R1R2=ZIP；R2-R1=CITY.(ZIPCITY)F+.分解具有无损连接性2)检查分解是否保持函数依赖求得：R1(F)=；R2(F)=ZIPCITY.R1(F)R2(
45、F)=ZIPCITYF+.该分解不保持函数依赖。483.4.3 关系模式的分解方法关系模式的分解方法1)对对R R（U U，F F）中的）中的F F进行极小化处理。处理后的函数依赖集进行极小化处理。处理后的函数依赖集仍用仍用F F表示。表示。2)2)找出不再在找出不再在F F中出现的属性中出现的属性（极小化后）（极小化后），这样的属性构成，这样的属性构成一个关系模式，并把这些属性从一个关系模式，并把这些属性从U U中去掉。中去掉。3)3)如果如果F F中有一个函数依赖涉及中有一个函数依赖涉及R R的全部属性，则的全部属性，则R R不能再分不能再分解。解。4)4)如果如果F F中含有中含有XAX
46、A，则分解应包含模式，则分解应包含模式XAXA，如果，如果XAXA1 1，XAXA2 2，XAnXAn均属于均属于F F，则分解应包含模式，则分解应包含模式XAXA1 1A A2 2A An n。【例4-6】设关系模式RU，F，U=C，T，H，R，S，G，X，Y，Z，F=CT，CSG，HRC，HSR，THR，CX，将R分解为3NF，且保持函数依赖。解：设该函数依赖集已经是最小化的，则分解为：=YZ，CTX，CSG，HRC，HSR，THR.一、将关系模式转化为3NF的保持函数依赖的分解492.将关系转化为3NF、且既具有无损连接性又能保持函数依赖的分解分解算法为：1)设X是R（U，F）的码，RU，F先进行保持函数依赖的分解，结果为=R1（U1，F1），R2U2，F2，RkUk，Fk，令=R*（X，Fx）。2)若有某个Ui，X Ui，将R*X，Fx从中去掉，就是所求的分解。【例3-7】有关系模式RU，F，U=C，T，H，R，S，G，F=CT，CSG，HRC，HSR，THR，将R分解为3NF，且既具有无损连接性又能保持函数依赖。解：求得关系模式R的码为HS，它的一个保持函数依赖的3NF为：=CT，CSG，HRC，HSR，THR.HSHSR =CT，CSG，HRC，HSR，THR为满足要求的分解。50
