第7章 关系数据库理论

第7章关系数据库理论7.1关系数据模式的规范化理论7.1.1关系模式规范化的必要性7.1.2函数依赖及其关系的范式7.1.3多值依赖及关系的第四范式7.2关系模式的分解算法7.2.1关系模式分解的算法基础7.2.3判定分解服从规范的方法7.2.4关系模式的分解方法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.关系模式的简化表示法关系模式的完整表示是一个五元组：R〈U，D，Dom，F〉.其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。关系模式可以用三元组来为：R〈U，F〉.2.函数依赖的概念1)设R〈U〉是属性集U上的关系模式，X、Y是U的子集。若对于R〈U〉的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，则称X函数确定Y函数，或Y函数依赖于X函数，记作X→Y。例如，对于教学关系模式：教学〈U，F〉；U={学号，姓名，年龄，性别，系名，系主任，课程名，成绩}；F={学号→姓名，学号→年龄，学号→性别，学号→系名，系名→系主任，(学号，课程名)→成绩}.①X→Y，但YX，则称X→Y是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。②X→Y，但YX，则称X→Y是平凡的函数依赖。③若X→Y，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。④若X→Y，Y→X，则记作X↔Y。⑤若Y不函数依赖于X，则记作XY。完全函数依赖、传递函数依赖2)在R〈U〉中，如果X→Y，并且对于X的任何一个真子集X’，都有X’Y，则称Y对X完全函数依赖，记作：X→Y；若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：X→Y。例如，在教学关系模式：(学号，课程名)→成绩，(学号，课程名)→姓名3)在R〈U〉中，如果X→Y，(YX)，YX，Y→Z，则称Z对X传递函数依赖。传递函数依赖记作X→Z。传递例如，在教学模式中，因为：学号→系名，系名→系主任；所以：学号→系主任。PFFP传递传递3.1NF的定义、2NF的定义如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记作R1NF。若R1NF，且每一个非主属性完全依赖于码，则R2NF。在教学中：属性集={学号，姓名，年龄，系名，系主任，课程名，成绩}.函数依赖集={学号→姓名，学号→年龄，学号→性别，学号→系名，系名→系主任，(学号，课程名)→成绩}.主码=(学号，课程名).F非主属性=(姓名，年龄，系名，系主任，成绩)。非主属性对码的函数依赖：{(学号，课程名)→姓名，(学号，课程名)→年龄，(学号，课程号)→性别，(学号，课程名)→系名，(学号，课程名)→系主任；(学号，课程名)→成绩}.显然，教学模式不服从2NF，即：教学2NF。PPPPP5.3NF的定义关系模式R〈U，F〉中若不存在这样的码X、属性组Y及非主属性Z(ZY)使得X→Y、YX、Y→Z成立，则称R〈U，F〉3NF。可以证明，若R3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。考查学生_系关系，由于存在：学号→系名，系名→系主任。则：学号→系主任。所以学生_系3NF。如果分解为：学生(学号，姓名，年龄，性别，系名)；教学系(系名，系主任).显然分解后的各子模式均属于3NF。传递6.BCNF的定义关系模式R〈U，F〉1NF。若X→Y且YX时X必含有码，则R〈U，F〉BCNF。也就是说，关系模式R〈U，F〉中，若每一个决定因素都包含码，则R〈U，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，T→J}显然：(S，J)和(T，S)都是关系的码；关系的主属性集为{S，T，J}，非主属性为（空集）。P由于STJ模式中无非主属性，所以它属于3NF；但因为存在T→J，由于T不是码，故STJBCNF。7.1.3多值依赖及关系的第四范式1.研究多值依赖的必要性例如，给定一个关系模式JPW(产品，零件，工序)，其中每种产品由多种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零件和工序如图所示。显像管电视机开关电源焊接调试测试装配调试焊接调试2.多值依赖的定义和性质设有关系模式R〈U〉，U是属性集，X、Y是U的子集。如果R的任一关系，对于X的一个确定值，都存在Y的一组值与之对应，且Y的这组值又与Z=U-X-Y中的属性值不相关，此时称Y多值依赖于X，或X多值决定Y，记为X→→Y。多值依赖具有以下性质：1)多值依赖具有对称性。即若X→→Y，则X→→Z，其中Z=U-X-Y。2)函数依赖可以看作是多值依赖的特殊情况。即若X→Y，则X→→Y。这是因为当X→Y时，对X的每一个值x，Y有一个确定的值y与之对应，所以X→→Y。3)在多值依赖中，若X→→Y且Z=U-X-Y≠φ，则称X→→Y为非平凡的多值依赖，否则称为平凡的多值依赖。7.2关系模式的分解算法7.2.1关系模式分解的算法基础1.函数依赖的逻辑蕴含设F是R〈U〉函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出X→Y，则称F逻辑蕴含X→Y，或称X→Y是F的逻辑蕴含。2.Armstrong公理系统(1)Armstrong公理系统:设U为属性集，F是U上的函数依赖集，于是有关系模式R〈U，F〉。1)自反律：若YXU，则X→Y为F所蕴含。2)增广律：若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。3)传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。(2)Armstrong公理的三个推理1)合并规则：由X→Y，X→Z，有X→YZ。2)伪传递规则：由X→Y，WY→Z，有XW→Z。3)分解规则：由X→Y及ZY，有X→Z。3.函数依赖集闭包F+和属性集闭包XF+(1)函数依赖集闭包F+和属性集闭包XF+的定义定义：在关系模式R〈U，F〉中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。定义：设有关系模式R〈U，F〉，X是U的子集，称所有从F推出的函数依赖集X→Ai中Ai的属性集为X的属性闭包，记作XF+。即：XF+={Ai|Ai∈U，X→Ai∈F+}(2)属性集闭包XF+的求法1)选X作为闭包XF+的初值XF(0)。2)XF(i+1)是由XF(i)并上集合A所组成，其中A为F中存在的函数依赖Y→Z，而AZ，YXF(i)。3)重复步骤2)。一旦发现XF(i)=XF(i+1)，则XF(i)为所求XF+。例子【例7-1】已知关系R〈U，F〉，其中U={A，B，C，D，E}，F={AB→C，B→D，C→E，EC→B，AC→B}，求(AB)F+。设X=AB∵XF(0)=ABXF(1)=ABCDXF(2)=ABCDEXF(3)=XF(2)=ABCDE∴(AB)F+=ABCDE={A，B，C，D，E}4.函数依赖集的最小化(1)最小函数依赖集的定义1)F中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。3)F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z-A}与F等价。(2)最小函数依赖集的求法1)逐一检查F中各函数依赖X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|j=1，2，…k}来取代X→Y。2)逐一检查F中各函数依赖X→A，令G=F-{X→A}，若A∈XG+，则从F中去掉此函数依赖。3)逐一取出F中各函数依赖X→A，设X=B1B2…Bm，逐一检查Bi（i=1，2，…，m），如果A∈(X-Bi)F+，则以X-Bi取代X。【例7-2】设F={A→BC，B→AC，C→A}，对F进行极小化处理。解：1)根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。F={A→B，A→C，B→A，B→C，C→A}2)去掉F中冗余的函数依赖。判断A→B。设：G1={A→C，B→A，B→C，C→A}，得：AG1+=AC∵BAG1+∴A→B不冗余判断A→C。设：G2={A→B，B→A，B→C，C→A}，得：AG2+=ABC∵CAG2+∴A→C冗余判断B→A。设：G3={A→B，B→C，C→A}，得：BG3+=BCA∵ABG3+∴B→A冗余判断B→C。设：G4={A→B，C→A}，得：BG4+=B∵CBG4+∴B→C不冗余判断C→A。设：G5={A→B，B→C}，得：CG5+=C∵ACG5+∴C→A不冗余Fm={A→B，B→C，C→A}【例7-3】求F={AB→C，A→B，B→A}的最小函数依赖集Fm。解：(1)去掉F中冗余的函数依赖。判断AB→C是否冗余。设：G1={A→B，B→A}，得：(AB)G1+=AB∵C(AB)G1+∴AB→C不冗余判断A→B是否冗余。设：G2={AB→C，B→A}，得：AG2+=A∵BABG2+∴A→B不冗余判断B→A是否冗余。设：G3={AB→C，A→B}，得：BG3+=B∵ABG3+∴B→A不冗余经过检验后的函数依赖集仍然为F={AB→C，A→B，B→A}。(2)去掉各函数依赖左部冗余的属性。本题只需考虑AB→C的情况。方法1：在决定因素中去掉B，若CAF+，则以A→C代替AB→C。求得：AF+=ABC∵CAF+∴以A→C代替AB→C故：Fm={A→C，A→B，B→A}方法2：在决定因素中去掉A，若CBF+，则以B→C代替AB→C。求得：BF+=ABC∵CBF