第5章数据库规范化.ppt

1、数 据 库 基 础规 范 化,汤 娜,一、概述 二、规范化 三、反规范化,关系模式Student中存在的问题 U Sno, Sdept, Mname, Cname, Grade 数据冗余太大 浪费大量的存储空间 例：每一个系主任的姓名重复出现 更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组,概述, 插入异常（Insertion Anomalies） 该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。 删除异常（Deletion Anomal

2、ies） 不该删除的数据不得不删 例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,概述,结论： Student关系模式不是一个好的模式。 “好”的模式： 不会发生插入异常、删除异常、更新异常， 数据冗余应尽可能少。 原因：由存在于模式中的某些数据依赖引起的 解决方法：通过分解关系模式来消除其中不合适 的数据依赖。,概述,一、函数依赖 二、平凡函数依赖与非平凡函数依赖 三、完全函数依赖与部分函数依赖 四、传递函数依赖,概述,主属性：候选键中的任意一个属性元素称为主属性 非主属性：不是候选键中的属性 定义1 设R（U）是属性集U上的关系模式，X、

3、Y是U的一个子集。r是R（U）中任意给定的一个关系。若对于r中任意两个元组s和t，当sX = tX时，就有sY = tY，则称属性子集X函数决定属性子集Y或者称Y函数依赖于X（Functional Dependence），记其为XY。否则就称X不函数决定Y或者称Y不函数依赖于X。,一、函数依赖,AB AB AB BA BA BA,函数依赖说明：,1. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 2. 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立 3. 数据库

4、设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。,二、平凡函数依赖与非平凡函数依赖,在关系模式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,平凡函数依赖与非平凡函数依赖（续）,于任一关系模式，平凡函数依赖都是必然成立的，它

5、不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。,三、完全函数依赖与部分函数依赖,定义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， 即

6、XY，则Z直接依赖于X。 例: 在关系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname Mname传递函数依赖于Sno,规范化,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,范式,范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。 范式的种类： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),范式,各种范式之间存在联系： 某一关系模式R

7、为第n范式，可简记为RnNF。,范式,1NF的定义 如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。 但是满足第一范式的关系模式并不一定是一个好的关系模式。,什么是一个好的模式,设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么这个关系模式就是一个好的模式（BCNF）。,要知道的7个公式,Inclusion rule(包含律）: if Y X, then X - Y（平凡依赖） Transitivity rule（传递率）: if X - Y and Y -

8、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 s

9、et 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 lar

10、ger 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; /* r

11、eturn closure of X */ t,If X Y Z and Z B then X Y Z B,例子：BCD AD E B A B的闭包：b cd a e AD的闭包 ade,例：描述学校的数据库： 学生的学号（Sno）、所在系（Sdept） 系主任姓名（Mname）、课程名（Cname） 成绩（Grade） 单一的关系模式 ： Student U Sno, Sdept, Mname, Cname, Grade ,判断是否是一个好模式的例子（1）,学校数据库的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名主任； 一个学生可以选修多门课程， 每门课程有若干学生选修

12、； 每个学生所学的每门课程都有一个成绩。 属性组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表示课程。 每一教师只教一门课。每门课由若干教师教，某

13、一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ： (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

14、right relational design by Normalization. 2.进行无损分解TT1，T2,步骤一：求解最小覆盖,Step 1. 用 decomposition rule.将所有的函数依赖的右边只有一个属性 xyz 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

15、. 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 FD

16、s 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

17、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不关键 只

18、留下了ABD C, C B, AD B, AD F,B E 3AD 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(T

19、1) Head(T2) - Head(T1), or Head(T1) Head(T2) - Head(T2),假设给定一个表，以及函数依赖F，算法产生T的一个符合3NF且保持F中函数依赖的无损分解。 例子 已知表T，head(T)=ABCDEF,函数依赖集包括ABC，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

20、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，

21、(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由于没有保留，

22、则要在sj和st上定义唯一性,规范化的其他例子（1）,1假设一个医生可以在几家医院工作并从每家医院领取工资。关系（doctor,hospital,salary）规范吗？规范 2如果在上例的关系中加入一个address字段，每个医生只有一个地址，但一个地址对应了几个医生，请问关系规范吗？不规范 3在例2的基础上，禁止医生同时在多家医院工作，其他不变。关系（doctor,hospital,salary， address ）规范吗？规范,规范化的其他例子（2）,在例3假设的基础上，加入医院的hospital-address信息，关系（doctor,hospital, hospital-address

23、 ，salary， address ）规范吗？不规范,规范化总结,关系数据库的规范化理论是数据库逻辑设计的工具。 规范化程度可以有多个不同的级别 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。(1NF表示可以入库) 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题,规范化总结（续）,一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化 所谓规范化实质上是概念的单一化，采用“一事一地”的模式设计原则 让一个关系描述一个概念、一个实体或者实体间的一种联

24、系。若多于一个概念就把它“分离”出去 采用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）,规范化总结（续）,不能说规范化程度越高的关系模式就越好 当一个应用的查询中经常涉及到两个或多个关系模式的属性时，系统必须经常地进行联接运算，而联系运算的代价是相当高的，可以说关系模型低效的

25、主要原因就是做联接运算引起的，因此在这种情况下，第二范式甚至第一范式也许是最好的。,规范化总结（续）,在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式 上面的规范化步骤可以在其中任何一步终止,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

26、 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