资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据库系统原理韶关学院计算机科学与技术系2018/7/13第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 关系数据模式的规范化理论n范式(Normal Form)是指规范化的关系模 式。由满足最基本规范化的关系模式叫第一范式, 第一范式的关系模式再满足另外一些约束条件就产 生了第二范式、第三范式、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的子集。若对于R U的任意一个可能的关系r,r中不可能存在两个元组在X上的 属性值相等,而Y上的属性值不等,则称X函数确定Y函数,或Y函 数依赖于X函数,记作XY。 例如,对于教学关系模式:教学U,F; U=学号,姓名,年龄,性别,系名,系主任,课程名,成绩; F=学号姓名,学号年龄,学号性别,学号系名,系名系主 任,(学号,课程名)成绩. XY,但Y X,则称XY是非平凡的函数依赖。若不特别声 明,总是讨论非平凡的函数依赖。 XY,但YX,则称XY是平凡的函数依赖。 若XY,则X叫做决定因素(Determinant),Y叫做依赖因 素(Dependent)。 若XY,YX,则记作XY。 若Y不函数依赖于X,则记作X Y。完全函数依赖、传递函数依赖n2) 在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的定义、 2NF的定义如果关系模式R,其所有的属性均为简单属性,即每个属性 都是不可再分的,则称R属于第一范式,记作R1NF。若R1NF,且每一个非主属性完全依赖于码,则R2NF。 在教学模式中:属性集=学号,姓名,年龄,系名,系主任,课程名,成绩. 函数依赖集=学号姓名,学号年龄,学号性别,学号系名,系名系主任,(学号,课程名)成绩. 主码=(学号,课程名). F 非主属性=(姓名,年龄,系名,系主任,成绩) 。 非主属性对码的函数依赖:(学号,课程名)姓名,(学号,课程名)年龄,(学号,课程号)性别 ,(学号,课程名)系名,(学号,课程名)系主任;(学号,课程名)成绩.显然,教学模式不服从2NF,即:教学2NF。PPPPP5. 3NF的定义关系模式RU,F中若不存在这样的码X、属性组Y及 非主属性Z(ZY)使得XY、Y X、YZ成立,则称RU, F3NF。 可以证明,若R3NF,则每一个非主属性既不部分函数依赖 于码,也不传递函数依赖于码。考查学生_系关系,由于存在:学号系名,系名系 主任。则: 学号 系主任。所以学生_系3NF。 如果分解为:学生(学号,姓名,年龄,性别,系名);教学系(系名,系主任). 显然分解后的各子模式均属于3NF。传递6. BCNF的定义n关系模式RU,F1NF。若XY且YX时X必含有码,则RU,FBCNF。也就是说,关系模式RU,F中,若每一个决定因素都包含码,则RU,FBCNF。由BCNF的定义可以得到结论,一个满足BCNF的关系模式有:1) 所有非主属性对每一个码都是完全函数依赖。2) 所有的主属性对每一个不包含它的码,也是完全依赖。3) 没有任何属性完全函数依赖于非码的任何一组属性。7. BCNF和3NF的比较1) BCNF不仅强调其他属性对码的完全的直接的依赖,而且 强调主属性对码的完全的直接的依赖,它包括3NF,即 RBCNF,则R一定属于3NF。 2) 3NF只强调非主属性对码的完全直接依赖,这样就可能出 现主属性对码的部分依赖和传递依赖。 例如,关系模式STJ(S,T,J)中,S表示学生,T表示教师 ,J表示课程。语义为:每一教师只能讲授一门课程,每门课 程由若干教师讲授;每个学生选修某门课程就对应一个固定 的教师。由语义可以得到STJ模式的函数依赖为:F=(S,J)T,TJ 显然:(S,J)和(T,S)都是关系的码;关系的主属性集为 S,T,J,非主属性为(空集)。 P由于STJ模式中无非主属性,所以它属于3NF;但因为存在 TJ,由于T不是码,故STJBCNF。7.1.3 多值依赖及关系的第四范式1. 研究多值依赖的必要性 例如,给定一个关系模式JPW(产品,零件,工序),其中每种产品由多 种零件构成,每个零件在装配时需要多道工序。设产品电视机需要的零 件和工序如图所示。 显像管电视机开关电源焊接调试测试装配调试焊接调试2. 多值依赖的定义和性质设有关系模式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的逻辑蕴含 。2. 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。 3) 分解规则:由XY及ZY,有XZ。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,而AZ,YXF(i)。 3) 重复步骤2)。一旦发现XF(i)= XF(i+1),则XF(i)为所求XF+ 。例子n【例7-1】已知关系RU,F,其中U=A,B,C,D, E,F=ABC,BD,CE,ECB,ACB,求 (AB)F+。 设X=AB XF(0)=AB XF(1)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A,B,C,D,E4. 函数依赖集的最小化(1) 最小函数依赖集的定义 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为 最小依赖集或最小覆盖。 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。【例7-2】设F=ABC,BAC, CA,对F进行极小化处理。解: 1) 根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集 合,分解后的函数依赖集仍用F表示。F=AB,AC,BA,BC,CA 2) 去掉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, 得:BG3+=BCA ABG3+ BA冗余 判断BC。设:G4= AB,CA, 得:BG4+=B CBG4+ BC不冗余 判断CA。设:G5= AB,BC ,得:CG
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号