模式分解精品课件

1、模式分解第1页，共67页，2022年，5月20日，6点25分，星期四最小依赖集第2页，共67页，2022年，5月20日，6点25分，星期四1）考查AB，去掉它，计算A+=AC，不包含B，不能去掉2）考查 B A，去掉它，计算BB C A，包含A，可去掉它3）考查 B C，去掉它，计算BB，不包含C，不能去掉4）考查A C，去掉它，计算AA B C，包含C，可去掉它5）考查 C A，去掉它，计算CC，不包含A，不能去掉1 2 3 4 5第3页，共67页，2022年，5月20日，6点25分，星期四求解关系模式的候选码属性分类L类：只出现在函数依赖的左边的属性R类：只出现在函数依赖的右边的属性N类：

2、在函数依赖的两边均未出现的属性LR类：出现在函数依赖的两边的属性第4页，共67页，2022年，5月20日，6点25分，星期四求解关系模式的候选码对于给定的关系模式R及其函数依赖集F如果X是L或N类属性，则X必为R的任一候选码的成员如果X是R类属性，则X必不在任何候选码中如果X是L和N类组成的属性组，且X+包含了全部属性，则X是R的唯一候选码第5页，共67页，2022年，5月20日，6点25分，星期四前例例：关系模式CTHRSG, 若最小依赖集为F=C T, HR C,CS G,HS R,HT R, 候选关键字为HS？解： L、N类属性为HS，LR属性为CTR HS+=HS RCTG，包含全部属

3、性，所以为唯一候选码第6页，共67页，2022年，5月20日，6点25分，星期四函数依赖图FDG用有向图表示的函数依赖，如XY即X Y第7页，共67页，2022年，5月20日，6点25分，星期四L或N类属性有E和C, LR类属性ADB，令X=EC,(EC)+=U,EC为R的唯一候选码。对左边为单属性的函数依赖集求所有候选码(1) 求F的最小依赖集F(2) 作出函数依赖图FDG(3) 从FDG图中找出无入边的属性集X(4) 察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5) 从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码第8页，共6

4、7页，2022年，5月20日，6点25分，星期四IBOQSD第9页，共67页，2022年，5月20日，6点25分，星期四ZWYXSDIBOQ第10页，共67页，2022年，5月20日，6点25分，星期四算法：对左边为多属性的函数依赖集求所有候选码 (1) 将R所有属性分为L,R,N,LR四类，并令X代表L,N两类，令Y代表LR类。(2) 求X+，若X+包含R全部属性，则X即为R的唯一候选码，结束，否则转下一步。(3) 在Y中取一属性A，求(XA)+,若它包含R的全部属性，则转下一步，否则换一个属性重试，直至试完所有Y中的属性。(4) 若已找出所有候选码，则结束，否则在Y中依次取两个、三个、，求

5、它们的属性闭包，直至其闭包包含R的全部属性。属于N-P完全问题 (一类直观上难解可又找不出方法来证明它们的确难解的计算问题)多属性下求解候选码的充分条件第11页，共67页，2022年，5月20日，6点25分，星期四第六章 关系数据理论6.1 数据依赖6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解第12页，共67页，2022年，5月20日，6点25分，星期四6.4 模式的分解把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的。只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。第13页，共67页，2022年，5月20日，6点25分，星期四关系模式分解的标准三

6、种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性第14页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）定义6.16 关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影第15页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）定义6.16 关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi

7、为 F在 Ui 上的投影。定义6.17 函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影第16页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种 。第17页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS

8、B 95005 PH B 第18页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）1. SL分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc)第19页，共67页，2022年，5月20日，6点25分，星期四分解后的关系为： SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 第20页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）分解后的数据库丢失了许多信息 例如无法查询95001学生所在系或所在宿舍。 如果分解后的关系可以通过自然连

9、接恢复为原来的关系，那么这种分解就没有丢失信息第21页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）2. SL分解为下面二个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的关系为： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B 第22页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 950

