access_规范化设计

1、1第第5章章规范化设计规范化设计重点概念：重点概念：u关系模式的设计问题关系模式的设计问题 u函数依赖函数依赖u关系模式的范式关系模式的范式25.1关系模式设计问题关系模式设计问题u数据库的一个主要任务就是如果将一组数据存数据库的一个主要任务就是如果将一组数据存储在数据库中，这就需要考虑如何为这些数据储在数据库中，这就需要考虑如何为这些数据设计一个合适的逻辑结构。设计一个合适的逻辑结构。u存储所占用的空间存储所占用的空间“最小最小”，消除数据冗余及，消除数据冗余及由此带来的各种操作异常现象。由此带来的各种操作异常现象。u在数据库中构造一个在数据库中构造一个“好的好的”、“合适的合适的”的的关系

2、模式，涉及到一系列的理论和方法，形成关系模式，涉及到一系列的理论和方法，形成了关系数据库的设计理论和技术。了关系数据库的设计理论和技术。u由于合适的关系模式要符合一定的规范化要求，由于合适的关系模式要符合一定的规范化要求，所以又称其为关系数据库的规范化理论。所以又称其为关系数据库的规范化理论。3一、一、问题的提出问题的提出 如果数据模式设计不当，就会出现数据冗如果数据模式设计不当，就会出现数据冗余；有了数据冗余，就可能出现操作异常；为余；有了数据冗余，就可能出现操作异常；为了解决这些问题，需要讨论数据依赖中的某些了解决这些问题，需要讨论数据依赖中的某些重要问题，例如函数依赖、多值依赖和连接依重

3、要问题，例如函数依赖、多值依赖和连接依赖等。赖等。4二、数据冗余及其操作异常二、数据冗余及其操作异常uData Redundancyu问题问题大量占用和消耗系统资源，造成不必要的开大量占用和消耗系统资源，造成不必要的开销销更严重的是带来各种操作异常更严重的是带来各种操作异常5冗余问题实例冗余问题实例例：描述学校的数据库：例：描述学校的数据库：学生的学号（学生的学号（Sno）、所在系（）、所在系（Sdept）系主任姓名（系主任姓名（Mname）、课程名（）、课程名（Cname）成绩成绩（Grade）单一的关系模式单一的关系模式 ： Student U Sno, Sdept, Mname, Cna

4、me, Grade 学校数据库的语义：学校数据库的语义：1、一个系有若干学生，、一个系有若干学生， 一个学生只属于一个系；一个学生只属于一个系；2、一个系只有一名主任；、一个系只有一名主任；3、一个学生可以选修多门课程，、一个学生可以选修多门课程， 每门课程有若干学生选修；每门课程有若干学生选修；4、每个学生所学的每门课程都有一个成绩。、每个学生所学的每门课程都有一个成绩。6冗余问题实例冗余问题实例（续）（续）属性组属性组U上的关系：上的关系： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade SnoCnameSdeptMnameGrade7关系模式关系

5、模式Student中存在的问题中存在的问题1、 数据冗余太大数据冗余太大浪费大量的存储空间浪费大量的存储空间 例：每一个系主任的姓名重复出现例：每一个系主任的姓名重复出现2、 更新异常（更新异常（Update Anomalies）数据冗余数据冗余 ，更新数据时，维护数据完整性代更新数据时，维护数据完整性代价大。价大。例：某系更换系主任后，系统必须修改与该系学例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组生有关的每一个元组8关系模式关系模式Student中存在的问题中存在的问题3、插入异常（、插入异常（Insertion Anomalies）该插的数据插不进去该插的数据插不进去 例

6、，如果一个系刚成立，尚无学生，我们就无法把这例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。个系及其系主任的信息存入数据库。4、删除异常（、删除异常（Deletion Anomalies）不该删除的数据不得不删不该删除的数据不得不删例，如果某个系的学生全部毕业了，例，如果某个系的学生全部毕业了， 我们在删除该系我们在删除该系学生信息的同时，把系及其系主任的信息也丢掉了。学生信息的同时，把系及其系主任的信息也丢掉了。9冗余问题实例冗余问题实例（续）（续）结论：结论：Student关系模式不是一个好的模式。关系模式不是一个好的模式。“好好”的模式：的模式：不会发生插入

7、异常、删除异常、更新异常，不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。数据冗余应尽可能少。原因：原因：由存在于学生数据库中的某些特定联系引起由存在于学生数据库中的某些特定联系引起10三、冗余产生的原因分析三、冗余产生的原因分析u从数据结构角度考察，如果对从数据结构角度考察，如果对多个文件多个文件和和同一同一文件中数据之间文件中数据之间的联系考虑不周或处理不当，的联系考虑不周或处理不当，就可能导致数据冗余产生就可能导致数据冗余产生u在在RDB中，数据之间的联系表现为同一关系模中，数据之间的联系表现为同一关系模式中各个属性之间的依赖关系，通常称为数据式中各个属性之间的依赖关系，通常称

