数据库模式的分解

16.4模式的分解模式分解是提高关系模式规范化程度的主要途径。主要内容：模式分解的三个定义分解的无损连接性和保持函数依赖性模式分解算法2泛关系假设：在进行模式分解时，我们总是假设存在着一个单一的关系模式，并从这个关系模式出发，而不是从一组关系模式出发实行分解。然后讨论这个关系模式与分解后的一组关系模式之间的等价问题。3模式的分解定义6.16关系模式RU,F的一个分解：ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}U=U1∪U2∪…∪Un，且不存在UiUj，Fi为F在Ui上的投影。定义6.17函数依赖集合{X→Y|X→YF+∧XYUi}的一个覆盖Fi叫作F在属性Ui上的投影4例：将R=(ABCD,{A→B,B→C,B→D,C→A})分解为关于U1=AB，U2=ACD两个关系,求R1,R2。解：R1=(AB,{A→B,B→A})R2=(ACD,{A→C,C→A,A→D})要注意：F在属性Ui上的投影，不仅要包括已知的函数依赖，而且还要包括为F所逻辑蕴含的函数依赖。5把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义6关系模式分解的标准三种模式分解的等价定义⒈分解具有无损连接性⒉分解要保持函数依赖⒊分解既要保持函数依赖，又要具有无损连接性7“无损连接性”是指分解后所得到的各个关系可以通过自然连接来实现还原；“还原”就是既不必比原来的信息多也不比原来的信息少，刚好一样。比原来的信息多也不符合“无损连接性”的要求。“保持函数依赖”是指分解后各个具体关系上的函数依赖集的并集刚好等价于原来关系上的依赖集；原来关系中个属性(属性组)之间的相互联系要在分解后还能得到完全而正确的体现。8模式的分解例2:SL（Sno，Sdept，MN）F={Sno→Sdept,Sdept→MN}存在插入异常、删除异常、冗余度大和修改复杂等问题；分解方法可以有多种。9模式的分解10模式的分解（续）1.进行如下分解:ρ1＝｛R1〈SNO,φ〉,R2〈SDEPT,φ〉,R3〈MN,φ〉｝(注：R1〈SNO,φ〉表示R1的函数依赖集为φ)分解后诸Ri的关系ri是R在Ui上的投影，即ri=R[Ui]r1={S1，S2，S3，S4}，r2={Dl，D2，D3}，r3={张五，李四，王一}。.11SNOS1S2S3S4SDEPTD1D2D3MN张五李四王一r1r2r312模式的分解（续）分解后的数据库丢失了许多信息；例如无法查询S1学生所在系以及系主任的信息。13如果分解后的数据库能够恢复到原来的情况，不丢失信息的要求也就达到了。Ri向R的恢复是通过自然连接来实现的，这就产生了无损连接性的概念。显然，本例的分解ρ1所产生的诸关系自然连接(投影连接)的结果实际上是它们的笛卡尔积，元组增加了，信息丢失了。14注意：本节中的自然连接与第二章中的自然连接有区别；在本节中，计算自然连接时，两个关系中如果有相同的属性列，则按第二章中的自然连接的定义进行，如果两个关系中没有相同的属性列，则按笛卡儿积运算进行。15模式的分解（续）2.对R又进行第二种分解ρ2={R1〈{SNO,SDEPT},{SNO→SDEPT}〉，R2〈{SNO,MN},{SNO→MN}〉}16SNOSDEPTS1D1S2D1S3D2S4D3SNOSMNS1张五S2张五S3李四S4王一R1R217以后可以证明ρ2对R的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，原因就在于原来在R中存在的函数依赖SDEPT→MN，现在在R1和R2中都不再存在了。因此人们又要求分解具有保持函数依赖的特性。183对R进行了第三种分解:ρ3={R1{SNO,SDEPT},{SNO→SDEPT}〉，R2〈{SDEPT,MN},{SDEPT→MN}〉}SNOSDEPTS1D1S2D1S3D2S4D3SDEPTSMND1张五D2李四D3王一R1R219可以证明分解ρ3既具有无损连接性，又保持函数依赖。它解决了更新异常，又没有丢失原数据库的信息，这是所希望的分解。20模式的分解如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。21设ρ={R1U1,F1,R2U2,F2,...RkUk,Fk}是R的一个分解，r是RU，F的一个关系。定义：mρ(r)=πR1(r)πR2(r)...πRk(r)(或mρ(r)=πRi(r)）,即mρ(r)是r在ρ中各关系模式上投影的连接。πRi(r)={t.Ui|t∈r},即r中的每一个元组t在属性Ui上的取值.6.4.2分解的无损连接性i=1k22注意的含义不同于一般的自然连接，它是一种特殊的连接运算。上式含义为：1）如果两个关系中有相同的属性列，则按第二章中的自然连接的定义进行；2）如果两个关系中没有相同的属性列，则按笛卡儿积运算进行；将运算后得到的中间与其他关系进行重复1）、2）步的计算，之到完成全部的连接运算23泛关系假设下的投影联接变换示意图关系模式R模式分解ρ={R1,R2,..Rk}R的一个实例rr1,r2,..rkS=mρ(r)πRi(r)πRi(s)242引理6.4设ρ={R1U1,F1,R2U2,F2,...RkUk,Fk}为关系模式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),求r1，r2，mρ(r)，由此可得到什么结论？27ABCa1b1c1a2b1c2a1b1c2rrABa1b1a2b1r1=πR1(r)BCb1c1b1c2r2=πR2(r)mρ(r)ABCa1b1c1a1b1c2a2b1c1a2b1c2ABa1b1a2b1BCb1c1b1c2r1=πR1(mρ(r))r2=πR2(mρ(r))28结论：分解后的关系做自然联接必包含分解前的关系，即分解不会丢失信息，但可能增加信息，只有r=mρ(r)时，分解才具有无损联接性29具有无损连接性的模式分解定义6.18关系模式RU,F的一个分解ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}若对于R的任何一个关系r均有r=mρ(r)成立,则称分解ρ具有无损连接性（Losslessjoin）30注意:具有无损连接性的分解保证不丢失信息但是,无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题31算法6.2判别一个分解的无损连接性ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}是RU,F的一个分解,U={A1,A2,…AN},F={FD1,FD2,…FDρ}设F是一极小依赖集,记FDi为Xi→Ali32算法6.2判别一个分解的无损连接性1.构造初始表:构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性Aj属于关系模式Ri,则在表的第i行第j列置符号aj否则置符号bij.332.根据F中的函数依赖修改表内容考察F中的每个函数依赖X→Y,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行，则修改这些行，则使这些行上属性组Y所在的列上元素相同。修改规则是：如果y所在的要修改的行中有一个为aj，则这些元素均变成aj；否则改动为bmj,，其中m为这些行的最小行号。注意，若某个bij被改动，则该列中凡是与bij相同的符号均做相同的改动。循环地对F中的函数依赖进行逐个处理，直到发现表中有一行变为a1,a2,…an或不能再被修改为止。343.判断分解是否是无损联接如果通过修改，发现表中有一行变为a1,a2,…an,则分解是无损联接的，否则分解不具有无损联接性。书上例题35例1:关系模式R(SAIP),F={S→A,SI→P},ρ={R1(SA),R2(SIP)}检验分解是否为无损联接？所以,分解是无损联接SAIPR1a1a2b13b14R2a1b22a3a4SAIPR1a1a2b13b14R2a1a2a3a436例2：已知关系模式R(U,F),U={SNO,CNO,GRADE,TNAME,TAGE,OFFICE}F={(SNO,CNO)→GRADE,CNO→TNAME,TNAME→(TAGE,OFFICE)}以及R上的两个分解ρ1={SC,CT,TO},其中SC={SNO,CNO,GRADE},CT={CNO,TNAME},TO={TNAME,TAGE,OFFICE}试检验ρ1的无损联接性。37定理6.5设RU,F的一个分解ρ={R1U1,F1,R2U2,F2}具有无损分解的充分必要条件是：(U1∩U2)→U1-U2∈F+或(U1∩U2)→U2-U1∈F+即:交决定差38例1:关系模式R(SAIP),F={S→A,SI→P},ρ={R1(SA),R2(SIP)}检验分解是否为无损联接？解:(U1∩U2)=SU1-U2=AS→A∈F+所以,分解是无损联接39保持函数依赖的模式分解定义6.19若F+=(F1∪F2∪…Fk)+,则称关系模式RU,F的分解ρ={R1U1,F1,…RkUk,Fk}是保持函数依赖的（Preservedependency）。40练习例：已知关系模式R(CITY,ST,ZIP),F={(CITY,ST)→ZIP,ZIP→CITY}以及R上的一个分解ρ={R1,R2},R1={ST,ZIP},R2={CITY,ZIP}求R1,R2,并检验分解的无损联接性和分解的函数依赖保持性。答案：R1=({ST,ZIP},{Φ})R2=(CITY,ZIP,{ZIP→CITY})ρ是无损分解,但不具有函数依赖保持性。41模式分解的算法若要求分解保持函数依赖,那么模式分解总可以达到3NF,但不一定能达到BCNF;若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF;若要求分解具有无损连接性,那一定可达到4NF.42算法6.3（合成法）转换为3NF的保持函数依赖的分解。算法6.4转换为3NF既有无损连接性又保持函数依赖的分解算法6.5转换为BCNF的无损连接分解（分解法）43算法6.3算法6.3（合成法）转换为3NF的保持函数依赖的分解。1对RU,F中的F进行最小化处理。2找出不在F中出现的属性，将它们单独构成一个关系模式，并从模式R的U中消去这些属性；3如果X→AF，且XA=U，则ρ={R}，算法终止；444否则,对F按具有相同左部的原则分组(假定分为K组),即对F中的每一个函数依赖X→A，构造一个关系模式XA。如果X→A1,X→A2,…,X→An均属于F，则构造一个关系模式XA1A2…An。45例：R（SNO，SNAME，SD，MN），F={SNO→SNAME，SNO→SD，SD→MN}，分解R,使其保持函数依赖达到3NF。解：F已经是最小集，同时也找不出不在F中出现的属性，现将F按照相同左部原则进行分组，结果为R1(SNO，SNAME，SD）,{SNO→SNAME,SNO→SD}R2(SD,MN),SD→MN46练习例:R(CTHRSG),{C