第13讲模式分解

1、,第5章 关系模式的规范化设计 模式分解,数据库原理与应用,关系模式的规范化设计,所要解决的问题 什么是“好”的关系数据模式 如何评价一个好的关系数据模式 如何设计一个“好”的关系数据模式,关系模式的规范化设计,主要内容 关系模式的设计问题 关系模式规范化的基本概念和理论 关系模式分解的理论基础和算法,回顾,1NF,2NF,3NF,BCNF,去除非主属性对于候选键的部分函数依赖,去除非主属性对于候选键的传递函数依赖,去除主属性对于候选键的部分和传递函数依赖,去除不被候选键所蕴涵的非平凡的多值依赖,4NF,Armstrong公理系统 逻辑蕴涵 Armstrong公理系统推理规则 FD的逻辑蕴涵

2、函数依赖集F 的闭包F+ 属性集闭包 函数依赖集等价和最小函数依赖集 候选码及其求解方法,回顾,主要内容 模式分解的概念 分解的无损连接性和保持函数依赖性 模式分解算法,模式分解,分解的概念 设有一关系模式R（U,F），若用一关系模式的集合= R1（U1,F1），R2（U2,F2），Rn（Un,Fn） 来取代，其中U=Ui，并且没有UiUj，1i, jn，Fi是F在Ui上的投影。则关系模式的集合为R的一个分解 = R1，R2，Rn,模式分解的概念,分解的概念 F在Ui上的投影 Fi =XY | XYF+XY Ui ,模式分解的概念,思考： 设有关系模式R（A，B，C，D），F是R上成立的FD集

3、F=ABC，DB ，则 F在模式ACD上的投影为_；F在模式AC上的投影为_。,ADC,空,分解的概念,模式分解的概念,【例】R(编号，连队，连长，科目，成绩), F= 编号连队，连队连长，(编号，科目)成绩 ,【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩 ， F=学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩,分解的概念,模式分解的概念,1NF,2NF,3NF,去除非主属性对于键的部分函数依赖,去除非主属性对于键的传递函数依赖,R（学生学号，学生姓名，所在系，系主任，课程名称，成绩 ）,R1（学生学号,课程名称,成绩） R2（学生学号，学生姓名，

4、所在系，系主任）,R1（学生学号,课程名称,成绩） R3（学生学号，学生姓名， 所在系） R4（所在系，系主任）,分解的概念,模式分解的概念,R（ 学生学号，学生姓名，所在系，系主任，课程名称，成绩 学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩,1= R1 (学生学号，课程名称，成绩, （学生学号，课程名称）成绩) , R3 (学生学号，学生姓名，所在系, 学生学号学生姓名，学生学号所在系) , R4 (所在系，系主任, 所在系系主任),分解的概念,模式分解的概念,R（ 学生学号，学生姓名，所在系，系主任，课程名称，成绩 学生学号学生姓名，学生学号所在系，所在系系

5、主任，（学生学号，课程名称）成绩,2=R1（学生学号）, R2（学生姓名）, R3（所在系）, R4（系主任）, R5（课程名称）, R6（成绩） U=Ui，并且没有UiUj，1i， jn Fi是F在Ui上的投影不存在非平凡的函数依赖。,不具有无损连接性,分解的概念,模式分解的概念,R（ 学生学号，学生姓名，所在系，系主任，课程名称，成绩 学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩,3= R1 (学生学号，课程名称，成绩, （学生学号，课程）成绩) , R2 (学生学号，学生姓名，所在系, 学生学号学生姓名，学生学号所在系) , R3 (学生学号，系主任, 学生

6、学号系主任) U=Ui，并且没有UiUj，1i, jn Fi是F在Ui上的投影。,没有保持函数依赖,分解的概念 一个关系模式的分解并不是唯一的。 理想的分解应该是既具有无损连接性又保持函数依赖，这样的分解是等价分解。 等价分解 分解具有无损连接性，即数据等价 分解保持函数依赖，即语义等价 分解既具有无损连接性又保持函数依赖，即数据等价并且语义等价,模式分解的概念,无损连接分解,无损连接分解 设= R1（U1,F1），Rk（Uk,Fk）是R（U,F）的一个分解，r是R（U,F）的一个关系，则 Ri (r)=t.Ui|tr为r在子模式Ri上的投影， m(r)=R1(r)R2(r) Rn(r)是r在