8、为数据依赖。依赖。u关系系统中数据冗余产生的重要原因就在于对关系系统中数据冗余产生的重要原因就在于对数据依赖的处理，也就是关系模式本身的结构数据依赖的处理，也就是关系模式本身的结构设计设计11三、冗余产生的原因分析（续）三、冗余产生的原因分析（续）u关系数据库中数据依赖来源于关系结构本身。关系数据库中数据依赖来源于关系结构本身。在关系模式中，各个属性一般说来是有联系的，在关系模式中，各个属性一般说来是有联系的，但这些联系有着不同的表现形式：但这些联系有着不同的表现形式：一部分属性的取值能够决定这个表中所有其他属性一部分属性的取值能够决定这个表中所有其他属性的取值（候选健、主健）的取值（候选健、

9、主健）一部分属性的取值决定表中其他部分属性的取值一部分属性的取值决定表中其他部分属性的取值（数据依赖，候选健的推广）（数据依赖，候选健的推广）12四、问题的解决思路四、问题的解决思路u在在RDB设计中，不是随便一种关系模式设计方设计中，不是随便一种关系模式设计方案都案都“合适合适”，更不是任何一种关系模式都可，更不是任何一种关系模式都可以投入使用的以投入使用的uRDB中关系模式的属性之间需要满足某种内在中关系模式的属性之间需要满足某种内在的必然联系，设计一个好的数据库的根本方法的必然联系，设计一个好的数据库的根本方法是先要分析和掌握属性间的语义关联，然后再是先要分析和掌握属性间的语义关联，然后

10、再依据这些关联得到相应的设计方案依据这些关联得到相应的设计方案13四、问题的解决思路（续）四、问题的解决思路（续）u属性间的关联表现为一个属性子集对另一个属属性间的关联表现为一个属性子集对另一个属性子集的性子集的“依赖依赖”关系关系多对一依赖：常见，函数依赖多对一依赖：常见，函数依赖一对多依赖：复杂，目前主要研究多值依赖一对多依赖：复杂，目前主要研究多值依赖和连接依赖和连接依赖u基于这三种依赖在不同层面上的具体要求，人基于这三种依赖在不同层面上的具体要求，人们把属性之间的这些关联分为若干等级，这就们把属性之间的这些关联分为若干等级，这就形成所谓的关系的规范化形成所谓的关系的规范化14四、问题的

11、解决思路（续）四、问题的解决思路（续）u解决解决RDB冗余问题的基本方案就是分析研究属冗余问题的基本方案就是分析研究属性之间的联系，按照每个关系中属性间满足某性之间的联系，按照每个关系中属性间满足某种内在语义条件和属性间联系所处的规范等级种内在语义条件和属性间联系所处的规范等级来构造关系。来构造关系。u由此产生的一整套有关理论称为关系数据库规由此产生的一整套有关理论称为关系数据库规范化理论范化理论u这是这是RDB设计中最重要的问题设计中最重要的问题15一、函数依赖的基本概念一、函数依赖的基本概念定义定义5.1 设设R(U)是一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子

12、集，的子集， r 是是R(U) 中中任意任意一个可能的关系。一个可能的关系。 若对于若对于r中任意两个元组中任意两个元组s和和t，当，当sX=tX时，都有时，都有sY=tY ， 则称则称 “属性子集属性子集X函数确定属性子集函数确定属性子集Y” 或或 “Y函数依赖于函数依赖于X”，记作，记作XY，否则就称，否则就称X不函数不函数决定决定Y，记作，记作XY X称为这个函数依赖的称为这个函数依赖的决定属性集决定属性集(Determinant)。5.2.1 函数依赖函数依赖16说明：说明： 1. 函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的约的某个或某些关系实例满足的约束

13、条件，而是指束条件，而是指R的的所有关系实例所有关系实例均要满足的约束条件。均要满足的约束条件。2. 函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数据的语义来确定函的概念。只能根据数据的语义来确定函数依赖。数依赖。 例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同名人的这个函数依赖只有在不允许有同名人的条件下成立条件下成立3. 数据库设计者可以对现实世界作强制的规定。例如规定不允数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖许同名人出现，函数依赖“姓名姓名年龄年龄”成立。所插入的成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，元组必须满

14、足规定的函数依赖，若发现有同名人存在， 则则拒绝插入该元组。拒绝插入该元组。17函数依赖（续）函数依赖（续）例例: Student(Sno, Sname, Ssex, Sage, Sdept) 假设不允许重名，则有假设不允许重名，则有:Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname SageSname Sdept但但Ssex Sage18二、函数依赖的分类二、函数依赖的分类u平凡和非平凡的函数依赖平凡和非平凡的函数依赖u部分与完全函数依赖部分与完全函数依赖u传递与直接函数依赖传递与直接函数依赖19平凡函数依赖与非平凡函数

15、依赖平凡函数依赖与非平凡函数依赖在关系模式在关系模式R(U)中，对于中，对于U的子集的子集X和和Y，如果如果XY，但，但Y X，则称，则称XY是是非平凡的函数依赖非平凡的函数依赖若若XY，但，但Y X, 则称则称XY是是平凡的函数依赖平凡的函数依赖例：在关系例：在关系SC(Sno, Cno, Grade)中，中， 非平凡函数依赖：非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖：平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno20平凡函数依赖与非平凡函数依赖（续）平凡函数依赖与非平凡函数依赖（续）对于任一关系模式，平凡函数依赖都是必然对于任一关系模式，