10、03 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 第23页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）NLDL比原来的SL关系多了3个元组 无法知道95002、95004、95005 究竟是哪个系的学生元组增加了，信息丢失了第24页，共67页，2022年，5月20日，6点25分，星期四第三种分解方法3. 将SL分解为下面二个关系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的关系为： 第25页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）ND NL Sno Sdep

11、t Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B 第26页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续） ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与SL关系一样，因此没有丢失信息。第27页，共67页，2022年，5月20日，6点25分，星期四具有无损连接性的模式分解关系模式R的一个分解 = R1，R2， ，Rn,若R与R

12、1、R2、Rn自然连接的结果相等，则称关系,模式R的这个分解具有无损连接性（Lossless join）具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题第28页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续） 第三种分解方法具有无损连接性 问题: 这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖SdeptSloc， 没有投影到关系模式ND、NL上 第29页，共67页，2022年，5月20日，6点25分，星期四保持函数依赖的模式分解设关系模式R被分解为若干个关系模式 R1，R2，Rn （其中U=U1U2Un，且不存

13、在Ui Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency）。第30页，共67页，2022年，5月20日，6点25分，星期四保持函数依赖的模式分解第31页，共67页，2022年，5月20日，6点25分，星期四例 子R(A,B,C), F=AB, C B分解1=(A,B,AB), (A,C)分解2=(A,B, AB), (B,C, C B)计算分解1,2中3个模式的闭包FAB：A+=AB,B+=B,AB+=AB, 则对AB的分解有函数依赖ABAC：A+=

14、A,C+=C,AC+=AC, 则对AC的分解没有函数依赖BC：B+=B,C+=CB,BC+=BC, 则对BC的分解只有函数依赖CB分解1：只有AB，显然，分解1不具有依赖保持性分解2：保留了所有函数依赖，具有依赖保持性分析两种分解的依赖保持性？第32页，共67页，2022年，5月20日，6点25分，星期四第四种分解方法SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc将SL分解为下面二个关系模式： ND(Sno, Sdept) DL(Sdept, Sloc) 这种分解方法就保持了函数依赖。 第33页，共67页，2022年，5月20日，6点25分

15、，星期四模式的分解（续）如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。第34页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）第一种分解方法既不具有无损连接性，也未保持函 数依赖，它不是原关系模式的一个等价分解 SN(Sno)， SD(Sdept)， SO(Sloc)第二种分解方法保持了函数依赖，但不具有无损连 接性。 NL(Sno, Sloc)， DL(Sd

16、ept, Sloc)SL（Sno， Sdept， Sloc）F= SnoSdept,SdeptSloc,SnoSloc第35页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）第三种分解方法具有无损连接性，但未持函数依赖 ND(Sno, Sdept)， NL(Sno, Sloc)第四种分解方法既具有无损连接性，又保持了函数依赖 ND(Sno, Sdept)， DL(Sdept, Sloc)SL（Sno， Sdept， Sloc）F= SnoSdept,SdeptSloc,SnoSloc第36页，共67页，2022年，5月20日，6点25分，星期四分解算法算法6.2 判别一个

17、分解的无损连接性算法6.3 （合成法）转换为3NF的保持函数依赖的分解。算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解算法6.5 转换为BCNF的无损连接分解（分解法）算法6.6 达到4NF的具有无损连接性的分解P196 图5 .11第37页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性算法6.2(1)构造初始表：构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。 如果属性Aj属于关系模式Ri, 则在表的第一i行第j列置符号aj，否则置符号bij 。(2)根据F中的函数依赖修改表内容： 考察F中的每个函数依赖XY

18、,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行， 则修改这些行，则使这些行上属性组Y所在的列上元素相同。 修改规则是：如果y所在的要修改的行中有一个为aj， 则这些元素均变成aj；否则改动为bmj（其中m为这些行的最小行号）。第38页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性注意：若某个bij被改动，则该列中凡是与bij相同的符号均做相同的改动。 循环地对F中的函数依赖进行逐个处理，直到发现表中有一行 变为a1,a2,an或不能再被修改为止。 (3)判断分解是否为无损联接： 如果通过修改，发现表中有一行变a1,a2, an, 则