7、中各关系模式上投影的连接。 若对R的任何一个关系r均有r= m(r)成立，则称分解具有无损连接性。,分解是无损分解,算法：检验一个分解是否是无损分解 输入： 关系模式R（U，F）， U=A1,A2 ,An； R上的分解= R1（U1,F1）, R2（U2,F2）, ,Rk（Uk,Fk） 。 设F是最小函数依赖集。 输出： 判断相对于F是否具有无损分解特性。,无损连接分解,无损连接分解,检验一个分解是否无损的算法 步骤,1）建立一张k行n列的表，每行对应分解中的一个关系模式Ri，每列对应一个属性Aj，若属性AjUi，则在i行j列处填aj，否则填bij。,A1U1,An Uk,无损连接分解,【例】

8、设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,初始状态,1）建立一张k行n列的表，每行对应分解中的一个关系模式Ri，每列对应一个属性Aj，若属性AjUi，则在i行j列处填aj，否则填bij。,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,初始状态,2）把表格看成模式R的一个关

9、系，反复检查F中的每个函数依赖在表格中是成立，若不成立，则修改表格中的值。,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,初始状态,2）对每一形如XY 的FD做如下操作： 检查X中的属性所对应的列，找出X相等的行，将这些行中对应的Y中的属性列所对应的符号改为一致。即若其中之一为aj，则都改成aj；否则，将其都改成这些列中行号最小的符号bij。,对F的一次扫描,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=

10、AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,

11、AC BC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。 =R1(AD)，R2

12、(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD DEC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。 =R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD D

13、EC,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD DEC CEA,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD DEC CEA,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC

14、，CEA。 =R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,AC BC CD DEC CEA,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,3）若表有变化，则返回步骤2)，否则算法终止。 若某次修改后，有一行全为a1,a2,an，则算法结束。,无损连接分解,【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)

15、，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。,定理： 为无损连接分解的充分必要条件是算法终止时，表中有一行为a1,a2,an。,判断一个关系模式分解成两个关系模式是否为无损分解的方法 定理： 设=R1(U1)，R2(U2)是R(U)的一个分解，则为无损分解的充分必要条件为 （U1U2）（U1-U2）F+ 或 （U1U2）（U2-U1）F+,无损连接分解,无损连接分解,证明：用检验分解无损算法构造的如下初始表。表中a和b的下标都已省略 充分性 因为（U1U2）（U1-U2），则算法8-2终止时，对应于(U1-U2)的bbb全为a，因此，=

16、R1(U1)，R2(U2)是R（U）的一个无损连接分解。 必要性 若=R1(U1)，R2(U2)是R（U）的一个无损连接分解，则算法终止时，表中必有一行全为a，假设R2行全为a，则（U1-U2）所对应的元素都应变为a。由于在表中，只有（U1U2）所对应的列的元素相同。设U1-U2中有一个属性Ai，则根据算法将Ai所对应的元素都改为a，则必有SAiF+，且S（U1U2）。根据自反律有（U1U2）S；根据传递律有（U1U2）Ai，即Ai(U1U2)+。所以（U1-U2） (U1U2)+ 即（U1U2） (U1U2)是(U1U2)所对应的元素都变为a的必要条件。,【例5-13】 设有关系模式R（U，

17、F），U=A,B,C,D,E，F=A BC，CDE，B D，E A 。 R的两个分解为1= R1(A,B,C)，R2(A,D,E)，2=R1(A,B,C)，R2(C,D,E)。试判断1、2是否为无损分解。,无损连接分解,解：对于分解1= R1（A,B,C），R2（A,D,E） 因为U1U2=A，U1-U2=BC，且A BCF 所以U1U2U1-U2，1为无损分解。 对于分解2= R1（A,B,C），R2（C,D,E） 因为U1U2=C，U1-U2=AB，U2-U1=DE， 且C AB F+ ，C DE F+ （如何来判断？） 即U1U2U1-U2F+ 或U1U2U2-U1F+， 所以2为有损分

18、解。,保持函数依赖分解,保持函数依赖 对于关系模式R（U,F），设= R1（U1,F1），R2（U2,F2）,Rn（Un,Fn） 是R的一个分解，若F+=(Fi)+，则称分解保持函数依赖。,引理5.3 F+=G+的充分必要条件是FG+且G F+ 判断分解是否保持函数依赖的方法： 令G=Fi，即只需判断FG+且GF+是否成立。 而要判定FG+或GF+ ，只需逐一对F或G中的函数依赖XY考察Y是否属于XG 或X就行了。,分解的保持函数依赖性,【例】 设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解=R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。,解答： 1）要先根据分解