16、平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别成立的，它不反映新的语义，因此若不特别声明，声明， 我们总是讨论非平凡函数依赖。我们总是讨论非平凡函数依赖。只有非平凡的函数依赖才和只有非平凡的函数依赖才和“真正的真正的”约束约束条件相关条件相关21完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖定义定义5.2 在关系模式在关系模式R(U)中，如果中，如果XY，并且，并且对于对于X的任何一个真子集的任何一个真子集X，都有，都有 X Y，则，则称称Y完全函数依赖于完全函数依赖于X，记作，记作X Y。 若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y部分部分函数依赖函

17、数依赖于于X，记作，记作X P Y。部分依赖中必然存在冗余属性定义部分依赖中必然存在冗余属性定义 22完全函数依赖与部分函数依赖（续）完全函数依赖与部分函数依赖（续）例例: 在关系在关系SC(Sno, Cno, Grade)中，中， 由于：由于：Sno Grade，Cno Grade， 因此：因此：(Sno, Cno) Grade说明：说明：u1：1为完全函数依赖为完全函数依赖u多：多：1为部分函数依赖为部分函数依赖 23传递函数依赖与直接函数依赖传递函数依赖与直接函数依赖定义定义5.3 在关系模式在关系模式R(U)中，如果中，如果XY，YZ，且且Y X，YX，则称，则称Z传递函数依赖传递函数

18、依赖于于X。注注: 如果如果YX， 即即XY，则，则Z直接函数依赖直接函数依赖于于X例例: 在关系在关系Std(Sno, Sdept, Mname)中，有：中，有：Sno Sdept，Sdept Mname Mname传递函数依赖于传递函数依赖于Sno24传递函数依赖与直接函数依赖传递函数依赖与直接函数依赖u如果如果Z传递依赖于传递依赖于X，则，则Z必然函数依赖于必然函数依赖于Xu如果如果Z传递依赖于传递依赖于X，说明，说明Z是间接依赖于是间接依赖于X，从而表明从而表明X和和Z间的关联较弱间的关联较弱u部分依赖存在部分依赖存在“冗余属性冗余属性”，传递依赖表现出，传递依赖表现出“间接间接”的弱

19、数据依赖，是产生数据冗余的主的弱数据依赖，是产生数据冗余的主要原因要原因25三、函数依赖的逻辑蕴涵三、函数依赖的逻辑蕴涵u研究函数依赖是解决数据冗余问题。研究函数依赖是解决数据冗余问题。u首要的问题是在一个给定的关系模式中，如何首要的问题是在一个给定的关系模式中，如何找出其中的各种函数依赖。找出其中的各种函数依赖。u关系模式理论上总有函数依赖存在（如平凡依关系模式理论上总有函数依赖存在（如平凡依赖或候选健确定的依赖）；在实际应用中，人赖或候选健确定的依赖）；在实际应用中，人们也会制定一些语义明显的依赖。这样，就会们也会制定一些语义明显的依赖。这样，就会有一个初始的函数依赖集有一个初始的函数依赖

20、集Fu我们要讨论如何通过已知的我们要讨论如何通过已知的F得到大量未知的得到大量未知的函数依赖，这就是函数依赖的闭包的概念函数依赖，这就是函数依赖的闭包的概念26函数依赖的逻辑蕴涵的概念函数依赖的逻辑蕴涵的概念uAB，BC，AC？u根据已知的函数依赖能否根据已知的函数依赖能否“推导推导”出某个未知出某个未知的的函数依赖？这就是函数依赖的逻辑蕴涵问的的函数依赖？这就是函数依赖的逻辑蕴涵问题题定义定义5.2 设设F是在关系模式是在关系模式R(U)上成立的函数依赖，上成立的函数依赖，X和和Y是属性集是属性集U的子集，如果对的子集，如果对R中每个满足中每个满足F的关系的关系r也满足也满足XY，则称，则称

21、F逻辑蕴含逻辑蕴含XY。27函数依赖的闭包的概念函数依赖的闭包的概念u如果要找出如果要找出F所蕴含（推导）的所有函数依赖，所蕴含（推导）的所有函数依赖，就用到了函数依赖集和闭包的概念就用到了函数依赖集和闭包的概念u设设F是函数依赖集，是由被是函数依赖集，是由被F逻辑蕴含的函数依逻辑蕴含的函数依赖的全体构成的集合，称为函数依赖集赖的全体构成的集合，称为函数依赖集F的闭的闭包包(closure)，记作，记作F+28四、函数依赖的推理规则四、函数依赖的推理规则u为从关系模式为从关系模式R上已知的函数依赖上已知的函数依赖F得到其闭得到其闭包包F+， Armstrong于于1974年提出一套推理规则。年

