资源描述
本章教学目标、重点和难点本章教学目标、重点和难点n教学目标：教学目标：使学生了解关系模式规范化的必要性，使学生了解关系模式规范化的必要性，理解函数依赖、多值依赖及其关系范式定义，掌理解函数依赖、多值依赖及其关系范式定义，掌握关系范式判断方法。握关系范式判断方法。n教学重点：教学重点：关系模式规范化，函数依赖、多值依关系模式规范化，函数依赖、多值依赖、赖、1-4NF的定义，关系范式判断方法。的定义，关系范式判断方法。n教学难点：教学难点：1-4NF的定义，关系范式判断方法，关的定义，关系范式判断方法，关系模式的分解。系模式的分解。第第7章章关系规范化理论和优化技术关系规范化理论和优化技术7.1关系数据模式的规范化理论关系数据模式的规范化理论7.2关系模式的分解算法关系模式的分解算法7.1 关系数据模式的规范化理论范式（范式（NormalForm）是指规范化的关系模式。由）是指规范化的关系模式。由满足最基本规范化的关系模式叫第一范式，第一范满足最基本规范化的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束条件就产生了第式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、二范式、第三范式、BC范式等等。一个低一级的范式等等。一个低一级的关系范式通过模式分解可以转换成若干高一级范式关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的规范化。的关系模式的集合，这种过程叫关系模式的规范化。7.1.1关系模式规范化的必要性关系模式规范化的必要性1.关系模式应满足的基本要求1)元组的每个分量必须是不可分的数据项。元组的每个分量必须是不可分的数据项。2)数据冗余应尽可能少。数据冗余应尽可能少。3)不能因为数据更新操作而引起数据不一致问题。不能因为数据更新操作而引起数据不一致问题。4)当执行数据插入操作时，数据不能产生插入异常当执行数据插入操作时，数据不能产生插入异常现象。现象。5)数据不能在执行删除操作时产生删除异常问题。数据不能在执行删除操作时产生删除异常问题。6)数据库设计应考虑查询要求，数据组织应合理。数据库设计应考虑查询要求，数据组织应合理。2.关系规范化可能出现的问题关系规范化可能出现的问题数据冗余大数据冗余大,插入异常插入异常,删除异常删除异常,更新异常。更新异常。学号学号姓名姓名年龄年龄性别性别系名系名系主任系主任课程名课程名成绩成绩98001李华李华20男男计算机系计算机系王民王民程序设计程序设计8898001李华李华20男男计算机系计算机系王民王民数据结构数据结构7498001李华李华20男男计算机系计算机系王民王民数据库数据库8298001李华李华20男男计算机系计算机系王民王民电路电路6598002张平张平21女女计算机系计算机系王民王民程序设计程序设计9298002张平张平21女女计算机系计算机系王民王民数据结构数据结构8298002张平张平21女女计算机系计算机系王民王民数据库数据库7898002张平张平21女女计算机系计算机系王民王民电路电路8398003陈兵陈兵20男男数学系数学系赵敏赵敏高等数学高等数学7298003陈兵陈兵20男男数学系数学系赵敏赵敏数据结构数据结构9498003陈兵陈兵20男男数学系数学系赵敏赵敏数据库数据库8398003陈兵陈兵20男男数学系数学系赵敏赵敏离散数学离散数学873.模式分解是关系规范化的主要方法模式分解是关系规范化的主要方法上述的关系模式上述的关系模式:教学教学(学号，姓名，年龄，性别，系名，系主任，学号，姓名，年龄，性别，系名，系主任，课程名，成绩课程名，成绩).).可以按可以按“一事一地一事一地”的原则分解成的原则分解成“学生学生”、“教教学系学系”和和“选课选课”三个关系，其关系模式为：三个关系，其关系模式为：学生学生(学号，姓名，年龄，性别，系名称学号，姓名，年龄，性别，系名称)；教学系教学系(系名，系主任系名，系主任)；选课选课(学号，课程名，成绩学号，课程名，成绩).).7.1.2函数依赖及其关系的范式函数依赖及其关系的范式1.关系模式的简化表示法关系模式的简化表示法关系模式的完整表示是一个五元组：关系模式的完整表示是一个五元组：RU，D，Dom，F.其中：其中：R为关系名；为关系名；U为关系的属性集合；为关系的属性集合；D为属性集为属性集U中中属性的数据域；属性的数据域；Dom为属性到域的映射；为属性到域的映射；F为属性集为属性集U的的数据依赖集。数据依赖集。关系模式可以用三元组来为：关系模式可以用三元组来为：RU，F.2.函数依赖的概念函数依赖的概念1)设设RU是属性集是属性集U上的关系模式，上的关系模式，X、Y是是U的子集。若对于的子集。若对于RU的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上上的属性值相等，而的属性值相等，而Y上的属性值不等，则称上的属性值不等，则称X函数确定函数确定Y函数，或函数，或Y函数依赖于函数依赖于X函数，记作函数，记作XY。例如，对于教学关系模式：教学例如，对于教学关系模式：教学U，F；U=学号，姓名，年龄，性别，系名，系主任，课程名，成绩学号，姓名，年龄，性别，系名，系主任，课程名，成绩；F=学号学号姓名，学号姓名，学号年龄，学号年龄，学号性别，学号性别，学号系名，系名系名，系名系主系主任，任，(学号，课程名学号，课程名)成绩成绩.XY，但，但Y X，则称，则称XY是非平凡的函数依赖。若不特别是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。声明，总是讨论非平凡的函数依赖。XY，但，但Y X，则称，则称XY是平凡的函数依赖。是平凡的函数依赖。若若XY，则，则X叫做决定因素（叫做决定因素（Determinant），），Y叫做依赖叫做依赖因素（因素（Dependent）。）。若若XY，YX，则记作，则记作XY。若若Y不函数依赖于不函数依赖于X，则记作，则记作X Y。完全函数依赖、传递函数依赖完全函数依赖、传递函数依赖 2)在在RU中，如果中，如果XY，并且对于，并且对于X的任何一个真子集的任何一个真子集X，都有，都有X Y，则称，则称Y对对X完全函数依赖，记作：完全函数依赖，记作：XY；若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y对对X部分函数依赖，部分函数依赖，记作：记作：XY。例如，在教学关系模式：例如，在教学关系模式：(学号，课程名学号，课程名)成绩，成绩，(学号，学号，课程名课程名)姓名姓名3)在在RU中，如果中，如果XY，(YX)，Y X，YZ，则，则称称Z对对X传递函数依赖。传递函数依赖记作传递函数依赖。传递函数依赖记作X Z。传递例如，在教学模式中，因为：学号传递例如，在教学模式中，因为：学号系名，系名系名，系名系主系主任；所以：学号任；所以：学号 系主任。系主任。PFFP传递传递3.1NF 3.1NF 的定义、的定义、2NF 2NF 的定义的定义n如果关系模式如果关系模式R，其所有的属性均为简单属性，即每个属性都，其所有的属性均为简单属性，即每个属性都是不可再分的，则称是不可再分的，则称R属于第一范式，记作属于第一范式，记作R 1NF。n若若R 1NF，且每一个非主属性完全依赖于码，则，且每一个非主属性完全依赖于码，则R 2NF。在教学中：属性集在教学中：属性集=学号，姓名，年龄，系名，系主任，课程名，成绩学号，姓名，年龄，系名，系主任，课程名，成绩.函数依赖集函数依赖集=学号学号姓名，学号姓名，学号年龄，学号年龄，学号性别，学号性别，学号系名，系名，系名系名系主任，系主任，(学号，课程名学号，课程名)成绩成绩.主码主码=(学号，课程名学号，课程名).非主属性非主属性=(姓名，年龄，系名，系主任，成绩姓名，年龄，系名，系主任，成绩)。非主属性对码的函数依赖：非主属性对码的函数依赖：(学号，课程名学号，课程名)姓名，姓名，(学号，课程名学号，课程名)年龄，年龄，(学号，课程号学号，课程号)性别性别，(学号，课程名学号，课程名)系名，系名，(学号，课程名学号，课程名)系主任；系主任；(学号，课程名学号，课程名)成绩成绩.显然，教学模式不服从显然，教学模式不服从2NF，即：教学，即：教学 2NF。PPPPP5.3NF 5.3NF 的定义的定义n关系模式关系模式RU，F中若不存在这样的码中若不存在这样的码X、属性组、属性组Y及非及非主属性主属性Z(ZY)使得使得XY、Y X、YZ成立，则称成立，则称RU，F 3NF。可以证明，若可以证明，若R 3NF，则每一个非主属性既不部分函数依，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。赖于码，也不传递函数依赖于码。考查学生考查学生_系关系，由于存在：学号系关系，由于存在：学号系名，系名系名，系名系主任。系主任。则：则：学号学号 系主任。所以系主任。所以学生学生_系系 3NF。如果分解为：如果分解为：学生学生(学号，姓名，年龄，性别，系名学号，姓名，年龄，性别，系名)；教学系教学系(系名，系主任系名，系主任).显然分解后的各子模式均属于显然分解后的各子模式均属于3NF。传递6.BCNF的定义的定义n关系模式关系模式RU，F 1NF。若。若XY且且YX时时X必含有码，必含有码，则则RU，F BCNF。也就是说，关系模式也就是说，关系模式RU，F中，若每一个决定因素都包中，若每一个决定因素都包含码，则含码，则RU，F BCNF。由。由BCNF的定义可以得到结的定义可以得到结论，一个满足论，一个满足BCNF的关系模式有：的关系模式有：1)所有非主属性对每一个码都是完全函数依赖。所有非主属性对每一个码都是完全函数依赖。2)所有的主属性对每一个不包含它的码，也是完全依赖。所有的主属性对每一个不包含它的码，也是完全依赖。3)没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一组属性。7.BCNF和3NF的比较1)BCNF不仅强调其他属性对码的完全的直接不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括的依赖，它包括3NF，即，即R BCNF，则，则R一一定属于定属于3NF。2)3NF只强调非主属性对码的完全直接依赖，只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传这样就可能出现主属性对码的部分依赖和传递依赖。递依赖。例如，关系模式例如，关系模式STJ(S，T，J)中，中，S表示学生，表示学生，T表示表示教师，教师，J表示课程。语义为：每一教师只能讲授一门表示课程。语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教师。由语义可以得到门课程就对应一个固定的教师。由语义可以得到STJ模式的函数依赖为：模式的函数依赖为：F=(S，J)T，TJ显然：显然：(S，J)和和(T，S)都是关系的码；关系的主属性都是关系的码；关系的主属性集为集为S，T，J，非主属性为，非主属性为（空集）。（空集）。由于由于STJ模式中无非主属性，所以它属于模式中无非主属性，所以它属于3NF；但因；但因为存在为存在TJ，由于，由于T不是码，故不是码，故STJ BCNF。7.1.3多值依赖及关系的第多值依赖及关系的第4范式范式1.研究多值依赖的必要性研究多值依赖的必要性例如，给定一个关系模式例如，给定一个关系模式JPW(产品，零件，工序产品，零件，工序)，其中每种产品由多，其中每种产品由多种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零件和工序如图所示。件和工序如图所示。显像管显像管电视机电视机开关开关电源电源焊接焊接调试调试测试测试装配装配调试调试焊接焊接调试调试2.多值依赖的定义和性质多值依赖的定义和性质n设有关系模式设有关系模式RU，U是属性集，是属性集，X、Y是是U的子集。如果的子集。如果R的任一关系，对于的任一关系，对于X的一个确定值，都存在的一个确定值，都存在Y的一组值与之的一组值与之对应，且对应，且Y的这组值又与的这组值又与Z=U-X-Y中的属性值不相关，此时中的属性值不相关，此时称称Y多值依赖于多值依赖于X，或，或X多值决定多值决定Y，记为，记为XY。多值依赖具有以下性质：多值依赖具有以下性质：1)多值依赖具有对称性。即若多值依赖具有对称性。即若XY，则，则XZ，其中，其中Z=U-X-Y。2)函数依赖可以看作是多值依赖的特殊情况。即若函数依赖可以看作是多值依赖的特殊情况。即若XY，则，则XY。这是因为当。这是因为当XY时，对时，对X的每一个值的每一个值x，Y有一个有一个确定的值确定的值y与之对应，所以与之对应，所以XY。3)在多值依赖中，若在多值依赖中，若XY且且Z=U-X-Y，则称，则称XY为为非平凡的多值依赖，否则称为平凡的多值依赖。非平凡的多值依赖，否则称为平凡的多值依赖。7.2 关系模式的分解算法7.2.1 关系模式分解的算法基础1.函数依赖的逻辑蕴含函数依赖的逻辑蕴含设设F是是RU函数依赖集，函数依赖集，X和和Y是属性集是属性集U的子的子集。如果从集。如果从F中的函数依赖能推出中的函数依赖能推出XY，则称，则称F逻逻辑蕴含辑蕴含XY，或称，或称XY是是F的逻辑蕴含。的逻辑蕴含。(1)Armstrong公理系统公理系统:设设U为属性集，为属性集，F是是U上的函数依赖集，上的函数依赖集，于是有关系模式于是有关系模式RU，F。1)自反律：若自反律：若Y X U，则，则XY为为F所蕴含。所蕴含。2)增广律：若增广律：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所所蕴含。蕴含。3)传递律：若传递律：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。(2)Armstrong公理的三个推理公理的三个推理1)合并规则：由合并规则：由XY，XZ，有，有XYZ。2)伪传递规则：由伪传递规则：由XY，WYZ，有，有XWZ。3)分解规则：由分解规则：由XY及及Z Y，有，有XZ。2.Armstrong公理系统公理系统3.函数依赖集闭包F+和属性集闭包XF+(1)函数依赖集闭包函数依赖集闭包F+和属性集闭包和属性集闭包XF+的定义的定义定义：在关系模式定义：在关系模式RU，F中，为中，为F所逻辑蕴含的所逻辑蕴含的函数依赖的全体叫做函数依赖的全体叫做F的闭包，记作的闭包，记作F+。定义：设有关系模式定义：设有关系模式RU，F，X是是U的子集，称的子集，称所有从所有从F推出的函数依赖集推出的函数依赖集XAi中中Ai的属性集为的属性集为X的属性闭包，记作的属性闭包，记作XF+。即：。即：XF+=Ai|AiU，XAiF+(2)属性集闭包属性集闭包XF+的求法的求法1)选选X作为闭包作为闭包XF+的初值的初值XF(0)。2)XF(i+1)是由是由XF(i)并上集合并上集合A所组成，其中所组成，其中A为为F中中存在的函数依赖存在的函数依赖YZ，而，而A Z，Y XF(i)。3)重复步骤重复步骤2)。一旦发现。一旦发现XF(i)=XF(i+1)，则，则XF(i)为所为所求求XF+。例子n【例例】已知关系已知关系RU，F，其中，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求，求(AB)F+。设设X=ABXF(0)=ABXF(1)=ABCDXF(2)=ABCDEXF(3)=XF(2)=ABCDE(AB)F+=ABCDE=A，B，C，D，E4.函数依赖集的最小化(1)最小函数依赖集的定义最小函数依赖集的定义1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真子集有真子集Z使使得得F-XAZ-A与与F等价。等价。(2)最小函数依赖集的求法最小函数依赖集的求法1)逐一检查逐一检查F中各函数依赖中各函数依赖XY，若，若Y=A1A2Ak，k2，则用，则用XAj|j=1，2，k来取代来取代XY。2)逐一检查逐一检查F中各函数依赖中各函数依赖XA，令，令G=F-XA，若，若AXG+，则从，则从F中去掉此函数依赖。中去掉此函数依赖。3)逐一取出逐一取出F中各函数依赖中各函数依赖XA，设，设X=B1B2Bm，逐一检查，逐一检查Bi（i=1，2，m），如果），如果A(X-Bi)F+，则以，则以X-Bi取代取代X。【例例】设设F=ABC，BAC，CA，对，对F进行极小化处理。进行极小化处理。解：解：1)把把F中的函数依赖转换成右部都是单属性的函数依赖，中的函数依赖转换成右部都是单属性的函数依赖，分解后的函数依赖集仍用分解后的函数依赖集仍用F表示。表示。F=AB，AC，BA，BC，CA2)去掉去掉F中冗余的函数依赖。中冗余的函数依赖。判断判断AB。设：。设：G1=AC，BA，BC，CA，得：得：AG1+=ACB AG1+AB不冗余不冗余判断判断AC。设：。设：G2=AB，BA，BC，CA，得：得：AG2+=ABCC AG2+AC冗余冗余判断判断BA。设：。设：G3=AB，BC，CA，得：得：BG3+=BCAA BG3+BA冗余冗余判断判断BC。设：。设：G4=AB，CA，得：得：BG4+=BC BG4+BC不冗余不冗余判断判断CA。设：。设：G5=AB，BC，得：得：CG5+=CA CG5+CA不冗余不冗余Fm=AB，BC，CA【例例】求求F=ABC，AB，BA的最小函数依赖集的最小函数依赖集Fm。解：解：(1)去掉去掉F中冗余的函数依赖。中冗余的函数依赖。判断判断ABC是否冗余。是否冗余。设：设：G1=AB，BA，得：，得：(AB)G1+=ABC(AB)G1+ABC不冗余不冗余判断判断AB是否冗余。是否冗余。设：设：G2=ABC，BA，得：，得：AG2+=AB ABG2+AB不冗余不冗余判断判断BA是否冗余。是否冗余。设：设：G3=ABC，AB，得：，得：BG3+=BA BG3+BA不冗余不冗余经过检验后的函数依赖集仍然为经过检验后的函数依赖集仍然为F=ABC，AB，BA。【例例】求求F=ABC，AB，BA的最小函数依赖集的最小函数依赖集Fm。解解(2)去掉各函数依赖左部冗余的属性。去掉各函数依赖左部冗余的属性。本题只需考虑本题只需考虑ABC的情况。的情况。方法方法1：在决定因素中去掉：在决定因素中去掉B，若，若C AF+，则以，则以AC代替代替ABC。求得：求得：AF+=ABCC AF+以以AC代替代替ABC故：故：Fm=AC，AB，BA方法方法2：在决定因素中去掉：在决定因素中去掉A，若，若C BF+，则以，则以BC代替代替ABC。求得：求得：BF+=ABCC BF+以以BC代替代替ABC故：故：Fm=BC，AB，BA7.2.3 判定分解服从规范的方法1.关系分解的无损连接性关系分解的无损连接性设关系模式设关系模式R，如果把它分解为两个（或多个），如果把它分解为两个（或多个）子模式子模式R1和和R2，相应一个，相应一个R关系中的数据就要被分关系中的数据就要被分成成R1、R2两个（或多个）子表。假如将这些子表自两个（或多个）子表。假如将这些子表自然连接，即进行然连接，即进行R1R2操作，得到的结果与原来关操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果有无损连接性，否则如果RR1R2，则称该分解不，则称该分解不具有无损连接性。具有无损连接性。2.判断分解成两个关系具有无损连接性的方法判断分解成两个关系具有无损连接性的方法定理：定理：RU，F的一个分解的一个分解=R1U1，F1，R2U2，F2具有无损连接性的充分必要条件是：具有无损连接性的充分必要条件是：U1U2U1-U2F+.或或U1U2U2-U1F+.3.判断分解保持函数依赖的方法判断分解保持函数依赖的方法设设U，F的分解的分解=R1U1，F1，R1U2，F2，RkUK，FK，若，若F+=(Fi)+，则称分解，则称分解 保持函数依赖保持函数依赖。【例例】关系模式关系模式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(F)=ZIPCITYF+.该分解不保持函数依赖。该分解不保持函数依赖。7.2.4 关系模式的分解方法1.将关系模式转化为将关系模式转化为3NF的保持函数依赖的分解的保持函数依赖的分解1)对对RU，F中的中的F进行极小化处理。处理后的函数依赖集进行极小化处理。处理后的函数依赖集仍用仍用F表示。表示。2)找出不再在找出不再在F中出现的属性，把这样的属性构成一个关系模中出现的属性，把这样的属性构成一个关系模式，并把这些属性从式，并把这些属性从U中去掉。中去掉。3)若若F中有一个函数依赖涉及中有一个函数依赖涉及R全部属性，则全部属性，则R不能再分解。不能再分解。4)如果如果F中含有中含有XA，则分解应包含模式，则分解应包含模式XA，如果，如果XA1，XA2，XAn均属于均属于F，则分解应包含模式，则分解应包含模式XA1A2An。【例例】设设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.2.2.将关系转化为将关系转化为3NF3NF、且既具有无损连接性又能保持、且既具有无损连接性又能保持函数依赖的分解函数依赖的分解对于给定的关系模式对于给定的关系模式RU，F，将其转换为，将其转换为3NF，且既具有无损连接性又能保持函数依赖的分解算法且既具有无损连接性又能保持函数依赖的分解算法为：为：1)设设X是是RU，F的码，的码，RU，F先进行保持先进行保持函数依赖的分解，结果为函数依赖的分解，结果为=R1U1，F1，R2U2，F2，RkUk，Fk，令，令=R*X，Fx。2)若有某个若有某个Ui，X Ui，将，将R*X，Fx从从中去掉，中去掉，就是所求的分解。就是所求的分解。【例例】有关系模式有关系模式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.HS HSR=CT，CSG，HRC，HSR，THR为满足为满足要求的分解。要求的分解。3.3.将关系模式转换为将关系模式转换为BCNFBCNF的无损连接的分解的无损连接的分解1)令令=RU，F。2)检查检查 中各关系模式是否均属于中各关系模式是否均属于BCNF。若是，。若是，则算法终止。则算法终止。3)假设假设 中中RiUi，Fi不属于不属于BCNF，那么必定有，那么必定有XA Fi+，(A X)，且，且X非非Ri的码。对的码。对Ri进行分进行分解：解：=S1，S2，US1=XA，US2=Ui-A，以，以代替代替RiUi，Fi，返回第，返回第2)步。步。【例例】关系模式关系模式RU，F，U=CTHRSG，F=CT，HRC，HTR，CSG，HSR，把，把R分解成具有无损连接的分解成具有无损连接的BCNF。解：令解：令=CTHRSG1)由于由于R的码为的码为HS，选择，选择CSG分解。得出：分解。得出：=S1，S2.其中：其中：S1=CSG，F1=CSG；S2=CTHRS，F2=CT，HRC，HTR，HSR.S2不服从不服从BCNF，需要继续分解。，需要继续分解。2)对对S2分解。分解。S2的码为的码为HS，选择，选择CT分解。得：分解。得：=S1，S3，S4.其中：其中：S3=CT，F3=CT；S4=CHRS，F4=HRC，HSR.S4不服从不服从BCNF，还需要继续分解。，还需要继续分解。3)对对S4分解。码为分解。码为HS，选择，选择HRC分解：分解：=S1，S3，S5，S6.其中：其中：S5=HRC，F5=HRC；S6=HRS，F6=HSR.4)最后的分解为：最后的分解为：=CSG，CT，HRC，HRS.习题习题77.2答：答：正确。因为学号能够多值决定课程号，且除了学号和课程号外还有成绩属性，它不是平凡的多值依赖。7.3设有关系模式R（A，B，C），数据依赖集F=ABC，CA，R属于第几范式？为什么？7.3答：答：BCNF。由于A多值依赖于C，而C不是码，故不服从4NF。但在函数依赖式中，C依赖于码AB，故该模式服从BCNF。7.4答：答：正确。正确。正确。正确。正确。正确。正确。不正确。例如，(学号，课程号)成绩，则不存在：学号成绩，课程号成绩。7.7答：把查询转换成语法树表示。把语法树转换成标准（优化）形式。选择低层的存取路径。生成查询计划，选择代价最小的查询计划。7.8试述查询优化的一般准则。7.8答：选择运算尽可能先做。在执行连接前对关系适当地预处理，即在连接属性上建立索引和对关系进行排序。把投影运算和选择运算同时进行。把投影同其前或其后的双目运算结合起来。把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算。找出公共子表达式。7.13答：是BCNF。二元关系中或为全码，或为一个单属性码候选码。是BCNF。关系模式中只有一个候选码。不是BCNF。因为模式中存在候选码为AD、BCD和BE，显然C对AD是部分依赖。7.22答：1）关系STUDENT是1NF。2）消除部分函数依赖S#,CNAMESNAME,SDEPT,MNAME将关系分解为：R1(S#,SNAME,SDEPT,MNAME)；R2(S#,CNAME,GRADE).由于在关系R1中，存在非主属性对候选码的传递函数依赖（S#SDEPT，SDEPT MNAME），所以以上关系模式还不是BCNF。进一步分解R1为：R11(S#,SNAME,SDEPT)；R12(SDEPT,MNAME).R11，R12都是3NF。对于关系模式：R2(S#,CNAME,GRADE)，F2=（S#,CNAME）GRADE;R11(S#,SNAME,SDEPT)，F11=S#SNAME,S#SDEPT;R12(SDEPT,MNAME)，F12=SDEPTMNAME.上述函数依赖都是非平凡的，并且决定因素是候选码，所以上述关系模式属于BCNF。7.23设有关系模式R（A，B，C，D），其函数依赖集：F=AC，CA，BAC，DAC。1）求F的最小等价依赖集FC。2）将R分解为满足3NF且具有无损连接并保持函数依。答：FC=AC，CA，BA，DAF1=A，C，F2=B，A，F3=D，A，F4=B，D7.24设有关系模式R（U，F），其中：U=C，T，H，R，S，G，F=CSG，CT，TH R，HRC，HSR。请根据算法将R分解为满足BCNF且具有无损连。答：F1=C，S，G，F2=C，T，F3=C，H，R，F4=C，H，S7.26答：答：1）由于基本的FD有3个：（职工编号，日期）日产量；职工编号车间编号；车间编号车间主任。得出R的关键码为（职工编号，日期）。2）由于R中有两个FD：（职工编号，日期）（车间编号，车间主任）；职工编号（车间编号，车间主任）。前一个FD是局部依赖，所以R不是2NF模式。R应分解成：R1（职工编号，车间编号，车间主任）；R2（职工编号，日期，日产量）.此处，R1和R2都是2NF模式。3）R2已是3NF模式。在R1中，存在两个FD：职工编号 车间编号；车间编号 车间主任。其中的“职工编号 车间主任”是一个传递依赖，R1不是3NF模式。R1应分解成：R11（职工编号，车间编号）；R12（车间编号，车间主任）.这样，=R11，R12，R2 是一个3NF模式集。7.27答：答：1）基本的FD有3个：（车间编号，零件编号）数量；零件编号仓库编号；仓库编号仓库地址。得出R的关键码为（车间编号，零件编号）。2）R中有两个这样的FD：（车间编号，零件编号）（仓库编号，仓库地址）；零件编号（仓库编号，仓库地址）。可见前一个FD是局部依赖，所以R不是2NF模式。R应分解成：R1（零件编号，仓库编号，仓库地址）；R2（车间编号，零件编号，数量）.此处，R1和R2都是2NF模式。3）R2已是3NF模式。在R1中，存在两个FD：零件编号仓库编号；仓库编号仓库地址。因此，“零件编号 仓库地址”是一个传递依赖，R1不是3NF模式。R1应分解成：R11（零件编号，仓库编号）；R12（仓库编号，仓库地址）.=R11，R12，R2 是一个3NF模式集。7.30答案答案D7.31答案答案B7.32答案答案D7.33答案答案B7.34答案 B7.35答案 A7.36答案 D7.37答案答案B7.38答案答案D7.39答案 A7.40答案 A7.41答案答案B7.42答案答案A7.43答案 D7.44答案 D7.45答案 B7.46答案答案B7.47答案答案B7.48答案答案D7.49答案 A7.51答案答案C
展开阅读全文