第5章 关系数据库理论13

第5章关系数据库理论第5章关系数据库理论5.1关系模式设计中的问题5.2函数依赖5.3函数依赖的公理系统5.4关系模式规范形式5.5关系模式的规范化习题5第5章关系数据库理论5.1关系模式设计中的问题随着时间的不断变化，关系也会有所变化。从理论上能否找到判断设计好的数据库模式的标准?第5章关系数据库理论例如:在校大学生的学习情况会涉及的属性：学号（S＃）、姓名（SN）、性别（SS）、身份证号（ID）、系别（SD）、学籍类型（SL）、专业（SG）、班级(SC)、课程号（CB）、课程名（CN）、学期数（T）、学分（CG）、成绩（G），其属性集合表示为U={S＃,SN,SS,ID,SD,SL,SG,SC,CB,CN,T,CG,G}。有人给出了如表5.1所示的表:第5章关系数据库理论表5.1关系r关系r存在问题?学号课程号课程名学期数学分成绩第5章关系数据库理论关系r存在的弊病：(1)冗余。课程号为J1的课程在第4学期开，课程名是“数据库系统”，在关系r的5个元组中都有记载----冗余。(2)插入异常。如果有一门课，课程号为J5，课程名为“编译原理”，学分为3，计划在第5学期开，但因为学生还未选课,学号没有确定值，构不成一个元组，无法插入到关系r中去。存在计划开设的课程因为暂时没有学生选，无法将这些课程号和课程名等信息保存到数据库中---插入异常。第5章关系数据库理论(3)删除异常。如果学号1110703的学生考J2课时违纪，分数作废，应在关系r中删去这个元组。但这个元组还包含课程号为J2，课程名为数据结构，学分为3的信息。要删除只能删除整个元组.因学号为1110703的学生的J2课分数作废，而把课程号为J2，课程名为“数据结构”，学分为3的信息也给“冤枉”地删除掉了----删除异常。不管目前有无学生学习“数据结构”这门课程，这门课程的相关信息应保留在数据库中，第5章关系数据库理论在数据库模式中，针对关系模式的某一关系r为什么会存在上述弊端呢？怎样才能在同一个属性集U上给出没有这些弊端的数据库模式呢？第5章关系数据库理论5.2函数依赖在现实世界中最广泛存在的一种数据依赖是函数依赖。例如，表5.1关系r的关系模式R={S＃,CB,CN,T,CG,G}存在的函数依赖有：T函数依赖于CB，CN函数依赖于CB，CG函数依赖于CB，G函数依赖于(S＃，CB)等。学号（S＃）、课程号（CB）、课程名（CN）、学期数（T）、学分（CG）、成绩（G），第5章关系数据库理论5.2.1函数依赖的概念函数依赖（FunctionalDependency，简记为FD）定义5.1设R(U)是属性集U上的一个关系模式，X，YU。若对R(U)中任意一个可能关系r，r中不可能有两个元组在X的属性分量值相等，而在Y的那些属性分量值不相等，则称“X函数决定Y”，或“Y函数依赖于X”，记作X→Y。X称为决定因子，或称为函数依赖的左部，Y称为函数依赖的右部。第5章关系数据库理论另一种等价定义为：设R(U)是属性集U上的一个关系模式，X，YU。对R(U)中任意一个可能关系r中的任意两个元组t和s，若有t［X］=s［X］，则有t［Y］=s［Y］，就称“X函数决定Y”，或“Y函数依赖于X”。对函数依赖，需要强调几点：(1)当确定关系模式R中的某个函数依赖时，是指R的所有可能关系r都必须满足这个函数依赖；反之，如果R中只要有一个关系r不满足这个函数依赖，就认为R不存在这个函数依赖。第5章关系数据库理论(2)当在确定一个关系模式中的函数依赖时，只能从属性含义上加以说明，而不能在数学上加以证明。(3)只有数据库设计者才能决定是否存在某种函数依赖。这就使得数据库系统可以根据设计者的意图来维护数据库的完整性。例如：关系模式R={S＃,CB,CN,T,CG,G}中的函数依赖可表示为：CB→T;(S＃,CB)→G;CB→CN;CB→CG等等。学号（S＃）、课程号（CB）、课程名（CN）、学期数（T）、学分（CG）、成绩（G），第5章关系数据库理论5.2.2几种特定的函数依赖1.非平凡函数依赖和平凡函数依赖定义5.3设关系模式R(U)，X、YU:如果X→Y，且Y不是X的子集，则称X→Y为非平凡的函数依赖；如果X→Y，且YX，则称X→Y为平凡的函数依赖。(S＃,CB)→G为非平凡的函数依赖(S＃,CB)→CB为平凡的函数依赖第5章关系数据库理论2.完全函数依赖和部分函数依赖定义5.4设关系模式R(U)，X，YU：如果X→Y，并且对于X的任何一个真子集Z，Z→Y都不成立，则称Y完全函数依赖于X;若X→Y，但对于X的某一个真子集Z，有Z→Y成立，则称Y部分函数依赖于X。例如：关系模式R={S＃,CB,CN,T,CG,G}中，CB→TT完全函数依赖于CB；(S＃,CB,CN)→G，G部分依赖于（S＃,CB,CN）因为(S＃,CB)→G，。第5章关系数据库理论3．传递函数依赖定义5.5设关系模式R(U)，XU，YU，ZU。如果X→Y，Y→Z成立，但Y→X不成立，且Z-X、Z-Y和Y-X均不空，则称X→Z为传递函数依赖。例如：关系模式R={A,B,C}，其上的函数依赖集F={A→B,B→C,A→C}，则A→C为传递函数依赖。A:学号,B:学院,C:宿舍,学生按学院分宿舍注：在函数依赖中还有两种特殊的函数依赖：X→Φ和Φ→Y，它们对于任意关系都是成立的。不考虑这样的函数依赖。第5章关系数据库理论5.2.3逻辑蕴涵在讨论函数依赖时，有时需要从一些已知的函数依赖去判断另一些函数依赖是否成立。这个问题称为逻辑蕴涵问题。1．F逻辑蕴涵X→Y定义5.6设关系模式R(U)，X，YU，F是关于R的函数依赖集合。又设X→Y为R中的一个函数依赖，就说F逻辑蕴涵X→Y，或称X→Y可从F推导出来的，或称X→Y逻辑蕴涵于F。第5章关系数据库理论2．函数依赖集合F的闭包定义5.7所有被F逻辑蕴涵的那些函数依赖组成的集合称为F的闭包，记为F+。设关系模式R(U)，U={A,B,C},F={AB→C,C→B}是R(U)上的一组函数依赖，则F+={A→A,B→B,C→C,C→B,C→BC,AB→A,AB→B,AB→C,AB→AB,AB→AC,AB→BC,AB→ABC,AC→A,AC→B,AC→C,AC→AC,BC→B,BC→C,BC→BC,ABC→A,ABC→B,ABC→C,ABC→AB,ABC→AC,ABC→BC,ABC→ABC}第5章关系数据库理论5.3函数依赖的公理系统5.3.1Armstrong公理系统1．Armstrong公理系统的三条推理规则设关系模式R(U)，X，Y，Z，WU，F是R的一个函数依赖集合，则Armstrong公理系统包含如下三条推理规则：第5章关系数据库理论（1）自反律（Reflexivity）:若YXU，则F蕴涵X→Y。（2）增广律（又称外延性，augmentation）:若F蕴涵X→Y，ZU，则F蕴涵XZ→YZ。（3）传递律（transitivity）:若F蕴涵X→Y和Y→Z，则F蕴涵X→Z。Armstrong公理提供一整套推理规则，它能从F推导出F+中的所有依赖（完备性），从F推不出任何不属于F+的依赖（正确性）。第5章关系数据库理论2．Arestrong公理的三个推论由Arestrong公理可得到下面三个推论：(1)合并规则:若X→Y，X→Z，则X→YZ。(2)分解规则:若X→Y且ZY，则X→Z。(3)伪传递规则:若X→Y，YZ→W，则XZ→W。第5章关系数据库理论定理5.2合并规则、分解规则、伪传递规则是正确的。证明：①合并规则:若X→Y，X→Z，则X→YZ。若X→Y，根据增广律得，XX→XY，即X→XY。若X→Z，根据增广律得，XY→YZ，根据传递律得，X→YZ。②分解规则:若X→Y且ZY，则X→Z。若ZY，根据自反律得，Y→Z，又已知X→Y，根据传递律得，X→Z。③伪传递规则:若X→Y，YZ→W，则XZ→W。若X→Y，根据增广律得，XZ→YZ，又已知YZ→W，根据传递律得，XZ→W。第5章关系数据库理论属性集合X关于函数依赖集F的闭包定义5.8设关系模式R(U)，U={A1,A2,…,An}，Ai∈U，XU，X+={Ai|X→Ai能由F根据Armstrong公理系统导出且Ai∈U}，则称X+是属性集合X关于函数依赖集F的闭包。第5章关系数据库理论算法5.1计算属性集X的闭包X+。输入：属性集X和函数依赖集F。输出：关于F的X的闭包X+。方法：①令X(0)=X，i=0;②令X(i+1)=X(i)∪{A|VX(i)，V→W∈F,A∈W};③若已经没有V→W∈F，能使X(i+1)≠X(i)，则X+=X(i),输出X+，算法结束；否则，令i=i+1，转去执行第(2)步。第5章关系数据库理论【例】设关系模式R(U)上的函数依赖集为F,U={A,B,C,D,E,I};F={A→D,AB→E,BI→E,CD→I,E→C}，试计算(AE)+。解：令X(0)=AE，i=0;在F中找出左边是AE子集的函数依赖，A→D,，因则X(1)=AED;因E→C，则X(2)=AEDC；因CD→I,则X(3)=AEDCI;因已没有V→W∈F，能使X(3+1)≠X(3)，则X+=X(3),即(AE)+=ACDEI。第5章关系数据库理论【例】设有关系模式R(U)，U={A,B,C,D,E}，F={A→BC,CD→E,B→D,E→A}，求B+F?A+F?B+F={B,D}，A+F={A,B,C,D,E}第5章关系数据库理论引理5.1设关系模式R(U),U={A1,A2,…,An},Ai∈U,XU，X→A1A2…An成立的充分必要条件是X→Ai(i=1,2,…,n)都成立。根据合并规则和分解规则，很容易得到这个引理的证明。引理5.2设F是关系模式R(U)上的函数依赖集，X、YU，X→Y能由F根据Armstrong公理系统导出的充分必要条件是YX+Ｆ。第5章关系数据库理论例:关系模式R(CITY,ST,ZIP)，其中CITY表示城市，ST表示城市的街道，ZIP表示街道所在地区的邮政编码，函数依赖集合F={(CITY,ST)→ZIP,ZIP→CITY}，证明{ST,ZIP}和{CITY,ST}是候选键。{ST,ZIP}+=?{CITY,ST}+=?第5章关系数据库理论证：因为ZIP→CITY（由给定条件得出）(ST,ZIP)→(CITY,ST)（由增广律得出）(CITY,ST)→ZIP（由给定条件得出）(CITY,ST)→(CITY,ST,ZIP)（由增广律得出）(ST,ZIP)→(CITY,ST,ZIP)（由传递律得出）并且，ST→(CITY,ST,ZIP)和ZIP→(CITY,ST,ZIP)均不成立，所以(ST,ZIP)是候选键。同理可证(CITY,ST)也是候选键。证毕。另:{ST,ZIP}+=?{CITY,ST}+=?第5章关系数据库理论5.3.2函数依赖集合F的极小函数依赖集实际应用中，经常需要将一个已知的函数依赖集变换为更简洁的表示形式。例如，把一个大的关系模式分解为几个小的关系模式，就需要将相应的函数依赖也投影到分解后的模式上。这涉及一个函数依赖集的等价问题。第5章关系数据库理论1.两个函数依赖集F和G等价定义5.9设模式R上的两个函数依赖集F和G，如果有F+=G+，则称F和G等价，记作F≡G。若F≡G，则F是G的一个覆盖，同样，G是F的一个覆盖。第5章关系数据库理论2.函数依赖集F的极小（最小）函数依赖集（Fmin）定义5.10如果函数依赖集F满足下列三个条件：(1)F中任一函数依赖的右部仅含有一个属性；(2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价；//不含多余的函数依赖(3)F中不存在这样的函数依赖X→A：X包括真子集Z，使得(F-{X→A})∪{Z→A}与F等价。//左边不含多余的属性称此函数依赖集为F的极小（最小）函数依赖集，记作Fmin。F的极小依赖集不一定是惟一的。第5章关系数据库理论计算函数依赖集F的极小依赖集Fmin算法。输入：一个函数依赖