19、分解是无损联接的，否则分解不具有无损联接性。第39页，共67页，2022年，5月20日，6点25分，星期四ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后结果：R1R2R3R1R2R3122例子：判断无损连接性第40页，共67页，2022年，5月20日，6点25分，星期四ABCDEa1a2a3a3a4a4a5ABCDEa1a2a3a4a5a3a4a5a4a5初始表：最后结果：R1R2R3R1R2R3122简易方法：只画关注数据第41页，共67页，2022年，5月20

20、日，6点25分，星期四判别一个分解的无损连接性已知关系模式R(ABCDE)及函数依赖集F=AC,BC,CD,DEC,CEA 验证分解=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)是否为无损联接。 第42页，共67页，2022年，5月20日，6点25分，星期四通过修改发现表中第三行元素变为a1,a2,an,分解是无损联接。 第43页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性定理：如果R的分解为r =R1，R2，F为R所满足的函数依赖集合，分解r具有无损联接性的充要条件是：R1 R2 （R1R2）F+或R1 R2 （R2R1） F+ 第

21、44页，共67页，2022年，5月20日，6点25分，星期四模式的分解（续）定义6.16 关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影第45页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性关系模式R(A,B,C,D) 函数依赖集F=AB,CD,=R1(AB)，R2(CD)， 求R1,R2 ,并检验分解的无损联接性和分解的函数依赖保持性。 解：F1=R1(F)=AB, F2=R2(F)=

22、CD，分解为 R1(AB,AB),R2(CD,CD) U1U2=ABCD=, U1-U2=AB, U2-U1=CD, AB F+, CD F+, 所以不是无损分解。 第46页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性例：设R=ABC，F=AB，则1=R1(AB)， R2(AC)和 2=R1(AB)， R3(BC)是否具有无损联接性 。第47页，共67页，2022年，5月20日，6点25分，星期四判别一个分解的无损连接性例 将R=(ABCD,AB,BC,BD,CA)分解为关于U1=AB，U2=ACD两个关系，求R1、R2， 并检验分解的无损联接性和分解的函数依

23、赖保持性。 解：F1=R1(F)=AB,BA, F2=R2(F)=AC,CA,AD R1=(AB,AB,BA)R2=(ACD,AC,CA,AD) U1U2=ABACD=A,U1-U2=AB-ACD=B,ABF+,所以是无损连接分解； 第48页，共67页，2022年，5月20日，6点25分，星期四（F1UF2)+=AB,BA,AC,CA,AD +AB,BC,BD,CA +=F+, 所以是函数依赖保持性。第49页，共67页，2022年，5月20日，6点25分，星期四练习：已知关系模式R(CITY,ST,ZIP), F=(CITY,ST)ZIP,ZIPCITY， 以及R上的一个分解=R1, R2,

24、R1 =ST,ZIP, R2 =CITY,ZIP， 求R1,R2 ,并检验分解的无损联接性和分解的函数依赖保持性。 答案 R1=(ST,ZIP,) R2=(CITY,ZIP,ZIPCITY)， 是无损分解,但不具有函数依赖保持性。 第50页，共67页，2022年，5月20日，6点25分，星期四(1)极小化处理F(2)如果R中的某些属性在F的所有依赖的左边和右边都不出现，那么这些属性可以从R中分出去，单独构成一个关系模式。 (3)如果F中有一个依赖XA有XA=R，则=R，转(4) (4)对于F中每一个XA，构成一个关系模式XA，如果F有有XA1，XA2.XAn,则可以用模式XA1A2.An代替n

25、个模式XA1,XA2.XAn; (5)分解结束。 算法6.3分解成3NF模式集（合成法）保持函数依赖一般情况下，只要用F中所有函数依赖左右两边的属性组成各个关系子模式，函数依赖中不涉及的属性组成一个关系。第51页，共67页，2022年，5月20日，6点25分，星期四具有依赖保持性的3NF分解例子例1：SL(Sno, Sdept, Sloc)F= SnoSdept, SdeptSloc, SnoSlocF=SnoSdept, SdeptSloc，因为去掉SnoSloc，Sno+=Sno Sdept Sloc, 包含Sloc, 则可去掉具有依赖保持性的3NF分解为Sno ，Sdept和Sdept