22、提出一套推理规则。使用这套规则，可以从已有的函数依赖推导出使用这套规则，可以从已有的函数依赖推导出新的函数依赖。后来又经过不断完善，形成了新的函数依赖。后来又经过不断完善，形成了著名的著名的“Armstrong公理系统公理系统”，为计算，为计算F+提提供了一个有效并且完备的理论基础。供了一个有效并且完备的理论基础。291. Armstrong公理公理 设有关系模式设有关系模式R ，则有下列推理规则：则有下列推理规则：自反律自反律（Reflexivity）：）： 若若Y X U，则，则X Y 为为F 所蕴含。所蕴含。增广律增广律（Augmentation）：若）：若XY 为为F 所蕴含，所蕴含，

23、且且Z U，则，则XZYZ 为为F 所蕴含。所蕴含。传递律传递律（Transitivity）：若）：若XY 及及YZ 为为F 所蕴所蕴含，则含，则XZ 为为F 所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于赖，自反律的使用并不依赖于F301. Armstrong公理公理（l）自反律：若）自反律：若Y X U，则，则X Y为为F 所蕴含所蕴含证明：设证明：设U是关系模式是关系模式R的属性集，的属性集，F是是R上成立上成立的只涉及的只涉及U中属性的函数依赖集，则对中属性的函数依赖集，则对R 的任一关系的任一关系

24、r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立。成立。311. Armstrong公理公理(2)增广律增广律: 若若XY 为为F 所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F 所蕴含。所蕴含。 证明：设证明：设R 的任一关系的任一关系r中任意的两个元中任意的两个元组组t，s；若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以所以XZYZ为为F所蕴含。所蕴含。321. Armstrong公理公理(3) 传递律：若传递律：若XY及及YZ为为F 所蕴含，则所蕴

25、含，则 XZ为为 F 所蕴含。所蕴含。证：设对证：设对R 的任一关系的任一关系 r中的任意两个元中的任意两个元组组 t，s。若若tX=sX，由于，由于XY，有，有 tY=sY；再由再由YZ，有，有t Z=sZ，所以，所以XZ为为F所蕴所蕴含。含。332. 导出规则导出规则为了方便进行推导，在此基础上导出另外为了方便进行推导，在此基础上导出另外3条规则：条规则：1、合并律：合并律：由由XY，XZ，有，有XYZ。2、分解律：分解律：由由XY 及及 Z Y，有，有XZ。3、伪传递律：伪传递律：由由XY，WYZ，有，有XWZ。34五、函数依赖和关键码的联系五、函数依赖和关键码的联系定义定义5.4 设关

26、系模式设关系模式R的属性集是的属性集是U，X是是U的一的一个子集，如果个子集，如果XU在在R上成立，则称上成立，则称X是是R的的一个超键。如果一个超键。如果XU在在R上成立，但对于上成立，但对于X的的任一真子集任一真子集X都有都有X U，则称，则称X是是R的一个的一个候选键。候选键。35六、属性集的闭包六、属性集的闭包u在实际应用中，经常要判断能否从已知的在实际应用中，经常要判断能否从已知的F集集推出该函数依赖是否蕴含推出该函数依赖是否蕴含XY的问题。理论的问题。理论上，只要反复使用上，只要反复使用Armstrong公理，求出公理，求出F+，即可判断即可判断XY是否被蕴涵。是否被蕴涵。u求函数

27、依赖集闭包是个复杂且困难的问题，而求函数依赖集闭包是个复杂且困难的问题，而且会产生大量且会产生大量“无意义无意义”或意义不大的函数依或意义不大的函数依赖赖u实际上，所感兴趣的通常是实际上，所感兴趣的通常是F+的子集，没有必的子集，没有必要计算要计算F+ ，为此引入了属性闭包的概念，为此引入了属性闭包的概念361.属性集的闭包的概念属性集的闭包的概念u设设F是属性集合是属性集合U上的一个函数依赖集，上的一个函数依赖集，X是是U的子集，则相对于的子集，则相对于F属性集属性集X的闭包的闭包X+为一个为一个从从F集使用集使用Armstrong规则推出的所有满足规则推出的所有满足XA的属性的属性A的集合

28、的集合uX+ =属性属性A| XA在在F +中中uX+ =A| XA能由能由Armstrong公理推出公理推出372.函数依赖闭包函数依赖闭包例例1 已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+ 。解解 设设X（0）=AB；(1)计算计算X（1）: 逐一的扫描逐一的扫描F集合中各个函数依赖，集合中各个函数依赖， 找左部为找左部为A，B或或AB的函数依赖。得到两个：的函数依赖。得到两个： ABC，BD。 于是于是X（1）=ABCD=ABCD。382.函数依赖闭包函数依赖闭包(2)因为因为X（0） X（1） ，所以再找出左

29、部为，所以再找出左部为ABCD子集的那子集的那些函数依赖，又得到些函数依赖，又得到ABC，BD， CE，ACB， 于是于是X（2）=X（1）BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+ =ABCDE。393.F逻辑蕴含的充要条件逻辑蕴含的充要条件u函数依赖闭包复杂，属性依赖闭包简单函数依赖闭包复杂，属性依赖闭包简单u一般而言，属性依赖集闭包只涉及到函数依赖一般而言，属性依赖集闭包只涉及到函数依赖集闭包中部分的函数依赖集闭包中部分的函数依赖u能否将能否将“XY属于属于F+”的判断问题和的判断问题和“Y属于属于X+”的问题联系起来已简化判断过程？的问题

