《数据库系统原理教学课件》.ppt

关系数据理论关系数据理论问题的提出问题的提出规范化规范化数据依赖的公理系统数据依赖的公理系统模式的分解模式的分解小结小结1关系数据库逻辑设计关系数据库逻辑设计l针针对对具具体体问问题题，如如何何构构造造一一个个适适合合于于它它的数据模式的数据模式l数数据据库库逻逻辑辑设设计计的的工工具具关关系系数数据据库库的的规范化理论规范化理论2概念概念回顾l关系关系l关系模式关系模式l关系数据库关系数据库l关系数据库的模式关系数据库的模式3关系模式的形式化定义关系模式的形式化定义关系模式五元组关系模式五元组R(U,D,DOM,F)R：关系名关系名U：组成该关系的属性名集合组成该关系的属性名集合D：属性组属性组U中属性所来自的域中属性所来自的域DOM：属性向域的映象集合属性向域的映象集合F：属性间数据依赖关系的集合属性间数据依赖关系的集合4数据依赖数据依赖l一个关系内部属性与属性之间的约束关系一个关系内部属性与属性之间的约束关系l现实世界属性间相互联系的抽象现实世界属性间相互联系的抽象l数据内在的性质数据内在的性质l语义语义的体现的体现5数据依赖的类型数据依赖的类型l函数依赖函数依赖lFunctionalDependency，简记为，简记为FDl多值依赖多值依赖lMultivaluedDependency，简记为，简记为MVD6关系模式的简化表示关系模式的简化表示l关系模式关系模式R（U,D,DOM,F）简化为一个三元组：简化为一个三元组：R（U,F）l当且仅当当且仅当U上的一个关系上的一个关系r满足满足F时，时，r称称为为关系模式关系模式R（U,F）的一个）的一个关系关系7函数依赖对关系模式的影响函数依赖对关系模式的影响例例1建立一个描述学校教务的数据库：建立一个描述学校教务的数据库：学生的学号（学生的学号（Sno）、所在系（）、所在系（Sdept）系主任姓名（系主任姓名（Mname）、课程名（）、课程名（Cname）成绩（成绩（Grade）单一单一的关系模式的关系模式：StudentU Sno,Sdept,Mname,Cname,Grade 8 属性组属性组U上的一组函数依赖上的一组函数依赖F：FSnoSdept,SdeptMname,(Sno,Cname)GradeSnoCnameSdeptMnameGrade9关系模式关系模式Student中存在的问题中存在的问题1.1.数据冗余太大数据冗余太大2.2.更新异常（更新异常（Update AnomaliesUpdate Anomalies）3.3.插入异常（插入异常（Insertion AnomaliesInsertion Anomalies）4.4.删除异常（删除异常（Deletion AnomaliesDeletion Anomalies）10结论：结论：nStudent关系模式不是一个好的模式。关系模式不是一个好的模式。n“好好”的模式：的模式：不会发生插入异常、删除异常、更新异常，不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少数据冗余应尽可能少原因：原因：由存在于模式中的由存在于模式中的某些数据依赖某些数据依赖引起的引起的解决方法：解决方法：通过通过分解分解关系模式来消除其中不合适关系模式来消除其中不合适的数据依赖的数据依赖11分解关系模式分解关系模式l把这个单一模式分成把这个单一模式分成3个关系模式：个关系模式：S（Sno，Sdept，SnoSdept）;SC（Sno，Cno，Grade，（，（Sno，Cno）Grade）;DEPT（Sdept，Mname，SdeptMname）12问题的提出问题的提出规范化规范化数据依赖的公理系统数据依赖的公理系统模式的分解模式的分解小结小结13函数依赖函数依赖l函数依赖函数依赖l平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖l完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖l传递函数依赖传递函数依赖14函数依赖函数依赖 设设R(U)是一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子集的子集若对于若对于R(U)的的任意任意一个可能的关系一个可能的关系r，r中不可能存在两中不可能存在两个元组在个元组在X上的属性值相等，上的属性值相等，而在而在Y上的属性值不等，上的属性值不等，则称则称“X函数确定函数确定Y”或或“Y函数依赖于函数依赖于X”记作记作XY。15说明说明 1.所有关系实例所有关系实例均要满足均要满足2.语义范畴语义范畴的概念的概念3.数据库设计者可以对现实世界作强制的规定数据库设计者可以对现实世界作强制的规定16平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖在关系模式在关系模式R(U)中，对于中，对于U的子集的子集X和和Y，如果如果XY，但，但Y X，则称，则称XY是是非平凡的函数依赖非平凡的函数依赖若若XY，但，但Y X,则称则称XY是是平凡的函数依赖平凡的函数依赖l例：在关系例：在关系SC(Sno,Cno,Grade)中，中，非平凡函数依赖：非平凡函数依赖：(Sno,Cno)Grade平凡函数依赖：平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)Cno17若若XY，则，则X称为这个函数依赖的决定属称为这个函数依赖的决定属性组，也称为决定因素（性组，也称为决定因素（Determinant）。）。若若XY，YX，则记作，则记作XY。若若Y不函数依赖于不函数依赖于X，则记作，则记作XY。18完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖在在R(U)中，如果中，如果XY，并且对于，并且对于X的任何一个真的任何一个真子集子集X，都有，都有XY,则称则称Y对对X完全函数依赖完全函数依赖，记作记作XFY。若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y对对X部分函数依赖部分函数依赖，记作，记作XPY。19例例1中中(Sno,Cno)Grade是完全函数依赖，是完全函数依赖，(Sno,Cno)Sdept是部分函数依赖是部分函数依赖因为因为SnoSdept成立，且成立，且Sno是（是（Sno，Cno）的真子集）的真子集 FP20传递函数依赖传递函数依赖在在R(U)中，如果中，如果XY，(Y X),YXYZ，则称则称Z对对X传递函数依赖传递函数依赖记为：记为：XZ 注注:如果如果YX，即即XY，则，则Z直接依赖于直接依赖于X例例:在关系在关系Std(Sno,Sdept,Mname)中，有：中，有：SnoSdept，SdeptMnameMname传递函数依赖于传递函数依赖于Sno传递传递21码码设设K为为R中的属性或属性组合。若中的属性或属性组合。若KU则则K称为称为R的的侯选码侯选码（CandidateKey）。）。若候选码多于一个，则选定其中的一个做为若候选码多于一个，则选定其中的一个做为主主码码（PrimaryKey）。）。码的最小化规则：码的任何一个真子集都不能是码的最小化规则：码的任何一个真子集都不能是码码F22l主属性与非主属性主属性与非主属性包含在任何一个候选码中的属性包含在任何一个候选码中的属性，称，称为主属性为主属性（Primeattribute）不包含在任何码中的属性称为不包含在任何码中的属性称为非主属性非主属性（Nonprimeattribute）或）或非码属性非码属性（Non-keyattribute）l全码全码整个属性组是码，称为整个属性组是码，称为全码全码（All-key）23例例2关系模式关系模式S(Sno,Sdept,Sage)，单个属性，单个属性Sno是码，是码，SC（Sno，Cno，Grade）中，（）中，（Sno，Cno）是码）是码例例3关系模式关系模式R（P，W，A）P：演奏者：演奏者W：作品：作品A：听众：听众一个演奏者可以演奏多个作品一个演奏者可以演奏多个作品某一作品可被多个演奏者演奏某一作品可被多个演奏者演奏听众可以欣赏不同演奏者的不同作品听众可以欣赏不同演奏者的不同作品码为码为(P，W，A)，即，即All-Key24外码外码 关系模式关系模式R 中属性或属性组中属性或属性组X 并非并非R的码，但的码，但X 是另一个关系模式的码，则称是另一个关系模式的码，则称X 是是R 的的外码外码（Foreignkey）l如在如在SC（Sno，Cno，Grade）中，）中，Sno不是码，但不是码，但Sno是关系模式是关系模式S（Sno，Sdept，Sage）的码，则）的码，则Sno是关系模式是关系模式SC的外码的外码l主码与外码一起提供了表示关系间联系的手段主码与外码一起提供了表示关系间联系的手段25范式范式l范式是符合某一种级别的关系模式的集合范式是符合某一种级别的关系模式的集合l关系数据库中的关系必须满足一定的要求。满关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式足不同程度要求的为不同范式l范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)26模式分解与规范化模式分解与规范化l各种范式之间存在联系：各种范式之间存在联系：l某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为RnNFl一个低一级范式的关系模式，通过一个低一级范式的关系模式，通过模式分解模式分解可可以转换为若干个高一级范式的关系模式的集合，以转换为若干个高一级范式的关系模式的集合，这种过程就叫这种过程就叫规范化规范化271NF如果一个关系模式如果一个关系模式R的所有属性都是的所有属性都是不可分的基本不可分的基本数据项数据项，则，则R1NFl第一范式是对关系模式的最起码的要求第一范式是对关系模式的最起码的要求l不满足第一范式的数据库模式不能称为关系数据库不满足第一范式的数据库模式不能称为关系数据库l满足第一范式的关系模式并不一定是一个好的关系满足第一范式的关系模式并不一定是一个好的关系模式模式28例例4关系模式关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)，Sloc为学生住处，假设每个系的学生为学生住处，假设每个系的学生住在同一个地方住在同一个地方l函数依赖包括：函数依赖包括：(Sno,Cno)FGradeSnoSdept(Sno,Cno)PSdeptSnoSloc(Sno,Cno)PSlocSdeptSloc29lS-L-C的码为的码为(Sno,Cno)lS-L-C满足第一范式。满足第一范式。l非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocS-L-C30S-L-C是一个好的关系模式吗？是一个好的关系模式吗？(1)插入异常插入异常(2)删除异常删除异常(3)数据冗余度大数据冗余度大(4)修改复杂修改复杂31S-L-C不是一个好的关系模式不是一个好的关系模式l原因原因Sdept、Sloc部分函数依赖于码。部分函数依赖于码。l解决方法解决方法S-L-C分解为两个关系模式，以消除这些部分分解为两个关系模式，以消除这些部分函数依赖函数依赖SC（Sno，Cno，Grade）S-L（Sno，Sdept，Sloc）32函数依赖图：函数依赖图：SnoCnoGradeSCS-LSnoSdeptSlocv关系模式关系模式SC的码为（的码为（Sno，Cno）v关系模式关系模式S-L的码为的码为Snov这样非主属性对码都是完全函数依赖这样非主属性对码都是完全函数依赖33 2NF若若R1NF，且每一个，且每一个非主属性非主属性完全函数依赖完全函数依赖于码，于码，则则R2NF。例：例：S-L-C(Sno,Sdept,Sloc,Cno,Grade)1NFS-L-C(Sno,Sdept,Sloc,Cno,Grade)2NFSC（Sno，Cno，Grade）2NFS-L（Sno，Sdept，Sloc）2NF34l采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的关系，可以在一定程度上减轻原的关系，可以在一定程度上减轻原1NF关关系中存在的插入异常、删除异常、数据冗余度系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。大、修改复杂等问题。l将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不的关系，并不能完全消除关系模式中的各种异常情况和数据能完全消除关系模式中的各种异常情况和数据冗余。冗余。353NFl关系模式关系模式R中若不存在这样的码中若不存在这样的码X、属、属性组性组Y及非主属性及非主属性Z（Z Y）,使得使得XY，YZ成立，成立，YX，则称，则称R3NF。n若若R3NF，则每一个，则每一个非主属性非主属性既不部既不部分依赖分依赖于码于码也不传递依赖也不传递依赖于码。于码。36例：例：2NF关系模式关系模式S-L(Sno,Sdept,Sloc)中中函数依赖：函数依赖：SnoSdeptSdeptSnoSdeptSloc可得：可得：SnoSloc，即，即S-L中存在非主属性对码的传递中存在非主属性对码的传递函数依赖，函数依赖，S-L3NF37函数依赖图：S-LSnoSdeptSloc38l解决方法解决方法采用投影分解法，把采用投影分解法，把S-L分解为两个关系模式，分解为两个关系模式，以消除传递函数依赖：以消除传递函数依赖：S-D（Sno，Sdept）D-L（Sdept，Sloc）S-D的码为的码为Sno，D-L的码为的码为Sdept。n分解后的关系模式分解后的关系模式S-D与与D-L中不再存在传递中不再存在传递依赖依赖39S-D的码为的码为Sno，D-L的码为的码为SdeptSnoSdeptS-DSdeptSlocD-LvS-L(Sno,Sdept,Sloc)2NFS-L(Sno,Sdept,Sloc)3NFS-D(Sno，Sdept)3NFD-L(Sdept，Sloc)3NF40l采用投影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的的关系，可以在一定程度上解决原关系，可以在一定程度上解决原2NF关系中存在的插关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题入异常、删除异常、数据冗余度大、修改复杂等问题l将一个将一个2NF关系分解为多个关系分解为多个3NF的关系后，仍然不能的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。完全消除关系模式中的各种异常情况和数据冗余。41BC范式（范式（BCNF）l关系模式关系模式R1NF，若，若XY且且Y X时时X必含有码，则必含有码，则RBCNF。l等价于：每一个决定属性因素都包含码等价于：每一个决定属性因素都包含码42l若若RBCNF所有非主属性对每一个码都是完全函数依赖所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码，也是所有的主属性对每一个不包含它的码，也是完全函数依赖完全函数依赖没有任何属性完全函数依赖于非码的任何一没有任何属性完全函数依赖于非码的任何一组属性组属性lR BCNF R 3NF充分充分不必要不必要43例例5关系模式关系模式C（Cno，Cname，Pcno）nC3NFnCBCNF例例6关系模式关系模式S（Sno，Sname，Sdept，Sage）n假定假定S有两个码有两个码Sno，SnamenS3NF。nSBCNF44例例7关系模式关系模式SJP（S，J，P）n函数依赖：（函数依赖：（S，J）P；(J，P）Sn（S，J）与（）与（J，P）都可以作为候选码）都可以作为候选码,属性相交属性相交nSJP3NF，nSJPBCNF4546l关系模式关系模式SJP（S，J，P）lS：学号；：学号；J：化验项目；：化验项目；P：送检顺序：送检顺序l约束：约束：l每个学生的每个化验项目在这个化验项每个学生的每个化验项目在这个化验项目里都有一个确定的送检顺序目里都有一个确定的送检顺序l每个化验项目的每个送检顺序编码只对每个化验项目的每个送检顺序编码只对应一位学生应一位学生47lF：l（S，J）Pl（J，P）Slkey（S，J）（）（J，P）lSJPBCNF例例8在关系模式在关系模式STJ（S，T，J）中，）中，S表示学生，表示学生，T表示教师，表示教师，J表示课程。表示课程。函数依赖：函数依赖：(S，J)T，(S，T)J，TJ(S，J)和和(S，T)都是候选码都是候选码48JSJTSTSTJ中的函数依赖中的函数依赖49lSTJ3NF没没有有任任何何非非主主属属性性对对码码传传递递依依赖赖或或部部分分依依赖赖lSTJBCNFT是决定因素，是决定因素，T不包含码不包含码50l解决方法：将解决方法：将STJ分解为二个关系模式：分解为二个关系模式：ST(S，T)BCNF，TJ(T，J)BCNF没有没有任何属性任何属性对码的部分函数依赖和传递函数依赖对码的部分函数依赖和传递函数依赖STSTTJTJ51lRBCNFR3NFl如果如果R3NF，且，且R只有一个候选码只有一个候选码RBCNFR3NF充分充分不必要不必要充分充分必要必要52多值依赖多值依赖例例9学校中某一门课程由多个教师讲授，他学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使授多门课程，每种参考书可以供多门课程使用用 53v非规范化关系非规范化关系课程课程C教师教师T参考书参考书B物理物理李勇李勇普通物理学普通物理学王军王军光学原理光学原理物理习题集物理习题集数学数学周闵周闵数学分析数学分析张平张平微分方程微分方程高等代数高等代数54把上述数据存入一张二维表把上述数据存入一张二维表Teaching：课程课程C教师教师T参考书参考书B物理物理李勇李勇普通物理学普通物理学物理物理李勇李勇光学物理光学物理物理物理李勇李勇物理习题集物理习题集物理物理王军王军普通物理学普通物理学物理物理王军王军光学物理光学物理物理物理王军王军物理习题集物理习题集数学数学周周闵闵数学分析数学分析数学数学周周闵闵微分方程微分方程数学数学周周闵闵高等代数高等代数数学数学张平张平数学分析数学分析数学数学张平张平微分方程微分方程数学数学张平张平高等代数高等代数55lTeachingBCNFlTeaching具有唯一候选码具有唯一候选码(C，T，B)，即全即全码码 56Teaching模式中存在的问题模式中存在的问题(1)数据冗余度大数据冗余度大(2)插入操作复杂插入操作复杂(3)删除操作复杂删除操作复杂(4)修改操作复杂修改操作复杂存在存在多值依赖多值依赖57多值依赖多值依赖l设设R(U)是一个属性集是一个属性集U上的一个关系模式，上的一个关系模式，X、Y和和Z是是U的子集，并且的子集，并且ZUXY。关系模式。关系模式R(U)中中多值依赖多值依赖XY成立，当且仅当对成立，当且仅当对R(U)的的任一关系任一关系r，给定的一对（，给定的一对（x，z）值，有一组）值，有一组Y的值，的值，这组值仅仅决定于这组值仅仅决定于x值而与值而与z值无关值无关l例例Teaching（C,T,B）58l多值依赖的另一个等价的形式化的定义：多值依赖的另一个等价的形式化的定义：在在R（U）的任一关系）的任一关系r中，如果存在元组中，如果存在元组t，s 使得使得tX=sX，那么就必然存在元组那么就必然存在元组w，v r，（，（w，v可以与可以与s，t相同），使相同），使得得wX=vX=tX，而，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换（即交换s，t元组的元组的Y值所得的两个新元组必在值所得的两个新元组必在r中），中），则则Y多值依赖于多值依赖于X，记为，记为XY。这里，这里，X，U的子集，的子集，Z=U-X-Y。59平凡多值依赖和非平凡的多值依赖平凡多值依赖和非平凡的多值依赖若若XY，而，而Z，则称，则称XY为为平凡的多值依赖平凡的多值依赖否则称否则称XY为为非平凡的多值依赖非平凡的多值依赖60例例10关系模式关系模式WSC（W，S，C）nW表示仓库，表示仓库，S表示保管员，表示保管员，C表示商品表示商品n假设每个仓库有若干个保管员，有若干假设每个仓库有若干个保管员，有若干种商品种商品n每个保管员保管所在的仓库的所有商品每个保管员保管所在的仓库的所有商品n每种商品被所有保管员保管每种商品被所有保管员保管 61WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C562WS且且WC用下图表示这种对应用下图表示这种对应63多值依赖的性质多值依赖的性质（1）多值依赖具有对称性）多值依赖具有对称性若若XY，则，则XZ，其中，其中ZUXY（2）多值依赖具有传递性）多值依赖具有传递性若若XY，YZ，则则XZY（3）函数依赖是多值依赖的特殊情况。）函数依赖是多值依赖的特殊情况。若若XY，则，则XY。（4）若）若XY，XZ，则，则XY Z。（5）若）若XY，XZ，则，则XYZ。（6）若）若XY，XZ，则，则XY-Z，XZ-Y。64多值依赖与函数依赖的区别多值依赖与函数依赖的区别(1)多值依赖的有效性与属性集的范围有关多值依赖的有效性与属性集的范围有关(2)若函数依赖若函数依赖XY在在R（U）上成立，则对于任）上成立，则对于任何何Y Y均有均有XY成立成立多值依赖多值依赖XY若在若在R(U)上成立，不能断言上成立，不能断言对于任何对于任何Y Y有有XY成立成立654NFl关系模式关系模式R1NF，如果对于，如果对于R的每个非平凡多的每个非平凡多值依赖值依赖XY（Y X），），X都含有码，则都含有码，则R4NF。l如果如果R4NF，则则RBCNFn不允许不允许有非平凡且非函数依赖的有非平凡且非函数依赖的多值依赖多值依赖n允许允许的非平凡多值依赖是的非平凡多值依赖是函数依赖函数依赖66例：例：Teaching(C,T,B)4NF存在非平凡的多值依赖存在非平凡的多值依赖CT，且，且C不是码不是码n用投影分解法把用投影分解法把Teaching分解为如下两个关系分解为如下两个关系模式：模式：CT(C,T)4NFCB(C,B)4NFCT，CB是平凡多值依赖是平凡多值依赖 67规范化小结规范化小结l关系数据库的规范化理论是数据库逻辑设计的关系数据库的规范化理论是数据库逻辑设计的工具工具l目的：尽量消除插入、删除一场，修改复杂，目的：尽量消除插入、删除一场，修改复杂，数据冗余数据冗余l基本思想：逐步消除数据依赖中不合适的部分基本思想：逐步消除数据依赖中不合适的部分实质：概念的实质：概念的单一化单一化68关系模式规范化的基本步骤关系模式规范化的基本步骤1NF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除决定属性消除决定属性2NF集非码的非平集非码的非平消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖凡函数依赖凡函数依赖3NF消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖BCNF消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖4NF69l不能说规范化程度越高的关系模式就越好不能说规范化程度越高的关系模式就越好l在设计数据库模式结构时，必须对现实世界的在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式一个合适的、能够反映现实世界的模式l上面的规范化步骤可以在其中任何一步终止上面的规范化步骤可以在其中任何一步终止70关系数据理论关系数据理论问题的提出问题的提出规范化规范化数据依赖的公理系统数据依赖的公理系统模式的分解模式的分解小结小结71逻辑蕴含逻辑蕴含 对于满足一组对于满足一组函数依赖函数依赖F 的关系模式的关系模式R，其任何一个关系，其任何一个关系r，若函数依，若函数依赖赖XY都成立都成立,（即（即r中任意两元组中任意两元组t，s，若，若tX=sX，则，则tY=sY），则），则称称F逻辑蕴含逻辑蕴含X Y72 Armstrong公理系统公理系统 关系模式关系模式R 有以下的推理规则：有以下的推理规则：A1.自反律自反律（Reflexivity）：若）：若Y X U，则则X Y为为F所蕴含。所蕴含。A2.增广律增广律（Augmentation）：若）：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。73定理定理 Armstrong推理规则是正确的推理规则是正确的（l）自反律）自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证:设设Y X U对对R 的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立，自反律得证成立，自反律得证74定理定理 Armstrong推理规则是正确的（续）推理规则是正确的（续）(2)增广律增广律:若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F所蕴含。所蕴含。证：证：设设XY为为F所蕴含，且所蕴含，且Z U。设设R的任一关系的任一关系r中任意的两个元组中任意的两个元组t，s：若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以，所以XZYZ为为F所蕴含，增广律得证。所蕴含，增广律得证。75定理定理 Armstrong推理规则是正确的（续）推理规则是正确的（续）(3)传递律：若传递律：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于XY，有，有tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含，传所蕴含，传递律得证。递律得证。76导出规则导出规则1.根据根据A1，A2，A3这三条推理规则可以得到这三条推理规则可以得到下面三条推理规则：下面三条推理规则：合并规则合并规则：由：由XY，XZ，有，有XYZ。（A2，A3）伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。（A2，A3）分解规则分解规则：由：由XY及及Z Y，有，有XZ。（A1，A3）77导出规则导出规则2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理引理引理XA1 A2Ak成立的充分必要条件成立的充分必要条件是是XAi成立（成立（i=l，2，k）78Armstrong公理系统的性质公理系统的性质lArmstrong公理系统公理系统n有效性：由有效性：由F出发根据出发根据Armstrong公理推导公理推导出来的每一个函数依赖一定在出来的每一个函数依赖一定在F+中；中；n完备性：完备性：F+中的每一个函数依赖，必定可中的每一个函数依赖，必定可以由以由F出发根据出发根据Armstrong公理推导出来公理推导出来79函数依赖闭包函数依赖闭包在关系模式在关系模式R中为中为F所逻辑蕴含的函数依所逻辑蕴含的函数依赖的全体叫作赖的全体叫作F的闭包的闭包，记为，记为F+。设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U，XF+=A|XA能由能由F 根据根据Armstrong公理导出公理导出，XF+称为属性集称为属性集X关于函数依赖集关于函数依赖集F 的闭包的闭包80F的闭包的闭包F=XY,YZF+=X,Y,Z,XY,XZ,YZ,XYZ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZ,XYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZF=XA1,XAn的闭包的闭包F+计算是计算是一个一个NP完全问题完全问题81关于闭包的引理关于闭包的引理l引理引理设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能能由由F 根据根据Armstrong公理导出的充分必要公理导出的充分必要条件是条件是Y XF+l用途用途将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出公理导出的问题，转化为求出的问题，转化为求出XF+、判定、判定Y是否为是否为XF+的子的子集的问题集的问题82求闭包的算法求闭包的算法求属性集求属性集X（X U）关于）关于U上的函数依赖集上的函数依赖集F 的闭包的闭包XF+输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B=A|(V)(W)(VW FV X（i）A W)；（3）X（i+1）=BX（i）（4）判断）判断X（i+1）=X（i）吗吗?（5）若相等或）若相等或X（i）=U,则则X（i）就是就是XF+,算法终止。算法终止。（6）若否，则）若否，则i=i+l，返回第（，返回第（2）步。）步。83求闭包的算法的复杂度求闭包的算法的复杂度对于算法对于算法6.1，令令ai=|X（i）|，ai 形成一个形成一个步长大于步长大于1的严格递增的序列，序列的上的严格递增的序列，序列的上界是界是|U|，因此该算法最多，因此该算法最多|U|-|X|次循次循环就环就会终止。会终止。84属性关于函数依赖的闭包属性关于函数依赖的闭包例例1已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+。解解设设X（0）=AB；(1)X（1）=ABCD=ABCD。(2)X（0）X（1）X（2）=X（1）BE=ABCDE。(3)X（2）=U，算法终止，算法终止（AB）F+=ABCDE。85Armstrong公理系统的有效性与完备性公理系统的有效性与完备性l定理定理Armstrong公理系统是有效的、完备的公理系统是有效的、完备的l证明：证明：1.有效性有效性可由正确性证明得证可由正确性证明得证2.完备性完备性只需证明只需证明逆否命题逆否命题:若函数依赖若函数依赖XY不能不能由由F从从Armstrong公理导出，那么它必然不为公理导出，那么它必然不为F所蕴含所蕴含86Armstrong公理系统完备性证明公理系统完备性证明(1)引理引理:若若VW成立，且成立，且V XF+，则，则W XF+(2)构造一张二维表构造一张二维表r，它由下列两个元组构成，可以证明，它由下列两个元组构成，可以证明r必是必是R（U，F）的一个关系）的一个关系，即，即F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。XF+U-XF+11.100.011.111.1(3)若若XY 不能由不能由F从从Armstrong公理导出，则公理导出，则Y 不是不是XF+的子集。的子集。8788函数依赖被逻辑蕴涵的判定函数依赖被逻辑蕴涵的判定lR（U，F），属性组），属性组X，Y U。l判定：判定：XY F+？l解决方案：解决方案：l1)X+F=?l2)Y X+F?89例子例子lF=AB,BC，ABC F+？l解解:l(AB)+F=ABC，C(AB)+FlABC F+90给定给定F，计算关系模式的码，计算关系模式的码lR=(U,F)l计算计算U的幂集的幂集l计算幂集中每一个元素在计算幂集中每一个元素在F上的闭包，若上的闭包，若闭包等于闭包等于U，则该元素是，则该元素是R的超码的超码l互相无包含关系的超码是互相无包含关系的超码是R的码的码91计算关系模式的码计算关系模式的码 例例lR(U,F)，U=SCG,F=（C，S）Gl（S：学号，：学号，C：课程号，：课程号，G：学习成绩）：学习成绩）lC+F=ClG+F=GlS+F=Sl应用自反律应用自反律92计算关系模式的码计算关系模式的码 例例lR(U,F)，U=SCG,F=（C，S）Gl（S：学号，：学号，C：课程号，：课程号，G：学习成绩）：学习成绩）lSC+F=SCGlSG+F=SGlCG+F=CGl应用自反律与应用自反律与F93计算关系模式的码计算关系模式的码 例例lR(U,F)，U=SCG,F=（C，S）Gl（S：学号，：学号，C：课程号，：课程号，G：学习成绩）：学习成绩）lSCG+F=SCGl应用自反律应用自反律l超码超码SCG，SCl码码SC94一些推论一些推论l若属性若属性X仅仅出现在出现在F的左部，则的左部，则X必然是必然是R每一个码的属性每一个码的属性l若属性若属性X未在未在F中出现，则中出现，则X必然是必然是R每一每一个码的属性个码的属性l若属性若属性X只出现在只出现在F的右部，则的右部，则X不是不是R的的主属性主属性95计算关系模式的码计算关系模式的码 例例l婚姻（男方身份证号码，女方身份证号婚姻（男方身份证号码，女方身份证号码，结婚日期，离婚日期）码，结婚日期，离婚日期）lF=(男方身份证号码男方身份证号码,结婚日期结婚日期)女方身女方身份证号码，份证号码，(女方身份证号码女方身份证号码,结婚日期结婚日期)男方身份证号码男方身份证号码K=男方身份证号码男方身份证号码,结婚日期结婚日期K=女方身份证号码女方身份证号码,结婚日期结婚日期96计算关系模式的码计算关系模式的码 例例lU=A,B,C,D,ElF=ABD，AE，CB，DClR的码必定都含有属性的码必定都含有属性AlA+F=AElB+F,C+F,D+F,E+F不必计算不必计算97计算关系模式的码计算关系模式的码 例例lU=A,B,C,D,ElF=ABD，AE，CB，DCl(AB)+F=ABDABDl(AB)+F=ABDCDCl(AB)+F=ABDCEAE98计算关系模式的码计算关系模式的码 例例lU=A,B,C,D,ElF=ABD，AE，CB，DCl(AC)+F=ACEBAE，CBl(AC)+F=ACEBDABD99计算关系模式的码计算关系模式的码 例例lU=A,B,C,D,ElF=ABD，AE，CB，DCl(AD)+F=ADECAE，DCl(AD)+F=ADECBCBK=A,B=A,C=A,D想一想为什么其余的幂集元素不必计算？想一想为什么其余的幂集元素不必计算？函数依赖集的等价函数依赖集的等价定义定义如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆盖覆盖G（F是是G的覆的覆盖，或盖，或G是是F的覆盖），或的覆盖），或F与与G等价等价。引理引理F+=G+的充分必要条件是的充分必要条件是F G+，和，和G F+证证:必要性显然，只证充分性。必要性显然，只证充分性。（1）若）若F G+，则，则XF+XG+。（2）任取）任取XY F+则有则有Y XF+XG+。所以所以XY (G+）+=G+。即。即F+G+。（3）同理可证）同理可证G+F+，所以，所以F+=G+。100最小函数依赖集最小函数依赖集定定义义如如果果函函数数依依赖赖集集F满满足足下下列列条条件件，则则称称F为为一一个个极极小函数依赖集小函数依赖集。亦称为。亦称为最小依赖集最小依赖集或或最小覆盖最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中中不不存存在在这这样样的的函函数数依依赖赖XA，使使得得F与与F-XA等价。等价。(3)F中中不不存存在在这这样样的的函函数数依依赖赖XA，X有有真真子子集集Z使得使得F-XAZA与与F等价。等价。101例例2关系模式关系模式S，其中：，其中：U=Sno，Sdept，Mname，Cno，Grade，F=SnoSdept，SdeptMname，(Sno，Cno)Grade设设F=SnoSdept，SnoMname，SdeptMname，(Sno，Cno)Grade，(Sno，Sdept)SdeptF是最小覆盖，而是最小覆盖，而F不是。不是。因为：因为：F -SnoMname与与F 等价等价 F -(Sno，Sdept)Sdept也与也与F 等价等价 102最小化过程最小化过程定定理理每每一一个个