数据库模式的分解ppt课件.ppt

《数据库模式的分解ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据库模式的分解ppt课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.4 模式的分解v模式分解是提高关系模式规范化程度的主要途径。v主要内容：模式分解的三个定义分解的无损连接性和保持函数依赖性模式分解算法1v泛关系假设：在进行模式分解时，我们总是假设存在着一个单一的关系模式，并从这个关系模式出发，而不是从一组关系模式出发实行分解。然后讨论这个关系模式与分解后的一组关系模式之间的等价问题。2模式的分解定义6.16 关系模式R的一个分解：=R1，R2，RnU=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影。定义6.17 函数依赖集合XY|XY F+XYUi的一个覆盖Fi 叫作F 在属性Ui 上的投影3例：将R=(ABCD,AB,BC,BD,CA)分解为

2、关于U1=AB，U2=ACD 两个关系,求R1,R2。解：R1=(AB,AB,BA)R2=(ACD,AC,CA,AD)要注意：F 在属性Ui 上的投影，不仅要包括已知的函数依赖，而且还要包括为F所逻辑蕴含的函数依赖。4v把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的v只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义5关系模式分解的标准三种模式分解的等价定义分解具有无损连接性分解要保持函数依赖分解既要保持函数依赖，又要具有无损连接性6v“无损连接性”是指分解后所得到的各个关系可以通过自然连接来实现还原；“还原”就是既不必比原来的信息多也不比原来的信息少，刚好一样。

3、比原来的信息多也不符合“无损连接性”的要求。v“保持函数依赖”是指分解后各个具体关系上的函数依赖集的并集刚好等价于原来关系上的依赖集；原来关系中个属性(属性组)之间的相互联系要在分解后还能得到完全而正确的体现。7模式的分解例2:SL（Sno，Sdept，MN）F=SnoSdept,SdeptMN 存在插入异常、删除异常、冗余度大和修改复杂等问题；分解方法可以有多种。8模式的分解9模式的分解（续）1.进行如下分解:1R1SNO,R2SDEPT,R3MN,(注：R1SNO,表示R1的函数依赖集为)分解后诸Ri的关系ri是R在Ui上的投影，即ri=RUi r1=S1，S2，S3，S4，r2=Dl，D

4、2，D3，r3=张五，李四，王一。.10SNOS1S2S3S4SDEPTD1D2D3MN张五李四王一r1 r2 r311模式的分解（续）分解后的数据库丢失了许多信息；例如无法查询S1学生所在系以及系主任的信息。12v如果分解后的数据库能够恢复到原来的情况，不丢失信息的要求也就达到了。v Ri向R的恢复是通过自然连接来实现的，这就产生了无损连接性的概念。v显然，本例的分解1所产生的诸关系自然连接(投影连接)的结果实际上是它们的笛卡尔积，元组增加了，信息丢失了。13v注意：本节中的自然连接与第二章中的自然连接有区别；在本节中，计算自然连接时，两个关系中如果有相同的属性列，则按第二章中的自然连接的定

5、义进行，如果两个关系中没有相同的属性列，则按笛卡儿积运算进行。14模式的分解（续）2.对R又进行第二种分解2=R1SNO,SDEPT,SNOSDEPT，R2SNO,MN,SNOMN 15SNO SDEPTS1 D1S2 D1S3 D2S4 D3SNO SMNS1张五S2张五S3李四S4王一R1R216v以后可以证明2对R的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，原因就在于原来在R中存在的函数依赖 SDEPTMN，现在在R1和R2中都不再存在了。因此人们又要求分解具有保持函数依赖的特性。173 对R进行了第三种分解:3=R1SNO,SDEPT,SNOSDEPT，R2SDEPT,

6、MN,SDEPTMN SNO SDEPTS1 D1S2 D1S3 D2S4 D3SDEPT SMND1张五D2李四D3王一R1R218v可以证明分解3既具有无损连接性，又保持函数依赖。它解决了更新异常，又没有丢失原数据库的信息，这是所希望的分解。19模式的分解v 如果一个分解具有无损连接性，则它能够保证不丢失信息。v 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。v 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。20设=R1,R2,.Rk是R的一个分解，r是R的一个关系。定义：

