1、数 据 库 基 础规 范 化汤 娜中山大学计算机科学系v一、概述v二、规范化v三、反规范化关系模式Student中存在的问题U Sno,Sdept,Mname,Cname,Grade 数据冗余太大浪费大量的存储空间 例：每一个系主任的姓名重复出现 更新异常（Update Anomalies）数据冗余，更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组概述 插入异常（Insertion Anomalies）该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。删除异常（Deletion Anomalies）不
2、该删除的数据不得不删例，如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。概述结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适 的数据依赖。概述一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖概述主属性：候选键中的任意一个属性元素称为主属性非主属性：不是候选键中的属性定义1 设R（U）是属性集U上的关系模式，X、Y是U的一个子集。r是R（U）中任意给定的一个关系
3、。若对于r中任意两个元组s和t，当sX=tX时，就有sY=tY，则称属性子集X函数决定属性子集Y或者称Y函数依赖于X（Functional Dependence），记其为XY。否则就称X不函数决定Y或者称Y不函数依赖于X。一、函数依赖 T1 T2 T3Row#ABABAB1X1Y1X1Y1X1Y12X2Y2X2Y4X2Y43X3Y1X1Y1X1Y14X4Y1X3Y2X3Y25X5Y2X2Y4X2Y46X6Y2X4Y3X4Y4AB AB ABBA BA BA函数依赖说明：1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范
4、畴的概念。只能根据数据的语义来确定函数依赖。例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立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平凡函
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，则
6、称Z传递函数依赖于X。注:如果YX，即XY，则Z直接依赖于X。例:在关系Std(Sno,Sdept,Mname)中，有：Sno Sdept，Sdept Mname Mname传递函数依赖于Sno规范化规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。范式v范式是符合某一种级别的关系模式的集合。v关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。v范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)范式v各种范式之间存在联系：v某一关
7、系模式R为第n范式，可简记为RnNF。NF5NF4BCNFNF3NF2NF1范式v1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。v第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。v但是满足第一范式的关系模式并不一定是一个好的关系模式。什么是一个好的模式v设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么这个关系模式就是一个好的模式（BCNF）。要知道的7个公式vInclusion rule(包含律）:if Y X,then X-Y（平凡依赖）vTransitivity rule（传递率）:if
8、X-Y and Y-Z,then X-ZvAugmentation rule（增广率）:if X-Y,then X Z-Y ZvUnion Rule（合并）（合并）:If X Y and X Z then X Y ZvDecomposition Rule（分解）（分解）:If X Y Z then X Y and X ZvPseudotransitivity Rule（伪传递）（伪传递）:If X Y and W Y Z then X W Zvset Accumulation Rule:If X Y Z and Z B then X Y Z B表中那些属性可以做候选键？vDef 属性集的闭包属
9、性集的闭包 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+.vAlgorithm 如何求闭包的算法如何求闭包的算法v如果某个属性集的闭包为表中的全体属性，则此属性集可以为候选键I=0;X0=X;/*integer I,attr.set X0*/REPEAT /*loop to find
10、 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
11、B then X Y Z Bv例子：BCD AD E B AvB的闭包：b cd a evAD的闭包 ade例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept）系主任姓名（Mname）、课程名（Cname）成绩（Grade）单一的关系模式：Student U Sno,Sdept,Mname,Cname,Grade 判断是否是一个好模式的例子（1）学校数据库的语义：一个系有若干学生，一个学生只属于一个系；一个系只有一名主任；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。属性组U上的一组函数依赖F：F Sno Sdept,Sdept Mname,
12、(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表示课程。v每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：(S，J)T，(S，T)J，TJv不是好模式不是好模式如何
13、分解？v1.求出函数依赖集合的最小覆盖集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.v2.进行无损分解TT1，T2步骤一：求解最小覆盖vStep 1.用
14、 decomposition rule.将所有的函数依赖的右边只有一个属性 xyz x y 和x zF:(1)A B,(2)C B,(3)D A B C,(4)A C DH:(1)A B,(2)C B,(3)D A,(4)D B,(5)D C,(6)A C DvStep 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
15、)A C DvA+=AB C+=BC D+=ABCD AC+=ACDBvH=(1)A B,(2)C B,(3)D A,(4)D C,(5)A C D(Renumber)vStep 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.如果第三
16、步函数依赖有改变要回到第二步(1)A B,(2)C B,(3)D A,(4)D C,(5)A C DvA+=AB C+=BC D+=ABCD AC+=ACDBvStep 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 yzv(1)A B,(2)C B,(3)D A,(4)D C,(5)A C Dv(1)A B,(2)C B,(3)D A C,(4)A C DOt
17、her examplevABD AC,C BE,AD BF,B E1.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 E3AD C,C B,AD B,AD F,B E重返第2步得到AD C,C B,AD F,B E4.AD CF,C B,B Ev如果第二步先，做完第三步如果有改变，则要重新作第二步v注意第二步骤和第三步可以调换次序。如何分解v什么是无损分解？使得分解后的表进行连接运算后等于原来的表v例1v例2
18、v算法假设表 T 具有函数依赖集合 F,如果要将表T无损分解为 T1,T2，则要满足以下两个条件：v(1)Head(T)=Head(T1)Head(T2)v(2)在函数依赖集合 F包含了以下的函数依赖：Head(T1)Head(T2)-Head(T1),or Head(T1)Head(T2)-Head(T2)Table ABCABCa1100c1a2200c2a3300c3a4200c4Table ABCABCa1100c1a2200c2a3300c3Table ABABa1100a2200a3300a4200Table BCBC100c1200c2300c3200c4Table ABABa1
19、100a2200a3300Table BCBC100c1200c2300c3AB JOIN BCABCa1100c1a2200c2a2200c4a3300c3a4200c2a4200c4ABCYABCa1100c1a2200c2a2200c4a3300c3a4200c4ABCZABCa1100c1a2200c2a3300c3a4200c2a4200c4v假设给定一个表，以及函数依赖F，算法产生T的一个符合3NF且保持F中函数依赖的无损分解。v例子已知表T，head(T)=ABCDEF,函数依赖集包括ABC，A D，B E分解结果：T1（ABF）T2（ABC）T3（AD）T4（BE）Replac
20、e F with minimal cover of FS=FOR ALL X Y IN F IF FOR ALL ZS,X YZTHEN S=S HERDING(X Y)END FOR 如果没有任何表包括X Y,则在s集合中添加一个新的表头(xy)IF FOR ALL CANDIDATE KEYS K FOR TFOR ALL Z S,K ZTHEN CHOOSE A CANDIDATE KEY K ANDSET S=S HERDING(K)如果T表中的候选键没有在任何表中，则在s集合中添加一个新的表头(候选键)例一：r=(SNO,CNO,GRADE,SDEPT,Mname)F Sno Sde
21、pt,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表示课程1NF2NF3NFBCNF消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除决定因素非码的非平凡函数依赖例二：(S，J)T，(S，T)J，TJBCNFv具有函数依赖的数据库设计目标：BCNF无损连接(数据等价)保持依赖（语义等价）v有些情况很难达到所有的三个目标，通常舍弃目标3而选择目标1和2BCNFvT表如何分解，首先将非码
22、依赖xY分解出去,将剩余的属性+x形成另一个表模式v例子：（S，J)T，(S，T)J，TJ（TJ）和（S，T）v如何保留函数依赖？定义一个物化视图，将表连接起来，对于没有保留的依赖xY，在视图上定义unique（x）v例如要定义一个物化视图（s，t，j），（S，J)T，(S，T)J由于没有保留，则要在sj和st上定义唯一性规范化的其他例子（1）v1假设一个医生可以在几家医院工作并从每家医院领取工资。关系（doctor,hospital,salary）规范吗？规范v2如果在上例的关系中加入一个address字段，每个医生只有一个地址，但一个地址对应了几个医生，请问关系规范吗？不规范v3在例2的基
23、础上，禁止医生同时在多家医院工作，其他不变。关系（doctor,hospital,salary，address）规范吗？规范规范化的其他例子（2）v在例3假设的基础上，加入医院的hospital-address信息，关系（doctor,hospital,hospital-address，salary，address）规范吗？不规范规范化总结v关系数据库的规范化理论是数据库逻辑设计的工具。v规范化程度可以有多个不同的级别一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。(1NF表示可以入库)规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除
24、异常、修改复杂、数据冗余等问题规范化总结（续）v一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化所谓规范化实质上是概念的单一化，采用“一事一地”的模式设计原则让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去采用case工具用e-r图确定实体和关系的方法就不容易出现非规范化。例子 医生doctor_IDnamespecialty医院hospital_IDnameaddressWorks-inDoctor（doctor_ID，name，specialty，hospital_ID，）hospital（h
25、ospital_ID，name，address）规范化总结（续）v不能说规范化程度越高的关系模式就越好v当一个应用的查询中经常涉及到两个或多个关系模式的属性时，系统必须经常地进行联接运算，而联系运算的代价是相当高的，可以说关系模型低效的主要原因就是做联接运算引起的，因此在这种情况下，第二范式甚至第一范式也许是最好的。规范化总结（续）v在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式v上面的规范化步骤可以在其中任何一步终止Normal FormsvBoyce-Codd Normal Form,or BCNF.A table T i
26、n 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
27、the keyif the BCNF property fails,then two case are possiblevx是key的子集vx是非key的属性集vPrime Attribute of a table T is any attribute that is part of a key for that table(not necessarily a primary key).vThird Normal Form(3NF).A table T in a database schema with FD set F is in 3NF iff,for any FD X-A implied
28、 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一定是超键）vSecond 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
29、 key of T.（X不是任何key的子集）有基于非码的函数依赖xy是能否找到y是非主属性的依赖有X是码的子集1NFX不是码的子集2NF否3NF否BCNF例子v（1）R(A,B,C,D),F=(A,D)-C,C-Bv（2）R(A,B,C）AB-C C-B v（3）R(A,B,C,(A,C)-B,(A,B)-C,B-C)v答案（1）码AD，2NF（2）码：AB，AC，3NF（3）码：AB，AC，3NFv采用规范化的方法设计表，然后判断与E-R图设计方法的不同。Gates has_seatSeatsFlightsPassengersseat_assignseatnoflightnoticketn
30、ogatenodepart_timedtimeddate(1,N)(1,1)(0,1)(1,1)marshallstravels_on(1,1)(0,N)(1,N)(1,1)逆（反）规范化v反规范化的必要性对于一个具体应用来说，到底规范化进行到什么程度，需要权衡响应时间和潜在问题两者的利弊才能决定。一般说来，BCNF范式就足够了。“分离”越深，产生的关系越多，结构越复杂。关系越多，连接操作越频繁，而连接操作是最费时间的，在数据库设计中特别对以查询为主的数据库设计来说，频繁的连接会严重影响查询速度。反规范化的好处是降低连接操作的需求、降低外码和索引数目，减少表的个数，从而提高查询速度，这对于性能
31、要求相对较高的数据库系统来说，能有效地改善系统的性能，但相应的问题是可能影响数据的完整性，加快查询速度的同时降低修改速度逆规范化的利弊总结v数据冗余的代价空间代价管理代价（主要是增删改异常）,维护数据的完整性v好处：减少查询所要连接表的个数，减少了I/O和CPU时间,加速了查询v做反规范时，一定要权衡利弊，仔细分析应用的数据存取需求和实际的性能特点。逆（反）规范化v优化策略数据应当按访问和修改的频率和重要性进行组织v原则：查询带来的收益应该大于两次查询之间进行维护所需要的额外时间v常用的反规范技术有增加冗余列、增加派生列、重新连接表和分割表逆规范化v增加冗余列增加冗余列是指在多个表中具有相同的
32、列，它常用来在查询时避免连接操作 例子：填写发票的明细项。报价单通常用于挑选客户订购的商品。我们可以只存储报价单 ID，而 ID 指向包含产品说明、价格和其他详细信息的报价单。但是，产品说明和价格会随着时间而改变。如果不将数据从报价单复制到明细表中，将来则无法准确地重新打印原始发票。如果您尚未收到付款，问题将非常严重。v增加派生列预计算和派生数据的存储，如求和、平均值、统计例如银行存款余额,超市的各类商品销售总额等主要用于频繁的报表统计或重复的计算v重新连接表避免多表连接，v对于经常更新的关系，这种逆规范化会降低性能。但在低更新率的情况下，逆规范化可能会提高性能。一般采用逆规范化设计档案数据的
33、模式，而使用规范化设计在线数据的模式如数据仓库v分割表垂直分割：v把主码和一些列放到一个表，然后把主码和另外的列放到另一个表中。如果一个表中某些列常用，而另外一些列不常用，则可以采用垂直分割，另外垂直分割可以使得数据行变小，一个数据页就能存放更多的数据，在查询时就会减少I/O次数。v其缺点是需要管理冗余列，查询所有数据需要join操作。逆（反）规范化水平分割：根据一列或多列数据的值把数据行放到两个独立的表中。v表很大，分割后可以降低在查询时需要读的数据和索引的页数，同时也降低了索引的层数，提高查询速度。v满足“80/20原则”的应用80/20原则：一个大关系中，经常被使用的数据只是关系的一部分
34、，约20%把经常使用的数据分解出来，形成一个子关系，可以减少查询的数据量。例如法规表law就可以分成两个表activelaw和inactivelaw。activealaw表中的内容是正生效的法规，是经常使用的，而inactivelaw表则使已经作废的法规，不常被查询。v并发事务经常存取不相交的数据如果关系R上具有n个事务，而且多数事务存取的数据不相交，则R可分解为少于或等于n个子关系，使每个事务存取的数据对应一个关系。v水平分割会给应用增加复杂度，它通常在查询时需要多个表名，查询所有数据需要union操作建立统一视图。在许多数据库应用中，这种复杂性会超过它带来的优点，因为只要索引关键字不大，则在索引用于查询时，表中增加两到三倍数据量，查询时也就增加读一个索引层的磁盘次数。