19、的定义，确定分解后的函数依赖，然后再加以判断。利用Armstrong公理的传递律，可将分解为,= R1(A,B，AB， BA), R2(B,C，BC， CB), R3(C,D，CD， DC),分解的保持函数依赖性,【例】 设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解 =R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。,解答： 2）判断DA是否为G所覆盖即可 G= AB，BA ，BC，CB ，CD ，DC 求得D=A，B，C，D 因为A D ，所以DAG+，故保持函数依赖。,模式分解算法,关系模式的规范化就是将低一级的关系模式分解为若干高一级的范式。 对数据库应用设

20、计而言，违反数据等价或依赖等价的分解很难说是一个好的模式设计。 在函数依赖范畴内，希望分解的结果能达到BCNF，并且能保持无损连接性和函数依赖性。,模式分解算法,这三个目标有时不能同时满足，一般只能做到如下几点： 若分解保持函数依赖，那么模式总可以分解到3NF，但不一定能达到BCNF； 若分解具有无损连接性，那么模式一定能分解到BCNF； 若分解既保持函数依赖，又具有无损连接性，那么模式可以分解到3NF，但不一定能达到BCNF。,模式分解算法,关于模式分解的几个重要事实：,模式分解算法,数据库设计者在设计关系数据库时，应权衡利弊，尽可能使数据库模式保持最好的特性。 一般尽可能设计成BCNF模式

21、集； 如果设计成BCNF模式集达不到保持函数依赖的特性，那么只能降低要求，设计成3NF模式集，以求达到保持依赖和无损分解的特性。,模式分解算法,分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法 输入：关系模式R（U，F） 输出：R的一个具有无损连接性且保持函数依赖的满足3NF的分解,模式分解算法,分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法 1）求F的最小覆盖Fm，令F= Fm。 2）若有XAF，且XA=U，输出=R，算法结束。 3）对F按具有相同左部的原则分组，即F中所有形如XA1,XA2,，XAn的函数依赖为一组。每一分组中包含的函数依赖子集Fi所涉及的全部属性组成

22、一个属性集Ui。若UiUj（ij）就去掉Ui。 4）将R中不在F中出现的属性，单独构成一属性集Ui。,模式分解算法,分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法 5）将Ui及F在Ui上的投影Fi构成一个关系模式Ri(Ui,Fi)，由于F是最小函数依赖集，Ri(Ui,Fi)一定是属于以X为候选键的3NF。并且Fi一定被Fi所包含，因此各关系模式Ri(Ui,Fi) 组成的分解是保持函数依赖的。 6）若某个Ui中已包含R中的候选键，则该分解也就具有无损连接性。若Ui中均不包含R中的候选键，则在分解的结果上再并入一个关系模式Rk(K,FK)，其中K为R的某一候选键，FK为F在K上的投影。

23、,模式分解算法,【例】关系模式R（U，F），其中U= E，G，H，I，J ，F= EI，JI，IG，GHI，IHE ，将R分解为3NF，并使之具有无损连接性和保持函数依赖特性。,解答： （1）F已为最小函数依赖集。 （2）没有类似XAF，且XA=U的函数依赖。 （3）对F按具有相同左部的原则分组，得到每组所对应的属性集U1= EI、U2= IJ、U3= GI、U4= GHI、U5= EHI。因为U1 U5、U3 U4，所以去掉U1、U3。 （4）R中的所有属性均在F中出现。,模式分解算法,【例】关系模式R（U，F），其中U= E，G，H，I，J ，F= EI，JI，IG，GHI，IHE ，将R

24、分解为3NF，并使之具有无损连接性和保持函数依赖特性。,解答： （5）将Ui及F在Ui上的投影Fi构成一个关系模式Ri（Ui,Fi），则分解=R1（ I,J , JI ），R2（G,H,I，IG,GHI），R3（E,H,I， EI,IHE ）保持函数依赖，且分解后的每个关系模式均为3NF。 （6）可确定R的一个候选键HJ，由于Ui 均不包含HJ，则=R4（H,J），因此将R分解为= R1（ I,J , JI ），R2（G,H,I，IG,GHI），R3（E,H,I， EI,IHE ），R4（H,J）。分解具有无损连接性，即为所求。,模式分解算法,算法：分解关系模式为满足BCNF的一个无损分解 输