7、m(r)=R1(r)R2(r).Rk(r)(或 m(r)=Ri(r)）,即 m(r)是r在中各关系模式上投影的连接。Ri(r)=t.Ui|tr,即r中的每一个元组t在属性Ui上的取值.6.4.2 分解的无损连接性i=1k21v 注意 的含义不同于一般的自然连接，它是一种特殊的连接运算。上式含义为：v 1）如果两个关系中有相同的属性列，则按第二章中的自然连接的定义进行；v 2）如果两个关系中没有相同的属性列，则按笛卡儿积运算进行；v 将运算后得到的中间与其他关系进行重复1）、2）步的计算，之到完成全部的连接运算22泛关系假设下的投影联接变换示意图关系模式R模式分解=R1,R2,.RkR的一个实例

8、rr1,r2,.rkS=m(r)Ri(r)Ri(s)232引理6.4设=R1,R2,.Rk为关系模式R的一个分解，r为R的任一个关系，ri=Ri(r),则 r m(r）(即r的投影连接包含r)如果s=m(r),则Ri(S)=ri m(m(r)=m(r)24r m(r）r的投影连接包含r,分解后再连接起来的r肯定不会比原来的r小；如果s=m(r),则Ri(S)=ri,投影连接后再投影到子关系模式=直接投影到该子关系模式。即Ri(r)=Ri(m(r),m(m(r)=m(r)多次投影连接的结果等于一次投影连接后的结果.25例：设有关系模式R(A,B,C),=R1,R2为它的一个分解，其中R1=AB,

9、R2=BC,r为R的一个关系，r1=R1(r),r2=R2(r),求 r1，r2，m(r)，由此可得到什么结论？26rrr1=R1(r)r2=R2(r)m(r)A B Ca1 b1 c1a1 b1 c2a2 b1 c1a2 b1 c2A Ba1 b1a2 b1B Cb1 c1b1 c2r1=R1(m(r)r2=R2(m(r)27v结论：分解后的关系做自然联接必包含分解前的关系，即分解不会丢失信息，但可能增加信息，只有r=m(r)时，分解才具有无损联接性28具有无损连接性的模式分解v 定义6.18关系模式R的一个分解=R1，R2，Rn若对于R的任何一个关系r均有r=m(r)成立,则称分解具有无损

10、连接性（Losslessjoin）29v 注意:v 具有无损连接性的分解保证不丢失信息v 但是,无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题30算法6.2 判别一个分解的无损连接性v=R1，R2，Rn是R的一个分解,vU=A1,A2,AN,F=FD1,FD2,FDv 设F是一极小依赖集,记FDi为XiAli31算法6.2 判别一个分解的无损连接性1.构造初始表:构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性Aj属于关系模式Ri,则在表的第i行第j列置符号aj否则置符号bij.322.根据F中的函数依赖修改表内容 考察F中的

11、每个函数依赖XY,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行，则修改这些行，则使这些行上属性组Y所在的列上元素相同。修改规则是：如果y所在的要修改的行中有一个为aj，则这些元素均变成aj；否则改动为bmj,，其中m为这些行的最小行号。注意，若某个bij被改动，则该列中凡是 与 bij相 同 的 符 号 均 做 相 同 的 改 动。循环地对F中的函数依赖进行逐个处理，直到发现表中有一行变为a1,a2,an或不能再被修改为止。333.判断分解是否是无损联接 如果通过修改，发现表中有一行变为a1,a2,an,则分解是无损联接的，否则分解不具有无损联接性。v 书上例题3

12、4例1:关系模式R(SAIP),F=SA,SIP,=R1(SA),R2(SIP)检验分解是否为无损联接？所以,分解是无损联接35例2：已知关系模式R(U,F),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的无损联接性。36定理6.5 设R的一个分解=R1,R2 具有无损分解的充分必要条件是：(U1U2)U1-U2F+或(U1U2)U

13、2-U1F+即:交决定差37例1:关系模式R(SAIP),F=SA,SIP,=R1(SA),R2(SIP)检验分解是否为无损联接？解:(U1U2)=S U1-U2=A S AF+所以,分解是无损联接 38保持函数依赖的模式分解定义6.19 若F+=(F1 F2 Fk)+,则称关系模式R的分解=R1,Rk 是保持函数依赖的（Preserve dependency）。39练习例：已知关系模式R(CITY,ST,ZIP),F=(CITY,ST)ZIP,ZIPCITY以及R上的一个分解=R1,R2,R1=ST,ZIP,R2=CITY,ZIP 求R1,R2,并检验分解的无损联接性和分解的函数依赖保持性。

14、答案：R1=(ST,ZIP,)R2=(CITY,ZIP,ZIPCITY)是无损分解,但不具有函数依赖保持性。40模式分解的算法v 若要求分解保持函数依赖,那么模式分解总可以达到3NF,但不一定能达到BCNF;v 若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF;v 若要求分解具有无损连接性,那一定可达到4NF.41v 算 法6.3（合成法）转换为3NF的保持函数依赖的分解。v 算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解v 算法6.5 转换为BCNF的无损连接分解（分解法）42算法6.3v 算法6.3（合成法）转换为3NF的保持函数依赖的分解。v

15、 1对R中的F进行最小化处理。v 2找出不在F中出现的属性，将它们单独构成一个关系模式，并从模式R的U中消去这些属性；v 3如果XA F，且XA=U，则=R，算法终止；43v 4否则,对F按具有相同左部的原则分组(假定分为K组),即对F中的每一个函数依赖XA，构造一个关系模式XA。如果XA1,XA2,XAn均属于F，则构造一个关系模式XA1A2An。44v 例：R（SNO，SNAME，SD，MN），v F=SNO SNAME，SNO SD，SD MN，分解R,使其保持函数依赖达到3NF。v 解：F已经是最小集，同时也找不出不在F中出现的属性，现将F按照相同左部原则进行分组，结果为R1(SNO，

16、SNAME，SD）,v SNO SNAME,SNO SDv R245练习例:R,分解R,使其保持函数依赖达到3NF.v 解：关系模式R的最小函数依赖集F=CT,CSG,HRC,HSR,THR。该模式可以保持函数依赖地分解为如下一组3NF的关系模式：v=CT，CSG，CHR，HSR，HRT。46v算法6.3本身用处不大，但可作为算法6.4的准备。47算法6.4v 算法6.4转换为3NF既有无损连接性又保持函数依赖的分解v 1设X是RU，F的侯选码v 2按算法6.3对R分解；v 3判断侯选码X是否在分解后的子关系模式的属性集中出现，v 如果出现，分解就是3NF既有无损连接性又保持函数依赖的分解；v

17、 如果没有出现，则把码X作为一个子关系模式加入分解中。48练习例：R,分解R为一组3NF的关系模式，要求分解既具有无损联接性又保持函数依赖.解：1）求R的码为HS；v 2）按算法6.3，=R1(CT)，R2（CSG），R3（CHR），R4（HSR），R5（HRT）；v 3）码HS包含在子模式R4（HSR）中，v 所以分解既具有无损联接性又保持函数依赖.49v 设R（ABCDE），F=A B，C D，分解R为一组3NF的关系模式，要求分解既具有无损联接性又保持函数依赖.v 解：1 ACE为侯选码；v 2 按算法5.3，=R1(AB)，R2（CD）;v 3 判断侯选码ACE不在分解后的子关系模式中

18、，所以加上码ACE组成的模式R3(ACE).v 所以=R1(AB)，R2（CD）,R3(ACE)是一个3NF的关系模式，既具有无损联接性又保持函数依赖.50算法6.5 转换为BCNF的无损连接分解（分解法）反复运用逐步分解定理，逐步分解关系模式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，

19、S2代替中的Ri，返回2）4）终止分解，输出。51例：R,分解R为一组BCNF的关系模式，要求分解具有无损联接性.52解1：第一遍循环1）R的码为HS，R不属于BCNF；2）由CSG，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)53第二遍循环因为CTHRS(CTHRS,HSR,HTR,CT,HRC)不是BCNF，所以继续对它进行分解.1)关系模式CTHRS

20、侯选码为：HS；2)由CT，C不包含侯选码，分解CTHRS为CT和CHRS(注意去掉了T)，并求得CT和CHRS上函数依赖最小集：CT(CT,CT)(属于BCNF)CHRS(CHRS,HSR,HRC)=CSG,CT,CHRS54v 第三遍循环v 因为CHRS(CHRS,HSR,HRC)不是BCNF，所以继续对它进行分解v 1)关系模式CHRS侯选码为：HS；v 2）由HRC，HR不包含侯选码，v 分解CHRS为HRC和HRS(注意去掉了C)，并求得HRC和HRS上函数依赖最小集：v CHR(CHR,HCR,HRC)(属于BCNF)v RHS(HS,HSR)(属于BCNF)v=CSG,CT,CH

21、R，RHS55v第四遍循环v因为所有的子分解模式都是BCNF，所以分解终止。v=（CSG,CT,CHR,RHS）为一组BCNF的关系模式，分解具有无损联接性.v 56v注意采用算法6.5分解的分解结果不唯一，也不是任何达到BCNF的分解都是理想的，这与选择分解次序有关。同时分解不一定能保持函数依赖。v例：第一次分解时如果选择CT，则分解的最终结果为又会不一样。所以分解要结合语义和实际应用来考虑。57小结：规范化的缺点v规范化的结果是将一个非规范化的关系模式分解成多个规范化的关系模式，也即将一个表分解成多个表，这些表有相对较少的列，并且这些列必须使用主码/外码连接起来。这样可能会产生以下几个缺点

22、：58v 1 降低数据库的性能。v当执行查询或事务处理请求时，规范化的数据库必须要定位所需的表，连接表中的数据来获得需要的信息，降低了处理速度并加重了硬件的负担。59v 2 增加了应用程序编制的难度。v如：一个不好的查询甚至可能造成系统的瘫痪60v 3 并非规范化的程度越高越好。v规范化仅仅从一个侧面提供了改善关系模式的理论和方法。一个关系模式的好坏，规范化是衡量的标准之一，但不是唯一的标准。61v 如：R（学号，姓名，省，市，街道，邮编）v 该模式实际上是描述了学生的地址信息，如果该模式主要用于查询，将他们都放入一张表中，是便于查询的。虽然R不属于3NF，但邮编确定后，实际上很少修改，由此引

23、起的更新异常并不严重。v 若将R分解成3NF的关系模式v（学号，姓名，省，市，街道）和v（省，市，街道，邮编）v 则查询一个学生的地址还要做一次连接，显然不方便，且大大降低了数据库性能。v 因此，对数据库规范化的程度要取决于具体的应用62反规范化v 反规范化是出于对提高数据库性能原因而对规范化的数据库的再考虑，它修改表结构以允许一些数据冗余。是在严格规范化的数据库基础上，通过反规范化重新合并一些分开的表，或在这些表中创建一些重复的数据，以减少查询处理时所需进行连接的表的个数，但反规范化也需要更多的代价以便跟踪有关的数据。因此，反规范化是在需要极大地提高性能时才需要的。63小结v规范化理论仅仅从

24、一个侧面为数据库设计提供了理论的指南和工具，判断一个关系模式的好坏。也仅仅是指南和工具v并不是规范化程度越高，模式就越好必须结合应用环境和现实世界的具体情况合理地选择数据库模式64v 在模式分解时，无损分解是分解是第一必须满足的。即分解前后的数据，做同样内容的操作，应产生同样的结果。（决定能否分解）v 在模式分解时，达到某一范式是第二要满足的。v 在模式分解时，保持函数依赖是第三要考虑的。（分解的好坏）在数据库设计中，只满足保持函数依赖不宜作为关系分解的一个独立准则。65练习v 1 设R(ABCD),R上的FD=AC,DC,BDA,试说明R上的一个分解(AB,ACD,BCD)相对于F不是无损分解.66v 2 设R(ABCDEFG),F=AB,BCDE,v AEFG,v试判断ACDG是否为F所逻辑蕴涵?67v 3 设R(A,B,C,D),F=ABC,BC,v AB,ABC,ACDv试计算F的最小函数依赖集.68v 4 设R(XYZWQ),F=XY,XZW,YWQv求R的一个无损的且保持函数依赖的3NF分解;69