3NF既具有无损连接性又保持函数依赖的分解算法 严选参考

求最小函数依赖集分三步:1.将F中的所有依赖右边化为单一元素此题fd=abd-e,ab-g,b-f,c-j,cj-i,g-h;已经满足2.去掉F中的所有依赖左边的冗余属性.作法是属性中去掉其中的一个,看看是否依然可以推导此题:abd-e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性ab-g,也没有cj-i,因为c+=c,j,i其中包含i所以j是冗余的.cj-i将成为c-iF=abd-e,ab-g,b-f,c-j,c-i,g-h;3.去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去掉(X-Y),然后在F中求X+,如果Y在X+中,则表明x-是多余的.需要去掉.此题如果F去掉abd-e,F将等于ab-g,b-f,c-j,c-i,g-h,而(abd)+=a,d,b,f,g,h,其中不包含e.所有不是多余的.同理(ab)+=a,b,f也不包含g,故不是多余的.b+=b不多余,c+=c,i不多余c-i,g-h多不能去掉.所以所求最小函数依赖集为 F=abd-e,ab-g,b-f,c-j,c-i,g-h;转换为3NF既具有无损连接性又保持函数依赖的分解算法：第一步：首先用算法1求出R的保持函数依赖的3NF分解，设为q=R1,R2,Rk（这步完成后分解已经是保持函数依赖，但不一定具有保持无损连接）第二步： 设X是R的码，求出p=q R(X)第三步：若X是q中某个Ri的子集，则在p中去掉R(X)第四步：得到的p就是最终结果 例题：R(S#,SN,P,C,S,Z)F=S#SN,S#P,S#C,S#S,S#Z,P,C,SZ,ZP,ZC 第一步:求出最小FD集：F=S# SN, S# P,S# C, S#S, P,C,SZ, Z P,Z C / S# Z冗余，FD：最小函数依赖按具有相同左部分组：q=R1(S#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)R3是R2的子集，所以去掉R3q=R1(S#,SN,P,C,S), R2(P,C,S,Z) 第二步:R的主码为S，于是p=q R(X)=R1(S#,SN,P,C,S), R2(P,C,S,Z), R(S#) 第三步:因为S是R1的子集，所以从p中去掉R(S#) 第四步:p =R1(S#,SN,P,C,S), R2(P,C,S,Z)即最终结果 判别一个分解的无损连接性举例2：已知R，U=A,B,C,D,E，F=AC,BC,CD,DEC,CEA，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。解：用判断无损连接的算法来解。 构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。 根据AC，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13（取行号最小值）。 根据BC，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13（取行号最小值）。 根据CD，对上表进行处理，由于属性列C上第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。 根据DEC，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。 根据CEA，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。 通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。 求属性集合X关于函数依赖集F的闭包X+ 【算法5.1】计算属性集关于的闭包。 输入：属性集为的子集，函数依赖集。 输出：。 步骤： (1) 置初始值 A=，A*=X； (2) 如果AA*，置A=A*，否则转(4)； (3) A*，置A*=A*Z。全部搜索完,转(2)；依次检查F中的每一个函数依赖YZ，若Y (4) 输出A*，即为X+。 【例】 已知关系模式R(A,B,C,D,E)，F=ABC,BD,CE,ECB,ACB是函数依赖集，求(AB)+。 依算法2.1解： (1) 置初始值 A=，A*=AB； (2) 因AA*，置A=AB； (3) 第一次扫描F，找到ABC和BD，其左部AB，故置A*=ABCD。搜索完,转(2)； (2) 因AA*，置A=ABCD； (3) 第二次扫描F，找到CE和ACB，其左部 ABCD，故置A*=ABCDE。搜索完,转(2)；(2) 因AA*，置A=ABCDE； (3) 第三次扫描F，找到ECB，其左部 ABCDE，故置A*=ABCDE。搜索完,转(2)； (2) 因A=A*，转(4)； (4) 输出A*，即(AB)+=ABCDE。举例：已知关系模式R，U=A,B,C,D,E,G，F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG，求F的最小函数依赖集。解1：利用算法求解，使得其满足三个条件 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F=ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 去掉F中多余的函数依赖A设ABC为冗余的函数依赖，则去掉ABC，得：F1=DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG计算(AB)F1+：设X(0)=AB计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。(AB)F1+= AB不包含C，故ABC不是冗余的函数依赖，不能从F1中去掉。B设CGB为冗余的函数依赖，则去掉CGB，得：F2=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEA,CEG计算(CG)F2+：设X(0)=CG计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CGD函数依赖。故有X(2)=X(1)D=ACDG。计算X(3)：扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得到两个ACDB和DE函数依赖。故有X(3)=X(2)BE=ABCDEG，因为X(3)=U，算法终止。(CG)F2+=ABCDEG包含B，故CGB是冗余的函数依赖，从F2中去掉。C设CGD为冗余的函数依赖，则去掉CGD，得：F3=ABC,DE,DG,CA,BEC,BCD,ACDB,CEA,CEG计算(CG)F3+：设X(0)=CG计算X(1)：扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3+=ACG。(CG)F3+=ACG不包含D，故CGD不是冗余的函数依赖，不能从F3中去掉。D设CEA为冗余的函数依赖，则去掉CEA，得：F4=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEG计算(CG)F4+：设X(0)=CE计算X(1)：扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CEA=ACE。计算X(2)：扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到一个CEG函数依赖。故有X(2)=X(1)G=ACEG。计算X(3)：扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个CGD函数依赖。故有X(3)=X(2)D=ACDEG。计算X(4)：扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个ACDB函数依赖。故有X(4)=X(3)B=ABCDEG。因为X(4)=U，算法终止。(CE)F4+=ABCDEG包含A，故CEA是冗余的函数依赖，从F4中去掉。 去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于CA，函数依赖ACDB中的属性A是多余的，去掉A得CDB。故最小函数依赖集为：F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG什么是数据独立性？数据库系统如何实现数据独立性？数据独立性是指应用程序和数据之间相互独立、不受影响，即数据结构的修改不会引起应用程序的修改数据独立性包括：物理数据独立性和逻辑数据独立 性物理