第3章 关系数据库的规范化理论.ppt

第3章 关系数据库的规范化理论,本章导读：关系规范化理论研究的是关系模式中各属性之间的依赖关系及其对关系模式性能的影响，探讨“好”的关系模式应该具备的性质，以及达到“好”的关系模式提供的方法。关系规范化理论提供了判断关系逻辑模式优劣的理论标准，是数据库设计的理论基础和关系模式算法工具，用于帮助数据库设计工程师预测和优化模式可能出现的问题。知识要点：存储异常函数依赖数据依赖的公理系统规范化,3.1 存储异常,3.1 存储异常,根据以上分析，可以采用单一的数据库模式，即Jxgl(学号，学生姓名，年龄，籍贯，职工编号，教师姓名，职称，课酬标准，课程编号，课程名称，学时，成绩)对应这种单一的模式，在实际数据库，可能会存在如下几个问题：（1）数据冗余如果某个学生选修多门课，则学生的信息会重复出现多次，造成数据冗余。同理多个学生选修一门课，则该门课程及授课的教师信息也会重复出现多次。（2）更新异常由于数据的冗余，当更新数据库中的数据时，系统需要付出很大的代价来维护数据库的完整性，否则会造成数据不一致。如更新某门课程的主讲教师，则要更新选修该门课程的所有元组，修改其中的主讲教师信息，如有疏忽，就会造成数据的不一致。（3）插入异常如果某个学生还没有选课，课程号为空，但是根据实体完整性规则主属性不能为空，无法插入主属性取空值的学生信息，同理也不能插入主属性取空值的课程信息和教师信息。（4）删除异常如果删除某个教师信息，由于主属性不能为空，必然在删除教师信息的同时，连带删除学生和课程信息，从而删除掉了不应该删除的信息，但事实上学生和课程信息应该予以保留。同理删除学生信息，或者课程信息，也会存在这个问题。,3.1 存储异常,发生这些异常问题的根本原因：数据冗余，即没有考虑模式内部属性之间的内在相关性，简单地把无直接联系的属性放在一起构成关系模式，造成不必要的数据冗余。解办法就是将现有单一关系模式进行分解，改造成如下5个模式。（1）学生(学号，姓名，年龄，籍贯)。（2）教师(职工编号，姓名，职称，课酬标准)。（3）课程(课程编号，课程名称，学时)。（4）选课(学号，课程编号，成绩）。（5）授课(职工编号，课程编号，课酬)。,3.2 函数依赖,设计好的数据库是否实用、高效，或者是否合理、正确，可依据关系数据库设计理论进行核查。关系数据库设计理论要包括3个方面：数据依赖、范式、模式设计方法，其中数据依赖起着核心作用，因为它是解决数据库的数据冗余和操作（插入、删除和更新）异常问题的关键所在。,3.2 函数依赖,1数据依赖和函数依赖关系模式中各属性之间相互依赖，相互制约的关系称为数据依赖。数据依赖是通过关系中属性间的值是否相等体现出来的数据间的相互关系，它是信息世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。数据冗余的产生和数据依赖有密切的关系。数据依赖一般分为函数依赖、多值依赖和连接依赖，其中最重要的是函数依赖。【定义3.1】 设有关系模式R(A1,A2,A3,An)，简记R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，对于X的每一个具体值，Y都有唯一的具体值与之对应，则称X函数决定Y，或Y函数依赖于X，记为XY。其中X称为这个函数依赖的决定属性集或决定因素，与之相对应，Y称为被决定因素。函数依赖如同数学中函数一样，自变量x确定以后，相应的的函数值f(x)也就唯一确定了。对于函数依赖有以下几点具体说明：（1）函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的所有关系均要满足的约束条件；（2）函数依赖是语义范畴的概念，只能根据语义来确定函数依赖。例如：函数依赖“姓名所在系”只有在学生不重名的情况下成立，如果允许重名，则“所在系”不能函数依赖于“姓名”了；（3）函数依赖是属性关联的客观存在和数据库设计者的人为强制相结合的产物；（4）若Y不函数依赖于X，记作XY；（5）若XY，且YX，则记作XY。函数依赖根据其性质可分为完全函数依赖，部分函数依赖，传递函数依赖、平凡函数依赖和非平凡函数依赖等。,3.2 函数依赖,2平凡函数依赖和非平凡函数依赖（1）非平凡函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且Y不属于X的子集，则称XY是非平凡函数依赖。（2）平凡函数依赖若XY，且Y属于X的子集，则称XY是平凡函数依赖。平凡函数依赖总是成立的，它不反映新的语义，没有特别说明，总是讨论非平凡函数依赖。例如在关系模式R(学号,姓名,课程号,成绩)中，(学号,课程号)成绩是非平凡函数依赖，(学号,课程号)学号，(学号,课程号) 课程号是平凡函数依赖。,3.2 函数依赖,3完全函数依赖和部分函数依赖（1）完全函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且对X中的任何真子集Z，都有ZY，则称Y完全函数依赖于X，记作：XfY。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号课酬，且课程号课酬，所以(教师编号，课程号)f 课酬。（2）部分函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且X中存在一个真子集Z，满足ZY，则称Y部分函数依赖于X，记作：XPY。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号姓名，且课程号课程名称，所以(教师编号，课程号)P姓名，(教师编号，课程号)P课程名称。换言之，在一个函数依赖关系中，只要决定属性集中不包含多余的属性，即从决定属性集中去掉任何一个属性，函数依赖关系都不成立，就是完全函数依赖，否则就是部分函数依赖。由此可知，决定属性集中只包含一个属性的函数依赖一定是完全函数依赖。,3.2 函数依赖,4传递函数依赖设有关系模式R(U)，X、Y和Z是属性集U的子集，如果对于R(U)的任意一个可能的关系r，如果XY，YZ，且YX，Z-X、Z-Y和Y-X均不为空，则称Z传递函数依赖于X，记作：XtZ。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号职称，职称课酬标准，职称教师编号，所以教师编号t课酬标准是课酬标准传递函数依赖教师编号。,3.3 规范化,数据依赖的公理系统是模式分解算法的理论基础，函数依赖的一个有效而完备的公理系统是Armstrong系统，它是Armstrong于1974年提出来的一套从函数依赖推导逻辑蕴含的推理规则。1.Armstrong公理系统【定义3.2】 设R是一个具有属性集合U的关系模式，F是R上函数依赖集合，对于任何一组满足函数依赖F的关系r，若函数依赖XY都成立（即r中任意两元组t，s，若tX=sX，则tY=sY），则称F逻辑蕴含XY。为了求得给定关系模式的码，从一组函数依赖中求得其蕴含的函数依赖，就需要使用Armstrong公理系统。Armstrong公理系统对关系模式R来说有以下的推理规则：A1. 自反律（平凡函数依赖）：若YXU，则XY为F所蕴含。A2. 增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3. 传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。根据A1、A2、A3这3条推理规则可以得到下面3条很有用的导出规则：合并规则：由XY，XZ，有XYZ（由A2、A3导出）。伪传递规则：由XY，WYZ，有XWZ（由A2、A3导出）。分解规则：由XY及ZY，有XZ（由A1、A3导出）。,3.3 规范化,【引理3.1】 XA1A2Ak成立的充分必要条件是XAi成立（i=l,2,k）。【定义3.3】 设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，X F+称为属性集X关于函数依赖集F的闭包。【引理3.2】 设F为属性集U上的一组函数依赖，X、YU，XY能由F根据Armstrong公理导出的充分必要条件是YX F+。于是，判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出X F+，判定Y是否为X F+的子集的问题。这个问题可以使用算法3.1解决。,2.求解函数依赖集的闭包,【算法3.1】 求属性集X（XU）关于U上的函数依赖集F的闭包X F+。输入：X，F。输出：X F+。步骤：（1）令X（0）=X，i=0；（2）求B，这里B=A|(V)(W)(VWFVX（i）AW)；注意：逐一的扫描F集合中的各函数依赖，找决定因素是X（i）的子集的函数依赖，用找到的函数依赖的依赖因素A组成集合B。（3）X（i+1）=BX（i）；（4）判断X（i+1）=X（i）；（5）若相等或X（i+1）=U，则X（i+1）就是XF+，算法终止；（6）若否，则i=i+l，返回第（2）步。,【例3-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。（2）因为X（0）X（1），所以再找出左部为ABCD的子集的那些函数依赖，又得到ABC，BD，CE，ACB。于是，X（2）=X（1）BCDE=ABCDE。（3）因为X（2）=U，算法终止。得到结果：(AB)F+=ABCDE。,3最小依赖集,从蕴含的概念出发，又引出了最小依赖集的概念。每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。求得最小函数依赖集是模式分解的基础。下面就给出求F的最小依赖集的算法。【算法3.2】 分3步对F进行“极小化处理”，找出F的一个最小依赖集。（1）逐一检查F中各函数依赖FDi：XY。若Y=A1A2Ak，k>2，则用XAj|j=1,2,k来取代XY。（2）逐一检查F中各函数依赖FDi：XA，令G=FXA，若AXG+，则从F中去掉此函数依赖。（3）逐一取出F中各函数依赖FDi：XA，设X=B1B2Bm，逐一考察Bi（i=l,2,m），若A(XBi)F+，则以XBi取代X。最后剩下的F就一定是极小依赖集。,【例3-2】 F=ABC, BD, CE, ECB, ACB，求其极小函数依赖集。解：第一步：先分解右端，F不变。F=ABC,BD,CE,ECB,ACB第二步：（1）去掉ABC，得到G=BD, CE, ECB, ACB，求ABG+，AB G+中不包含C，不可以去掉ABC。F不变。（2）去掉BD，得到G=ABC,CE,ECB,ACB，求B G+，B G+中不包含D，不可以去掉BD。F不变。（3）去掉CE，得到G=ABC,BD,ECB,ACB，求CG+，CG+中不包含E，不可以去掉CE。F不变。（4）去掉ECB，得到G=ABC,BD,CE,ACB，求ECG+，ECG+中不包含B，不可以去掉ECB。F不变。 （5）去掉ACB，得到G=ABC,BD,CE,ECB，求ACG+，ACG+中包含B，可以去掉ACB。F=G= ABC,BD,CE,ECB。第三步：（1）判断ABC：求AF+=A，不包含C，不能去掉B。求BF+=BD，不包含C，不能去掉A。（2）判断ECB：求EF+=E，不包含B，不能去掉C。求CF+=BCDE，包含B，可以去掉E。F变为F= ABC,BD,CE,CB最终得到的就是F的最小函数依赖集。注意：F的最小函数依赖集不一定是唯一的，它与对各函数依赖FDi及XA中X各属性的处理顺序有关。,3.4 规范化,设计、验证和修改关系模式，首要的问题就是将关系模式中各属性之间的关系分析清楚。在关系数据库模式的设计过程中，为了避免由数据依赖引起的数据冗余和插入、删除和更新异常问题，必须对关系模式进行合理分解，以消除数据依赖中的不合适部分。也就是说，通过投影运算，将低一级范式的关系模式转换成若干个高一级范式的关系模式的集合，这个过程就是关系的规范化。关系规范化是数据库设计的手段，不是目的。1范式概念在关系规范化理论中，将满足特定要求的约束条件划分成若干等级标准，这些标准统称为范式（Normal Formula，简写为NF）。通常，按照属性间的数据依赖程度的高低来区分，将关系规范化等级划分为1NF、2NF、3NF、4NF、5NF。5类范式的条件一个比一个严格，1NF的规范化程度最低吗，而5NF的规范化程度最高，其中3NF和BCNF最重要。各范式之间存在低级包含高级的包含关系，即1NF2NF3NF4NF5NF。范式的级别越高，分解就越细，所得关系的数据冗余就越小，异常情况也就越少。但是，在减少关系数据冗余和消除异常的同时，也加大了系统对数据检索的开销，降低了数据检索的效率。从1971年E.F.Codd提出了关系规范化理论开始，人们对数据库模式的规范化问题进行了长期的研究，并已经取得了很大进展。关系设计的一般原则包括：（1）数据冗余量小；（2）对关系的更新、插入、删除不要出现异常问题；（3）尽量能如实反映现实世界的实际情况，而且又易懂。,3.4 规范化,2范式类型（1）第一范式（1NF）对于给定的关系R，如果R中的所有行、列交点处的值都是不可再分的数据项，则称关系R属于第一范式，记作：R1NF。在关系数据库中，1NF是对关系模式的最低要求，它是由关系的基本性质决定的，任何一个关系模式都必须遵守，不满足第一范式的关系模式不能称为关系数据库。,（2）第二范式（2NF）如果关系R1NF，并且R的每一个非主属性都完全函数依赖于R的候选键，则称R属于第二范式，记作：R2NF。换言之，不存在部分函数依赖的第一范式称为第二范式。显然，主码只包含一个属性的关系模式，如果属于属于1NF，那么一定属于2NF。例如，在关系模式R(教师编号,姓名,性别,职称,课酬标准,课程号,课程名称,学时,课酬)中，由属性组(教师编号，课程号)构成一个关键字，姓名，职称，课酬标准，课程名称，学时和课酬属性为非主属性。只有课酬对关键字完全函数依赖，而其它主非属性仅是部分函数依赖主关键字，所以R2NF。由1NF到2NF的规范化就是为了消除非主属性对主关键字的部分函数依赖。具体做法是：采用投影运算方法，将部分函数依赖的属性和完全函数依赖的属性分离，分别组成不同的关系模式，向高一级范式转化，模式分解如下：教师(教师编号,姓名,性别,职称,课酬标准）；课程(课程号,课程名称,学时）；课酬(教师编号,课程号,课酬）。其中，教师的主键为教师编号，课程的主键为课程号，课酬的主键为（教师编号，课程号），它们分别为具有以下的函数依赖：教师：教师编号f姓名，教师编号f性别，教师编号f职称，教师编号f课酬标准；课程：课程编号f课程名称，课程编号f学时；课酬：（教师编号,课程号）f课酬。分解后的三个关系模式中不存在非主属性对主关键字的部分函数依赖，故属于第二范式。,3.4 规范化,（3）第三范式（3NF）如果关系R2NF，并且R的每一个非主属性都不传递函数依赖于R的任何候选键，则称R属于第三范式，记作：R3NF。换言之，不存在部分函数依赖和传递函数以来的第一范式称为第三范式。考查上面分解的三个关系中：关系模式“课酬”中非主属性课酬既不部分函数依赖于关键字，也不传递函数于关键字，所以课酬3NF。同理关系模式“课程”中非主属性课程名称和学时既不部分函数依赖于关键字，也不传递函数于关键字，所以课程3NF。但是关系模式“教师”中，由于，教师编号职称，职称课酬标准，职称教师编号，所以教师编号t课酬标准。因此，教师3NF。同样，为了消除非主属性对主关键字的传递依赖，也可以通过投影运算方法将关系模式教师进行分解，得到如下两个关系模式：教师(教师编号，姓名，性别)职称(职称编号，职称，课酬标准)分解后的关系模式中不存在非主属性对关键字的传递函数依赖，故属于第三范式。3NF只是规定了非主属性对主键的数据依赖关系，但没有限制主属性对主键的数据依赖关系。如果存在主属性对主键的部分函数依赖和传递函数依赖，同样会出现数据冗余、操作异常问题。在实际应用中，一般达到了3NF的关系就可以认为是较为优化的关系。,（4）BCNFBCNF是3NF范式的改进形式，他建立在1NF范式的基础上。如果关系R1NF，并且R的每一个属性都不传递函数依赖于R的候选键，则称R属于BCNF范式，记作：RBCNF。从BCNF定义可知，一个满足BCNF的关系模式存在如下关系：所有非主属性对键是完全函数依赖；所有主属性对不包含它的键是完全函数依赖；没有属性完全函数依赖于非键的任何属性组。从函数依赖的角度考虑，一个关系模式如果达到了BCNF，数据冗余和操作（插入、删除和更新）异常问题就已经彻底消除了。不过数据依赖除了函数依赖以外，还有多值依赖和连接依赖，即使达到BCNF范式的关系模式仍有可能存在冗余等问题，这也是范式理论存在4NF、5NF等范式的原因。,3.4 规范化,【例3-3】 关系模式R，U=A,B,C,D,E，函数依赖集F=ABCE,EAB,CD，试问R最高属于第几范式？（1）求函数依赖集中决定因素是否为候选码，即求ABF+、E F+、C F+。得到：AB F+=U、E F+=U，求A F+和B F+，判断是否为U，A F+U，B F+U，所以AB和E是候选码。（2）由候选码判断主属性为A、B、E，非主属性为C和D。（3）判断非主属性对候选码有没有部分函数依赖。候选码E只有一个属性，不可分，所以不必判断。判断候选码AB，决定因素中没有A或B，所以不存在非主属性对候选码的部分函数依赖，达到2NF。（4）判断非主属性对候选码有没有传递函数依赖。在函数依赖集中有ABCE、CD，所以ABC、CD，存在非主属性D对候选码AB的传递函数依赖，只能达到2NF。得到结论：关系模式R只能达到第二范式。（5）判断非主属性对候选码有没有传递函数依赖。在函数依赖集中有ABCE、CD，所以ABC、CD，存在非主属性D对候选码AB的传递函数依赖，只能达到2NF。得到结论：关系模式R只能达到第二范式。,2.5.3 规范化,3模式分解关系规范化实质就是模式分解，按照一定的原则，将关系模式不断地分解为若干个关系模式的集合，通过模式分解使关系模式逐步达到较高范式。任何一个非规范化的关系模式经过分解，都可以达到3NF，但不一定要达到BCNF，模式分解的基本思想是从低到高，逐步规范，权衡利弊，适可而止。模式分解步骤如图3-1所示。,模式分解步骤如图2-1所示。,3.4 规范化,实际应用中，数据库设计人员应根据具体情况灵活掌握，不能在消除操作异常的情况下，产生其它新的问题。关系模式的分解满足两个基本原则：（1）关系分解后必须具有无损连接性。所谓无损连接是指通过分解后的关系进行某种连接运算，能够还原出分解前的关系。设关系模式R被分解为若干个关系模式R1(Ul,F1),R2(U2,F2),Rn(Un,Fn)（其中U=U1U2Un，且不存在UiUj，Ri为R在Ui上的投影），若R与R1,R2,Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性。（2）关系分解后要保持函数依赖。保持函数依赖是指分解过程不能破坏或丢失原来关系中存在的函数依赖。设关系模式R被分解为若干个关系模式R1(Ul,F1),R2(U2,F2),Rn(Un,Fn)（其中U=U1U2Un，且不存在UiUj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的。如果一个分解具有无损连接，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。,本章小结,本章主要讲述了关系数据库的基本概念，探讨了关系的数学定义、关系代数、关系演算、函数依赖、范式等关系数据库的基本理论。其中关系代数和关系规范化是本章的中的重点。,