软考辅导之关系数据库专题(基础).ppt

候选关键字的求解理论和算法 对于给定的关系R(A1,A2,…An)和函数依赖集F，可将其属性分成四类： L类：仅出现在F左部的属性； R类：仅出现在F右部的属性； N类：在函数依赖两边均未出现的属性； LR类：在F左右两边都出现的属性。 候选关键字的求解理论和算法 定理1：对于给定的关系模式R及其函数依赖F，若X(X属于R)是L类属性，则X必定为R的任一候选关键字成员。 试题6：设有关系模式R(U,F),其中U=(A,B,C,D),F={D-B,B-D,AD-B,AC-D} 求：R的候选关键字。 候选关键字的求解理论和算法 定理2：对于给定的关系模式R及其函数依赖F，若X(X属于R)是R类属性，则X不在任何候选关键字中。 定理3：对于给定的关系模式R及其函数依赖F，若X(X属于R)是N类属性，则X必包含在R的任一候选关键字中 试题：设有关系模式R(U,F),其中U=(A,B,C,D,E,F),F={A-D,E-D,D-B,BC-D,DC-A} 求：R的候选关键字。 1.6 考点：无损分解的判断 什么是无损分解？ 设关系模式R(ABC),分解成ρ={R1（AB），R2（AC）｝ R在投影，连接以后仍能够恢复成r，即未丢失信息。这种 分解叫无损分解 r A B C 1 1 1 1 2 1 r1 A B 1 1 1 2 r2 A C 1 1 1 1 检验无损连接性 算法：检验无损连接性 (1)构造一个K行n列的表，第i行对应于关系模式Ri,第j列对应于属性Aj.如果Aj 属于Ri,则在第i行第j列上放符号ai,否则，放bij (2)逐个检查F中的每一个函数依赖，并修改表中的元素。方法：取得F中一个函数依赖X-Y,在X的分量中寻找相同的行，然后将这些行中的Y的分量改为相同的符号，如果其中有aj则将bij改为aj;若无aj,则改为bij; (3)这样反复进行，若发现某一行变成全a，则具有无损连接性 检验无损连接性 试题7：设有关系模式R(U,F),其中U=(A,B,C),F={A-B,C-B} 判断一个分解P={AC,BC}是否具有无损连接性。 检验无损连接性 试题8：设有关系模式R(U,F),其中U=(B,O,I,S,Q,D),F={S-D,I-B,IS-Q,B-O} 判断一个分解P={SD,IB,ISQ,BO}是否具有无损连接性。 试题9 设关系模式R为R(H,I,J,K,L),R上的一个函数依赖集为F={H→J, J→K, I→J, JL→H},分解 (6) 是无损联接的。 (6) A. ρ={HK,HI,IJ,JKL,HL} B. ρ={HIL,IKL,IJL} C. ρ={HJ,IK,HL} D. ρ={HI,JK,HL} 考点：无损联接 答案：B 试题解析9 解法二： 无损联接的测试 ? ? 输入：关系模式R=A1A2…An,R上成立的FD集F，及R的一个分解ρ={Ri}（i=1,2, ? …,k）。 ? 输出：判断ρ相对于F是否具有无损联接特性。 ? 方法： ? 第一步：构造一张k行n列的表格，每列对应一个属性Ai, ? 每行对应一个分解后的关系模式Ri。如果Aj在Ri中，则在表格的第i行第j列上填写上aj，否则填上bij。 ?  试题解析9 第二步：反复检查F的每一个FD，并修改表格中的元素，其方法如下：（Chase过程）取F的一个FD ? X → Y，如果表中有两行在X分量上相等，在Y分量上不等，则修改Y，使在这两行上的分量相等。如果Y的分量上有一个是aj,则另一个也修改为aj，如果没有aj，则用其中的某一个bij替代另一个符号（尽量将ij改成较小的数），一直到表格不能再修改为止。 ? 第三步：判断若修改到最后表格中有一行是全a，即a1a2…an,则可以下结论ρ相对于F是无损联接。 ?  试题解析9 思路 输入： R(H,I,J,K,L), F={H→J, J→K, I→J, JL→H} ρ={HIL,IKL,IJL} 输出：判断ρ相对于F是否具有无损联接特性。 ? 方法： ? 第一步：构造初始表，有属性处填ai，没有属性处用bij表示  H I J K L HIL a1 a2 b13 b14 a5 IKL b21 a2 b23 a4 a5 IJL b31 a2 a3 b34 a5 试题解析9 第二步： 检查函数依赖集F={H→J, J→K, I→J, JL→H} H→J:H列没有相同的值，不修改 H I J K L HIL a1 a2 b13 b14 a5 IKL b21 a2 b13 a4 a5 IJL b31 a2 a3 b14 a5 试题解析9 第二步： 检查函数依赖集F={H→J, J→