30、联系起来已简化判断过程？u下面的定理给出了回答下面的定理给出了回答404.关于闭包的定理关于闭包的定理u定理定理5.3 设设F 为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY 能由能由F 根据根据Armstrong公理导出的充分必公理导出的充分必要条件是要条件是Y XF+u用途用途 将判定将判定XY是否能由是否能由F根据根据Armstrong公理导公理导出的问题，就转化为求出出的问题，就转化为求出XF+ ，判定，判定Y是否为是否为XF+的子集的问题的子集的问题414.关于闭包的定理关于闭包的定理u计算计算XF+ 算法：算法：u初始化，令初始化，令 X+ =Xu在在F中依

31、次查找每个没有标记的函数依赖，若中依次查找每个没有标记的函数依赖，若“左边属性集左边属性集”包含于包含于X+ ，则令，则令X+ =X+ “右右边属性集边属性集”，并为访问过的函数依赖设置标记。，并为访问过的函数依赖设置标记。u反复执行上一步，直到反复执行上一步，直到X+不改变为止。不改变为止。424.关于闭包的定理关于闭包的定理例例1：设：设R=ABC，F=AB，BC，分别求，分别求A，B，C的闭包。的闭包。解：解：A+=ABC B+=BC C+=C434.关于闭包的定理关于闭包的定理例例2：已知关系模式：已知关系模式R中，中，U=A，B，C，D，E，G，F=ABC，C A，BCD，ACDB，

32、DEG，BEC，CGBD，CEAG，求（，求（BD）+，判断，判断BDAC是否属于是否属于F+。解：解： （BD）+=ABCDEG因为（因为（BD）+=ABCDEG，所以，所以BD AC，可由，可由F导出，导出，即即BD AC属于属于F+属属（由于（由于DEG，则，则BD BEG，分解得，分解得BD BG，又因为，又因为BEC，则，则BD C，又因，又因C A，则，则BD A故故BDAC）44七、最小依赖集定义七、最小依赖集定义怎样求出一个与怎样求出一个与F “等价等价”的的“最小最小”函数依赖集函数依赖集Fmin?定义定义5.5 如果函数依赖集如果函数依赖集Fmin+满足下列条件，则称满足下

33、列条件，则称F为一个为一个最小依赖集最小依赖集。亦称为。亦称为最小覆盖最小覆盖。1.Fmin+ = F+2.F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。3.F中不存在冗余的函数依赖中不存在冗余的函数依赖XA，使得，使得F与与F-XA等价。等价。4.F中不存在这样的函数依赖中不存在这样的函数依赖XY，X有真子集有真子集W使得使得F-XYWY与与F等价。等价。451.最小依赖集最小依赖集例例2 对于对于5.l节中的关系模式节中的关系模式S，其中：，其中： U = SNO，SDEPT，MN，CNAME，G ， F = SNOSDEPT，SDEPTMN， （SNO，CNA

34、ME）G 设设F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF 是最小覆盖，而是最小覆盖，而F 不是。不是。因为：因为：F -SNOMN与与F 等价等价 F -(SNO，SDEPT)SDEPT也与也与F 等价等价 F -(SNO，SDEPT)SDEPT SNOSDEPT也与也与F 等价等价462.最小化过程最小化过程定义定义5.6 每一个函数依赖集每一个函数依赖集F 均等价于一个极小均等价于一个极小 函数依赖集函数依赖集Fm。此。此Fm称为称为F 的最小依赖集的最小依赖集证证:构造性证明，依据定义分三步对构造性证明，依据定义分三

35、步对F 进行进行“极小化处极小化处理理”，找出，找出F 的一个最小依赖集。的一个最小依赖集。(1) 分解右多属性分解右多属性逐一检查逐一检查F 中各函数依赖中各函数依赖FDi：XY，若若Y=A1A2 Ak，k 2，则用，则用 XAj |j=1，2， k 来取代来取代XY。 472.最小化过程最小化过程(2)逐一检查逐一检查F 中各函数依赖中各函数依赖FDi：XA， 令令G = F - XA， 若若A XG+， 则从则从F 中去掉此函数依赖。中去掉此函数依赖。 由于由于F 与与G =F -XA等价的充要条件是等价的充要条件是A XG+ 因此因此F变换前后是等价的。变换前后是等价的。482.最小化

36、过程最小化过程(3)逐一取出逐一取出F 中各函数依赖中各函数依赖FDi：XA， 设设X=B1B2Bm， 逐一考查逐一考查Bi （i=l，2，m），）， 若若A （X-Bi ）F+ ， 则以则以X-Bi 取代取代X。 由于由于F与与F-XAZA等价的充要条件是等价的充要条件是A ZF+ ，其中，其中Z=X-Bi 因此因此F变换前后是等价的。变换前后是等价的。由定义，最后剩下的由定义，最后剩下的F 就一定是极小依赖集。就一定是极小依赖集。 因为对因为对F 的每一次的每一次“改造改造”都保证了改造前后的两个都保证了改造前后的两个函数依赖集等价，因此剩下的函数依赖集等价，因此剩下的F 与原来的与原来的

