第6章 关系数据理论

教学目的：①关系模式的异常问题②函数依赖③Armstrong公理④闭包及其计算算法⑤最小依赖集和候选码的求解方法⑥1NF,2NF,3NF和BCNF的概念⑦模式分解的等价标准重点难点：①Armstrong公理系统②最小依赖集和候选码的求解方法③如何将模式分解为1NF,2NF,3NF和BCNF教学方法：多媒体教学教学课时：10节理论课+2节习题课目录6.1问题的提出6.2规范化6.3函数依赖的公理系统6.4模式的分解6.1问题的提出针对一个具体的问题，应该如何构造一个适合于它的数据模式？即应该构造几个关系模式？每个关系模式由哪些属性组成呢？这就是数据库设计的问题。对于一个信息系统来说，如果所设计的数据库均具有良好的、合理的范式级别，那么系统的正确性将自动得到某种保证。如：对于学生和课程的关系模式，属性集：U={sno、dept、dean、cno、grade}关系模式包含的语义：(1)一个系有多名学生，但一个学生只属于一个系(2)一个系只有一名正系主任(3)一个学生可以选修多门课程，一门课程有多名学生选修根据语义，得到属性之间有某种关系，即属性值之间的相互依赖又相互制约的关系，称它为数据依赖。数据依赖分为：函数依赖和多值依赖。1、数据依赖一个关系模式描述为：R(U,D,dom,F)，F是属性组U上的一组数据依赖。假如有下关系模式：学生表D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)在数据库中的D表模式信息如图表：Sno(5)Sname(10)Sdept(10)Sage(2)Cno(5)Cname(20)Credit(2)Grade(2)0001张三计算机17c101数据结构4900001张三计算机17c102网络安全3880001张三计算机17c103软件工程4780001张三计算机17c105数值分析2800001张三计算机17c110编译原理3860002李四物理19c103软件工程4820002李四物理19c105数值分析2800003王五计算机17c107C语言475此关系的关键字：sno+cno2、什么是不好的关系模式？此表包含了哪些信息呢？①一个学生可以选多门课程②一门课程可以被多名学生选修③一个学生选修一门课程的成绩在实际应用中，此关系会不会出现问题呢？可能出现些什么问题？第一类问题是数据冗余太大，这表现在：总字节数=(5+10+10+2+5+20+2+2)*8=448B关于学生张三的sname、sdept和Sage在关系中出现了五次。这样，一方面浪费存储空间，另一方面系统要付出很大的代价来维护数据库的完整性。第二类问题是更新出现异常，这表现在：（1）修改异常：如果把张三同学的sdept改为“数学”，那么它要修改5次，在维护D表时不够小心的话，可能我只修改了四次，漏掉了一个，那么张三同学的sdept的值就有两个（计算机，数学），这样造成数据不一致。(2)插入异常：此表的主关键字是(sno,cno),那么这两个字段不能为空。在这个数据表中，如果我们要插入一门课程的信息，但此课程本学期不开设，故无学生选读，这样就无法将这门课程的信息存入到数据表中，这就使表在功能上产生了极不正常的现象。如果在Sno和Sname两属性上定义了非空约束，上述元组的插入就是非法操作。（该插入的数据不能插入。）(3)删除异常：如果在这个数据表中0003的王五同学因病退学，因而有关他的元组在数据表中就被删除，但遗憾的是在王五的有关情况删除时，连课程“C语言”的有关信息也同时被删除了(因为在这个数据表中，只有在王五这个元组中记载有“C语言”课程的有关信息)，并且在整个数据表中再也找不到有关课程“C语言”的有关信息了。这就叫做：“城门失火，殃及池鱼”。这也是数据表中的一种极其不正常的现象，这种现象就叫删除异常。（不该被删除的数据被删除。）问题的分析这两类现象的根本原因在于关系的结构。一个关系可以有一个或者多个候选键，其中一个可以选为主键。主键的值唯一确定其他属性的值，它是各个元组之间区别的标识，也是一个元组存在的标识。这些候选键的值不能重复出现，也不能全部或者部分设为空值。本来这些候选键都可以作为独立的关系存在，而现在却不得不依附于其他关系而存在。这就是关系结构带来的限制，它不能正确反映现实世界的真实情况。如果在构造关系模式的时候，不从语义上研究和考虑到属性间的这种关联，而简单地将有关系和无关系的、关系密切的和关系松散的属性都随意编排在一起，就必然发生某种冲突，引起某些“排它”现象出现，即冗余度水平较高，更新产生异常。解决问题的根本方法就是将关系模式进行分解，也就是进行关系的规范化。6.2规范化•关系数据库中关系规范化问题在1970年Codd提出关系模型时同时被提出来。•关系模式必须是规范化的，规范化的最基本要求是关系的每个分量必须是不可再分的数据项。但是，并不是所有满足基本要求的关系模式就是一个好的关系模式，一个好的关系模式必须能很好的反映现实世界。为了说明一个好的关系模式如何能真实的反映现实世界，必须首先要研究关系模式中属性之间的数据依赖关系。snocnogradesdeptdean1、函数依赖FD(FunctionalDependency)给定一个属性的值，另一个属性的值也会唯一的确定了。这种关系像数学中的函数。因此称之为函数依赖。如前例：学生(sno，sdept、dean、cno、grade)规定：一个学生只能属于一个系，一个系只能有一个系主任，每个学生每学一门课程只有一个成绩。即：sno的值一经确定后sdept的值也随之唯一地确定了，此时即称sno函数决定sdept或称sdept函数依赖于sno，它可用下面符号表示：sno→sdept同样，我们还可以有：sdept→dean(sno，cno)→grade其函数依赖图为：6.2.1函数依赖定义6.1：设有关系模式R(U)，属性集合U={A1,A2,…,An}，X，Y是U的子集，设u,v是关系r中的任意两个元组，若有u[X]=v[X]，就有u[Y]=v[Y](即r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等。换句话说，对于任一个关系R中的任一元组在X中的属性值确定后则在Y中的属性值必确定)，则称Y函数依赖于X或称X函数决定Y,并记作X→Y，而其中X称为决定因素，Y称为依赖因素。例如：在关系D中，各属性间的函数依赖集合为：F={sno→sname,sno→sdept,sno→sage,cno→cname，cno→credit,cno+sno→grade}课堂练习：设有一个关系模式R(A,B,C,D)，在关系R中，属性值间有这样的联系：A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系；C值与D值是一对一联系，即每个C值只有一个D值与之联系，每个D值只有一个C值与之联系。试写出相应的函数依赖。B→AD→C，C→D函数依赖与属性关系：属性之间有3种关系，但并不是每一种关系中都存在函数依赖。设有属性集X、Y以及关系模式R：•如果X和Y之间是“1：1”关系(学校和校长)，则存在函数依赖：X→Y和Y→X•如果X和Y之间是“m：1”关系(学生和班长)，则存在函数依赖：X→Y•如果X和Y之间是“m：n”关系(学生和课程)，则X和Y之间不存在函数依赖。注意：①不是R的某个关系，而是R的一切关系，任意抽取两个元组②函数依赖与码有关，而函数依赖和码都是由语义决定的，是由数据库开发人员，根据用户模型和事务规则人为确定的。所以数据依赖属于语义范畴，不能用数学方法去证明。2、平凡函数依赖与非平凡函数依赖设函数依赖关系X→Y，若满足YX，则称此函数依赖是非平凡的函数依赖。在本章中若无特殊声明，凡提到函数依赖时总认为指的是非平凡的函数依赖。设函数依赖关系X→Y，若满足YX，则称此函数依赖是平凡的函数依赖。若X→Y，Y→X，称为X←→Y这里引入一种完全函数依赖的概念，这个概念为真正的函数依赖打下基础。例如在D中我们有Sno→Sdept，因而我们同样也会有：(Sno，Sname)→Sdept(Sno，Sage)→Sdept比较这三种函数依赖后我们会发现，实际上真正起作用的函数依赖是：Sno→Sdept而其他两种函数依赖都是由它派生而成的，即是说在函数依赖中真正起作用的是Sno，而不是Snane或Sage等。这样，我们在研究函数依赖时要区别这两种不同类型的函数依赖，前一种叫完全函数依赖，而后一种叫不完全函数依赖(部分函数依赖)。3、完全函数依赖与部分函数依赖定义6.2：R(U)中如有X，YU，满足X→Y，且对任何X的真子集X’，都有X’→Y不成立，则称Y完全函数依赖于X，并记作：XY在R(U)中如有X，YU，满足X→Y，对任何X的真子集X’，都有X’→Y成立，则称Y部分依赖于X，或称Y函数依赖于X的某个真子集，记作：XY由上所述可知，Sdept完全函数依赖于Sno，但Sdept不完全函数依赖于(Sno，Sname)，亦即有：SnoSdept(Sno，Sname)Sdept(Sno，Sage)SdeptFPFPP在函数依赖中还要区别直接函数依赖与间接函数依赖这两个不同的概念，例如Sno→Sdept中Sdept是直接函数依赖于Sno，但如果在属性中有系主任dean(假如每个系有唯一的一个系主任)，则有：Sdept→dean，从而由Sno→Sdept及Sdept→dean可得到：Sno→dean在这个函数依赖中，dean并不直接函数依赖于Sno，而是经过中间属性Sdept传递而依赖于Sno，亦即是dean直接依赖于Sdept(Sdept不依赖于Dean)，而Sdept又直接依赖于Sno，从而构成了dean依赖于Sno。这种函数依赖关系，是一种间接依赖关系，或叫传递依赖关系。我们可以对它定义如下。定义6.3：在R(U)中如有X，Y，ZU且满足：X→Y，(YX)Y/X，Y→Z则称Z传递函数依赖于X，否则，称为非传递函数依赖。记为：XZT4、传递函数依赖定义6.4：设K为RU,F中的属性或属性组合，若KU且满足KU,则K为R的候选码。若候选码多于一个，则选定其中的一个为主码。在最简单的情况下，候选码只包含一个属性。包含在任何一个候选码中的属性，叫做主属性。不包含在任何码中的属性称为非主属性或非码属性。所有的属性的组合构成候选码，这时称为全码。F例：有关系CSZ(city，st，zip)，其中有三个属性：城市city，街道st，邮政编码zip。其函数依赖关系为：F={(city,st)→zip，zip→city}解：在这个关系模式中，有两个候选码(city，st)和(st，zip)。所以city，st，zip都是主属性。6.2.2码(键)6.3函数依赖的公理系统1、逻辑蕴涵定义6.11：设F是关系模式R的函数依赖集合，由F出发可以证明其他某些函数依赖也成立，我们称这些函数依赖被F逻辑蕴涵。如：F={A→B，B→C}，从这个函数依赖集中可以推出A→C，所以说函数依赖集F逻辑蕴涵函数依赖A→C。1974年W.W.Armstrong首先提出了函数依赖的公理系统，称为Armstrong公理(Armstrong’saxioms)。对于一组已知的函数依赖，利用该公理可导出所逻辑蕴函的函数依赖，从而确定一个关系模式中的码。2、Armstrong公理公理如下：设U为属性集总体，X，Y，Z，W均是U的子集，F是U上的一组函数依赖,于是有关系模式R〈U,F〉。对R〈U,F〉且有：A1：若YXU,则X→Y为F所蕴涵(自反律)。A2：若X→Y为F所蕴含,且ZU,则XZ→YZ为F所蕴涵(增广律)。A3：若X→Y及Y→Z为F所蕴含,则X→Z为F所蕴涵(传递律)。根据Armstrong公理可以得到下面另三条很有用的推论:推论1：由X→Y,X→Z,有X→YZ（合并律）。推论2：由X→Y,WY→Z,有XW→Z（伪传递律）。推论3：由X→ZY,有X→Y及X→Z成立（分解律）。4、算法6.1属性集闭包的计算。原则上讲，对于一个关系模式R(U,F)，根据