第5章数据库规范化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数 据 库 基 础,规 范 化,汤 娜,一、概述,二、规范化,三、反规范化,关系模式,Student,中存在的问题,U,Sno,Sdept,Mname,Cname, Grade,数据冗余太大,浪费大量的存储空间,例：每一个系主任的姓名重复出现,更新异常（,Update Anomalies,）,数据冗余,，,更新数据时，维护数据完整性代价大。,例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组,概述, 插入异常（,Insertion Anomalies,）,该插的数据插不进去,例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。, 删除异常（,Deletion Anomalies,）,不该删除的数据不得不删,例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,概述,结论：,Student,关系模式不是一个好的模式。,“好”的模式：,不会发生插入异常、删除异常、更新异常，,数据冗余应尽可能少。,原因：,由存在于模式中的,某些数据依赖,引起的,解决方法：,通过,分解,关系模式来消除其中不合适,的数据依赖。,概述,一、函数依赖,二、平凡函数依赖与非平凡函数依赖,三、完全函数依赖与部分函数依赖,四、传递函数依赖,概述,主属性：候选键中的任意一个属性元素称为主属性,非主属性：不是候选键中的属性,定义,1,设,R,（,U,）,是属性集,U,上的关系模式，,X,、,Y,是,U,的一个子集。,r,是,R,（,U,）,中任意给定的一个关系。若对于,r,中任意两个元组,s,和,t,，当,sX = tX,时，就有,sY = tY,，,则称属性子集,X,函数决定属性子集,Y,或者称,Y,函数依赖,于,X,（,Functional Dependence,），,记其为,XY,。,否则就称,X,不函数决定,Y,或者称,Y,不函数依赖于,X,。,一、函数依赖,A,B A,B A,B,B,A,B,A,B,A,函数依赖,说明：,1.,函数依赖不是指关系模式,R,的某个或某些关系实例满足的约束条件，而是指,R,的,所有关系实例,均要满足的约束条件。,2.,函数依赖是,语义范畴,的概念。只能根据数据的语义来确定函数依赖。,例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立,3.,数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。,二、平凡函数依赖与非平凡函数依赖,在关系模式,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,) ,Cno,平凡函数依赖与非平凡函数依赖（续）,于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖,。,三、完全函数依赖与部分函数依赖,定义,2,在关系模式,R(U),中，如果,XY,，,并且对于,X,的任何一个真子集,X,，,都有,X Y,则称,Y,完全函数依赖于,X,，,记作,X,Y,。,若,XY,，但,Y,不完全函数依赖于,X,，,则称,Y,部分函数依赖,于,X,，,记作,X,P,Y,。,完全函数依赖与部分函数依赖（续）,例,:,在关系,SC(Sno,Cno, Grade),中，,由于：,Sno,Grade,，,Cno, Grade,，,因此：,(,Sno,Cno,),Grade,四、传递函数依赖,定义,3,在关系模式,R(U),中，如果,XY,，,YZ,，且,Y,X,，,YX,，,则称,Z,传递函数依赖,于,X,。,注,:,如果,YX,， 即,XY,，则,Z,直接依赖,于,X,。,例,:,在关系,Std(Sno,Sdept,Mname,),中，有：,Sno,Sdept,，,Sdept,Mname,Mname,传递函数依赖于,Sno,规范化,规范化理论,正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,范式,范式是符合某一种级别的关系模式的集合。,关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。,范式的种类：,第一范式,(1NF),第二范式,(2NF),第三范式,(3NF),BC,范式,(BCNF),第四范式,(4NF),第五范式,(5NF),范式,各种范式之间存在联系：,某一关系模式,R,为第,n,范式，可简记为,RnNF,。,范式,1NF,的定义,如果一个关系模式,R,的所有属性都是,不可分的基本数据项,，则,R1NF,。,第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。,但是满足第一范式的关系模式并不一定是一个好的关系模式。,什么是一个好的模式,设关系模式,R,1NF,，,如果对于,R,的,每个函数依赖,XY,，若,Y,不属于,X,，则,X,必含有候选码，那么这个关系模式就是一个好的模式（,BCNF,）。,要知道的,7,个公式,Inclusion rule,(,包含律）,: if Y,X, then X - Y,（,平凡依赖,）,Transitivity rule,（,传递率）,: if X - Y and Y - Z, then X - Z,Augmentation rule,（,增广率）,: if X - Y, then X Z - Y Z,Union Rule,（,合并）,:,If X,Y and X,Z then X,Y Z,Decomposition Rule,（,分解）,:,If X,Y Z then X,Y and X,Z,Pseudotransitivity,Rule,（,伪传递）,:,If X,Y and W Y,Z then X W,Z,set,Accumulation Rule:,If X,Y Z and Z,B then X,Y Z B,表中那些属性可以做候选键？,Def,属性集的闭包,Given a set X of attributes in a table T and a set F of,FDs,on T, we define the CLOSURE of the set X (under F), denoted by X+, as the largest set of attributes Y such that X - Y is in F+.,Algorithm,如何求闭包的算法,如果某个属性集的闭包为表中的全体属性，则此属性集可以为候选键,I = 0; X0 = X; /* integer I,attr,. set X0 */,REPEAT /* loop to find larger XI */,I = I + 1; /* new I */,XI = XI-1; /* initialize new XI */,FOR ALL Z,W in F /* loop on all,FDs,Z,W in F */,IF Z,XI /* if Z contained in XI */,THEN XI = XI,W; /* add attributes in W to XI */,END FOR /* end loop on,FDs,*/,UNTIL XI = XI-1; /* loop till no new attributes */,RETURN X,+,= XI; /* return closure of X */,t,If X,Y Z and Z,B then X,Y Z B,例子：,B,CD AD,E B,A,B,的闭包：,b,cd,a e,AD,的闭包,ade,例：描述学校的数据库：,学生的学号（,Sno,）、,所在系（,Sdept,）,系主任姓名（,Mname,）、,课程名（,Cname,）,成绩（,Grade,）,单一,的关系模式 ：,Student ,U,Sno,Sdept,Mname,Cname, Grade,判断是否是一个好模式的例子（,1,）,学校数据库的语义：, 一个系有若干学生， 一个学生只属于一个系；, 一个系只有一名主任；, 一个学生可以选修多门课程， 每门课程有若干学生选修；, 每个学生所学的每门课程都有一个成绩。,属性组,U,上的一组函数依赖,F,：,F,Sno,Sdept,Sdept,Mname,(,Sno,Cname,) Grade,判断是否是一个好模式的例子（,1,）,判断是否是一个好模式的例子（,1,）,Student ,U,Sno,Sdept,Mname,Cname, Grade,属性组,U,上的一组函数依赖,F,：,F,Sno,Sdept,Sdept,Mname,(,Sno,Cname,) Grade,不是好模式,判断是否是一个好模式的例子（,2,）,例：在关系模式,STJ,（,S,，,T,，,J,）,中，,S,表示学生，,T,表示教师，,J,表示课程。,每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ：,(S,，,J)T,，,(S,，,T)J,，,TJ,不是好模式,如何分解？,1.,求出函数依赖集合的最小覆盖集,when we list a set of,FDs, we normally try to list a,MINIMAL set, so that a smaller set doesnt exist that will imply these. It will turn out that finding a minimal set of,FDs,is very important in finding the right relational design by Normalization.,2.,进行无损分解,TT1,，,T2,步骤一：求解最小覆盖,Step 1.,用,decomposition rule.,将所有的函数依赖的右边只有一个属性,x,yz,x y,和,x z,F: (1) A,B, (2) C,B, (3) D,A B C, (4) A C,D,H: (1) A,B, (2) C,B, (3) D,A, (4) D,B, (5) D,C, (6) A C,D,Step 2.,去除多余的函数依赖,Remove inessential,FDs,from the set H to get the set J. Determine inessential X,A if A is in X,+,under,FDs,without X - A.,(1) A,B, (2) C,B, (3) D,A,(4) D,B,(5) D,C, (6) A C,D,A+=AB C+=BC D+=ABCD AC+=ACDB,H = (1) A,B, (2) C,B, (3) D,A, (4) D,C, (5) A C,D (Renumber),Step 3.,去除左边多余的属性,Successively replace,FDs,in H with,FDs,that have a smaller number of,FDs,on the left-hand side so long as H+ remains the same,：,changing X,A to Y,A, then checking if Y+ under new FD set is unchanged.,如果第三步函数依赖有改变要回到第二步,(1) A,B, (2) C,B, (3) D,A, (4) D,C, (5),A C,D,A+=AB C+=BC D+=ABCD AC+=ACDB,Step 4.,Apply Union rules to bring things back together on the right for common sets of attributes on the left of,FDs, renamed M.,（,X,y and x,z then,x,yz,(1) A,B, (2) C,B, (3) D,A, (4) D,C, (5) A C,D,(1) A,B, (2) C,B, (3) D,A C, (4) A C,D,Other example,ABD,AC, C BE,AD BF,B E,1.,ABD,A,ABD, C,C B, C E,AD B, AD F,B E,(ABD+= ABDECF,ABC+=ABCE AD+=ADBFEC B+=BE),2.,ABD,A,是平凡依赖,C E,不关键,只留下了,ABD, C, C B, AD B, AD F,B E,3,AD C, C B,AD B,AD F,B E,重返第,2,步得到,AD C, C B,AD F,B E,4. AD CF, C B, B E,如果第二步先，做完第三步如果有改变，则要重新作第二步,注意第二步骤和第三步可以调换次序。,如何分解,什么是无损分解？,使得分解后的表进行连接运算后等于原来的表,例,1,例,2,算法,假设表,T,具有函数依赖集合,F ,如果要将表,T,误算分解为,T1, T2,，,则要满足以下两个条件：,(1),Head(T) =Head(T1),Head(T2),(2),在函数依赖集合,F,包含了以下的函数依赖：,Head(T1),Head(T2) - Head(T1), or Head(T1),Head(T2) - Head(T2),假设给定一个表，以及函数依赖,F,，,算法,产生,T,的一个符合,3,NF,且保持,F,中函数依赖的无损分解。,例子,已知表,T,，,head(T)=ABCDEF,函数依赖集包括,AB,C,，,A,D,，,B,E,分解结果：,T1,（,ABF,）,T2,（,ABC,）,T3,（,AD,）,T4,（,BE,）,Replace F with minimal cover of F,S=,FOR ALL X,Y IN F,IF FOR ALL ZS, X YZ,THEN S=S HERDING(X Y),END FOR,如果没有任何表包括,X,Y,则在,s,集合中添加一个新的表头,(,xy,),IF FOR ALL CANDIDATE KEYS K FOR T,FOR ALL Z S,K Z,THEN CHOOSE A CANDIDATE KEY K AND,SET S=S HERDING(K),如果,T,表中的候选键没有在任何表中，则在,s,集合中添加一个新的表头,(,候选键,),例一：,r=(SNO,CNO,GRADE,SDEPT,Mname,),F,Sno,Sdept,Sdept,Mname, (,Sno,Cno,) Grade,SC(,Sno,Cno, Grade),SD,（,Sno,，,Sdept,）,DL,（,Sdept,，,Mname,）,例二：,(S,，,J)T,，,(S,，,T)J,，,TJ S,表示学生，,T,表示教师，,J,表示课程,例二：,(,S,，,J)T,，,(S,，,T)J,，,TJ,BCNF,具有函数依赖的数据库设计目标：,BCNF,无损连接,(,数据等价,),保持依赖（语义等价）,有些情况很难达到所有的三个目标，通常舍弃目标,3,而选择目标,1,和,2,BCNF,T,表如何分解，首先将非码依赖,xY,分解出去,将剩余的属性,+,x,形成另一个表模式,例子：,（,S,，,J)T,，,(S,，,T)J,，,TJ,（,TJ,）,和（,S,，,T,）,如何保留函数依赖？,定义一个物化视图，将表连接起来，对于没有保留的依赖,xY,，,在视图上定义,unique,（,x,）,例如要定义一个物化视图（,s,，,t,，,j,）， （,S,，,J)T,，,(S,，,T)J,由于没有保留，则要在,sj,和,st,上定义唯一性,规范化的其他例子（,1,）,1,假设一个医生可以在几家医院工作并从每家医院领取工资。关系（,doctor,hospital,salary,）,规范吗？规范,2,如果在上例的关系中加入一个,address,字段，每个医生只有一个地址，但一个地址对应了几个医生，请问关系规范吗？不规范,3,在例,2,的基础上，禁止医生同时在多家医院工作，其他不变。关系（,doctor,hospital,salary,，,address,）,规范吗？规范,规范化的其他例子（,2,）,在例,3,假设的基础上，加入医院的,hospital-address,信息，关系（,doctor,hospital, hospital-address,，,salary,，,address,）,规范吗？不规范,规范化总结,关系数据库的规范化理论是数据库逻辑设计的工具。,规范化程度可以有多个不同的级别,一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。,(1,NF,表示可以入库,),规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题,规范化总结（续）,一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫,关系模式的规范化,所谓规范化实质上是概念的单一化，采用“一事一地”的模式设计原则,让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去,采用,case,工具用,e-r,图确定实体和关系的方法就不容易出现非规范化。 例子,医生,doctor_ID,name,specialty,医院,hospital_ID,name,address,Works-in,Doctor（doctor_ID，name，specialty， hospital_ID ，）,hospital （hospital_ID，name，address）,规范化总结（续）,不能说规范化程度越高的关系模式就越好,当一个应用的查询中经常涉及到两个或多个关系模式的属性时，系统必须经常地进行联接运算，而联系运算的代价是相当高的，可以说关系模型低效的主要原因就是做联接运算引起的，因此在这种情况下，第二范式甚至第一范式也许是最好的。,规范化总结（续）,在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式,上面的规范化步骤可以在其中任何一步终止,Normal Forms,Boyce-,Codd,Normal Form, or,BCNF,.,A table T in a database schema with FD set F is in BCNF,iff, for any FD X - A in F+ that lies in T (all attributes of X and A in T), A is a single attribute not in X, then X must be a,superkey,for T.,In another words,Every attribute in T is determined by a key (definition), the whole key (no subset of it) and nothing but the key,if the BCNF property fails,then two case are possible,x,是,key,的子集,x,是非,key,的属性集,Prime Attribute,of a table T is any attribute that is part of a key for that table (not necessarily a primary key).,Third Normal Form (3NF).,A table T in a database schema with FD set F is in 3NF,iff, for any FD X - A implied by F that lies in T, if A is a single non-prime attribute not in X, then X must be a,superkey,for T.,（,A,是非主属性，,X,一定是超键）,Second Normal Form (2NF).,A table T with FD set F is in 2NF,iff,: for any X - A implied by F that lies in T, where A is a single non-prime attribute not in X, X is not,properly,contained in any key of T.,（,X,不是任何,key,的子集）,有基于非码的函数依赖,xy,是,能否找到,y,是非主属性的依赖,有,X,是码的子集,1NF,X,不是码的子集,2NF,否,3NF,否,BCNF,采用规范化的方法设计表，然后判断与,E-R,图,设计方法的不同。,逆规范化,对于一个具体应用来说，到底规范化进行到什么程度，需要权衡响应时间和潜在问题两者的利弊才能决定。一般说来，,BCNF,范式就足够了。,出于性能考虑，允许冗余数据的存在,非,BCNF,的关系模式虽然从理论上分析会存在不同程度的更新异常，但如果在实际应用中对此关系模式只是查询，并不执行更新操作，则就不会产生实际影响。,逆规范化的利弊,数据冗余的代价,空间代价,管理代价（主要是增删改异常）,好处：减少查询所要连接表的个数，减少了,I/O,和,CPU,时间,加速了查询,逆规范化,逆规范化通常包括的例子,预计算和派生数据的存储，如求和、平均值、统计例如存款余额,超市的各类商品销售总额等,主要用于频繁的报表统计或重复的计算,避免多表连接，复制某些数据列到一些表,对于经常更新的关系，这种逆规范化会降低性能。但在低更新率的情况下，逆规范化可能会提高性能。,一般采用逆规范化设计档案数据的模式，而使用规范化设计在线数据的模式,如数据仓库,原则：查询带来的收益应该大于两次查询之间进行维护所需要的额外时间,