37、F等价。等价。 证证毕毕492.最小化过程最小化过程例例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是都是F 的最小依赖集：的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA uF 的最小依赖集的最小依赖集Fm 不一定是唯一，它与对各函不一定是唯一，它与对各函数依赖数依赖FDi 及及XA中中X 各属性的处置顺序有关各属性的处置顺序有关505.3 函数模式的分解函数模式的分解函数模式的分解目的：函数模式的分解目的：解决数据冗余和操作异常，提高范式等级解决数据冗余和操作异常，提高范式等级分解的概念：分解的概念：用原关系模式的若干个投影构成新的关系模式。用原

38、关系模式的若干个投影构成新的关系模式。515.3.1 模式的分解定义模式的分解定义定义定义5.7 关系模式关系模式R(U)，R1，R2，Rk都是都是U的子集，的子集， U=R1R2Rk，关系模式，关系模式R1，Rk的集合用的集合用表示，表示， = R1，Rk,用用代替代替R的过程称为关系模式的分解。的过程称为关系模式的分解。52模式分解问题模式分解问题u把低一级的关系模式分解为若干个高一级的关把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的系模式的方法并不是唯一的u只有能够保证分解后的关系模式与原关系模式只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义等价，分解方

39、法才有意义53关系模式分解的标准关系模式分解的标准三种模式分解的等价定义三种模式分解的等价定义1.分解具有无损连接性分解具有无损连接性分解前后是否表示同样的数据分解前后是否表示同样的数据,即不少即不少,也也不能多不能多2.分解要保持函数依赖分解要保持函数依赖分解前后是否具有相同的语义，属性间的分解前后是否具有相同的语义，属性间的联系不能变联系不能变3.分解既要保持函数依赖，又要具有无损连接分解既要保持函数依赖，又要具有无损连接性性545.3.2 无损分解无损分解例例: SL（Sno， Sdept， Sloc（宿舍）（宿舍） F= SnoSdept, SdeptSloc, SnoSloc存在插入

40、异常、删除异常、冗余度大和修存在插入异常、删除异常、冗余度大和修改复杂等问题改复杂等问题分解方法可以有多种分解方法可以有多种 55无损分解（续）无损分解（续）SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHBSL1. SL分解为下面三个关系模式：分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc)56分解后的关系为：分解后的关系为： SN SD SOSno9500195002950039500495005SdeptCSISMAPHSlocABC57SL的一种的一种分解（续）分解（续）分解后的数据库丢失了许多信息分解

41、后的数据库丢失了许多信息 例如无法查询例如无法查询95001学生所在系或所在宿舍。学生所在系或所在宿舍。 如果分解后的关系可以通过自然连接恢复为原如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息来的关系，那么这种分解就没有丢失信息58SL的一种另的一种另分解分解2. SL分解为下面二个关系模式：分解为下面二个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的关系为：分解后的关系为： NL DLSdeptSlocCSAISBMACPHBSnoSloc95001A95002B95003C95004B95005B59SL的一种另的一种另分解（续

42、）分解（续）NL DL SnoSlocSdept95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH60SL的一种另的一种另分解（续）分解（续）NL DL比原来的比原来的SL关系多了关系多了3个元组个元组 无法知道无法知道95002、95004、95005 究竟是哪个系的学生究竟是哪个系的学生 元组增加了，信息丢失了元组增加了，信息丢失了61SL的的第三种分解方法第三种分解方法3. 将将SL分解为下面二个关系模式：分解为下面二个关系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的关系为：分解后

43、的关系为：ND NL SnoSdept95001CS95002IS95003MA95004IS95005PHSnoSloc95001A95002B95003C95004B95005BF= SnoSdept, SdeptSloc, SnoSloc 62SL的的第三种分解方法第三种分解方法（续）（续）SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHBNL DL与与SL关系一样，因此没有丢失信息关系一样，因此没有丢失信息63无损模式分解的定义无损模式分解的定义u设设R是一个关系模式是一个关系模式,F是是R上的一个上的一个FD集，集， R分解成数据

44、库模式分解成数据库模式 = R1，R2， ，Rk，若若R与与R1、R2、Rn自然连接的结果相等，自然连接的结果相等，则称关系模式则称关系模式R的这个分解的这个分解具有无损连接性具有无损连接性（Lossless join）u具有无损连接性的分解保证不丢失信息具有无损连接性的分解保证不丢失信息u无损连接性能在一定程度上解决数据冗余和操无损连接性能在一定程度上解决数据冗余和操作异常等问题作异常等问题645.3.3 无损分解的测试方法无损分解的测试方法关系模式关系模式R(U),U=A1,An，F是是R上成立的函数上成立的函数依赖集，依赖集，= R1, R2,Rk是是R上的一个分解。上的一个分解。判断判

