模式分解的例子.doc

模式分解、最小函数依赖集函数依赖的公理系统： 设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下： 自反律：如果YXU,则XY在R上成立。 增广律：如果XY为F所蕴涵，ZU，则XZYZ在R上成立。(XZ表示XZ，下同) 传递律：如果XY和YZ在R上成立，则XZ在R上成立。以上三条为Armstrong公理系统 合并律：如果XY和XZ成立，那么XYZ成立。 伪传递律：如果XY和WYZ成立，那么WXZ成立。 分解律：如果XY和ZY成立，那么XZ成立。这三条为引理注意： 函数依赖推理规则系统(自反律、增广律和传递律)是完备的。 由自反律所得到的函数依赖均是平凡的函数依赖。模式分解的几个重要事实： 若只要求分解具有“无损连接性”，一定可以达到4NF； 若要求分解要“保持函数依赖”，可以达到3NF，但不一定能达到BCNF； 若要求分解既要“保持函数依赖”，又要具有“无损连接性”，可以达到3NF，但不一定能达到BCNF；试分析下列分解是否具有无损联接和保持函数依赖的特点：设R(ABC)，F1=AB 在R上成立，1=AB,AC。首先，检查是否具有无损联接特点：第1种解法-算法4.2:ABCABa1a2b13ACa1b22a3ABCa1a2b13a1a2a3(1) 构造表(2)根据AB进行处理结果第二行全是a行，因此分解是无损联接分解。第2种解法:(定理4.8)R1(AB)R2(AC)=AR2- R1=BAB,该分解是无损联接分解。然后，检查分解是否保持函数依赖R1（F1）=AB，以及按自反率推出的一些函数依赖R2（F1）=按自反率推出的一些函数依赖F1被R1（F1）所蕴涵，所以该分解保持函数依赖。保持函数依赖的模式分解一、转换成3NF的保持函数依赖的分解算法：=R1,R2,.,Rk是关系模式R的一个分解，U=A1,A2,.,An，F=FD1,FD2,.,FDp，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下：对R的函数依赖集F进行极小化处理（处理后的结果仍记为F）；找出不在F中出现的属性，将这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U；若有XAF，且XA=U，则=R，算法终止；否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(ij)，就去掉Ui。由于经过了步骤，故，于是构成的一个保持函数依赖的分解。并且，每个Ri(Ui,Fi)均属于3NF且保持函数依赖。例1：关系模式R，其中U=C,T,H,I,S,G，F=CSG,CT,THI,HIC,HSI，将其分解成3NF并保持函数依赖。解：根据算法进行求解(一)计算F的最小函数依赖集利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性，故不用分解。去掉F中多余的函数依赖A设CSG为冗余的函数依赖，则去掉CSG，得：F1=CT,THI,HIC,HSI计算(CS)F1+：设X(0)=CS计算X(1)：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个CT函数依赖。故有X(1)=X(0)T=CST。计算X(2)：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X(2)=X(1)。算法终止。(CS)F1+= CST不包含G，故CSG不是冗余的函数依赖，不能从F1中去掉。B设CT为冗余的函数依赖，则去掉CT，得：F2=CSG,THI,HIC,HSI计算(C)F2+：设X(0)=C计算X(1)：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故CT不是冗余的函数依赖，不能从F2中去掉。C设THI为冗余的函数依赖，则去掉THI，得：F3=CSG,CT,HIC,HSI计算(TH)F3+：设X(0)=TH计算X(1)：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故THI不是冗余的函数依赖，不能从F3中去掉。D设HIC为冗余的函数依赖，则去掉HIC，得：F4=CSG,CT,THI,HSI计算(HI)F4+：设X(0)=HI计算X(1)：扫描F4中的各个函数依赖，没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HIC不是冗余的函数依赖，不能从F4中去掉。E设HSI为冗余的函数依赖，则去掉HSI，得：F5=CSG,CT,THI,HIC计算(HS)F5+：设X(0)=HS计算X(1)：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HSI不是冗余的函数依赖，不能从F5中去掉。即：F5=CSG,CT,THI,HIC,HSI去掉F5中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）没有发现左边有多余属性的函数依赖。故最小函数依赖集为：F=CSG,CT,THI,HIC,HSI(二)由于R中的所有属性均在F中都出现，所以转下一步。(三)对F按具有相同左部的原则分为：R1=CSG，R2=CT，R3=THI，R4=HIC，R5=HSI。所以=R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)。二、转换成3NF的保持无损连接和函数依赖的分解算法：输入关系模式R和R的最小函数依赖集F。输出R的一个分解=R1,R2,.,Rk，Ri为3NF，且具有无损连接又保持函数依赖的分解。步骤根据算法1求出保持函数依赖的分解=R1,R2,.,Rk判断分解是否具有无损连接性，若有，转令=X，其中X是R的候选关键字（候选码）；输出例2：关系模式R，其中：U=C,T,H,I,S,G，F=CSG,CT,THI,HIC,HSI，将其分解成3NF并保持无损连接和函数依赖。解：根据例1，得到3NF并保持函数依赖的分解如下：=R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)。判断是否是无损连接构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。根据CT，对上表的处理结果如下表。根据HIC，对上表的处理结果如下表。根据CSG，对上表的处理结果如下表。根据CT，对上表的处理结果如下表。通过上述的修改，使第五行成为a1a2a3a4a5a6，则算法终止。且分解具有无损连接性。三、转换成BCNF的保持无损连接的分解算法：输入关系模式R和R的函数依赖集F。输出R的一个分解=R1,R2,.,Rk，Ri为BCNF，且具有无损连接的分解。步骤令=R，根据算法1求出保持函数依赖的分解=R1,R2,.,Rk若中的所有模式都是BCNF，转若中有一个关系模式Ri不是BCNF，则Ri中必能找到一个函数依赖XA，且X不是Ri的候选码，且A不属于X，设Ri1(XA)，Ri2(Ri-A)，用分解Ri1,Ri2代替Ri，转；输出例3：关系模式R，其中：U=C,T,H,I,S,G，F=CSG,CT,THI,HIC,HSI，将其分解成BCNF并保持无损连接。解：令=R(U,F)。中不是所有的模式都是BCNF，转入下一步。分解R：R上的候选关键字为HS（因为所有函数依赖的右边没有HS）。考虑CSG函数依赖不满足BCNF条件（因CS不包含候选键HS），将其分解成R1(CSG)、R2(CTHIS)。计算R1和R2的最小函数依赖集分别为：F1=CSG，F2=CT,THI,HIC,HSI。分解R2：R2上的候选关键字为HS。考虑CT函数依赖不满足BCNF条件，将其分解成R21(CT)、R22(CHIS)。计算R21和R22的最小函数依赖集分别为：F21=CT，F22=CHI,HIC,HSI。其中CHI是由于R22中没有属性T且CT,THI。分解R22：R22上的候选关键字为HS。考虑CHI函数依赖不满足BCNF条件，将其分解成R221(CHI)、R222(CHS)。计算R221和R222的最小函数依赖集分别为：F221=CHI,HIC，F222=HSC。其中HSC是由于R222中没有属性I且HSI,HIC。由于R221上的候选关键字为H，而F221中的所有函数依赖满足BCNF条件。由于R222上的候选关键字为HS，而F222中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如：=R1(CSG),R21(CT),R221(CHI),R222(CHS)例4：关系模式R，其中：U=A,B,C,D,E，F=AC,CD,BC,DEC,CEA，将其分解成BCNF并保持无损连接。解：令=R(U,F)。中不是所有的模式都是BCNF，转入下一步。分解R：R上的候选关键字为BE（因为所有函数依赖的右边没有BE）。考虑AC函数依赖不满足BCNF条件（因A不包含候选键BE），将其分解成R1(AC)、R2(ABDE)。计算R1和R2的最小函数依赖集分别为：F1=AC，F2=BD,DED,BEA。其中BD是由于R2中没有属性C且BC,CD；DED是由于R2中没有属性C且DEC,CD；BEA是由于R2中没有属性C且BC,CEA。又由于DED是蕴含关系，可以去掉，故F2=BD,BEA。分解R2：R2上的候选关键字为BE。考虑BD函数依赖不满足BCNF条件，将其分解成R21(BD)、R22(ABE)。计算R21和R22的最小函数依赖集分别为：F21=BD，F22=BEA。由于R22上的候选关键字为BE，而F22中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如：=R1(AC),R21(BD),R22(ABE)四、转换成4NF的保持无损连接的分解算法：输入关系模式R和R的函数依赖集F。输出R的一个分解=R1,R2,.,Rk，Ri为4NF，且具有无损连接的分解。步骤令=R，根据算法1求出保持函数依赖的分解=R1,R2,.,Rk若中的所有模式都是4NF，转若中有一个关系模式Ri不是4NF，则Ri中必能找到一个函数依赖XA，且X不是Ri的候选码，且A-X，XARi，令Z=A-X，由分解规则得出XZ。令Ri1(XZ)，Ri2(Ri-Z)，用分解Ri1,Ri2代替Ri，由于(Ri1Ri2)(Ri1-Ri2)，所以分解具有无损连接性，转；输出一、转换成3NF的保持函数依赖的分解算法：=R1,R2,.,Rk是关系模式R的一个分解，U=A1,A2,.,An，F=FD1,FD2,.,FDp，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下：对R的函数依赖集F进行极小化处理（处理后的结果仍记为F）；找出不在F中出现的属性，将这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U；若有XAF，且XA=U，则=R，算法终止；否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(ij)，就去掉Ui。由于经过了步骤，故，于是构成的一个保持函数依赖的分解。并且，每个Ri(Ui,Fi)均属于3NF且保持函数依赖。例1：关系模式R，其中U=C,T,H,I,S,G，F=CSG,CT,THI,HIC,HSI，将其分解成3NF并保持函数依赖。解：根据算法进行求解(一)计算F的最小函数依赖集利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性，故不用分解。去掉F中多余的函数依赖A设CSG为冗余的函数依赖，则去掉CSG，得：F1=CT,THI,HIC,HSI计算(CS)F1+：设X(0)=CS计算X(1)：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个CT函数依赖。故有X(1)=X(0)T=CST。计算X(2)：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X(2)=X(1)。算法终止。(CS)F1+= CST不包含G，故CSG不是冗余的函数依赖，不能从F1中去掉。B设CT为冗余的函数依赖，则去掉CT，得：F2=CSG,THI,HIC,HSI计算(C)F2+：设X(0)=C计算X(1)：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故CT不是冗余的函数依赖，不能从F2中去掉。C设THI为冗余的函数依赖，则去掉THI，得：F3=CSG,CT,HIC,HSI计算(TH)F3+：设X(0)=TH计算X(1)：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故THI不是冗余的函数依赖，不能从F3中去掉。D设HIC为冗余的函数依赖，则去掉HIC，得：F4=CSG,CT,THI,HSI计算(HI)F4+：设X(0)=HI计算X(1)：扫描F4中的各个函数依赖，没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HIC不是冗余的函数依赖，不能从F4中去掉。E设HSI为冗余的函数依赖，则去掉HSI，得：F5=CSG,CT,THI,HIC计算(HS)F5+：设X(0)=HS计算X(1)：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HSI不是冗余的函数依赖，不能从F5中去掉。即：F5=CSG,CT,THI,HIC,HSI去掉F5中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）没有发现左边有多余属性的函数依赖。故最小函数依赖集为：F=CSG,CT,THI,HIC,HSI(二)由于R中的所有属性均在F中都出现，所以转下一步。(三)对F按具有相同左部的原则分为：R1=CSG，R2=CT，R3=THI，R4=HIC，R5=HSI。所以=R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)。二、转换成3NF的保持函数依赖的分解算法2：例1：关系模式R，其中U=C,T,H,R,S,G，F=CSG,CT,THR,HRC,HSR，将其分解成3NF并保持函数依赖。解：根据算法进行求解(一)计算F的最小函数依赖集 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性，故不用分解。 去掉F中多余的函数依赖 A设CSG为冗余的函数依赖，则去掉CSG，得： F1=CT,THR,HRC,HSR 计算(CS)F1+： 设X(0)=CS 计算X(1)：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个CT函数依赖。故有X(1)=X(0)T=CST。 计算X(2)：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X(2)=X(1)。算法终止。 (CS)F1+= CST不包含G，故CSG不是冗余的函数依赖，不能从F1中去掉。 B设CT为冗余的函数依赖，则去掉CT，得： F2=CSG,THR,HRC,HSR 计算(C)F2+： 设X(0)=C 计算X(1)：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故CT不是冗余的函数依赖，不能从F2中去掉。 C设THR为冗余的函数依赖，则去掉THR，得： F3=CSG,CT,HRC,HSR 计算(TH)F3+： 设X(0)=TH 计算X(1)：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故THR不是冗余的函数依赖，不能从F3中去掉。 D设HRC为冗余的函数依赖，则去掉HRC，得： F4=CSG,CT,THR,HSR 计算(HR)F4+： 设X(0)=HR 计算X(1)：扫描F4中的各个函数依赖，没有找到左部为HR或HR子集的函数依赖。故有X(1)=X(0)。算法终止。故HRC不是冗余的函数依赖，不能从F4中去掉。 E设HSR为冗余的函数依赖，则去掉HSR，得： F5=CSG,CT,THR,HRC 计算(HS)F5+： 设X(0)=HS 计算X(1)：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HSR不是冗余的函数依赖，不能从F5中去掉。即：F5=CSG,CT,THR,HRC,HSR 去掉F5中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）,没有发现左边有多余属性的函数依赖。故最小函数依赖集为：F=CSG,CT,THR,HRC,HSR(二)由于R中的所有属性均在F中都出现，所以转下一步。(三)对F按具有相同左部的原则分为：R1=CSG，R2=CT，R3=THR，R4=HRC，R5=HSR。所以=R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)。三、转换成3NF的保持无损连接和函数依赖的分解算法3：例2：关系模式R，其中：U=C,T,H,R,S,G，F=CSG,CT,THR,HRC,HSR，分解成3NF并保持无损连接和函数依赖。解：(1) 根据上例例1，得到3NF并保持函数依赖的分解如下： = R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR) 。(2) 而HS是原模式的关键字，所以=CT，CSG，CHR，HSR，HRT，HS。由于HS是模式HSR的一个子集，所以消去HS后的分解CT，CSG，CHR，HSR，HRT就是具有无损联接性和保持函数依赖性的分解，且其中每一个模式均为3NF。四、转换成BCNF的保持无损连接的分解算法1：例3:关系模式R，其中U=C,T,H,R,S,G，F=CSG,CT,THR,HRC,HSR，将其分解成BCNF并保持无损连接。例4：关系模式R，其中：U=A,B,C,D,E，F=AC,CD,BC,DEC,CEA，将其分解成BCNF并保持无损连接。 解： 令=R(U,F)。 中不是所有的模式都是BCNF，转入下一步。 分解R：R上的候选关键字为BE（因为所有函数依赖的右边没有BE）。考虑AC函数依赖不满足BCNF条件（因A不包含候选键BE），将其分解成R1(AC)、R2(ABDE)。计算R1和R2的最小函数依赖集分别为：F1=AC，F2=BD,DED,BEA。其中BD是由于R2中没有属性C且BC,CD；DED是由于R2中没有属性C且DEC,CD；BEA是由于R2中没有属性C且BC,CEA。又由于DED是蕴含关系，可以去掉，故F2=BD,BEA。 分解R2：R2上的候选关键字为BE。考虑BD函数依赖不满足BCNF条件，将其分解成R21(BD)、R22(ABE)。计算R21和R22的最小函数依赖集分别为：F21=BD，F22=BEA。 由于R22上的候选关键字为BE，而F22中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如：=R1(AC),R21(BD),R22(ABE)最小函数依赖举例：已知关系模式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判别一个分解的无损连接性算法：=R1,R2,.,Rk是关系模式R的一个分解，U=A1,A2,.,An，F=FD1,FD2,.,FDp，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下：建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性AjUi，则在j列i行上真上aj，否则填上bij；对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。如果在某次更改后，有一行成为：a1,a2,.,an，则算法终止。且分解具有无损连接性，否则不具有无损连接性。对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。比较扫描前后，表有无变化，如有变化，则返回第步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。举例1：已知R，U=A,B,C，F=AB，如下的两个分解：1=AB,BC2=AB,AC判断这两个分解是否具有无损连接性。用无损连接的定理来解。方法一：因为ABBC=B，AB-BC=A，BC-AB=C所以BAF+，BCF+故1是有损连接。方法二：因为ABAC=A，AB-AC=B，AC-AB=C所以ABF+，ACF+故2是无损连接。举例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，则算法终止。且分解具有无损连接性。总结关系数据库设计基础(函数依赖、无损连接性、保持函数依赖、范式、)联系（Relationship）1:1联系：如果实体集E1中的每个实体最多只能和实体集E2中一个实体有联系，反之亦然，那么实体集E1对E2的联系成为一对一联系，记为1:1；1：N联系：一对多，记为1：N；M:N联系：多对多联系，记为M:N。/wiki/%E5%85%B3%E7%B3%BB%E4%BB%A3%E6%95%B0_(%E6%95%B0%E6%8D%AE%E5%BA%93)函数依赖（Function Dependency）定义设关系模式R（U），属性集合U=A1，A2，An，X，Y为属性集合U的子集，如果对于关系模式R(U)的任一可能的关系r，r中的任意两个元组u、v，若有uX=vX，就有uY=vY，则称X函数决定Y，或称Y函数依赖于X。用符号XY表示。其中X为决定因素，Y为被决定因素。若对于R（U）的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值性等，而在Y上的属性值不等。(1) 函数依赖是语义范畴的概念，只能根据语义来确定一个函数依赖关系。(2) 函数依赖XY的定义要求关系模式R的任何可能的关系r中的元组都满足函数依赖条件。术语(1)若XY，则X称作决定因素（Determinant）(2)若XY，YX，称作XY。(3)若Y不函数依赖于X，称作X -/- Y。(4)XY，若Y不包含X，则称XY为非平凡的函数依赖。正常讨论的都是非平凡的函数依赖。(5)XY，若Y包含X，则称XY为平凡的函数依赖。(6)完全函数依赖(full functional dependency)：在R(U)中，设X、Y是关系模式R（U）中不同的属性子集，若存在 XY，且不存在X的任何真子集X，使得 XY，则称Y完全函数依赖 ( full functional dependency ) 于X。记作 X-F-Y。(7)部分函数依赖：在关系模式R（U）中，X、Y是关系模式R（U）中不同的属性子集，若XY成立，如果X中存在任何真子集X，而且有XY也成立，则称Y对X是部分函数依赖，记作：X-P-Y。(8)设R是关系模式，U是其属性集，K包含于U。若K完全函数确定U，则称K是R的候选键(又叫候选关键字，候选码)。包含在任意候选键内的属性称为键属性（又叫主属性），不是键属性的属性称为非键属性（又叫非主属性）。显然，候选键可以唯一标识关系的元组。候选键可能不唯一，通常指定一个候选键作为识别元组的主键。候选键的严格定义： 关系模式R（U）的属性集合K U的候选键，如果（1）R（U）的任何一个关系实例的任意两个元素在属性集合K上的值部不相同唯一性（2）K的任何真子集都不满足条件 最小性通俗点，候选键在每一行数据里的值都不相同，就像自动增长的id一样，可以说成是候选的主键。码（键）是数据系统中的基本概念。所谓码就是能唯一标识实体的属性，它是整个实体集的性质，而不是单个实体的性质。它包括超码，候选码，主码。超键(super key):在关系中能唯一标识元组的属性集称为关系模式的超键（又叫超码），超码是一个或多个属性的集合，这些属性可以让我们在一个实体集中唯一地标识一个实体。超码的任意超集也是超码，也就是说如果K是超码，那么所有包含K的集合也是超码。候选键(candidate key):不含有多余属性的超键称为候选键（又叫候选码）。候选码是从超码中选出的，自然地候选码也是一个或多个属性的集合。因为超码的范围太广，很多是我们并不感兴趣即无用处的。所以候选码是最小超码，它们的任意真子集都不能成为超码。主键(primary key):用户选作元组标识的一个候选键程序主键（又叫主码）一题搞懂什么是候选键学号姓名性别年龄系别专业20020612李辉男20计算机软件开发20020613张明男19计算机软件开发20020614王小玉女18物理力学20020615李淑华女17生物动物学20020616赵静男21化学食品化学20020617赵静女20生物植物学【题目】数据库中有一个学生信息表如上所示，在该表中不能作为候选键的属性集合为（ ） （选择一项）a）学号 b）学号、姓名 c）年龄、系别d）姓名、性别e）姓名、专业【解析】透过概念，我们可以了解到，超键包含着候选键，候选键中包含着主键。主键一定是惟一的。为什么呢？因为他的爷爷超键就是惟一的。我们分析一下上面的题目，a，b，c，d，e，5个答案都可以作为超键，他们组合在一起的集合可以用来惟一的标识一条数据记录（实体）。请注意我们的要求：候选键。候选键要求是不能包含多余属性的超键，我们看一下答案b。在答案b中，如果我们不使用姓名也可以惟一的标识一条数据实体，可以说姓名字段在这里是多余的。那么很明显，b选项包含了多余字段属性。那么这题答案应该选择b。那么其他的4个选项都可以作为候选键，假设很幸运，a）学号被选择作为用户正在使用的候选键来惟一标识元组了，那么他很幸运的获得了主键的称号【答案】b(9)若关系R的属性子集X是另一关系S的候选键，则称X是R关于S的外部键。主键和外部键描述了关系之间的联系。(10)传递函数依赖：在关系模式R(U) 中，如果YX，XA，且XY（X不决定Y）， AX（A不属于X）,那么称YA是传递依赖。函数依赖的推理规则1. 逻辑蕴含给定一个关系模式，只考虑给定的函数依赖是不够的，必须找出在该关系模式上成立的其他函数依赖。逻辑蕴含：设F是关系模式R（U）的函数依赖集合，由F出发，可以证明其他某些函数依赖也成立，我们称这些函数依赖被F逻辑蕴含。F蕴含XY意味着关系实例只要满足F就满足XY。例如，设F= AB，BC ，则函数依赖AC被F逻辑蕴含，记作：F |= AC。即函数依赖集 F 逻辑蕴含函数依赖AC。2. F的闭包F+对于一个关系模式，如何由已知的函数依赖集合F，找出F逻辑蕴涵的所有函数依赖集合呢？这就是我们下面要讨论的问题。F的闭包F+：设F为一个函数依赖集，F的闭包是指F逻辑蕴涵的所有函数依赖集合。 F的闭包记作F+。例如，给定关系模式R(A,B,C,G,H,I)，函数依赖集合F=AB，AC，CGH，CGI，BH。可以证明函数依赖AH被F逻辑蕴涵。设有元组s和t，满足sA=tA，根据函数依赖的定义，由已知的AB，可以推出sB=tB。又根据函数依赖BH，可以有sH=tH。因此，已经证明对任意的两个元组s和t，只要有sA=tA，就有sH=tH。所以，函数依赖AH被F逻辑蕴涵。计算F的闭包F+，可以由函数依赖的定义直接计算，如上面的示例。但是，当F很大时，计算的过程会很长。为了从已知的函数依赖推导出其它函数依赖，Armstrong 提出了一套推理规则，称为Armstrong 公理 ，通过反复使用这些规则，可以找出给定F的闭包F+。其推理规则可归结为如下3条：自反律(reflexivity)、增广律(augmentation)和 传递律(transitivity)。3Armstrong 公理设U为属性总体集合，F为U上的一组函数依赖，对于关系模式R（U，F），X、Y、Z为属性U的子集，有下列推理规则：A1：自反律(reflexivity) 若Y X U，则XY为F所蕴函。A2：增广律(augmentation) 若XY为F所蕴函，且Z是U的子集，则XZYZ为F所蕴函。式中XZ和YZ是XZ 和 YZ的简写。A3：传递律(transitivity)若XY、YZ为F所蕴函，则XZ为F所蕴函。由自反律所得到的函数依赖都是平凡的函数依赖，自反律的使用并不依赖于F，而只依赖于属性集U。Armstrong公理是有效的和完备的。可以利用该公理系统推导F的闭包F+。由于利用Armstrong公理直接计算F+很麻烦。根据A1, A2, A3这三条推理规则还可以得到其他规则，用于简化计算F+的工作。如下面扩展的三条推理规则:合并规则: 由XY, XZ, 有XYZ伪传递规则: 由XY, WYZ, 有XWZ分解规则: 由XYZ, 则有XZ，XYArmstrong公理可以有多种表示形式，例如，增广律A2可以用合并规则代替。例如，用自反律A1，传递律A3和合并规则可推导出增广律A2。证明：XZ X (A1：自反律) X Y (给定条件) XZ Y (A3：传递律)XZ Z (A1：自反律)XZ YZ (合并规则)4属性集的闭包原则上讲，对于一个关系模式R(U,F)，根据已知的函数依赖F，反复使用前面的规则，可以计算函数依赖集合F的闭包F+。但是，利用推理规则求出其全部的函数依赖F+是非常困难的，而且也没有必要。因此，可以计算闭包的子集，即选择一个属性子集，判断该属性子集能函数决定哪些属性，这就是利用属性集闭包的概念。（1）属性集闭包的定义设F为属性集U上的函数依赖集，XU，即X为U的一个子集。在函数依赖集F下被X函数决定的所有属性为F+下属性集X的闭包，记作X+。即X+ A| XA 。（2）计算属性集闭包X+的算法如下：输入：X，F输出： X+迭代算法的步骤： 选取X+的初始值为X ，即X+X； 计算X+， X+X,Z ，其中Z要满足如下条件：Y是X+的真子集，且F中存在一函数依赖YZ。实际上就是以X+中的属性子集作为函数依赖的决定因素，在F中搜索函数依赖集，找到函数依赖的被决定属性Z放到X+中。 判断：如果X+没有变化？或X+等于U？则X+就是所求的结果，算法终止。否则转。因为U是有穷的，所以上述迭代过程经过有限步骤之后就会终止。例如，已知关系模式R(U,F)，U=A,B,C,D,E,G，F=ABC,DEG,CA,BEC,BCD,ACB,CEAG,求(BD)+解： (BD)+= BD； 计算(BD)+，在F中扫描函数依赖，其左边为B,D或BD的函数依赖，得到一个DEG。所以，(BD)+= BDEG。 计算(BD)+，在F中查找左部为BDEG的所有函数依赖，有两个：DEG和BEC。所以(BD)+(BD)EGC=BCDEG。 计算(BD)+，在F中查找左部为BCDEG子集的函数依赖，除去已经找过的以外，还有三个新的函数依赖：CA,BCD,CEAG。得到(BD)+(BD)ADGABCDEG。 判断(BD)+=U，算法结束。得到(BD)+ABCDEG。说明：上面说明(B,D)是该关系模式的一个候选码。5. Armstrong公理系统的有效性和完备性Armstrong公理系统的有效性指的是：由F出发根据Armstrong公理系统推导出来的每一个函数依赖一定是F所逻辑蕴含的函数依赖。Armstrong公理系统的完备性指的是：对于F所逻辑蕴含的每一函数依赖，必定可以由F出发根据Armstrong公理系统推导出来。6. 极小函数依赖集（最小函数依赖集）定义：如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 F中的任何一个函数依赖的右部仅含有一个属性； F中不存在这样一个函数依赖XA，使得F与F-XA等价； F中不存在这样一个函数依赖XA，X有真子集Z使得F-XAZA与F等价。 求最小函数依赖集分三步: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=ab