SQLServer教案第04周-关系模式的分解

数据库原理与应用——SQLServer2005邹竞授课日期年月日第4周授课形式讲课授课时数4章节名称第04章关系模式的分解教学目的与要求①理解关系模式的分解、保持无损连接的分解、保持函数依赖分解的概念②掌握判断某个关系模式的分解是否是无损分解的方法和Chase过程教学重点无损分解和保持函数依赖的分解教学难点判断某个关系模式的分解是否是无损分解的方法和Chase过程教学方法和手段讲授法结合课堂实例分析讨论教学过程与组织导入新课我们已经学习了数据库规范化设计的第一范式、第二范式、第三范式、BC范式、第四范式、第五范式。一般的工程应用，大多只需要满足第三范式即可。要将某个只满足较低范式的关系模式修改为满足较高范式的关系模式，就要对原有的关系模式进行分解。现在我们将学习如何对一个关系模式进行合理的分解。讲授新课第04章关系模式的分解第01节关系模式的分解3.5.1关系模式的分解原则解决关系模式的冗余、插入异常和删除异常的的方法是将其分解。在分解中会涉及一些新问题。这些新问题的实质是如何能够通过分解而保持原来关系模式的特性，这些特性就是函数依赖。也即原关系模式的函数依赖通过分解并不丢失。因此要求分解具备无损联接性和保持其原有的函数依赖。设有关系模式R=A1A2…An，R1,R2,…,Rk都是R的子集，其中R=R1∪R2∪Rk∪…∪Rk。3.3.4BCNF范式BCNF由Boyce和Codd提出，通常认为是3NF的改进形式。设R(U,F)是一个关系模式,如果R∈1NF且R的每个属性都不传递依赖于R的候选键,则称R满足Boyce-Codd范式(BCNF),记为R∈BCNF。换句话说：如果R的F中每一个函数依赖X→Y,其决定因素X都是键,则R∈BCNF。由BCNF范式的定义可知：①所有非主属性对于每一个键都是完全函数依赖的；②所有主属性对于每一个不含有它的键也是完全函数依赖的；③任何属性都不会完全依赖于非键的任何一组属性。BCNF的本质在于其中的每个决定因素都是键。或者说,在BCNF中,除了键决定其所有属性之外,不会有其他的非平凡函数依赖,特别是不会有非主属性作为决定因素的非平凡函数依赖。由于BCNF排除了任何属性对键的传递依赖和部分依赖,所以,如果R∈BCNF,则必定R∈3NF；但是,如果R∈3NF,不一定有R∈BCNF成立。因此,BCNF比3NF更为严格。例3-9设关系模式STC(SNO,TNO,CNO)表达了学生选课信息。其中：SNO为学生学号,TNO为教师号,CNO为课程号。规定每位教师只教1门课程，每门课程可由多位教师讲授，每位学生的每一门课程只由1位教师授课。因此,对于STC有：SNO、CNO函数依赖于TNO,TNO函数依赖于CNO,CNO、TNO函数依赖于CNO。所以,STC不属于BCNF。数据库原理与应用——SQLServer2005邹竞关系模式R1,R2,…,Rk的集合用ρ表示，ρ={R1,R2,…,Rk}。用ρ代替R的过程称为关系模式的分解。3.4.1无损联接(1)无损联接的定义设关系模式R，它的一个分解是ρ={R1,R2,…,Rk}，F是R上的一个函数依赖集。如果对于R中满足F的每一个关系r都有r=πR1(r)πR2(r)…πRk(r)成立，则称分解ρ相对于F是“无损联接分解”(losslessjoindecomposition)。即r是它在Ri的投影的自然连接。其中πRi(r)表示关系r在关系模式Ri的属性上的投影。用mρ(r)表示r的投影连接表达式，即：mρ(r)=πR1(r)πR2(r)…πRk(r)则称mρ(r)为r的投影连接变换。一般情况下r与mρ(r)是不相等的。关系模式R关于F的无损连接条件是：任何满足F的关系r，都有r=mρ(r)。上述定义可以这样较为直观地理解：设有关系模式R，如果把R分解为n个(n1)子模式，相应一个R关系中的数据就要被分成n个子表R1,R2,…,Rn。如果这n个子表自然连接（即进行R1R2…Rn）的结果与原来的R关系相同（即数据未损失），则称该分解具备无损连接性。保持关系模式分解的无损连接性是必要的，因为它保证了该模式上的任何一个关系能由它的那些投影通过自然连接而得到恢复。定理3-4设R是一个关系模式，ρ={R1,R2,…,Rk}是关系模式R的一个分解，r是R的任一关系，ri=πRi(R)（1≤i≤k），则有：①rmρ(r)；②如果S=mρ(r),则ri=πR1(S)；③mρ(mρ(r)=mρ(r)(2)无损联接的判定定理3-5若R的分解ρ={R1,R2}，F为R所满足的函数依赖集，分解ρ具备无损联接的充分必要条件是：R1∩R2(R1-R2)F+或者R1∩R2(R2-R1)F+定理3-5中R1∩R2为模式R1和R2的交集，由两模式的公共属性组成；(R1-R2)、(R2-R1)表考虑把STC分解为SC(SNO,CNO)、ST(SNO,TNO)两个关系模式,则SC∈BCNF、ST∈BCNF。3.3.5多值依赖与第四范式(1)多值依赖设有关系模式R(U),U是属性集,X、Y、Z是U的子集,Z=U-X-Y。如果R的任一关系,对于X的一个确定值,都存在Y的一组值与之对应,且Y的这组值又与Z中的属性值不相关,则称Y多值依赖于X,或称X多值决定Y,记为X→→Y。多值依赖具有以下性质：①多值依赖具有对称性：如果X→→Y,则X→→Z。②多值依赖中,若X→→Y且Z≠φ,则X→→Y为非平凡的多值依赖,否则为平凡的多值依赖。③函数依赖可以看作多值依赖的特例：如果X→Y,则X→→Y。多值依赖与函数依赖的之间存在以下基本区别：①多值依赖的有效性与属性集的范围有关：在关系模式R中,函数依赖X→Y的有效性仅仅决定于X、Y这两个属性集；在多值依赖中,X→→Y在U上是否成立,而且要检查Z的值。因此,即使X→→Y在V上成立(VU),但在U上不一定成立。②多值依赖没有自反律：如果函数依赖X→Y在R上成立,则对于任何Y’Y,都有X→Y’成立；对于多值依赖X→→Y,如果在R上成立,却不一定对于任何Y’Y都有X→→Y’成立。(2)第四范式设R∈1NF,如果对于R的每个非平凡多值依赖X→Y(YX),X都含有键,则称R属于第四范式(简称为4NF),记为R∈4NF。4NF限制关系模式的属性之间不能有非平凡且非函数依赖的多值依赖。因为4NF要求每个非平凡多值依赖X→→Y,X都含有键,则必然有X→Y,所以4NF所允许的非平凡多值依赖实际上是函数依赖。显然,如果R∈4NF,则R∈BCNF。例3-10设关系模式SPW(SNO,SPN,SWN)表达了学生的娱乐爱好(如足球)和社会兼职(如家教)信息(其中SNO为学生学号,SPN为娱乐爱好,SWN为社会兼职)。由于每个学生可以有0或多个娱乐爱好和社会兼职,故SNO与SPN、SWN之间是一对多关系,且SPN与SWN无直接联系(即设SU=(SNO,SPN,SWN),则SWN=U-SNO-SPN),即有SNO→→SPN、SNO→→SWN，使得SPW表中可能有数据冗余,有大量空值存在。显然,SPW不属于4NF。考虑把SPW分解为SP(SNO,SPN)、SW(SNO,SWN)两个关系模式,则SP∈4NF、SW∈4NF。3.3.6连接依赖与第五范式(1)连接依赖设R(U)是属性集U上的关系模式,X1、X2、…、Xn是U的子集且X1∪X2∪…∪Xn=U,如果R=R(X1)R(X2)…R(Xn)对R的一切关系均成立,则称R在X1、X2、…、Xn上具有n目依赖连接,记为[[X1][X2]…[Xn]。连接依赖也是一种数据依赖,它不能直接从语义中推出,只能从连接运算中反映出来。数据库原理与应用——SQLServer2005邹竞示两模式的差集，分别由R1、R2中去除两模式的公共属性后的其它属性组成。该定理表明当一个关系模式分解成两个关系模式时，如果两关系模式的公共属性能够函数决定它们中的其它属性时，这样的分解具备无损联接性。例3-13设有关系模式R(A,B,C)，F={A→B},判断R的两个分解ρ1={R1(A,B),R2(A,C)}、ρ2={R1(A,B),R3(B,C)}是否具备无损连接性。解：根据定理3-5，ρ1具备无损连接性，ρ2不具备无损连接性。算法3-3无损联接的测试算法。输入：关系模式R=A1A2…An，R上的函数依赖集F，R的一个分解ρ={Ri}（i=1,2,…,k）。输出：判断ρ相对于F是否具备无损联接特性。方法：①构造一张k行n列的表格，每列对应一个属性Ai(1≤j≤n)，每行对应一个分解后的关系模式Ri(1≤i≤k)。如果Aj在Ri中，则在表格的第i行第j列上填写上aj,否则填上bij。②反复检查F的每一个函数依赖，并修改表格中的元素，其方法为(Chase过程)：取F的一个函数依赖XY，如果表中有两行在X分量上相等，在Y分量上不等，则修改Y，使在这两行上的分量相等。如果Y的分量上有一个是aj，则另一个也修改为aj，如果没有aj，则用其中的某一个bij替代另一个符号（尽量将ij改成较小的数），一直到表格不能再修改为止。③判断：若修改到最后表格中有一行是全a，即a1a2…an，则可以下结论ρ相对于F是无损联接。例3-14关系模式R(S,A,I,P)，F={S→A,{S,I}→P}，ρ={R1(SA),R2(SIP)}，检验分解是否为无损联接分解。解：通过修改发现表中第二行元素变为a1,a2,…,an,所以该分解是无损联接分解。例3-15已知关系模式R(A,B,C,D,E)及函数依赖集F={A→C,B→C,C→D,{D,E}→C,{C,E}→A},验证分解ρ={R1(A,D),R2(A,B),R3(B,E),R4(C,D,E),R5(A,E)}是否为无损联接分解。解：SAIPR1(S,A)a1a2b13b14R2(S,I,P)a1a2a3a4SAIPR1(S,A)a1a2b13b14R2(S,I,P)a1b22a3a4例3-11设关系模式SPW(SNO,SPN,SWN)。设有关系SPW,如果将SPW模式分解为SP、PW、WS,并进行SPPW及SPPWWS的自然连接,其操作数据及连接结果如图3-4。从图中可以看出,SPW中存在连接依赖[SP][PW][WS]。SPWSPPWWSSNOSPNSWNSNOSPNSPNSWNSWNSNOs1p1w2s1p1p1w2w2s1s1p2w1s1p2p2w1w1s1s2p1w1s2p1p1w1w1s2s1p1w1SPPWSPPWWS图3-4连接依赖举例(2)第五范式如果关系模式R中的每个连接依赖均由R的候选键所隐含(即在连接时,所连接的属性均为候选键),则称R属于第五范式(简称为5NF),记为R∈5NF。例3-11中,因为SPJ仅有的候选键(SNO,SPN,SWN)不是SPJ是SP、PW、WS自然连接的公共属性,所以SPJ5NF。3个投影因为多值依赖是连接依赖的特例,所以任何5NF的关系自然都符合4NF。而且任何关系模式都能无损分解成等价的5NF的关系模式的集合。关系模式如果不服从5NF,在原表与分解后的子表间进行数据插入和删除时,为保持其无损连接性(关于无损连接,请参见本章第3.4.1节),会出现一些麻烦。例3-12对于关系模式SPW(SNO,SPN,SWN),设有关系SPW(其数据如图3-5(a)所示)和它的分解子表SP、PW、WS。现要在SPW中插入1个元组(s2,p1,w1),变成图3-5(b)的形式,此时其相应的分解子表SP、PW、WS分别如图3-5(c)、图3-5(d)、图3-25(e)所示。要保证分解具有无损连接性,则在SPJ插入上述元组后,还必须插入元组(s1,p1,w1),插入后的SPW表如图3-5(f)所示。SPJ【原表】SPJ【插入(s2,p1,w1)后】SPSNOSPNSWNs1p1w2s1p1w1s1p2w2s1p2w1s2p1w2s2p1w1SNOSPNSWNs1p1w2s1p2w1s2p1w1s1p1w1SNOSPNSWNs1p1w2s1p2w1SNOSPNSWNs1p1w2s1p2w1s2p1w1SN