45、断相对相对F是否具有无损分解性是否具有无损分解性方法：方法：1.构造一张构造一张k行行n列的表格，每列对应一个属性列的表格，每列对应一个属性Aj(1jn),每行对应一个模式每行对应一个模式Ri(1ik)。如果。如果Aj在在Ri中，就在表格的第中，就在表格的第i行第行第j列处填上符号列处填上符号aj，否则填上，否则填上bij.65无损分解的测试方法无损分解的测试方法(续续)2. 反复检查反复检查F中每个中每个FD，并且修改表格中的元，并且修改表格中的元素，直到表格不能修改为止。素，直到表格不能修改为止。u取取F中的一个中的一个FD XY,如果表格有两行在如果表格有两行在X分分量上相等，在量上相等

46、，在Y分量上不相等，则修改分量上不相等，则修改Y分量分量上的值，使这两行在上的值，使这两行在Y分量上也相等，具体分分量上也相等，具体分两种情况：两种情况：如果如果Y分量中有一个是分量中有一个是aj,另一个也修改成另一个也修改成aj如果如果Y分量中没有分量中没有aj,就用标号较小的那个就用标号较小的那个bij替换另一个符号替换另一个符号3. 修改结束后的表格中有一行全是修改结束后的表格中有一行全是a,则则相对相对F是无损分解，否则不是无损分解是无损分解，否则不是无损分解665.3.4 保持函数依赖的模式分解保持函数依赖的模式分解设关系模式设关系模式R被分解为若干个关系模式被分解为若干个关系模式R

47、1，R2，Rn （其中（其中U=U1U2Un，且不存在，且不存在Ui Uj，Fi为为F在在Ui上的投影），若上的投影），若F所逻辑蕴含的函数依所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数赖一定也由分解得到的某个关系模式中的函数依赖依赖Fi所逻辑蕴含，则称关系模式所逻辑蕴含，则称关系模式R的这个分的这个分解是保持函数依赖的（解是保持函数依赖的（Preserve dependency）。）。67模式各种分解情况模式各种分解情况u如果一个分解具有无损连接性，则它能够保证如果一个分解具有无损连接性，则它能够保证不丢失信息。不丢失信息。u如果一个分解保持了函数依赖，则它可以减轻如果一个分解

48、保持了函数依赖，则它可以减轻或解决各种异常情况。或解决各种异常情况。u分解具有无损连接性和分解保持函数依赖是两分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。的分解也不一定具有无损连接性。68保持函数依赖的测试方法保持函数依赖的测试方法u由保持函数依赖的概念可知，检验一个分解是由保持函数依赖的概念可知，检验一个分解是否保持函数依赖，其实就是检验函数依赖集否保持函数依赖，其实就是检验函数依赖集G= UiF 与与F+是

49、否等价，也就是检验对于任是否等价，也就是检验对于任意一个函数依赖意一个函数依赖XY F +是否可以由是否可以由G根据根据Armstrong公理导出，即是否有公理导出，即是否有Y XG +69举例举例判断无损连接性和函数依赖性判断无损连接性和函数依赖性设有关系：设有关系：S-C-M（S学号，学号，C班级，班级，M班主任）班主任）F=S学号学号 C班级，班级， C班级班级 M班主任，班主任， S学号学号 M班班主任主任1=S-C（学号，班级），（学号，班级），C-M（班级，班主任）（班级，班主任）1具有无损连接和保持函数依赖性具有无损连接和保持函数依赖性2=S-C（学号，班级），（学号，班级），S

50、-M（学号，班主任）（学号，班主任）2具有无损连接性，但不具有保持函数依赖性具有无损连接性，但不具有保持函数依赖性3=S-M（学号，班主任），（学号，班主任），C-M（班级，班主任）（班级，班主任）3不具有无损连接性和保持函数依赖性不具有无损连接性和保持函数依赖性70举例举例判断无损连接性和函数依赖性判断无损连接性和函数依赖性设有关系：设有关系：S-C-M（S学号，学号，C班级，班级，M班主任）班主任）F=S学号学号 C班级，班级， C班级班级 M班主任，班主任， S学号学号 M班班主任主任1=S-C（学号，班级），（学号，班级），C-M（班级，班主任）（班级，班主任）1具有无损连接和保持函数

51、依赖性具有无损连接和保持函数依赖性2=S-C（学号，班级），（学号，班级），S-M（学号，班主任）（学号，班主任）2具有无损连接性，但不具有保持函数依赖性具有无损连接性，但不具有保持函数依赖性3=S-M（学号，班主任），（学号，班主任），C-M（班级，班主任）（班级，班主任）3不具有无损连接性和保持函数依赖性不具有无损连接性和保持函数依赖性715.3.5 模式分解与模式等价问题模式分解与模式等价问题模式等价模式等价 = 数据等价数据等价 + 依赖等价依赖等价数据等价：表达同样的信息，不少也不能多数据等价：表达同样的信息，不少也不能多依赖等价：相同的数据依赖集闭包依赖等价：相同的数据依赖集闭包

