《数据库模式的分解ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据库模式的分解ppt课件.ppt（69页珍藏版）》请在三一办公上搜索。
1、1,6.4 模式的分解,模式分解是提高关系模式规范化程度的主要途径。主要内容：模式分解的三个定义分解的无损连接性和保持函数依赖性模式分解算法,2,泛关系假设：在进行模式分解时，我们总是假设存在着一个单一的关系模式，并从这个关系模式出发，而不是从一组关系模式出发实行分解。然后讨论这个关系模式与分解后的一组关系模式之间的等价问题。,3,模式的分解,定义6.16 关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影,4,例：将R=
2、(ABCD,AB,BC,BD,CA)分解为关于U1=AB，U2=ACD 两个关系,求R1,R2。 解：R1=(AB,AB,BA) R2=(ACD,AC,CA,AD) 要注意： F 在属性 Ui 上的投影，不仅要包括已知的函数依赖，而且还要包括为F所逻辑蕴含的函数依赖。,5,把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义,6,关系模式分解的标准,三种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性,7,“无损连接性”是指分解后所得到的各个关系可以通过自然连接来实现还
3、原；“还原”就是既不必比原来的信息多也不比原来的信息少，刚好一样。比原来的信息多也不符合“无损连接性”的要求。“保持函数依赖”是指分解后各个具体关系上的函数依赖集的并集刚好等价于原来关系上的依赖集；原来关系中个属性(属性组)之间的相互联系要在分解后还能得到完全而正确的体现。,8,模式的分解,例2: SL（Sno， Sdept， MN） F= SnoSdept, SdeptMN 存在插入异常、删除异常、冗余度大和修改复杂等问题； 分解方法可以有多种 。,9,模式的分解,10,模式的分解（续）,1.进行如下分解: 1R1SNO,R2SDEPT,R3MN,(注：R1SNO,表示R1的函数依赖集为)分
4、解后诸Ri的关系ri是R在Ui上的投影，即ri=RUi r1=S1，S2，S3，S4，r2=Dl，D2，D3，r3=张五，李四，王一。 .,11,r1,r2,r3,12,模式的分解（续）,分解后的数据库丢失了许多信息； 例如无法查询S1学生所在系以及系主任的信息。,13,如果分解后的数据库能够恢复到原来的情况，不丢失信息的要求也就达到了。Ri向R的恢复是通过自然连接来实现的，这就产生了无损连接性的概念。显然，本例的分解1所产生的诸关系自然连接(投影连接)的结果实际上是它们的笛卡尔积，元组增加了，信息丢失了。,14,注意：本节中的自然连接与第二章中的自然连接有区别；在本节中，计算自然连接时，两个
5、关系中如果有相同的属性列，则按第二章中的自然连接的定义进行，如果两个关系中没有相同的属性列，则按笛卡儿积运算进行。,15,模式的分解（续）,2. 对R又进行第二种分解2=R1SNO,SDEPT,SNOSDEPT，R2SNO,MN,SNOMN,16,R1,R2,17,以后可以证明2对R的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，原因就在于原来在R中存在的函数依赖 SDEPTMN，现在在R1和R2中都不再存在了。因此人们又要求分解具有保持函数依赖的特性。,18,3 对R进行了第三种分解: 3=R1SNO,SDEPT,SNOSDEPT， R2SDEPT,MN,SDEPTMN,R1,R
6、2,19,可以证明分解3既具有无损连接性，又保持函数依赖。它解决了更新异常，又没有丢失原数据库的信息，这是所希望的分解。,20,模式的分解,如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。,21,设=R1, R2,.Rk是R的一个分解，r是R的一个关系。定义：m(r)=R1(r) R2(r) . Rk(r)(或 m(r)= Ri(r)）, 即 m(r)是r在中各关系模式上投影的连接。
7、 Ri(r)=t.Ui|tr , 即r中的每一个元组t在属性Ui上的取值.,6.4.2 分解的无损连接性,22,注意 的含义不同于一般的自然连接，它是一种特殊的连接运算。上式含义为：1）如果两个关系中有相同的属性列，则按第二章中的自然连接的定义进行；2）如果两个关系中没有相同的属性列，则按笛卡儿积运算进行；将运算后得到的中间与其他关系进行重复1）、2）步的计算，之到完成全部的连接运算,23,泛关系假设下的投影联接变换示意图,关系模式R,模式分解,=R1,R2,.Rk,R的一个实例r,r1,r2,.rk,S=m(r),Ri(r),Ri(s),24,2引理6.4,设=R1, R2,.Rk为关系模式
8、R的一个分解，r为R的任一个关系，ri=Ri(r),则 r m(r）(即r的投影连接包含r) 如果s=m(r) ,则Ri(S)=ri m(m(r)=m(r),25,r m(r） r的投影连接包含r,分解后再连接起来的r肯定不会比原来的r小； 如果s=m(r) ,则Ri(S)=ri, 投影连接后再投影到子关系模式=直接投影到该子关系模式。即Ri(r)= Ri(m(r) ), m(m(r)=m(r) 多次投影连接的结果等于一次投影连接后的结果.,26,例：设有关系模式R(A,B,C), =R1,R2为它的一个分解，其中R1=AB,R2=BC,r为R的一个关系，r1=R1(r),r2=R2(r),求
9、 r1，r2，m(r)，由此可得到什么结论？,27,rr,r1=R1(r),r2=R2(r),m(r),r1=R1(m(r),r2=R2(m(r),28,结论：分解后的关系做自然联接必包含分解前的关系，即分解不会丢失信息，但可能增加信息，只有r=m(r)时，分解才具有无损联接性,29,具有无损连接性的模式分解,定义6.18 关系模式R的一个分解 = R1，R2， ，Rn若对于R的任何一个关系r均有r=m(r)成立,则称分解具有无损连接性（Lossless join）,30,注意:具有无损连接性的分解保证不丢失信息但是,无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题,31,算
10、法6.2 判别一个分解的无损连接性,= R1，R2， ，Rn是R的一个分解,U=A1,A2,AN,F=FD1,FD2,FD设F是一极小依赖集,记FDi为XiAli,32,算法6.2 判别一个分解的无损连接性,1.构造初始表:构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性Aj属于关系模式Ri, 则在表的第i行第j列置符号aj否则置符号bij .,33,2.根据F中的函数依赖修改表内容 考察F中的每个函数依赖XY,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行，则修改这些行，则使这些行上属性组Y所在的列上元素相同。 修改
11、规则是：如果y所在的要修改的行中有一个为aj，则这些元素均变成aj；否则改动为bmj,，其中m为这些行的最小行号。注意，若某个bij被改动，则该列中凡是与bij相同的符号均做相同的改动。循环地对F中的函数依赖进行逐个处理，直到发现表中有一行变为a1,a2,an或不能再被修改为止。,34,3.判断分解是否是无损联接 如果通过修改，发现表中有一行变为a1,a2,an, 则分解是无损联接的，否则分解不具有无损联接性。书上例题,35,例1: 关系模式R(SAIP), F=SA,SIP,=R1(SA),R2(SIP) 检验分解是否为无损联接？所以,分解是无损联接,36,例2：已知关系模式R(U,F) ,
12、U=SNO,CNO,GRADE,TNAME,TAGE,OFFICE F=(SNO,CNO)GRADE,CNOTNAME, TNAME(TAGE,OFFICE)以及R上的两个分解 1=SC,CT,TO, 其中SC=SNO,CNO,GRADE, CT=CNO,TNAME,TO=TNAME,TAGE,OFFICE试检验1的无损联接性。,37,定理6.5 设R的一个分解=R1, R2 具有无损分解的充分必要条件是： (U1U2)U1-U2F+ 或 (U1U2)U2-U1F+ 即:交决定差,38,例1: 关系模式R(SAIP), F=SA,SIP,=R1(SA),R2(SIP) 检验分解是否为无损联接？
13、解: (U1U2)=S U1-U2=A S AF+ 所以,分解是无损联接,39,保持函数依赖的模式分解,定义6.19 若F+=(F1F2Fk)+,则称关系模式R的分解=R1, Rk 是保持函数依赖的（Preserve dependency）。,40,练习,例：已知关系模式R(CITY,ST,ZIP), F=(CITY,ST)ZIP,ZIPCITY以及R上的一个分解=R1, R2, R1 =ST,ZIP, R2 =CITY,ZIP 求R1,R2 ,并检验分解的无损联接性和分解的函数依赖保持性。,答案：R1=(ST,ZIP,) R2=(CITY,ZIP,ZIPCITY)是无损分解,但不具有函数依赖
14、保持性。,41,模式分解的算法,若要求分解保持函数依赖,那么模式分解总可以达到3NF,但不一定能达到BCNF;若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF;若要求分解具有无损连接性,那一定可达到4NF.,42,算法6.3 （合成法）转换为3NF的保持函数依赖的分解。算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解算法6.5 转换为BCNF的无损连接分解（分解法）,43,算法6.3,算法6.3 （合成法）转换为3NF的保持函数依赖的分解。1 对R中的F进行最小化处理。2 找出不在F中出现的属性，将它们单独构成 一个关系模式，并从模式R的U中消去这些
15、属性；3 如果XAF，且XA=U，则=R ，算法终止；,44,4 否则,对F按具有相同左部的原则分组(假定分为K组),即对F中的每一个函数依赖XA，构造一个关系模式XA。 如果XA1,XA2,XAn均属于F，则构造一个关系模式XA1A2An。,45,例：R（SNO，SNAME，SD，MN）， F=SNO SNAME，SNO SD，SD MN，分解R,使其保持函数依赖达到3NF。解：F已经是最小集，同时也找不出不在F中出现的属性，现将F按照相同左部原则进行分组，结果为R1,46,练习,例 :R,分解R,使其保持函数依赖达到3NF.解：关系模式R的最小函数依赖集F=CT,CSG,HRC,HSR,T
16、HR。该模式可以保持函数依赖地分解为如下一组3NF的关系模式：=CT，CSG，CHR，HSR，HRT。,47,算法6.3本身用处不大，但可作为算法6.4的准备。,48,算法6.4,算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解1 设X是RU，F的侯选码2 按算法6.3对R分解；3 判断侯选码X是否在分解后的子关系模式的属性集中出现，如果出现，分解就是3NF既有无损连接性又保持函数依赖的分解；如果没有出现，则把码X作为一个子关系模式加入分解中。,49,练习,例：R,分解R为一组3NF的关系模式，要求分解既具有无损联接性又保持函数依赖.解：1）求R的码为HS； 2）按算法6.3，=R1
17、(CT)，R2（CSG）， R3（CHR），R4（HSR）， R5（HRT）； 3）码HS包含在子模式R4（HSR）中，所以分解既具有无损联接性又保持函数依赖.,50,设R（ABCDE），F=A B，C D，分解R为一组3NF的关系模式，要求分解既具有无损联接性又保持函数依赖.解：1 ACE为侯选码； 2 按算法5.3， =R1(AB)，R2（CD）; 3 判断侯选码ACE不在分解后的子关系模式中，所以加上码ACE组成的模式R3(ACE).所以=R1(AB)，R2（CD）, R3(ACE)是一个3NF的关系模式，既具有无损联接性又保持函数依赖.,51,算法6.5 转换为BCNF的无损连接分解（
18、分解法）,反复运用逐步分解定理，逐步分解关系模式R，使得每次分解都具有无损联接性，而且每次分解出来的子关系模式至少有一个是BCNF的，即：1）置初值=R；2）检查中的关系模式，如果均属BCNF，则转4） ；3）在中找出不属于BCNF的子关系模式Ri，那么必有XAF+，（A不包含于X），且X不是Ri的关键字。因此XA必不包含Ri的全部属性。把Ri分解为S1，S2，其中S1=XA，S2=Ui-A，并以S1，S2代替中的Ri ，返回2）4） 终止分解，输出。,52,例：R,分解R为一组BCNF的关系模式，要求分解具有无损联接性.,53,解1：第一遍循环1）R的码为HS，R不属于BCNF；2）由CSG
19、，CS不包含侯选码， 分解R为CSG和CTHRS(注意去掉了G)，并求得CSG和CTHRS上函数依赖最小集： F1= CSG ， F2=HSR,HTR,CT,HRC =CSG, CTHRS CSG (CSG,CSG) (属于BCNF) CTHRS (CTHRS,HSR,HTR,CT,HRC) (不属于BCNF),54,第二遍循环因为CTHRS (CTHRS,HSR,HTR,CT,HRC)不是BCNF，所以继续对它进行分解.1) 关系模式CTHRS侯选码为：HS；2)由CT，C不包含侯选码，分解CTHRS为CT和CHRS(注意去掉了T)，并求得CT和CHRS上函数依赖最小集： CT(CT,CT)
20、 (属于BCNF) CHRS(CHRS,HSR,HRC)=CSG,CT, CHRS,55,第三遍循环因为CHRS(CHRS,HSR,HRC)不是BCNF，所以继续对它进行分解1) 关系模式CHRS侯选码为：HS；2） 由HRC ，HR不包含侯选码 ，分解CHRS为HRC和HRS(注意去掉了C)，并求得HRC和HRS上函数依赖最小集： CHR(CHR,HCR,HRC) (属于BCNF) RHS(HS,HSR) (属于BCNF) =CSG,CT, CHR，RHS,56,第四遍循环因为所有的子分解模式都是BCNF，所以分解终止。=（CSG,CT,CHR,RHS）为一组BCNF的关系模式，分解具有无损
21、联接性.,57,注意采用算法6.5分解的分解结果不唯一，也不是任何达到BCNF的分解都是理想的，这与选择分解次序有关。同时分解不一定能保持函数依赖。例：第一次分解时如果选择CT，则分解的最终结果为又会不一样。所以分解要结合语义和实际应用来考虑。 。,58,小结：规范化的缺点,规范化的结果是将一个非规范化的关系模式分解成多个规范化的关系模式，也即将一个表分解成多个表，这些表有相对较少的列，并且这些列必须使用主码/外码连接起来。这样可能会产生以下几个缺点：,59,1 降低数据库的性能。当执行查询或事务处理请求时，规范化的数据库必须要定位所需的表，连接表中的数据来获得需要的信息，降低了处理速度并加重
22、了硬件的负担。,60,2 增加了应用程序编制的难度。如：一个不好的查询甚至可能造成系统的瘫痪,61,3 并非规范化的程度越高越好。规范化仅仅从一个侧面提供了改善关系模式的理论和方法。一个关系模式的好坏，规范化是衡量的标准之一，但不是唯一的标准。,62,如：R（学号，姓名，省，市，街道，邮编）该模式实际上是描述了学生的地址信息，如果该模式主要用于查询，将他们都放入一张表中，是便于查询的。虽然R不属于3NF，但邮编确定后，实际上很少修改，由此引起的更新异常并不严重。若将R分解成3NF的关系模式（学号，姓名，省，市，街道）和（省，市，街道，邮编）则查询一个学生的地址还要做一次连接，显然不方便，且大大
23、降低了数据库性能。因此，对数据库规范化的程度要取决于具体的应用,63,反规范化,反规范化是出于对提高数据库性能原因而对规范化的数据库的再考虑，它修改表结构以允许一些数据冗余。是在严格规范化的数据库基础上，通过反规范化重新合并一些分开的表，或在这些表中创建一些重复的数据，以减少查询处理时所需进行连接的表的个数，但反规范化也需要更多的代价以便跟踪有关的数据。因此，反规范化是在需要极大地提高性能时才需要的。,64,小结,规范化理论仅仅从一个侧面为数据库设计提供了理论的指南和工具，判断一个关系模式的好坏。也仅仅是指南和工具并不是规范化程度越高，模式就越好必须结合应用环境和现实世界的具体情况合理地选择数
24、据库模式,65,在模式分解时，无损分解是分解是第一必须满足的。即分解前后的数据，做同样内容的操作，应产生同样的结果。（决定能否分解）在模式分解时，达到某一范式是第二要满足的。在模式分解时，保持函数依赖是第三要考虑的。（分解的好坏）在数据库设计中，只满足保持函数依赖不宜作为关系分解的一个独立准则。,66,练习,1 设R(ABCD),R上的FD=AC,DC, BDA,试说明R上的一个分解(AB,ACD,BCD)相对于F不是无损分解.,67,2 设R(ABCDEFG),F=AB,BCDE, AEFG,试判断ACDG是否为F所逻辑蕴涵?,68,3 设R(A,B,C,D),F=ABC,BC, AB,ABC, ACD试计算F的最小函数依赖集.,69,4 设R(XYZWQ),F=XY,XZW,YWQ求R的一个无损的且保持函数依赖的3NF分解;,
