《数据库系统概论15候选码的求解方法》由会员分享，可在线阅读，更多相关《数据库系统概论15候选码的求解方法（19页珍藏版）》请在金锄头文库上搜索。
1、一、求函数依赖的最小集 定义6.15：对于给定的函数依赖F，当满足下列条件时，称为F的最小依赖集，记作FM。 FM的每个依赖的右边都是单个属性。 对于FM中的任何一个XA和X的真子集Z， (FM-XA) ZA与FM都不等价。(保证了FM中每个函数依赖的左边没有多余的属性) 对于FM中的任何一个函数依赖XA，FM-XA与FM都不等价。(保证了在FM中不存在多余的函数依赖) 定理：每个函数依赖集与它的最小依赖集FM等价。,输入：一个函数依赖集F 输出：F的一个等价最小依赖集G 方法： (1)应用分解规则，使F中每一个依赖的右边属性单一化。 (2)去掉各依赖左边多余的属性。具体做法是；一个一个地检查
2、F中左边是非单属性的依赖，例如XYA。现在要判断Y是否多余的，即以XA代替XYA是否等价。只要在F中求X+，若X+包含A，则Y是多余的属性；否则Y不是多余的属性。依次判断其他属性即可消除各依赖左边的多余属性。 (3)去掉多余的依赖。具体做法是：从第一个依赖开始，从F中去掉它(假设该依赖是XY)，然后在剩下的依赖中求X+，看X+是否包含Y，若是，则可以去掉XY；若不包含Y，则不能去掉。,例：设有依赖集：F=ABC，CA，BCD，ACDB，DEG，BEC，CGBD，CEAG，计算其等价的最小依赖集。,解： (1)将依赖右边属性单一化，结果为： F1=ABC，CA，BCD，ACDB，DE， DG，B
3、EC，CGB，CGD，CEA，CE G,(2)在F1中去掉左边多余的属性。 、对于ACDB，由于(CD)+=ABCDEG，则A是多余的，所以结果为： F2=ABC，CA，BCD，CDB，DE， DG，BEC，CGB，CGD，CE G 、对于CEA，由于CA，则E是多余的,(3)在F2中去掉多余的依赖。 对于CDB，在剩下的函数依赖中，由于(CD)+=CDAEGB，所以CDB是多余的，则Fm=ABC，CA，BCD，DE， DG，BEC， CGB ，CGD，CEG 或者对于CGB，由于(CG)+=ABCDEG，所以CGB是多余的，则 Fm=ABC，CA，BCD，CDB，DE， DG，BEC，CGD
4、，CEG,总结：求得的最小依赖集并不是唯一的。,课堂练习：设有关系模式，其中U=E，F，G，H，F=EG，GE，FEG，HEG，FHE，计算其等价的最小依赖集。,结果为：Fm= EG，GE，FG，HG 或者：Fm= EG，GE，FG，HE 或者：Fm= EG，GE，FE，HG 或者：Fm= EG，GE，FE，HE,二、候选码求解理论和算法 对于给定的关系R(A1,A2,An)和函数依赖集F，可将其属性分为4类： L类：仅出现在F的函数依赖左边的属性 R类：仅出现在F的函数依赖右边的属性 N类：在F的函数依赖左右边均未出现的属性 LR类：在F的函数依赖左右边均出现的属性,1、快速求解候选码的一个
5、充分条件 定理1：对于给定的关系模式R及其函数依赖集F，若X(XR)是L类属性，则X是R的任一候选码成员。 推论：对于给定的关系模式R及其函数依赖集F，若X(XR)是L类属性，且X包含了R的全部属性，则X必是R的唯一候选码。 例：设有关系模式R(A,B,C,D)，其函数依赖集F=DB，BD，ADB，ACD，求R的所有候选码。 解：考察F发现，A、C两属性是L类属性，由上面定理1可知，A、C必是R的候选码的成员。又因为(AC)+=ABCD，所以AC必是R的唯一候选码。,定理2：对于给定的关系模式R及其函数依赖集F，若X(XR)是R类属性，则X不在任何候选码中。 定理3：对于给定的关系模式R及其函
6、数依赖集F，若X(XR)是N类属性，则X必包含在R的任一候选码中。 例：设有关系模式R(A,B,C,D,E,P)，其函数依赖集F=AD，ED，DB，BCD ，DCA，求R的所有候选码。 解：考察F发现，C、E两属性是L类属性，由上面定理1可知，C、E必是R的候选码的成员； P是N类属性，由上面的定理3可知，P也是R的候选码的成员。 又因为(CEP)+=ABCDEP，所以CEP必是R的唯一候选码。 定理4：对于给定的关系模式R及其函数依赖集F，若X(XR)是N类和L类组成的属性集，且X+包含了R的全部属性，则X必是R的唯一候选码。,2、左边是单属性的函数依赖集的候选码成员的图论判定方法 定义1：
7、一个函数依赖图G是一个有序二元组(R,F)，记做G=(R,F)，简称依赖图。其中： (1)R=(A1,A2,An)是一个有限非空集，Ai(I=1,2,n)是G 的结点，它们表示对应关系模式R的属性全集。 (2)F是G的边集，其元素是G的一条有向线段(即边)，每条边(Ai，Aj)表示一个函数依赖AiAj，F是R的单属性最小依赖集。,定义2：在一个函数依赖图中有下列术语： (1)引出线/引入线： (2)原始点：只有引出线而无引入线的结点。它表示L类属性。 (3)终结点：只有引入线而无引出线的结点。它表示R类属性。 (4)途中点：既有引出线又有引入线的结点。它表示LR类属性。 (5)孤立点：即无引出
8、线而无引入线的结点。它表示N类属性。 (6)关键点：原始点和孤立点的统称。 (7)关键属性：关键点对应的属性。 (8)独立回路：不能被其他结点到达的回路。,定理5：一个关系模式R的函数依赖图G中若存在关键结点，则关键结点对应的属性必在R的任何候选码中，而所有的终结点必不在R的任何候选码中。 定理6：属性集X是R的唯一候选码的充要条件是X为能到达G中任一结点的关键属性集。 推论：在单属性情况下，R具有唯一候选码的充要条件是G中不存在独立回路。 定理7：设Y是途中点，则Y必在某个候选码中的充要条件是Y为某一独立回路中的结点。,定理8：设F为单属性依赖集。R的关键属性集X不能到达G中的某个结点，G中
9、存在K(k=1)个独立回路r1,r2,rk，各回路的结点集分别为： AA1=A11，A12，A1n1 AA2=A21，A22，A2n2 AAk=Ak1，Ak2，Aknn 其中Aij(I=1,2,k，j=1,2,n)都是R的属性，则： (1)R的候选码必不唯一 (2)R的每个候选码均由两部分组成 关键属性集X(X可以为空) K个独立回路中，每个独立回路任选一个点作为候选码的成员，候选码的集合Y是AA1， AA2， AKk (3)候选码的个数等于各回路中结点个数的乘积 (4)每个候选码所含属性个数是一个常数，它等于关键属性个数|X|独立回路个数，即N=|X|+K,例：设有关系模式R(O,B,I,S
10、,Q,D)，其函数依赖集F=SD，DS，IB，BI ，BO， OB，求R的所有候选码。 解： (1)FM=F= SD，DS，IB，BI ，BO， OB (2)构造函数依赖图，如右图所示：,(3)关键属性集：Q (4)共有2条回路，SD，IBO，所以候选码个数是2*3=6，每个候选码的属性个数是1+2=3。,所以R的候选码不唯一，所有候选码为：QSI，QDI，QSB，QDB，QSO，QDO,例：设有关系模式R(X,Y,Z,W)，其函数依赖集F=WY，YW，XWY，ZWY ，XZW，求R的所有候选码。 解： (1)FM= WY，YW，XY，ZW (2)构造函数依赖图，如右图所示：,(3)关键属性集
11、：X，Z (4)无独立回路 所以，R只有唯一候选码XZ,3、多属性依赖集候选码求解法 算法：多属性依赖集候选码求解法 输入：关系模式R及其函数依赖集F 输出：R的所有候选码 方法： (1)将R的所有属性分为L、R、N、LR四类，并令X代表L、N类，Y代表LR类。 (2)求X+，若X+包含了R的全部属性，则X即为R的唯一候选码，转(5)；否则，转(3) (3)在Y中取一属性A，求(XA)+。若它包含了R的全部属性，那么XA为其中一个候选码，然后转(4)；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。 (4)如果已找出所有候选码，则转(5)；否则在Y中依次取两个、三个、，求它们的属性闭
12、包，直到其闭包包含了R的所有属性。 (5)停止，输出。,例：关系模式CSZ(CITY，ST，ZIP)，其中城市CITY，街道ST，邮政编码ZIP。属性的函数依赖集：F=(CITY,ST)ZIP，ZIPCITY，试找出CSZ的候选码。,解：候选码为(ST，ZIP)和(ST，CITY) (1)因为ST是L类属性，所以ST是候选码的成员之一。CITY 和ZIP是LR类。 (2)(ST)+没有包含CSZ的所有属性，所以ST不是唯一候选码。 (3)(ST，ZIP)+包含CSZ的所有属性，所以(ST,ZIP) 是一个 候选码。 (4)(ST，CITY)+也包含CSZ的所有属性，所以(ST,CITY) 是一
13、个候选码。,例：设有关系模式R(A,B,C,D,E)，其函数依赖集F=ABC，CDE，BD，EA，求R的所有候选码。 解： (1)Fm=AB， AC，CDE，BD，EA (2)A，B，C，D，E五个属性在F中各个函数依赖的右边和左边都出现了，所以候选码中可能包含A，B，C，D，E。,候选码有：A，E，BC，CD,小结,1、最小函数依赖集算法。 2、候选码的求解方法。,课后作业：,1、设有关系模式，其中U=A，B，C，D，E，P，H，G，F=ABCE，AC，GPB，EPA，CDEP，HBP，DHG，ABCPG，计算其等价的最小依赖集。 Fm=ABE，AC，GPB，EPA，CDEP，HBP，DH， DG，ABCP ，ABCG 2、设有关系模式R(A,B,C,D,E,P)，其函数依赖集F=AB，CP，EA，CED，求R的所有候选码。 候选码为：CE 3、设有关系模式R(S,D,I,B,O,Q)，其函数依赖集F=SD，IB，BO，OQ，QI，求R的所有候选码。 候选码为：SI，SB，SQ，SO,