52、数据冗余及操作异常解决的办法是关系模式的分数据冗余及操作异常解决的办法是关系模式的分解。分解要保证信息无损和依赖无损。那么怎样分解，解。分解要保证信息无损和依赖无损。那么怎样分解，分解到何时才是分解到何时才是“规范规范”的？的？ 规范化理论规范化理论正是用来改造关系模式，通过分解关正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题的理论向导。常、删除异常、更新异常和数据冗余问题的理论向导。72范式范式u范式范式(Normal Form)是符合某一种级别的关系是符合某一种级别的关系模式的

53、集合。构造数据库必须遵循一定的规则，模式的集合。构造数据库必须遵循一定的规则，在关系数据库中，这种规则就是范式。在关系数据库中，这种规则就是范式。u满足不同程度要求的为不同范式。满足不同程度要求的为不同范式。u范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)一般说来，数据一般说来，数据库只要满足第三库只要满足第三范式就行了范式就行了73范式范式u各种范式之间存在联系：各种范式之间存在联系：u某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为RnNF。N

54、F5NF4BCNFNF3NF2NF1745.4.1 1NF1NF的定义的定义如果一个关系模式如果一个关系模式R的所有属性都是不可分的基本数的所有属性都是不可分的基本数据项据项(原子项原子项)，则，则R1NF。 第一范式是对关系模式的最起码的要求。不满第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。足第一范式的数据库模式不能称为关系数据库。 在第一范式（在第一范式（1NF）中表的每一行只包含一个实）中表的每一行只包含一个实例的信息（例的信息（第一范式就是无重复的列第一范式就是无重复的列 ） 但是满足第一范式的关系模式并不一定是一个但是满足第一范式的关系模式并不一

55、定是一个好的关系模式。好的关系模式。755.4.2 2NF的引入的引入u对于一个关系而言，除了要确定对于一个关系而言，除了要确定R的属性的属性U之之外，还要根据外，还要根据R的语义确定关系模式上的所有的语义确定关系模式上的所有函数依赖函数依赖F。u通常满足通常满足1NF的关系模式常包含许多部分依赖，的关系模式常包含许多部分依赖，因而就会存在数据冗余因而就会存在数据冗余765.4.2 2NF例例: 关系模式关系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc为学生住处，假设每个系的学生住在同一个为学生住处，假设每个系的学生住在同一个地方。地方。u函数依赖包括：函

56、数依赖包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc77 2NFSLC的码为的码为(Sno, Cno)SLC满足第一范式。满足第一范式。 非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno, Cno)SnoCnoGradeSdeptSlocSLC78 2NF(1) 插入异常插入异常假设假设Sno95102，SdeptIS，SlocN的学的学生还未选课，因课程号是主属性，因此该学生还未选课，因课程号是主属性，因此该学生的信息无法插入生的信

57、息无法插入SLC。(2) 删除异常删除异常 假定某个学生本来只选修了假定某个学生本来只选修了3号课程这一门号课程这一门课。现在因身体不适，他连课。现在因身体不适，他连3号课程也不选号课程也不选修了。因课程号是主属性，此操作将导致该修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。学生信息的整个元组都要删除。79 2NF(3) 数据冗余度大数据冗余度大 如果一个学生选修了如果一个学生选修了10门课程，那么他的门课程，那么他的Sdept和和Sloc值就要重复存储了值就要重复存储了10次。次。(4) 修改复杂修改复杂 例如学生转系，在修改此学生元组的例如学生转系，在修改此学生元组的S

58、dept值的同时，还可能需要修改住处（值的同时，还可能需要修改住处（Sloc）。）。如果这个学生选修了如果这个学生选修了K门课，则必须无遗漏门课，则必须无遗漏地修改地修改K个元组中全部个元组中全部Sdept、Sloc信息。信息。802NF的引入的引入u确定了函数依赖集确定了函数依赖集F后，关系模式就可以进行后，关系模式就可以进行规范化工作了。规范化工作了。u规范化的核心是对关系模式逐级提出所必需的规范化的核心是对关系模式逐级提出所必需的遵循的约束条件，其表现形式就是各级遵循的约束条件，其表现形式就是各级“范范式式”，其出发点和落脚点都是使得所建立的关，其出发点和落脚点都是使得所建立的关系模式具

59、有较低的冗余度和较少的异常性。系模式具有较低的冗余度和较少的异常性。81 2NFu原因原因 Sdept、 Sloc部分函数依赖于码。部分函数依赖于码。u解决方法解决方法 SLC分解为两个关系模式，以消除这些部分函分解为两个关系模式，以消除这些部分函数依赖数依赖 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）822NF函数依赖图函数依赖图：SnoCnoGradeSCSLSnoSdeptSloc83 2NFu2NF的定义的定义定义定义5.8 若关系模式若关系模式R1NF，并且每一个，并且每一个非主非主属属性属属性都都完全函数依赖完全函数依赖于于R的候选键，则的候选

60、键，则R2NF。例：例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF84 2NFu采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的关系，可以在一定程度上减轻原的关系，可以在一定程度上减轻原1NF关关系中存在的插入异常、删除异常、数据冗余度系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。大、修改复杂等问题。u将一个将一个1NF关系分解为多个关系分