关系数据库规范化理论1xt.ppt

1,数据库技术及应用,第三章关系数据库的规范化理论,2,3.1关系模式的冗余和异常问题,范式（NormalForm）：是指规范化的关系模式。第一范式（1NF）：由满足最基本规范化的关系模式。第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、BC范式等等。一个低一级的关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的规范化（Normalization）。,3,二、关系模式规范化的必要性,关系模式应满足的基本要求1)元组的每个分量必须是不可分的数据项。2)数据库中的数据冗余应尽可能少。数据量巨增，系统负担过重，浪费存储空间，造成数据的不完整。3)关系数据库不能因为数据更新操作而引起数据不一致问题。（数据冗余）4)当执行数据插入操作时，数据库中的数据不能产生插入异常现象。数据库中的数据因不能满足某种完整性要求而不能正常地插入到数据库中。5)数据库中的数据不能在执行删除操作时产生删除异常问题。删除某种信息的同时，把其他信息也删除了。多种信息捆绑在一起。,4,关系中每一个分量都必须是不可分的数据项。判断是否为关系的标准关系的一切数学理论都是基于关系服从1NF。,修改后的数据结构：,将大大增加关系操作的表达、优化及执行的复杂度。,5,6)数据库设计应考虑查询要求，数据组织应合理。,在数据库设计时，不仅要考虑到自身结构的完整性，还要考虑到数据的使用要求。为了使数据查询方便、数据处理简便，有必要通过视图、索引和适当增加数据冗余的方法。,6,2.关系中异常和冗余问题,数据冗余大；插入异常；删除异常；更新异常。,7,3.模式分解是关系规范化的主要方法,按“一事一地”的原则分解成“单位”、“物资”和“领料”三个关系，其关系模式为：,单位（单位编码，单位名称）物资（物资编码，物资名称，计量单位，价格）领料（单位编码，物资编码，领料时间，请领量，实发量）,关系模式:物资领料（单位编码，单位名称，物资编码，物资名称，领料时间，计量单位，价格，请领量，实发量）。,8,学生(学号，姓名，年龄，性别，系名称)；教学系(系名，系主任)；选课(学号，课程名，成绩).,9,3.2函数依赖,关系模式的简化表示法关系模式的完整表示是一个五元组：R(U，D，Dom，F).其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。关系模式可以用三元组来为：R(U，F),10,2.函数依赖的概念,设R（U）是属性集U上的关系模式，X、Y是U的子集。若对于R（U）的任意一个可能的关系r，r中的任一元组在X中的属性值确定后，则在Y中的属性值也必确定。则称X函数决定Y，或Y函数依赖于X，记作XY。XY，但YX，则称XY是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。XY，但YX，则称XY是平凡的函数依赖。若XY，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。若XY，YX，则记作XY。若Y不函数依赖于X，则记作XY。,函数依赖是数据依赖的一种，实际上它描述的是同一关系中属性间的联系。,11,例3，对于教学关系模式：教学（U，F）；U=学号，姓名，年龄，性别，系名，系主任，课程名，成绩；,例1：物资（物资编码，物资名称，计量单位，价格）属性“物资编码”和“物资名称”间有函数依赖关系，物资编码的值确定，物资名称的值也惟一确定。称“物资编码”函数决定“物资名称”或“物资名称”函数依赖于“物资编码”。,例2：领料（单位编码，物资编码，领料时间，请领量，实发量）,F=学号姓名，学号年龄，学号性别，学号系名，系名系主任，(学号，课程名)成绩.,“物资编码”与“请领量”间没有函数依赖关系。但,12,注意：函数依赖是语义范畴的概念，我们只能根据数据的语义来确定函数依赖。例如，“姓名所在系”这个函数依赖只有在没有同名人的条件下成立。如果有相同名字的人，则“所在系”就不再函数依赖于“姓名”了。,13,完全函数依赖、传递函数依赖,在R(U)中，如果XY，并且对于X的任何一个真子集X，都有XY，则称Y对X完全函数依赖，记作：XY；若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：XY。例:在教学关系模式：(学号，课程名)成绩，(学号，课程名)姓名.在R(U)中，如果XY，(YX)，YX，YZ，则称Z对X传递函数依赖。传递函数依赖记作XZ。例如，在教学模式中，因为：学号系名，系名系主任；所以：学号系主任。,P,f,f,P,传递,传递,14,码定义：设K为关系模式R(U)中的属性或属性组合，若KU，则称K为R的一个候选码。若关系模式有多个候选码，则选定其中的一个做为主码（primarykey）。主属性：包含在任何一个关键字中的属性。非主属性：不包含在任何候选码中的属性。在最简单的情况下，候选码只包含一个属性。在最极端的情况下，关系模式的所有属性组是这个关系模式的候选码，称为全码。,15,3.3范式和规范化方法,数据依赖引起的主要问题是插入、删除及更新异常等，解决的办法是进行关系模式的合理分解，也就是对关系模式规范化。范式是符合某一种级别的关系模式的集合。满足最低要求的叫第一范式，简称为1NF。在第一范式基础上进一步满足一些要求的为第二范式，简称为2NF。其余以此类推。显然各种范式之间存在联系。通常把某一关系模式R为第n范式简记为RnNF。,小知识：从1971年起，E。F。Codd相继提出了第一范式、第二范式，第三范式，Codd与Boyce合作提出了BoyceCodd范式，到目前为止，已提出了第五范式。,16,如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记作R1NF。它不允许属性值为元组、数组或某种复合数据等。,一、1NF的定义,仅满足第一范式是不够的，仍然存在异常和冗余问题，需对关系模式继续规范，使之服从更高的范式，才能得到性能较高的关系模式。,17,二、2NF,若关系模式RlNF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。2NF就是不允许关系模式的非主属性对码的部分依赖。即：XY，其中X是码的真子集，Y是非主属性。,显然，码只包含一个属性的关系模式如果属于1NF，那么它一定属于2NF。,18,例1：分析关系模式R（dwbm，wzbm，rq，dwmc，zgld，zgdz，qls，sfs）中的函数依赖：,19,如对关系模式R分解为两个关系模式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm，dwmc，zgld，zgdz）,关系分解实际上是把联系不紧密的属性尽量分开。,20,在教学模式中：,属性集=学号，姓名，年龄，系名，系主任，课程名，成绩.函数依赖集=学号姓名，学号年龄，学号性别，学号系名，系名系主任，(学号，课程名)成绩.主码=(学号，课程名).非主属性=(姓名，年龄，系名，系主任，成绩)。,(学号，课程名)姓名，(学号，课程名)年龄，(学号，课程号)性别，,(学号，课程名)系名，(学号，课程名)系主任；(学号，课程名)成绩.显然，教学模式不服从2NF，即：教学2NF。,P,P,P,P,P,非主属性对码的函数依赖：,21,根据2NF的定义，将教学关系模式分解：学生系（学号，姓名，性别，年龄，系名，系主任）。选课（学号，课程名，成绩）,问题：满足2NF的关系模式是否还存在异常和冗余问题？,22,三.3NF,关系模式RU，F中若不存在这样的码X、属性组Y及非主属性Z(ZY)使得XY、YX、YZ成立，则称R（U，F）3NF。可以证明，若R3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。,分析下面关系模式的范式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm，dwmc，zgld，zgdz）,R13NF，R23NF，对R2分解：R21（dwbm，dwmc，zgld）R22（zgld，zgdz）,23,例2：学生_系（学号，姓名，性别，年龄，系名，系主任）。,学号系名，系名系主任。则：,如果分解为：学生(学号，姓名，年龄，性别，系名)；教学系(系名，系主任).显然分解后的各子模式均属于3NF。,学生_系3NF。,24,说明：,1、3NF范式是一个可用的关系模式应满足的最低范式。,2、把关系模式分解到第三范式，可以在相当程度上减轻原关系中的异常和信息冗余，但也不能保证完全消除关系模式中的各种异常和信息冗余。要想使数据库性能得到进一步的改善，就要把关系模式进一步规范化。,25,四.BCNF（BoyceCoddNormalForm）,关系模式R（U，F）1NF。若XY（YX）时X必含有码，则R（U，F）BCNF。即：关系模式RU，F中，若每一个决定因素都包含码，则RU，FBCNF。一个满足BCNF的关系模式有：1)所有非主属性对每一个码都是完全函数依赖。2)所有的主属性对每一个不包含它的码，也是完全依赖。3)没有任何属性完全函数依赖于非码的任何一组属性。,26,例1：分析下面的关系是否满足BC范式？S11(学号，姓名，所在系)S12(所在系，系主任姓名)S2(学号，课程名，成绩),答：均满足BCNF范式,27,例2：关系模式SPC(S，C，P)中，S是学生，C表示课程，P表示名次。语义：每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生(即没有并列名次)。由语义可得到下面的函数依赖：,（S，C）P；(C，P)S候选码：(S，C)与(C，P)。SPC3NF，而且除(S，C)与(C，P)以外没有其它决定因素，所以SPCBCNF,28,例3：关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教师。由语义可以得到STJ模式的函数依赖为：F=(S，J)T，TJ显然：(S，J)和(T，S)都是关系的码；关系的主属性集为S，T，J，非主属性为（空集）。P由于STJ模式中无非主属性，所以它属于3NF；但因为存在TJ，由于T不是码，故STJBCNF。,29,五、BCNF和3NF的比较,1)BCNF不仅强调非主属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，故RBCNF，R一定属于3NF。2)3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传递依赖。,30,1NF,2NF,3NF,BCNF,削除非主属性对码的部分函数依赖,削除非主属性对码的传递函数依赖,削除主属性对码的部分和传递函数依赖,图1各种范式规范化过程,31,规范化小结：1、在关系数据库中，对关系模式的基本要求是满足第一范式。这样的关系模式就是合法的、允许的。但是，人们发现有些关系模式存在插入、删除异常、修改复杂、数据冗余等毛病。人们寻求解决问题的方法，这就是规范化的目的。2、规范化的基本思想是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”，即“一事一地”的模式设计原则。让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去。因此所谓规范化实质上是概念的单一化。,32,3、实际上，在对模式进行分解时，除考虑数据等价和依赖等价以外，还要考虑效率。当我们对数据库的操作主要是查询而更新较少时，为了提高查询效率，可能宁愿保留适当的数据冗余，让关系模式中的属性多些，而不愿把模式分解得太小，否则为了查询一些数据，常常要做大量的连接运算，把多个关系模式连在一起才能从中找到相关的数据。,在实际应用中，对模式分解的要求并不一定要达到BC范式或更高的范式，有时达到第三范式就足够了。,33,关系规范化理论研究：,函数依赖理论的研究（1）关系模式上的所有依赖通过一些公理系统（Armstrong）而获得关系模式上的所有依赖。基本的由语义获取，其他部分由公理系统推出。（2）最小函数依赖集:等价的函数依赖集中最小者。模式分解的研究（1）无损连接（反映了模式分解的数据等价原则。）当对关系模式R进行分解时，R的元组将分别在相应属性集进行投影而产生新的关系。如果对新的关系进行自然连接得到的元组的集合与原关系完全一致，则称为无损连接。（2）保持依赖当对关系模式R进行分解时，R的函数依赖集也将按相应的模式进行分解。如果分解后总的函数依赖集与原函数依赖集保持一致，则称为保持依赖。,34,F1=AB，BC，AC与F2=AB，BC，ABCF3=AB，BC是否等价？,35,3.4关系模式的分解算法一、关系模式分解的算法基础,函数依赖的逻辑蕴含设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出XY，则称F逻辑蕴含XY，或称XY是F的逻辑蕴含。如：FAB，BC，问AC是否成立？这就需要函数依赖的逻辑隐含知识，用函数依赖的公理系统推出。,36,2.Armstrong公理系统(1)Armstrong公理系统设U为属性集，F是U上的函数依赖集，于是有关系模式RU，F。对R（U，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。,由合并规则和分解规则，容易知：XA1A2Ak成立的充分必要条件为XAi成立。（i=1,2,k）,37,2、指出下列关系属于第几范式？并说明理由。,（1）R(X,Y,Z)F=XYZ解：R的候选码为XY，而R中决定因素只有XY，决定因素包含了码。RBCNF。,（2）R(X,Y,Z)F=YZ，XZY解：R的候选码为XY或XZ，不存在非主属性对码的部分或传递函数依赖R3NF。,38,（3）R(X,Y,Z)F=YZ，YX，XYZ，解：R的候选码为X和Y（单个属性），XYZ等价于：XY，XZ，故XY，不存在非主属性Z对码的传递函数依赖。又决定因素都是码，RBCNF。,（4）R(X,Y,Z)F=XY，XZ解：R的候选码为X（单个属性），又每一个函数依赖的左部都是码，RBCNF。,39,（5）R(X,Y,Z)F=XYZ解：R的候选码为XY，又每一个函数依赖的左部都是码，RBCNF。,（6）R(W，X,Y,Z)F=XZ，WXY解：R的候选码为WX，存在非主属性对码的部分函数依赖。R1NF。,40,3.函数依赖集闭包F+和属性集闭包XF+,(1)函数依赖集闭包F+和属性集闭包XF+的定义在关系模式R（U，F）中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。设有关系模式R（U，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，而AZ，YXF(i)。3)重复步骤2)。一旦发现XF(i)=XF(i+1)，则XF(i)为所求XF+。,41,【例1】已知关系RU，F，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)F+。设X=ABXF(0)=AB：AB为闭包初值,为本身。XF(1)=ABCD：由ABC，BD可得CD在闭包中。由XF(2)=ABCDE：由CE，知E在闭包中。XF(3)=XF(2)=ABCDE(AB)F+=ABCDE=A，B，C，D，E,42,4.函数依赖集的最小化,最小函数依赖集的定义如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。1)F中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖XA，使得F与FXA等价。(不含冗余函数依赖。)3)F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZ-A与F等价。(决定因素不含冗余属性。)如F=AB，BC，AC不是最小函数依赖集。,43,(2)最小函数依赖集的求法1)逐一检查F中各函数依赖XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY。(右边的属性单值化)2)逐一检查F中各函数依赖XA，令G=FXA，若AXG+，则从F中去掉此函数依赖。(去掉冗余函数依赖)3)逐一取出F中各函数依赖XA，设X=B1B2Bm，逐一检查Bi（i=1，2，m），如果A(X-Bi)F+，则以XBi取代X。(左边的属性单值化),44,【例4-2】设F=ABC，BAC，CA，对F进行极小化处理。,解：1)根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。F=AB，AC，BA，BC，CA2)去掉F中冗余的函数依赖。判断AB。设：G1=AC，BA，BC，CA，得：AG1+=ACBAG1+AB不冗余判断AC。设：G2=AB，BA，BC，CA，得：AG2+=ABCCAG2+AC冗余判断BA。设：G3=AB，BC，CA，（去掉AC冗余后）得：BG3+=BCAABG3+BA冗余判断BC。设：G4=AB，CA，得：BG4+=BCBG4+BC不冗余判断CA。设：G5=AB，BC，得：CG5+=CACG5+CA不冗余Fm=AB，BC，CA,45,【例4-3】求F=ABC，AB，BA的最小函数依赖集Fm。,解：(1)去掉F中冗余的函数依赖。判断ABC是否冗余。设：G1=AB，BA，得：(AB)G1+=ABC(AB)G1+ABC不冗余判断AB是否冗余。设：G2=ABC，BA，得：AG2+=ABABG2+AB不冗余判断BA是否冗余。设：G3=ABC，AB，得：BG3+=BABG3+BA不冗余经过检验后的函数依赖集仍然为F=ABC，AB，BA。(2)去掉各函数依赖左部冗余的属性。本题只需考虑ABC的情况。方法1：在决定因素中去掉B，若CAF+，则以AC代替ABC。求得：AF+=ABCCAF+以AC代替ABC故：Fm=AC，AB，BA方法2：在决定因素中去掉A，若CBF+，则以BC代替ABC。求得：BF+=ABCCBF+以BC代替ABC故：Fm=BC，AB，BA,46,3.4.2判定分解服从规范的方法,1.关系分解的无损连接性设关系模式R，如果把它分解为两个（或多个）子模式R1和R2，相应一个R关系中的数据就要被分成R1、R2两个（或多个）子表。假如将这些子表自然连接，即进行R1R2操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果RR1R2，则称该分解不具有无损连接性。2.判断分解成两个关系具有无损连接性的方法定理：RU，F的一个分解=R1(U1，F1)，R2(U2，F2)具有无损连接性的充分必要条件是：(U1U2)(U1-U2F+).或U1U2U2-U1F+.3.判断分解保持函数依赖的方法设U，F的分解=R1U1，F1，R1U2，F2，RkUK，FK，若F+=(Fi)+，则称分解保持函数依赖。,47,【例-5】关系模式R=CITY，ST，ZIP，其中CITY为城市，ST为街道，ZIP为邮政编码，F=(CITY，ST)ZIP，ZIPCITY。如果将R分解成R1和R2，R1=ST，ZIP，R2=CITY，ZIP，检查分解是否具有无损连接和保持函数依赖。解：1)检查无损连接性。求得：R1R2=ZIP；R2-R1=CITY.(ZIPCITY)F+.分解具有无损连接性2)检查分解是否保持函数依赖求得：R1(F)=；R2(F)=ZIPCITY.R1(F)R2(F)=ZIPCITYF+.该分解不保持函数依赖。,48,3.4.3关系模式的分解方法,1)对R（U，F）中的F进行极小化处理。处理后的函数依赖集仍用F表示。2)找出不再在F中出现的属性（极小化后），这样的属性构成一个关系模式，并把这些属性从U中去掉。3)如果F中有一个函数依赖涉及R的全部属性，则R不能再分解。4)如果F中含有XA，则分解应包含模式XA，如果XA1，XA2，XAn均属于F，则分解应包含模式XA1A2An。【例4-6】设关系模式RU，F，U=C，T，H，R，S，G，X，Y，Z，F=CT，CSG，HRC，HSR，THR，CX，将R分解为3NF，且保持函数依赖。解：设该函数依赖集已经是最小化的，则分解为：=YZ，CTX，CSG，HRC，HSR，THR.,一、将关系模式转化为3NF的保持函数依赖的分解,49,2.将关系转化为3NF、且既具有无损连接性又能保持函数依赖的分解,分解算法为：1)设X是R（U，F）的码，RU，F先进行保持函数依赖的分解，结果为=R1（U1，F1），R2U2，F2，RkUk，Fk，令=R*（X，Fx）。2)若有某个Ui，XUi，将R*X，Fx从中去掉，就是所求的分解。【例3-7】有关系模式RU，F，U=C，T，H，R，S，G，F=CT，CSG，HRC，HSR，THR，将R分解为3NF，且既具有无损连接性又能保持函数依赖。解：求得关系模式R的码为HS，它的一个保持函数依赖的3NF为：=CT，CSG，HRC，HSR，THR.HSHSR=CT，CSG，HRC，HSR，THR为满足要求的分解。,50,本章结束谢谢,