数据库应用第3章Desig.ppt

关系数据库设计,满足用户的完整性和安全性要求；动态关系至少具有第三规范形式，静态关系至少具有第一规范形式；能够在逻辑级上高效率地支持各种数据库事务的运行；存储空间利用率高。,2023/10/14,2,关系数据库设计：目标,2023/10/14,3,关系数据库设计：任务,现实世界,信息世界,概念数据库设计,逻辑世界,逻辑数据库设计,物理世界,文件,物理数据库设计,形成初始关系数据库模式；关系模式规范化；关系模式优化；定义关系上的完整性和安全性约束；子模式定义；性能估计。,2023/10/14,4,关系数据库设计步骤,问题初始关系模式可以是逻辑设计的最终结果吗?某些关系模式可能存在冗余问题、插入问题、更新问题和删除问题。,2023/10/14,5,形成初始关系数据库模式,例：学生有下列信息：学号(S#)、系(SD)、系主任(MN)，课程名(CN)，成绩(G)有一个描述学生的关系模式：U=S#,SD,MN,CN,G现实世界的已知事实：F=S#SD,SDMN,(S#,CN)G,2023/10/14,6,形成初始关系数据库模式,2023/10/14,7,插入异常,2023/10/14,8,插入异常,2023/10/14,9,删除异常,2023/10/14,10,数据冗余和更新问题,数据冗余：同一系中有n个学生，“系名”与”系主任”就重复n-1次；同一个学生选修了m门课程，学号就重复了m-1次。更新异常：若调整了某系系主任，数据表中所有行的“系主任”值都要更新，否则会出现同一系系主任姓名不同的情况。,2023/10/14,11,形成初始关系数据库模式,插入异常：假设要开设一门新的课程，暂时还没有人选修。这样，由于还没有“学号”关键字，课程名称和设课系也无法记录入数据库。删除异常：假设一批学生已经完成课程的选修，这些选修记录就应该从数据库表中删除。但是，与此同时，系名与系主任信息也被删除了。很显然，这也会导致插入异常。,2023/10/14,12,形成初始关系数据库模式,需要用关系模式的规范化方法消除初始逻辑数据库模式中存在的问题。某些关系模式可能存在由属性间的函数依赖引起的冗余问题、插入问题、更新问题和删除问题。,2023/10/14,13,形成初始关系数据库模式,确定函数依赖集 函数依赖：Functional Dependency对初始关系数据库模式中的每个关系模式进行深入地分析，与用户协商，确定每个初始关系的函数依赖集，使用关系数据库设计理论，对关系模式进行规范化处理。,2023/10/14,14,形成初始关系数据库模式,函数依赖定义1：设R是一个关系模式，U是R的属性集合，X和Y是U的子集。对于R的任意实例r，r中任意两个元组t1和t2，如果t1X=t2X，则t1Y=t2Y，我们称X函数地确定Y，或Y函数依赖于X，记作XY。只能根据数据的语义来确定函数依赖。描述学生的关系模式：U=S#,SD,MN,CN,G根据数据的语义确定的函数依赖：F=S#SD,SDMN,(S#,CN)G,2023/10/14,15,设计理论,函数依赖定义1：设R是一个关系模式，U是R的属性集合，X和Y是U的子集。对于R的任意实例r，r中任意两个元组t1和t2，如果t1X=t2X，则t1Y=t2Y，我们称X函数地确定Y，或Y函数依赖于X，记作XY。只能根据数据的语义来确定函数依赖。描述学生的关系模式：U=S#,SD,MN,CN,G根据数据的语义确定的函数依赖：F=S#SD,SDMN,(S#,CN)G,2023/10/14,16,设计理论,如果XY而且Y不是X的子集，则称XY是非平凡函数依赖。若不特别声明，我们总是讨论非平凡函数依赖。如果XY，我们称X为这个函数依赖的决定属性集。描述学生的关系模式：US#,SD,MN,CN,G(S#,SD)SDSDMN,2023/10/14,17,函数依赖,定义2设R是一个具有属性集合U的关系模式，如果XY，并且对于X的任何一个真子集Z，ZY都不成立，则称Y完全函数依赖于X。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X。描述学生的关系模式：US#,SD,MN,CN,G(S#,SD)MN(S#,CN)G,2023/10/14,18,函数依赖,定义3：设R是一个具有属性集合U的关系模式，XU,YU,ZU，且YX不成立，同时Z-X、Z-Y和Y-X不空。如果XY，YZ，则称Z传递地函数依赖于X。描述学生的关系模式：U=S#,SD,MN,CN,G根据S#SD,SD MN,导出如下传递依赖：S#MN,2023/10/14,19,函数依赖,定义4：设R是一个具有属性集合U的关系模式,KU。如果K满足下列两个条件，则称K是R的一个候选键：(1)KU。(2)不存在K的真子集Z使得ZU。候选键可以唯一地标识关系的元组。,2023/10/14,20,函数依赖,一个关系模式中可能具有多个候选键，指定其中一个作为识别关系元组的主键。包含在任何一个候选键中的属性称为键属性。不包含在任何候选键中的属性称为非键属性。在最简单的情况下，候选键只包含一个属性。在最复杂的情况下，候选键包含关系模式的所有属性，称为全键。,2023/10/14,21,函数依赖,定义5：设X是关系模式R的属性子集合。如果X是另一个关系模式的候选键，则称X是R的外部键。,2023/10/14,22,函数依赖,设R是一个具有属性集合U的关系模式，F是R上的函数依赖集合。如果对于R的任意一个使F成立的关系实例r，函数依赖XY都成立，则称F逻辑地蕴含XY.已知的函数依赖：F=S#SD,SDMN,(S#,CN)G,2023/10/14,23,逻辑蕴含,S#MN成立吗？,F蕴含S#MN,给定一个函数依赖集合，希望知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。推导依据：Armstrong公理系统,2023/10/14,24,函数依赖的公理系统,Armstrong公理系统 设R是一个具有属性集合U的关系模式，F是R的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则：,2023/10/14,25,函数依赖的公理系统,自反律：若YXU，则F蕴含XY 增广律：若F蕴含XY，ZU，则F蕴含XZYZ 传递律：若F蕴含XY和YZ，则F蕴含XZ,三条推论 合并规则：如果XY，XZ，则XYZ。伪传递规则：如果XY，YWZ，则XWZ。分解规则：如果XY，ZY，则XZ。,2023/10/14,26,函数依赖的公理系统,自反律：若YXU，则F蕴含XY 增广律：若F蕴含XY，ZU，则F蕴含XZYZ 传递律：若F蕴含XY和YZ，则F蕴含XZ,引理1：XA1A2.Ak成立的充分必要条件是对于1ik，XAi成立。证明：,2023/10/14,27,函数依赖的公理系统,合并规则：如果XY，XZ，则XYZ。伪传递规则：如果XY，YWZ，则XWZ。分解规则：如果XY，ZY，则XZ。,定义7：设R是一个具有属性集合U的关系模式，F是给定的函数依赖集合。由F逻辑蕴含的所有函数依赖称为F的闭包，记为F+。描述学生的关系模式：US#,SD,MN,CN,G根据数据的语义确定的函数依赖：F=S#SD,SDMN,(S#,CN)GF+=S#SD,SDMN,(S#,CN)G,S#MN,(S#,SD)SD,2023/10/14,28,函数依赖的公理系统,Armstrong公理系统是有效而且完备的吗？Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中；Armstrong公理的完备性是指F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来。,2023/10/14,29,函数依赖的公理系统,为了证明Armstrong公理的完备性，首先需要解决如何判定一个函数依赖是否可以由F根据Armstron公理推导出来。,2023/10/14,30,函数依赖的公理系统,定义8（属性闭包）：设F为属性集U上的一组函数依赖，XU。X+=A|XA能由F根据Armstrong公理导出称为属性集X关于函数依赖集F的闭包。例:关系模式R(A1,A2,A3)的函数依赖集F为A1A2，A2A3,2023/10/14,31,函数依赖的公理系统,(1)若X=A1,X+=,(2)若X=A2,X+=,(3)若X=A3,X+=,A1,A2,A3,A2,A3,A3,引理2 设F为属性集U上的函数依赖，X、YU，XY能由F根据Armstrong公理导出的充分必要条件是Y X+。证：三条推论 合并规则：如果XY，XZ，则XYZ。伪传递规则：如果XY，YWZ，则XWZ。分解规则：如果XY，ZY，则XZ。,2023/10/14,32,函数依赖的公理系统,算法1 计算X+输入:X，F输出:X+算法:.,2023/10/14,33,函数依赖的公理系统,在整个计算机领域，算法无处不在！操作系统的进程管理，内存管理，编译系统的语法分析、词法分析、代码优化.数据库管理系统的数据操作算法、查询优化算法Google、Baidu等搜索引擎使用数据挖掘算法PageRank,2023/10/14,34,附加内容：算法介绍,算法是解决某问题的一个方法或一个过程。,时间复杂性空间复杂性排序冒泡、插入、快速等分治算法动态规划算法贪心算法近似算法,2023/10/14,35,附加内容：算法介绍,算法1 计算X+输入:X，F输出:X+1.X(1):=空集合;X(0):=X;2.B:=A|VWF，VX(0)，AW;3.X(1):=BX(0);4.IF X(1)X(0)THEN X(0):=X(1);GOTO；ELSE X+:=X(1)ENDIF.,2023/10/14,36,函数依赖的公理系统,例：计算X+=A,B,C,D,E，=ABC,ACB,BD,CE,ECB，求(AB)+。,2023/10/14,37,函数依赖的公理系统,1.X(1):=空集合;X(0):=X;2.B:=A|VWF，VX(0)，AW;3.X(1):=BX(0);4.IF X(1)X(0)THEN X(0):=X(1);GOTO；ELSE X+:=X(1)ENDIF.,定理3 算法1正确地计算出了X关于F的闭包X+。证：算法的终止性算法的正确性,2023/10/14,38,函数依赖的公理系统,定理4 Armstrong公理系统是有效而且完备的。证：Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中现只需证明完备性（Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来）。,2023/10/14,39,函数依赖的公理系统,证明完备性的逆否命题：如果函数依赖XY不能由F根据Armstrong公理导出，它必然不为F蕴含。,由F出发经Armstrong公理导出的函数依赖集合为F+,定义9：设G和F是两个函数依赖集。如果G+=F+则称F与G等价。引理3 设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+。证明：,2023/10/14,40,函数依赖的公理系统,引理3给出了一个判断两个函数依赖集等价的算法。例F=S#SD,SDMN,(S#,CN)GG=S#SD,SDMN,(S#,CN)G,S#MNF和G等价吗？,2023/10/14,41,函数依赖的公理系统,引理3 设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+。,定义10：函数依赖集F称为极小函数依赖集如果F满足下列条件:F中任一函数依赖的右部仅含有一个属性；F中不存在这样的函数依赖XA，使得F与F-XA等价；F中不存在这样的函数依赖XA：X包括真子集Z使得(F-XA)ZA与F等价。,2023/10/14,42,函数依赖的公理系统,2023/10/14,43,函数依赖的公理系统,F1=S#SD,SDMN,(S#,SD,CN)GF1是最小依赖集？F2=S#SD,SDMN,S#SD,(S#,SD)GF2是最小依赖集？,2023/10/14,44,函数依赖的公理系统,F中任一函数依赖的右部仅含有一个属性；F中不存在这样的函数依赖XA，使得F与F-XA等价；F中不存在这样的函数依赖XA：X包括真子集Z使得(F-XA)ZA与F等价。,定理5 每一个函数依赖集F都等价于一个极小函数依赖集。构造性证明。极小函数依赖集是否唯一？,2023/10/14,45,函数依赖的公理系统,极小函数依赖集不唯一例：F=AB,BA,BC,AC,CA的极小函数依赖集为F1=AB,BC,CAF=AB,BC,BA,AC,CA的极小函数依赖集为F2=AB,BA,AC,CA,2023/10/14,46,函数依赖的公理系统,函数依赖集F称为极小函数依赖集如果F满足下列条件:(1)F中任一函数依赖的右部仅含有一个属性；(2)F中不存在这样的函数依赖XA，使得F与F-XA等价；(3)F中不存在这样的函数依赖XA：X包括真子集Z使得(F-XA)ZA与F等价。,求极小函数依赖集练习：例：求F=ABC,BC,ABC的极小函数依赖集答案：AB,BC求F=ABD,AC,ADC,BD的极小函数依赖集答案：AB,AC,BD,2023/10/14,47,函数依赖的公理系统,函数依赖集F称为极小函数依赖集如果F满足下列条件:(1)F中任一函数依赖的右部仅含有一个属性；(2)F中不存在这样的函数依赖XA，使得F与F-XA等价；(3)F中不存在这样的函数依赖XA：X包括真子集Z使得(F-XA)ZA与F等价。,以函数依赖为基础讨论关系模式的规范形式(范式)。关系模式的范式包括第一范式（1NF）第二范式（2NF）第三范式（3NF）Boyce Codd范式（BCNF）第四范式(4NF)第五范式(5NF),2023/10/14,48,关系模式的规范形式,满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题、更新问题和删除问题。,2023/10/14,49,关系模式的规范形式,关系模式范式的基本概念定义11：第一范式(1NF)设R是一个关系模式。如果R的每个属性的值域都是不可分的简单数据项的集合，则称这个关系模式为第一范式关系模式，记作1NF。,2023/10/14,50,关系模式的规范形式,2023/10/14,51,关系模式的规范形式,关系模式范式的基本概念定义12：第二范式(2NF)若关系模式R是1NF，而且每一个非主属性都完全函数依赖于R的键，则R称为第二范式关系模式，记作2NF。,2023/10/14,52,关系模式的规范形式,完全依赖定义设R是一个具有属性集合U的关系模式，如果XY，并且对于X的任何一个真子集Z，ZY都不成立，则称Y完全函数依赖于X。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X。,2023/10/14,53,关系模式的规范形式,描述学生的关系模式：US#,SD,MN,CN,G根据数据的语义确定的函数依赖：F=S#SD,SDMN,(S#,CN)G,非2NF关系模式的插入问题,2023/10/14,54,1NF存在,非2NF关系模式的插入问题,2023/10/14,55,1NF存在,非2NF关系模式的删除问题,2023/10/14,56,1NF存在,非2NF关系模式的删除问题,2023/10/14,57,1NF存在,非2NF关系模式的更新问题,2023/10/14,58,1NF存在,非2NF关系模式的更新问题,2023/10/14,59,1NF存在,把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程，简称为规范化。,2023/10/14,60,2NF的规范形式,定义12：第二范式(2NF)若关系模式是1NF，而且每一个非主属性都完全函数依赖于的键，则称为第二范式关系模式，记作2NF。,2023/10/14,61,2NF的规范形式,SC(S#,C#,G)是2NF,SSS(S#,CN,MN)是2NF,2NF关系模式解决了插入问题了吗？,2023/10/14,62,2NF,解决了！,2NF关系模式解决了删除问题了吗？,2023/10/14,63,2NF,解决了！,2NF关系模式解决了更新问题了吗？,2023/10/14,64,2NF,没完全解决！,计算机,刘伟,定义13：第三范式(3NF)如果关系模式R是2NF,而且它的任何一个非键属性都不传递地依赖于任何候选键，则R称为第三范式关系模式，记作3NF。,2023/10/14,65,3NF,传递地函数依赖定义：设是一个具有属性集合的关系模式，X,Y,Z，YX不成立，Z-X、Z-Y和Y-X不空。如果XY，YZ，则称Z传递地函数依赖于X。,2023/10/14,66,3NF,对非3NF关系模式进行规范化处理。,2023/10/14,67,3NF,SSS(S#,SD,MN)不是3NF,SSD(S#,SD)是3NF,SSL(SD,SL)是3NF,3NF关系模式解决了更新问题了吗？,2023/10/14,68,3NF,解决了!,计算机,定义14：BCNF范式(Boyce Codd Normal Form)设关系模式R是1NF。如果对于R的每个函数依赖XY，则X必为候选键，则R是BCNF范式。每个BCNF关系模式都具有如下三个性质：所有非键属性都完全函数依赖于每个候选键。所有键属性都完全函数依赖于每个不包含它的候选键。没有任何属性完全函数依赖于非键的任何一组属性。,2023/10/14,69,Boyce Codd范式,完全依赖定义设R是一个具有属性集合U的关系模式，如果XY，并且对于X的任何一个真子集Z，ZY都不成立，则称Y完全函数依赖于X。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X。,2023/10/14,70,范式的关系,BCNF 3NF若关系模式R是BCNF，则R一定是3NF。证明：,2023/10/14,71,关系模式范式的基本概念,?,2023/10/14,72,关系模式范式的基本概念,例：关系模式SJP(S,J,P)；S表示学生，J表示课程，P表示名次。每个学生每门课程都有一个确定的名次，每门课程中每一名次只有一个学生。由这些语义得到下面的函数依赖：S,JP和J,PS。候选键有哪些？S,J与J,P都是候选键。,2023/10/14,73,关系数据库设计理论,SJP是3NF吗？是！因为没有任何非主属性传递或部分依赖于任何候选键。SJP是BCNF吗？是！因为每个函数依赖的决定属性集都是候选键。,例：关系模式STJ(S,T,J)；S表示学生，T表示教师，J表示课程。每一教师只教一门课，每门课由若干教师教。某一学生选定某门课，就确定了一个固定的教师。由这些语义得到下面的函数依赖：S,JT,S,TJ,TJ候选键有哪些：(S,J)和(S,T)都是候选键。,2023/10/14,74,3NF与BCNF,STJ是3NF吗？是！因为没有任何非主属性传递或部分依赖于任何候选键。STJ是BCNF吗？不是！因为T是决定属性，而T不是候选键。,如果一个关系数据库的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已达到了最高的规范化程度。属于BCNF的关系模式是否就很完美了呢？,2023/10/14,75,关系数据库设计理论,设某学校有多个专业，每个专业有多个教员，该专业的每个教员讲授该专业的所有课程。用关系模式TEACH(S,T,C)来表示专业S、教员T、课程C之间的关系。,2023/10/14,76,关系数据库设计理论,王军李明,数据结构系统结构,计算机,软件,张宏李明赵亮,数据结构JAVA,专业(S),教师(T),课程(C),2023/10/14,77,关系数据库设计理论,设某学校有多个专业，每个专业有多个教员，该专业的每个教员讲授该专业的所有课程。用关系模式TEACH(S,T,C)来表示专业S、教员T、课程C之间的关系。,2023/10/14,78,关系数据库设计理论,对关系模式TEACH的分析：候选键？(S,T,C)是BCNF吗？是！存在的问题：数据增删不方便，冗余明显！,2023/10/14,79,关系数据库设计理论,在关系模式WSC(W,S,C)中，W表示仓库，S表示保管员，C表示商品。假设每个仓库有多个保管员和多种商品。每个保管员保管所在库的所有商品，每种商品被所有保管员保管。,2023/10/14,80,关系数据库设计理论,对关系模式WSC的分析：候选键？(W,S,C)是BCNF吗？是！存在的问题：数据增删不方便，冗余明显！,定义15：设R是一个具有属性集合的关系模式，X、Y和Z是U的子集，并且Z=U X-Y，多值依赖XY成立当且仅当对R的任一关系r，r在(X,Z)上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。,2023/10/14,81,多值依赖与4NF,2023/10/14,82,多值依赖与4NF,在TEACH关系实例中，每个(S,C)上的值对应一组T值，而且这种对应与C无关。例如，尽管与(S,C)对应的两个元组(计算机，数据结构)和(计算机，系统结构)在C属性上的值不同(一个是“数据结构”，一个是“系统结构”)，它们都对应T的同一组值王军，李明。因此，T多值依赖于S，即ST。,2023/10/14,83,多值依赖与第四范式,在WSC关系实例中，每个(W,C)上的值对应一组S值，而且这种对应与S无关例如，尽管与(W,C)对应的两个元组(W1，C1)和(W1，C2)在C属性上的值不同(一个是“C1”，一个是“C2”)，它们都对应S的同一组值S1，S2。因此，S多值依赖于W，即WS。由C与S的完全对称性，有WC成立。,定义16：设R是一个关系模式，D是R上的多值依赖集。如果对于R的每个多值依赖XY(Y-X=非空集,XY未包含R的全部属性)，X都含有R的候选键，则R是第四范式关系模式，简记4NF。,2023/10/14,84,多值依赖与第四范式,与函数依赖类似，可以定义多值依赖集合D的闭包D+。我们也有一组完备有效的多值依赖推理规则，可以用来推导出D+中的所有多值依赖。,2023/10/14,85,多值依赖与第四范式,2023/10/14,86,多值依赖与第四范式,在WSC关系中，候选键是(W,S,C)。该关系模式上，有多值依赖WS，W不是候选键，因此，WSC不是第四范式。,问题：WSC的关系可能具有相当大的数据冗余。例如，若某一仓库Wi有个保管员，存放m件物品，则对应关系中属性W的值为Wi的元组数是mn。每个保管员重复存储m次，每种物品重复存储n次。,2023/10/14,87,多值依赖与第四范式,2023/10/14,88,多值依赖与第四范式,是4NF！,是4NF！,2023/10/14,89,多值依赖与第四范式,当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然。例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。,2023/10/14,90,多值依赖与第四范式,当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然。例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。WSC是4NF吗？由于W不是候选键，WSC不是4NF。WSC是BCNF吗？WSC是BCNF。,形成初始关系数据库模式关系数据库设计理论关系模式规范化方法关系模式的优化完整性和安全性约束的定义逻辑数据库的性能估计,2023/10/14,91,关系数据库设计,关系模式的分类：静态关系：一旦数据已加载,用户只能在这个关系上运行查询操作,不再进行插入、删除和更新操作。动态关系：经常被更新、插入和删除。静态关系只需具有第一规范形式。动态关系必须至少具有第三规范形式。,2023/10/14,92,关系模式规范化方法,关系模式规范化的主要方法：关系模式分解。把一个关系模式分解为几个子模式，使得这些子模式具有指定的规范化形式。关系模式分解中的重要问题是分解的无损连接性和函数依赖保持性。,2023/10/14,93,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。,2023/10/14,94,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。R的关系实例:该实例存在的问题:,2023/10/14,95,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1：1=R1(车号)，R2(车主)，R3(车型),2023/10/14,96,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1：1=R1(车号)，R2(车主)，R3(车型),2023/10/14,97,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1：1=R1(车号)，R2(车主)，R3(车型),2023/10/14,98,关系模式规范化方法,不具有无损连接性！,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2：2=R1(车号,车主)，R2(车号,车型),2023/10/14,99,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2：2=R1(车号,车主)，R2(车号,车型),2023/10/14,100,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2：2=R1(车号,车主)，R2(车号,车型),2023/10/14,101,关系模式规范化方法,具有无损连接性！,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2：2=R1(车号,车主)，R2(车号,车型),2023/10/14,102,关系模式规范化方法,不具有函数依赖保持性！,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3：3=R1(车号,车主)，R2(车主,车型),2023/10/14,103,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3：3=R1(车号,车主)，R2(车主,车型),2023/10/14,104,关系模式规范化方法,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3：3=R1(车号,车主)，R2(车主,车型),2023/10/14,105,关系模式规范化方法,具有无损连接性！,例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3：3=R1(车号,车主)，R2(车主,车型),2023/10/14,106,关系模式规范化方法,具有无损连接性！,具有函数依赖保持性！,定义1 设R是具有属性集合U的关系模式。R的一个分解定义为=R1,R2,.,Rn,其中,Ri的属性集合是Ui，且,2023/10/14,107,关系模式规范化方法,定义1 设R是具有属性集合U的关系模式。R的一个分解定义为=R1,R2,.,Rn,其中,Ri的属性集合是Ui，且例：关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,108,关系模式规范化方法,定义2 设R是一个具有属性集合U和函数依赖集合F的关系模式，=R1,.,Rn是R的一个分解。F在Ri的属性集合Ui上的投影是Fi=XYXYF,X,YUi。,2023/10/14,109,关系模式规范化方法,定义2 设R是一个具有属性集合U和函数依赖集合F的关系模式，=R1,.,Rn是R的一个分解。F在Ri的属性集合Ui上的投影是Fi=XYXYF,X,YUi。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型)函数依赖的投影：F1=车号车主，F2=车主车型,2023/10/14,110,关系模式规范化方法,定义3 设=R1,.,Rn是关系模式R的一个分解，r是R的一个关系。定义m(r)R1(r)R2(r).Rn(r)，即m(r)是r在中各关系模式上投影的连接。,2023/10/14,111,关系模式规范化方法,例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,112,关系模式规范化方法,R1(r),R2(r),例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,113,关系模式规范化方法,R1(r),R2(r),m(r)=R1(r)R2(r),引理1 设R是一个关系模式，=R1,.,Rn是R的一个分解，r是R的一个关系实例，则：r m(r)若s=m(r)，则Ri(r)=Ri(s)m(m(r)=m(r)证明：,2023/10/14,114,关系模式规范化方法,引理1 设R是一个关系模式，=R1,.,Rn是R的一个分解，r是R的一个关系实例，则：r m(r)若s=m(r)，则Ri(r)=Ri(s)m(m(r)=m(r)证明：,2023/10/14,115,关系模式规范化方法,定义3.3 设=R1,.,Rn是关系模式R的一个分解，是R的一个关系。定义m(r)R1(r)R2(r).Rn(r)，即m(r)是r在中各关系模式上投影的连接。,定义4 设=R1,.,Rn是R的一个分解。若对R的任何一个关系r均有r=m(r)成立，则称分解具有无损连接性。简称为无损连接分解。,2023/10/14,116,关系模式规范化方法,例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,117,关系模式规范化方法,R1(r),R2(r),m(r)=R1(r)R2(r),算法1:判别一个分解的无损连接性。输入:关系模式R(A1,.,An),R的函数依赖集F,R的分解=R1,.,Rk。输出:分解是否具有无损连接性。算法:,2023/10/14,118,关系模式规范化方法,(1)建立矩阵S,列j对应属性Aj,行i对应Ri(2)FOR i=1 TO k DO FOR j=1 TO n DO Si,j=bij;ENDFOR ENDFOR(3)FOR i=1 TO k DO FOR j=1 TO n DO IF Ri包含属性Aj,THEN Si,j=aj;ENDFOR ENDFOR(4)见下页,2023/10/14,119,关系模式规范化方法,2023/10/14,120,关系模式规范化方法,DO UNTIL S 不变化 FOR 每个X Y F DO FOR S中所有在X对应列上具有相同符号的行 DO 考察这些行中，Y所对应列的符号，按照下列进行规则修改(a)FOR 每个具有”a”类符号的Y对应列 DO 把该列所有符号改成相同的”a”类符号;ENDFOR(b)FOR 每个具有”b”类符号的Y对应列 DO 在该列中选择一个下标最小”b”类符号;把该列的其它位置变为选中的”b”类符号;ENDFOR ENDFOR ENDFOR ENDUNTIL如果S中存在一行全为”a”类符号，则 具有无损连接分解；否则，不具有无损连接分解,定理1 关系R的分解具有无损连接性的充分必要条件是算法1终止时,矩阵S中有一行为(a1,a2,.,an).,2023/10/14,121,关系模式规范化方法,当关系模式R被分解为两个子模式时,下述定理给出了一个判别无损连接性的简单方法。定理2 设=R1,R2是关系模式R的一个分解,U1、U2和U分别是R1、R2和R的属性集合,F是R的函数依赖集合。具有无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+。,2023/10/14,122,关系模式规范化方法,当关系模式R被分解为两个子模式时,下述定理给出了一个判别无损连接性的简单方法。定理2 设=R1,R2是关系模式R的一个分解,U1、U2和U分别是R1、R2和R的属性集合,F是R的函数依赖集合。具有无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+。,2023/10/14,123,关系模式规范化方法,例子：关系模式R的属性集合U=A,B,C,D,E,F函数依赖集F=AB,CF,EA,CED分解=R1(A,B,E),R2(C,D,E,F),定义5 设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解，Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。,2023/10/14,124,关系模式规范化方法,定义5 设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解，Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,125,关系模式规范化方法,定义5 设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解，Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,126,关系模式规范化方法,定义5 设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解，Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解：=R1(车号,车主),R2(车主,车型),2023/10/14,127,关系模式规范化方法,具有函数依赖保持性,算法2 函数依赖保持性的判别算法输入:函数依赖集F,F1,F2,Fk,记 输出:是否F+=G+。方法:(1)FOR 每个XYF DO IF Y不属于X关于G的闭包 THEN 输出F+G+,停止。ENDFOR；(2)输出“F+=G+”,停止。,2023/10/14,128,关系模式规范化方法,算法3 3NF分解算法1：只能保证函数依赖保持性的分解算法。定理3 设关系模式R的分解=R1,.,Rk是算法3的输出结果，G是F的最小函数依赖集，则具有函数依赖保持性，而且中每个关系模式都是3NF。,2023/10/14,129,关系模式分解算法,2023/10/14,130,关系模式分解算法,输入:关系模式R,R的属性集合U和极小函数依赖集G,R是1NF输出:具有函数依赖性的分解,中所有关系模式都是3NF。算法:=空集合;IF 存在XA G且X,A=U,Then:=R，停止。ELSE FOR 每个不出现在G的任何函数依赖中的属性A Do:=R(A)FOR XA G DO:=R(X,A)ENDFORENDIF,2023/10/14,131,关系模式分解算法,输入:关系模式R,R的属性集合U和极小函数依赖集G,R是1NF输出:具有函数依赖性的分解,中所有关系模式都是3NF。算法:=空集合;IF 存在XA G且X,A=U,Then:=R，停止。ELSE FOR 每个不出现在G的任何函数依赖中的属性A Do:=R(A)FOR XA G DO:=R(X,A)ENDFORENDIF,描述学生的关系模式R(U)：US#,SD,MN,CN,G根据数据的语义确定的函数依赖：F=S#SD,SDMN,(S#,CN)G,2023/10/14,132,2023/10/14,133,关系模式分解算法,算法3 3NF分解算法1：只能保证函数依赖保持性的分解算法。,2023/10/14,134,关系模式分解算法,算法3 3NF分解算法1：只能保证函数依