26、，Sloc例2：关系模式CTHRSG, 若最小依赖集为F=C T, HR C,CS G,HS R,HT R具有依赖保持性的3NF分解为CT,CHR,CSG,HSR,HTR第52页，共67页，2022年，5月20日，6点25分，星期四分解成3NF模式（保持函数依赖又无损连接）使用合成法将RU,F分解为= 设X是R的码，令=R*X,FX 如有某个Ui，使得：X Ui，则从中去掉R*X,FX 即所求 第53页，共67页，2022年，5月20日，6点25分，星期四例 子例：关系模式CTHRSG, 若最小依赖集为F=C T, HR C,CS G,HS R,HT R, 候选关键字为HS如前例，具有依赖保持

27、性的3NF分解为CT,CHR,CSG,HSR,HTR则具有无损连接和依赖保持性的3NF分解为CT,CHR,CSG,HSR,HTR, HSHS和HSR重复，则为CT,CHR,CSG,HSR,HTR 第54页，共67页，2022年，5月20日，6点25分，星期四1、设U=A，B，C，D，E，F F=ABCDE,DEABC,ABD,EC,DEF 求最小依赖集，并使用算法分解到3NF解： F=ABCD，ABCE，DEA，DEB，DEC， ABD，EC，DEF ABD， ABCD 去掉ABCD 又 EC， DEC 去掉DEC Fm=ABCE,ABD,EC,DEA,DEB,DEF 其码：ABC，ABE，D

28、E 按算法1得到： =R1ABCE，ABCE，R2（ABD，ABD）， R3，R4例 题第55页，共67页，2022年，5月20日，6点25分，星期四例 题其中，(1)R3的属性包含在R1关系的属性中，去掉R3 R2的属性包含在R4关系的属性中，去掉R2；=R1ABCE，ABCE，R2（ABD，ABD）， R3，R4 (2)由于R*ABC，FABC，R*DE，FDE， R*ABE，FABE皆是中的某个Ui的子集，因此全部去掉。最终的分解为：=R1ABCE，ABCE，EC，R2故上面的分解既保持函数依赖又无损连接。 第56页，共67页，2022年，5月20日，6点25分，星期四分解成BCNF模式

29、集的算法无损联接分解成BCNF模式集的算法： (1)置初值=R; (2)如果中所有关系模式都是BCNF，则转(4); (3)如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖集XA有X不是S的键，且A不属于X，设S1=XA，S2=S-A，用分解S1,S2代替S，转(2)； (4)分解结束。输出。Notice:重点在于(3)步，判断哪个关系不是BCNF，并找到X和A。第57页，共67页，2022年，5月20日，6点25分，星期四分成BCNF设关系模式R，R的函数依赖关系F=AD，ED，DB，BCD，DCA请将该关系分解到BCNF。 解：找到候选键： ED ECDC .(1)DCA E

30、CA .(2)DB DCBCB ECB .(3) 由(1)(2)(3) 得ECABD EC为键，这里关系键仅有一个(在右边有E和C未出现键中必包含EC为键) 主属性EC, 非主属性A,B,D 。第58页，共67页，2022年，5月20日，6点25分，星期四分成BCNF（无损） 直接分解到BCNF AD，A BCE R1(AD)，R2(ABCE) 在R2中 EB 分解：R21(EB)，R22(EAC) R分解为R1(AD)，R2(EB)，R3(EAC) 分解不是唯一的。第59页，共67页，2022年，5月20日，6点25分，星期四分解算法解P196 图5 .11若要求分解具有无损连接性，那么模式分解一定能够达到4NF。若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF。若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF。第60页，共67页，2022年，5月20日，6点25分，星期四泛关系假设 “假设已知一个模式S，它仅由单个关系模式组成，问题是要设计一个模式SD，它与S等价，但在某些方面更好一些”。从一个关系模式出发，而不是从一组关系模式出发实行分解。“等价”的定义也是一组关系模式与一个关系模式的“等价”。第61页，共67页，2022年，5月20日，6点25分，星期四小结(续