25、入：关系模式R（U，F） 输出：R的一个为BCNF的无损连接分解。,模式分解算法,算法：分解关系模式为满足BCNF的一个无损分解 方法： 1）令=R。 2）检查中每个关系模式是否均属于BCNF。若是，则算法终止。 3）对中每一个不满足BCNF的关系模式S，做如下操作 S中必有不满足BCNF的非平凡的函数依赖XA，其中X不是S的候选键。 对S进行分解，分解为S1（XA）和S2（US-A），其中US为S的属性集，用S1和S2取代中的S。返回步骤(2)。 由于U中属性有限，因而有限次循环后算法一定终止。,模式分解算法,【例】有关系模式R，U=C,T,H,I,S,G，F=CSG, CT,TH I,HI

26、C,HSI，将R分解成具有无损连接的BCNF。,解答： 1）令=R 2）检查中每个关系模式是否均属于BCNF； H、S是L类属性，且HS F+ = U，所以HS为 R的一个候 选键。 由此可判断中关系模式R不属于BCNF。,模式分解算法,【例】有关系模式R，U=C,T,H,I,S,G，F=CSG, CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。,解答： 3）考虑CSG，CS不是R的候选键，将R分解为 =R1（CSG，CSG）， R2（CTHIS， CT,TH I,HIC,HSI ）； R1是BCNF，R2不是(R2的候选键仍为HS )，需对R2进一步分解。,模式分解算法,【

27、例】有关系模式R，U=C,T,H,I,S,G，F=CSG, CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。,解答： 3）对于 R2（CTHIS， CT,TH I,HIC,HSI ） 考虑CT，C不是R2的候选键，将R2分解为 =R21（CT，CT）， R22（CHIS，CH I,HIC,HSI ）； (CT，TH I CH I ) R21是BCNF，R22不是(R22的候选键仍为HS )，需对R22进一步分解。,模式分解算法,【例】有关系模式R，U=C,T,H,I,S,G，F=CSG, CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。,解答： 对于R22（

28、CHIS，CH I,HIC,HSI ） 考虑CH I，CH不是R22的候选键，将 分解为 =R221（CHI ， CH I，HIC ）， R222（CHS，HSC ）； R221 和R222均是BCNF，不需进一步分解。,模式分解算法,【例】有关系模式R，U=C,T,H,I,S,G，F=CSG, CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。,解答： 因此，将R分解为=R1（CSG ，CSG ），R21（CT，CT ），R221（CHI ， CH I，HIC ），R222（CHS，HSC ），即为所求。 在关系模式R222（CHS，HSC）中， 包含R的一个候选键HS ，利

29、用算法5.3可验证分解具有无损连接性。,模式分解算法,【例】关系模式R(U,F)中U=ABCDEG, F=BGC, BDE, DGC, ADGBC, AGB, BD，完成下列问题： （1）求F的最小函数依赖集； （2）求解R的候选键； （3）判断R最高满足第几范式； （4）若R不满足3NF，将R分解为无损且保持函数依赖的3NF。,模式分解算法,【例】关系模式R(U,F)中U=ABCDEG, F=BGC, BDE, DGC, ADGBC, AGB, BD。 （1）求F的最小函数依赖集；,解答： 函数依赖右边属性单一化 将ADGBC分解为ADGB、ADGC， AGB，DGC， ADGB、ADGC为

30、冗余依赖 F=BGC, BDE, DGC, AGB, BD。,模式分解算法,【例】关系模式R(U,F)中U=ABCDEG, F=BGC, BDE, DGC, ADGBC, AGB, BD。 （1）求F的最小函数依赖集；,解答： F=BGC, BDE, DGC, AGB, BD 去掉冗余的函数依赖 判断BGC是否冗余： 令G= BDE, DGC, AGB, BD BG= BGDEC; C BG，BGC冗余； F= BDE, DGC, AGB, BD 同理， 判断其他函数依赖不冗余，F不变。,模式分解算法,【例】关系模式R(U,F)中U=ABCDEG, F=BGC, BDE, DGC, ADGBC, AGB, BD。 （1）求F的最小函数依赖集；,解答： F= BDE, DGC, AGB, BD 去掉各函数依赖左部冗余的属性。 本题需考虑BDE, DGC, AGB。 对于BDE，在决定因素中去掉B, DE，DF+D,不包含E，B不冗余，F不变。 在决定因素中去掉D, BE，BF+BDE, 包含E，D多余。所以用BE代替BDE