1、1第5讲 关系规范化与分解理论思考以下问题思考以下问题: 1. 不规范的关系模式会带来什么不规范的关系模式会带来什么问题？问题？ 2. 关系规范化有哪些标准？关系规范化有哪些标准？ 3. 如何将不规范的关系模式分解如何将不规范的关系模式分解成满足要求的关系模式呢？成满足要求的关系模式呢？2一. 关系模式的规范化理论 “不好不好”的数据库设计的数据库设计举例：为学校设计一个关系数据库举例：为学校设计一个关系数据库 关系模式关系模式: 选修情况选修情况 属性集：学号属性集：学号 课程编号课程编号 分数分数 学生所在系学生所在系 系主任姓名系主任姓名 按照实际情况装入部分数据按照实际情况装入部分数据
2、:3从以上数据可以看出从以上数据可以看出: 该关系模式的主码：学号和课程编号该关系模式的主码：学号和课程编号4一. 关系模式的规范化理论 对以上关系模式进行操作时对以上关系模式进行操作时,会出现以下问题会出现以下问题1. 数据冗余数据冗余(系主任名的存储次数系主任名的存储次数) 数据重复存储数据重复存储:浪费存储空间浪费存储空间,数据库维护困难数据库维护困难2. 插入异常插入异常(一个系刚成立一个系刚成立) 主码为空的记录不能存在于数据库主码为空的记录不能存在于数据库,导致不能导致不能进行插入操作进行插入操作3. 删除异常删除异常(一个系的学生全部毕业一个系的学生全部毕业) 删除操作后删除操作
3、后,一些相关信息无法保存在数据库中一些相关信息无法保存在数据库中4. 修改复杂修改复杂 （如学生转系）（如学生转系）5一. 关系模式的规范化理论 关系模式应满足的基本要求关系模式应满足的基本要求 1) 元组的每个分量必须是不可分的数据项。元组的每个分量必须是不可分的数据项。 2) 数据库中的数据冗余应尽可能少。数据库中的数据冗余应尽可能少。 3) 关系数据库不能因为数据更新操作而引起关系数据库不能因为数据更新操作而引起数据不一致问题。数据不一致问题。 4) 当执行数据插入操作时，数据库中的数据当执行数据插入操作时，数据库中的数据不能产生插入异常现象。不能产生插入异常现象。 5) 数据库中的数据
4、不能在执行删除操作时产数据库中的数据不能在执行删除操作时产生删除异常问题。生删除异常问题。 6) 数据库设计应考虑查询要求，数据组织应数据库设计应考虑查询要求，数据组织应合理。合理。6一. 关系模式的规范化理论范式范式(Normal Form)是指规范化的关系是指规范化的关系模式模式 由满足最基本规范化的关系模式叫第一由满足最基本规范化的关系模式叫第一范式，第一范式的关系模式再满足另外范式，第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三一些约束条件就产生了第二范式、第三范式、范式、BC范式等等。一个低一级的关范式等等。一个低一级的关系范式通过模式分解可以转换成若干高系范式通过模
5、式分解可以转换成若干高一级范式的关系模式的集合，这种过程一级范式的关系模式的集合，这种过程叫关系模式的规范化。叫关系模式的规范化。7一. 关系模式的规范化理论 函数依赖函数依赖 设设R RU U是属性集是属性集U U上的关系模式，上的关系模式，X X、Y Y是是U U的子的子集。若对于集。若对于R RU U的任意一个可能的关系的任意一个可能的关系r r，r r中不中不可能存在两个元组在可能存在两个元组在X X上的属性值相等，而上的属性值相等，而Y Y上的属性上的属性值不等，则称值不等，则称X X函数确定函数确定Y Y函数，或函数，或Y Y函数依赖于函数依赖于X X函函数，记作数，记作XYXY。
6、 XY XY，但，但Y XY X，则称，则称XYXY是非平凡的函数依赖。是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。 XY XY，但，但Y Y X X，则称，则称XYXY是平凡的函数依赖。是平凡的函数依赖。 若若XYXY，则，则X X叫做决定因素（叫做决定因素（DeterminantDeterminant），），Y Y叫做依赖因素（叫做依赖因素（DependentDependent）。）。 若若XYXY，YXYX，则记作，则记作X XY Y。 若若Y Y不函数依赖于不函数依赖于X X，则记作，则记作X YX Y。8一. 关系模式的规范化理
7、论 举例举例:职工号职工号(A) 基本工资基本工资(B)奖金奖金(C) 051 390 50 052 420 50 053 390 80 A B A C B A C A B C C B 9一. 关系模式的规范化理论 举例举例:1.1.下列函数依赖中，下列函数依赖中，( )( )是平凡的函数依赖。是平凡的函数依赖。 A) ABBC B) ABCDA) ABBC B) ABCD C) ABA D) ABD C) ABA D) ABD2. 若属性若属性X函数依赖于属性函数依赖于属性Y时，则属性时，则属性X与属与属性性Y之间具有之间具有( )的联系。的联系。 A）一对一）一对一 B）一对多）一对多 C
8、）多对一）多对一 D）多对多）多对多10一. 关系模式的规范化理论完全函数依赖、传递函数依赖完全函数依赖、传递函数依赖 在在R RU U中，如果中，如果XYXY，并且对于，并且对于X X的任何一个真子的任何一个真子集集XX，都有，都有X YX Y，则称，则称Y Y对对X X完全函数依赖，记作：完全函数依赖，记作：XYXY；若；若XYXY，但，但Y Y不完全函数依赖于不完全函数依赖于X X，则称，则称Y Y对对X X部分部分函数依赖，记作：函数依赖，记作： XYXY。例如，在选修关系模式：例如，在选修关系模式：( (学号，课程名学号，课程名)成绩，成绩，( (学学号，课程名号，课程名)姓名姓名
9、在在R RU U中，如果中，如果XYXY，(Y X)(Y X)，Y XY X，YZYZ，则，则称称Z Z对对X X传递函数依赖。传递函数依赖记作传递函数依赖。传递函数依赖记作X ZX Z。传递例如，在选修模式中，因为：学号传递例如，在选修模式中，因为：学号系名，系名系名，系名系主任；所以：学号系主任；所以：学号 系主任系主任。 FPFP传递传递11二. 范式介绍 1NF 如果关系模式如果关系模式R R，其所有的属性均为简单属，其所有的属性均为简单属性，即每个属性都是不可再分的，则称性，即每个属性都是不可再分的，则称R R属于第属于第一范式，记作一范式，记作R R1NF1NF。 2NF 若若R
10、1NF，且每一个非主属性完全，且每一个非主属性完全依赖于码，则依赖于码，则R 2NF。12二. 范式介绍 3NF 关系模式关系模式RURF中若不存在这样的码中若不存在这样的码X X、属、属性组性组Y Y及非主属性及非主属性Z(Z Y)Z(Z Y)使得使得XYXY、Y XY X、YZYZ成立，则称成立，则称RURF3NF3NF。可以证明，若可以证明，若R R3NF3NF，则每一个非主属性既不，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。部分函数依赖于码，也不传递函数依赖于码。13二. 范式介绍 BCNF 关系模式关系模式R 1NF。若。若XY且且Y X时时X必含有码，则必含有码，
11、则R BCNF。也就是说，。也就是说，关系模式关系模式R 中，若每一个决定因素都包中，若每一个决定因素都包含码，则含码，则R BCNF。一个满足一个满足BCNF的关系模式有：的关系模式有： 1) 所有非主属性对每一个码都是完全函数依赖。所有非主属性对每一个码都是完全函数依赖。 2) 所有的主属性对每一个不包含它的码，也是完所有的主属性对每一个不包含它的码，也是完全依赖。全依赖。3) 没有任何属性完全函数依赖于非码的任何一组没有任何属性完全函数依赖于非码的任何一组属性。属性。14示例：设有教师任课关系模式有教师任课关系模式TDC TDC(教师编号教师编号,教师姓名教师姓名,职称职称,教师地址教师
12、地址,系系编号编号,系名称系名称,系地址系地址,课程号码课程号码,课程名课程名,学分学分,教教学水平学水平) 现实世界的实事告诉我们，一个系有若干名现实世界的实事告诉我们，一个系有若干名教师，但一个教师只能属于一个系，一个教师教师，但一个教师只能属于一个系，一个教师可以担任多门课程的教学，同时任意一门课程可以担任多门课程的教学，同时任意一门课程可以由多名教师承担。可以由多名教师承担。试分析该关系模式有何弊病？该关系模式是否试分析该关系模式有何弊病？该关系模式是否属于属于3NF？若不是，请将其规范化为？若不是，请将其规范化为3NF。15示例：分析：分析：存在的函数依赖有：存在的函数依赖有：教师编
13、号教师编号教师姓名教师姓名, 教师编号教师编号职称职称,教师编号教师编号教师地址教师地址, 教师编号教师编号系编号系编号,教师编号教师编号系名称系名称, 教师编号教师编号系地址系地址,系编号系编号系名称系名称, 系编号系编号系地址系地址,课程号码课程号码课程名课程名, 课程号码课程号码学分学分, (教师编号教师编号,课程号码课程号码)教学水平教学水平存在以下问题：存在以下问题： 数据大量冗余数据大量冗余 插入异常插入异常(新教师，新课程的插入新教师，新课程的插入) 删除异常删除异常(某个课程取消某个课程取消) 修改复杂修改复杂(教师改上其它课程）教师改上其它课程）16示例：解答：解答：该关系模
14、式属于1NF，将其分解为： 教师教师(教师编号教师编号,教师姓名教师姓名,职称职称,教师地址教师地址) 课程课程(课程号码课程号码,课程名课程名,学分学分) 系系(系编号系编号,系名称系名称,系地址系地址) 讲课讲课(教师编号教师编号,课程号码课程号码,教学水平教学水平)以上分解符合以上分解符合3NF，且符合，且符合BCNF17三. 关系模式分解理论函数依赖的逻辑蕴含 设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出XY，则称F逻辑蕴含XY，或称XY是F的逻辑蕴含。Armstrong公理系统(1) Armstrong公理系统设U为属性集，F是U上的函数依赖集，于是
15、有关系模式RU，F。对RU，F来说，有以下的推理规则。1) 自反律：若YXU，则XY为F所蕴含。2) 增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。3) 传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。(2) Armstrong公理的三个推理1) 合并规则：由XY，XZ，有XYZ。2) 伪传递规则：由XY，WYZ，有XWZ。3) 分解规则：由XY及ZY，有XZ。18三. 关系模式分解理论函数依赖集闭包F+和属性集闭包XF+(1) 函数依赖集闭包函数依赖集闭包F+和属性集闭包和属性集闭包XF+的定义的定义定义：在关系模式定义：在关系模式RU，F中，为中，为F所逻辑蕴含的函数依赖的全体
16、所逻辑蕴含的函数依赖的全体叫做叫做F的闭包，记作的闭包，记作F+。定义：设有关系模式定义：设有关系模式RU，F，X是是U的子集，称所有从的子集，称所有从F推出的推出的函数依赖集函数依赖集XAi中中Ai的属性集为的属性集为X的属性闭包，记作的属性闭包，记作XF+。即：。即： XF+= Ai | AiU，XAiF+(2) 属性集闭包属性集闭包XF+的求法的求法1) 选选X作为闭包作为闭包XF+的初值的初值XF(0)。2) XF(i+1)是由是由XF(i)并上集合并上集合A所组成，其中所组成，其中A为为F中存在的函数依赖中存在的函数依赖YZ，而，而A Z，Y XF(i)。3) 重复步骤重复步骤2)。
17、一旦发现。一旦发现XF(i)= XF(i+1)，则，则XF(i)为所求为所求XF+。19三. 关系模式分解理论函数依赖集的最小化函数依赖集的最小化(1) 最小函数依赖集的定义最小函数依赖集的定义如果函数依赖集如果函数依赖集F满足下列条件，则称满足下列条件，则称F为一个极小函数依赖集。亦为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。称为最小依赖集或最小覆盖。1) F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。3) F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真
18、子集有真子集Z使得使得F-XAZA与与F等价。等价。(2) 最小函数依赖集的求法最小函数依赖集的求法1) 逐一检查逐一检查F中各函数依赖中各函数依赖XY，若，若Y=A1A2Ak，k2，则用，则用XAj|j=1，2，k来取代来取代XY。2) 逐一检查逐一检查F中各函数依赖中各函数依赖XA，令，令G=F-XA，若，若AXG+，则从，则从F中去掉此函数依赖。中去掉此函数依赖。3) 逐一取出逐一取出F中各函数依赖中各函数依赖XA，设，设X=B1B2Bm，逐一检查，逐一检查Bi（i=1，2，m），如果），如果A(X-Bi)F+，则以，则以X-Bi取代取代X。20三. 关系模式分解理论将关系转化为将关系转
19、化为3NF、且既具有无损连接性又能保持函数依赖的分解、且既具有无损连接性又能保持函数依赖的分解(1)将关系模式转化为将关系模式转化为3NF的保持函数依赖的分解的保持函数依赖的分解1) 对RU，F中的F进行极小化处理。处理后的函数依赖集仍用F表示。2) 找出不再在F中出现的属性，把这样的属性构成一个关系模式，并把这些属性从U中去掉。3) 如果F中有一个函数依赖涉及R的全部属性，则R不能再分解。4) 如果F中含有XA，则分解应包含模式XA，如果XA1，XA2，XAn均属于F，则分解应包含模式XA1A2An。(2)将关系转化为将关系转化为3NF既具有无损连接性又能保持函数依赖的分解既具有无损连接性又能保持函数依赖的分解对于给定的关系模式RU，F，将其转换为3NF，且既具有无损连接性又能保持函数依赖的分解算法为：1) 设X是RU，F的码，RU，F先进行保持函数依赖的分解，结果为 = R1U1，F1，R2U2，F2，RkUk，Fk， 令=R*X，Fx。2) 若有某个Ui，X Ui，将R*X，Fx从中去掉，就是所求的分解。
