数据库原理与应用教程ppt课件

4.3关系模式的分解*,4.3.1模式分解问题,定义4.11设有关系模式R(U)，属性集为U，R1、Rk都是U的子集，并且有R1R2RkU。关系模式R1、Rk的集合用表示，=R1，Rk。用代替R的过程称为关系模式的分解。这里称为R的一个分解，也称为数据库模式。,1,泛关系模式R,r泛关系,数据库模式=R1，Rk,=r1，rk数据库实例(数据库),这里就有两个问题：和r是否等价?用“无损分解”表示。F1,Fk与F是否等价?用“保持依赖”表示。,计算机中的数据并不是存储在泛关系r中，而是存储在数据库中。,R上有函数依赖集F，每一个Ri上有一个函数依赖集Fi，F1，Fk,2,4.3.2无损连接分解,定义4.12：设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式=R1，Rk。如果对R中满足F的每一个关系r，都有r=R1（r）R2（r）Rk（r）那么称分解相对于F是“无损连接分解”（losslessjoindecomposition），简称为“无损分解”，否则称为“损失分解”（lossydecomposition）。,3,例4.10（1）未丢失信息的分解：r1r2=r,（2）丢失信息的分解：r1r2r,多出来的元组称为寄生元组（额外元组）丢失的元组称为悬挂元组。,4,在泛关系模式R分解成数据库模式=R1，Rk时，泛关系r在的每一模式Ri（1in）上投影后再连接起来，比原来r中多出来的元组，称为“寄生元组”（SpuriousTuple）。实际上，寄生元组表示着错误的信息。寄生元组也就是4.1.3节模式设计准则4中提到的额外元组(在上节NO15中）。无损的损指的是信息丢失而不是元组丢失.如果一个分解不具有无损的性质，那么泛关系在投影连接后就可能产生寄生元组。寄生元组表示着错误的信息,5,r的投影连接表达式R1（r）Rk（r）用符号m（r）表示，即m（r）=Ri（r）。设=R1，Rk是关系模式R的一个分解，r是R的任一关系，ri=Ri（r）（1ik），那么有下列性质：rm(r)；若s=m(r)，则Ri(s)=ri；m(m(r)=m(r)，这个性质称为幂等性（idempotent）。r=m(r)时就是无损连接分解,6,4.3.3无损分解的测试算法（算法4.3）,构造一张k行n列的表格，每列对应一个属性Aj，每行对应一个模式Ri。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下：对函数依赖XY,找X相等的行，改Y的分量值：如果Y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其中一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为追踪chase过程）若修改的最后一张表格中有一行是全a，即a1a2an，那么称相对于F是无损分解，否则称损失分解。,7,例4.11设关系模式R(ABCD)，R分解成=AB,BC,CD。如果R上成立的函数依赖集F1=BA，CD，那么相对于F1是否无损分解？,(无损分解),8,续例4.11设关系模式R(ABCD)，R分解成=AB,BC,CD。如果R上成立的函数依赖集F1=AB，CD，那么相对于F1是否无损分解？,(损失分解),再看例4-12（P153),9,ABCDE,例：设R=(ABCDE)分解成AD,AB,BE,CDE,AE函数依赖F=AC，BC，CD，DEC，CEA判断是否无损连接分解。解：按条件给出初始表,a1b12b13a4b15,AD,a1a2b23b24b25,b31a2b33b34a5,b41b42a3a4a5,a1b52b53b54a5,AB,BE,CDE,AE,10,ABCDE,a1b12b13a4b15,AD,a1a2b13a4b25,a1a2a3a4a5,a1b42a3a4a5,a1b52a3a4a5,AB,BE,CDE,AE,通过追踪过程（CHASE）最终得表：,由于第3行全为a,所以该分解是无损连接分解。,11,定理4.6设=R1，R2是关系模式R的一个分解，F是R上成立的FD集，那么分解相对于F是无损分解的充分必要条件是（R1R2）（R1R2）或（R1R2）（R2R1）。（可用CHASE(追踪)算法证明）定理4.7如果FDXY在模式R上成立，且XY=，那么R分解成=RY，XY是无损分解。,12,4.3.4保持函数依赖的分解,定义4.13：设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用Z（F）表示，定义为Z(F)=XY|XYF+，且XYZ设=R1，Rk是R的一个分解，F是R上的FD集如果有(Ri(F)+=F+，那么称分解保持函数依赖集F的分解。根据定义，测试一个分解是否保持FD,比较可行的方法是逐步验证F中的每个FD是否被(Ri(F)+=F+蕴涵,13,两个数据库模式的等价问题，这种等价包括数据等价和依赖等价两个方面。数据等价是指两个数据库实例应表示同样的信息内容，用“无损分解”衡量。如果是无损分解，那么对泛关系反复的投影和连接都不会丢失信息。依赖等价是指两个数据库模式应有相同的依赖集闭包。在依赖集闭包相等情况下，数据的语义是不会出差错的。违反数据等价或依赖等价的分解不是一个好的模式设计。一个无损连接分解不一定是保持函数依赖的一个保持函数依赖的分解也不一定是无损连接的没有必然联系（见下例）,14,例：设关系模式R(ABC)，=AB,AC是R的一个分解。试分析分别在各种FD的情况下，是否具有无损分解和保持FD的分解特性。解：相对于F1=AB，分解是无损分解，且保持FD的分解。相对于F2=AC,BC，分解是无损分解，但不保持FD集(丢失了BC)。相对于F3=BA，分解是损失分解，但保持FD集的分解。相对于F4=CB,BA，分解是损失分解，且不保持FD集(丢失了CB)。,15,16,4.4关系模式的范式,关系模式的好与坏，用什么标准衡量？这个标准就是模式的范式（NormalForms，简记为NF）。范式的种类与数据依赖有着直接的联系。范式的概念由E.F.Codd于1971年提出。（发展过程见P155）1NF是关系模式的基础；在数据库设计中最常用的是3NF和BCNF。,17,各种范式之间的关系,18,4.4.1第一范式(1NF),定义4.14:如果关系模式R所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，简称1NF，记作R1NF。1NF是关系模式应具备的最起码的条件。第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。例如关系模式SCD属于1NF，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖。克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行转换。,19,4.4.2第二范式(2NF),定义4.15:如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式（2NF）的模式。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。（即.没有对候选键的部分函数依赖）从1NF中消除非主属性对主键（主码）的部分函数依赖得到2NF.分解时遵循“一事一地”的基本原则：一个关系只描述一个实体或联系。,20,违反2NF的局部依赖的情况示意图：,21,本章开始例：教学管理数据库（P137）SCD(SNo,SN,Age,Dept,MN,CNo,Score),主键：(SNO,CNO)，存在数据冗余、修改、删除、插入异常的弊病。原因之一是存在部分函数依赖。,22,如果把SCD分解成:(将部分函数依赖分离出来）SD(SNo,SN,Age,Dept,MN)C(SNo，CNo，SCORE)SD与C都是2NF模式。部分函数依赖消失，分数关系C不存在冗余、修改、删除、插入异常。但还是有系、系主任的冗余和操作异常。说明2NF不是理想的模式分解。,23,算法4.5分解成2NF模式集的算法设关系模式R(U)，主键是W，R上还存在FD：XZ，并且Z是非主属性，XW，那么WZ就是一个部分函数依赖。此时应把R分解成两个模式R1（XZ），主键是X；（将部分依赖分解出来）R2（Y），其中Y=U-Z，主键仍是W，外键是X(REFERENCES参照R1)。利用外键和主键的连接可以从R1和R2重新得到R。如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。,24,定义4.16：如果关系模式R是1NF，且每个非主属性都不传递函数依赖于R的候选键，那么称R属于第三范式（3NF）的模式。如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式。,4.4.3第三范式（3NF),25,例:在上边例中，SD(SNo,SN,Age,Dept,MN)主键SNO,无部分函数依赖，是2NF模式。SD中存在函数依赖SNODept和DeptMN，那么SNOMN就是一个传递依赖，SD不是3NF模式。此时也会出现冗余和异常操作。譬如一个系有500学生，那么系和系主任就会重复500次。还有操作异常。若将SD分解成S（SNo,SN,Age,Dept）和D（Dept,MN）已无传递函数依赖，S、D都是3NF模式，冗余和操作异常消失。,26,算法4.6分解成3NF模式集的算法设关系模式R（U），主键是W，R上还存在FDXZ。并且Z是非主属性，ZX，X不是候选键，这样WZ就是一个传递依赖。此时应把R分解成两个模式：R1（XZ），主键是X；（将传递依赖分解出来）R2（Y），其中Y=U-Z，主键仍是W，外键是X(REFERENCES参照R1)。利用外键和主键相匹配机制，R1和R2通过连接可以重新得到R。如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。,27,由定义可看出：局部依赖必定蕴涵传递依赖的存在定理4.8：如果R是3NF模式，那么R也是2NF模式。证明：只要证明模式中部分依赖的存在蕴涵着传递依赖即可。设A是R的一个非主属性，K是R的一个候选键，且KA是一个部分依赖。那么R中必存在某个KK，有KA成立。由于A是非主属性，因此AKK=。从KK，可知KK，但KK成立。因而从KK和KA可知KA是一个传递依赖。部分依赖和传递依赖是模式产生冗余和异常的两个重要原因。由于3NF模式中不存在非主属性对候选键的部分依赖和传递依赖，因此消除了很大一部分存储异常，具有较好的性能。,28,4.4.4BCNF(BoyceCoddNF),定义4.17：如果关系模式R1NF，且所有的函数依赖XY（YX），决定因素X都包含了R的一个候选键，则称R属于BC范式，记作RBCNF。(3NF不一定是BCNF)例4-19设有关系模式SNC（SNo，SN，CNo，Score）假设学生无重名，SNoSN。候选键：(SNo,CNo)，（SN，CNo）唯一非主属性Score不存在对键的部分函数依赖及传递函数依赖，所以是3NF但存在着主属性对键的部分函数依赖：（SNo，CNo）SN，（SN，CNo）SNo，所以SNC不是BCNF。,29,定理:如果R是BCNF模式，那么R也是3NF模式。证明：设R是BCNF，但不是3NF，那么R上必存在传递依赖XY，YA，这里X是R的键，AY，YX。显然Y不包含R的键，否则YX也成立。因此YA违反了BCNF的定义，与假设R是BCNF矛盾。,30,无损分解成BCNF模式集的算法（1）令=R。（2）如果中所有模式都是BCNF，则转（4）。（3）如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖XA且X不是S的候选键，且A不属于X，设S1=XA，S2=S-A，用分解S1，S2代替S，转（2）。（4）分解结束，输出。,这个算法是从泛关系模式R出发，去寻找一个满足条件的BCNF模式集，因此称为“分解算法”。这个算法能保证把R无损分解成，但不一定能保证能保持FD。,31,F=SNoSN，SNSNo，(SNo，CNo)Score，(SN，CNo)Score,前例：关系模式SNC（SNo，SN，CNo，Score）假设学生无重名，SNoSN。候选键：(SNo,CNo)，（SN，CNo）,（1）令=SNC(SNo，SN，CNo，Score)。（2）经过前面分析可知，中关系模式不属于BCNF。（3）考虑SNoSN，由于SNo不是候选键，且SN不属于SNo.用分解S1(SNo，SN)，S2(SNo，CNo，Score)代替SNC。（4）分解结果为：S1(SNo，SN)描述学生实体；S2(SNo，CNo，Score)描述学生与课程的联系。都属于BCNF.,32,（1）如果Fmin中有一函数依赖XA，且XA=R，则输出=R，转（4）。（2）如果R中某些属性与Fmin中所有依赖的左部和右部都无关，则将它们构成关系模式，从R中将它们分出去，单独构成一个模式。（3）对于Fmin中的每一个函数依赖XA，都单独构成一个关系子模式XA。若Fmin中有XA1，XA2，XAn，则可以用模式XA1A2An取代n个模式XA1，XA2，XAn。（4）停止分解，输出。看例4-16：（P159）,算法4.6把一个关系模式分解为3NF，使它具有保持函数依赖性。,33,算法4.7把一个关系模式分解为3NF，使它既具有无损连接性又具有保持函数依赖性。（1）根据算法4.6求出保持函数依赖的分解：=R1，R2，Rk。（2）判定是否具有无损连接性，若是，转（4）。（3）令=X=R1，R2，Rk，X，其中X是R的候选键。（4）输出。见例4-17（P160）,34,例：设关系模式R(ABCDE)，R的最小依赖集为AB，CD。从依赖集可知R的候选键为ACE。（L、N类计算）按算法4-6，根据最小依赖集，保持函数依赖的分解=AB,CD。按算法4-7，再加入由候选键组成的模式ACE。因此最后结果=AB,CD,ACE是一个3NF模式集且相对于该依赖集是无损分解且保持FD。,35,关系模式R相对于函数依赖集F分解成数据库模式R1，Rk，一般应具有三个特性：是BCNF模式集，或3NF模式集；无损分解，即对于R上任何满足F的泛关系应满足r=m(r)；保持函数依赖集F，即(Ri(F)F。数据库设计者在进行关系数据库设计时，应作权衡，尽可能使数据库模式保持最好的特性。一般尽可能设计成BCNF模式集。如果设计成BCNF模式集时达不到保持FD的特点，那么只能降低要求，设计成3NF模式集，以求达到保持FD和无损分解的特点。一个好的模式设计方法应符合三条原则：表达性、分离性和最小冗余性。,36,4.4.5多值依赖与第四范式,多值依赖的定义假设学校中一门课程可由多名教师讲授，教学中他们使用相同的一套参考书。,关系CTB,37,CTB转化成规范化的关系如下图所示：,数据冗余大,插入异常,删除异常,C与T间的联系被称为多值依赖多个T对应一个C一个确定的C值，与其所对应的一组T值与B值无关,38,例：设关系模式R（DN,TN,SN)分别代表系名，教师名，学生名教师与系有直接联系，但与学生无直接联系。学生与系有直接联系。教师与学生之间的联系是间接联系。将间接联系的属性放在一个关系里出问题。若系里有50个教师，500名学生，则关系中将出现25000条记录。一个系有多名教师（一对多），多名学生（一对多），教师与学生无直接联系。系与教师之间、系与学生之间的联系被称为多值依赖。,39,定义4.18设有关系模式R（U），U是属性全集，X、Y、Z是属性集U的子集，且Z=UXY，如果对于R的任一关系，对于X的一个确定值，存在Y的一组值与之对应，且Y的这组值仅仅决定于X的值而与Z值无关，此时称Y多值依赖于X，或X多值决定Y，记作XY。若XY且Z=UXY，则称XY是非平凡的多值依赖(MultivaluedDependenceMVD)，否则称为平凡的多值依赖。,40,多值依赖公理及其推论多值依赖公理增广律：如果XY，VWU，则WXVY。传递律：如果XY，YZ，则XZ-Y。补余律：如果XY，则XU-X-Y。函数依赖公理与多值依赖混合公理复制规则：从FD导出MVD，如果XY，则XY。接合规则：从MVD导出FD：如果XY，ZY，且存在WU有WY=，WZ，则XZ。多值依赖推论合并律：如果XY，XZ，则XYZ。伪传递律：如果XY，WYZ，则XW(Z-W-Y)。分解律：如果XY，XZ，则X（YZ），X(Y-Z)，X(Z-Y)。混合伪传递律：如果XY，XYZ，则X(Z-Y)。,41,第四范式（4NF）定义定义4.19设有一关系模式R（U），U是其属性全集，X、Y是U的子集，D是R上的数据依赖集。如果对于任一多值依赖XY，此多值依赖是平凡的，或者X包含了R的一个候选关键字，则称R是第四范式的关系模式，记为R4NF。一个BCNF的关系模式不一定是4NF4NF是BCNF的推广一个BCNF的关系模式不一定是4NF,42,第四范式（4NF）的分解（1）令=R。（2）如果中所有模式Ri都是4NF，则转（4）。（3）如果中有一个关系模式S不是4NF，则S中必能找到一个多值依赖XY且X不包含S的候选键，Y-X，XYS，令Z=Y-X，设S1=XZ，S2=S-Z，用分解S1，S2代替S，由于S1S2=X，S1-S2=Z，所以有(S1S2)(S1-S2)，分解具有无损连接性，转（2）。（4）分解结束，输出。,43,4.5关系模式的规范化,一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的规范化。关系模式规范化的目的和原则规范化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。规范化的基本原则就是遵循“一事一地”的原则。,44,4.5.2关系模式规范化的步骤,规范化过程,1NF,2NF,3NF,BCNF,消除决定属性,不是候选键的,非平凡的函数,依赖,消除非主属性对键的部分函数依赖,消除非主属性对键的传递函数依赖,消除主属性对键的部分和传递函数依赖,4NF,消除非平凡且非函数依赖的多值依赖,45,4.5.3关系模式规范化的要求,本章讨论如何设计关系模式问题。关系模式设计得好与坏，直接影响到数据冗余度、数据一致性等问题。要设计好的数据库模式，必须有一定的理论为基础。这就是模式规范化理论。在数据库中，数据冗余是指同一个数据存储了多次，由数据冗余将会引起各种操作异常。通过把模式分解成若干比较小的关系模式可以消除冗余。,46,函数依赖XY是数据之间最基本的一种联系，在关系中有两个元组，如果X值相等那么要求Y值也相等。FD有一个完备的推理规则集。关系模式在分解时应保持“等价”，有数据等价和语义等价两种，分别用无损分解和保持依赖两个特征来衡量。前者能保持泛关系在投影连接以后仍能恢复回来，而后者能保证数据在投影或连接中其语义不会发生变化，也就是不会违反FD的语义。但无损分解与保持依赖两者之间没有必然的联系。,47,范式是衡量模式优劣的标准，范式表达了模式中数据依赖之间应满足的联系。如果关系模式R是3NF，那么R上成立的非平凡FD都应该左边是超键或右边是非主属性。如果关系模式R是BCNF，那么R上成立的非平凡的FD都应该左边是超键。范式的级别越高，其数据冗余和操作异常现象就越少。,48,分解成BCNF模式集的算法能保持无损分解，但不一定能保持FD集。而分解成3NF模式集的算法既能保持无损分解，又能保持FD集。关系模式的规范化过程实际上是一个“分解”过程：把逻辑上独立的信息放在独立的关系模式中。分解是解决数据冗余的主要方法，也是规范化的一条原则：“关系模式有冗余问题就分解它”。,49,书中未讲到的还有：嵌入多值依赖连接依赖和第五范式以后可查找资料学习。上海复旦大学施伯乐丁宝康汪卫数据库系统教程,50,嵌入多值依赖,有时关系模式R中，多值依赖XY不成立，但在R的某个子集W中可能成立。在数据库设计中，对这种现象也应加以重现。定义：设关系模式R（U），X和Y是属性集U的子集，W是U的真子集，并且XYW。多值依赖XY在模式R上不成立，但在模式W上成立。那么XY在R上称为嵌入多值依赖（EmbeddedMVD），用符号（XY）W表示。,51,例:设模式R(C,S,P,Y)的属性分别表示课程、选修课程的学生、这门课程的先修课程和该学生先修的年份。在R上仅有的非平凡的依赖是SPY，关键码是CSP。因此可将R分解为R1(CSP)和R2(SPY)。显然R2已是4NF。在R中，CS和CP显然不成立。但是在模式R1（C