(软考软件设计师)模式分解的无损连接性之深入剖析

1、书山有路勤为径FROM：及时雨模式分解的无损连接性之深入剖析模式分解的无损连接性之深入剖析1. 无损连接分解的形式定义无损连接分解的形式定义无损连接分解的形式定义如下：设 R 是一个关系模式，F 是 R 上的一个函数依赖(FD)集。R 分解成数据库模式 =R1,Rk。如果对 R 中每一个满足 F 的关系 r 都有下式成立：那么称分解 相对于 F 是“无损连接分解”，否则称为“损失连接分解”。其中表示自然连接。从上述形式定义中可知，若直接根据定义来判断某个分解是否具有无损连接性，那么就得“对 R 中每一个满足 F 的关系 r”进行测试，看是否满足上面的等式，这显然不可操作，因为“对 R 中每一个满足 F 的关系 r”进行测试就意味着“对 R 中所有满足 F 的关系 r”进行测试，显然是不可能的。这里所说的“关系”就是指一张具体的表。因此，必须寻求其它的可操作性方法来判别分解的无损连接性。2. 无损连接分解的普通判别方法无损连接分解的普通判别方法表格法表格法设关系模式 R=A1,An，R 上成立的 FD 集 F，R 的一个分解 p=R1,Rk。无损连接分解的判断步骤如下：(1)构造一张 k

2、 行 n 列的表格，每列对应一个属性 Aj(1jn)，每行对应一个模式Ri(1ik)。如果 Aj 在 Ri 中，那么在表格的第 i 行第 j 列处填上符号 aj，否则填上符号bij。(2)把表格看成模式 R 的一个关系，反复检查 F 中每个 FD 在表格中是否成立，若不成立，则修改表格中的元素。修改方法如下：对于 F 中一个 FD：XY，如果表格中有两行在 X 分量上相等，在 Y 分量上不相等，那么把这两行在 Y 分量上改成相等。如果 Y 的分书山有路勤为径FROM：及时雨量中有一个是 aj，那么另一个也改成 aj;如果没有 aj，那么用其中的一个 bij 替换另一个(尽量把 ij 改成较小的数，亦即取 i 值较小的那个)。若在修改的过程中，发现表格中有一行全是 a，即 a1,a2,an，那么可立即断定 p 相对于 F 是无损连接分解，此时不必再继续修改。若经过多次修改直到表格不能修改之后，发现表格中不存在有一行全是 a 的情况，那么分解就是有损的。特别要注意，这里有个循环反复修改的过程，因为一次修改可能导致表格能继续修改。修改过程中要特别注意，若某个 bij 被改动，那么它所在列的所

3、有 bij 都需要做相应的改动。为了明确这一点，举例说明。例如，我们根据 FD“HI”、“ KL”来修改表格之前时的表格如表 1 所示(已经过多次修改，非初始表，空的单元表示省略)：表表 1HIJKLR1 b12 b35R2a1a2 a4b25R3a1b12 a4b35R4 b12 b35R2、R3 所在行的 H 分量都为 a1，根据 FD“HI”，需要修改这两行对应的 I 分量，而R2 所在行的 I 分量为 a2，因此，要将 R3 所在行的 I 分量 b12 修改为 a2，注意到，R1、R4所在行的 H 分量也为 b12，因此，这两行对应的 I 分量也必须修改为 a2。R2、R3 所在行的 K 分量都为 a4，根据 FD“KL”，需要修改这两行对应的 L 分量，于是将 R3 所在行的L 分量 b35 修改为较小的 b25，同时注意到，R1、R4 所在行的 L 分量也为 b35，因此，这两行对应的 L 分量也必须修改为 b25。修改后的表格如表 2 所示：表表 2HIJKLR1 a2 b25R2a1a2 a4b25R3a1a2 a4b25R4 a2 b25书山有路勤为径FROM：及时雨

4、【例题例题】(软件设计师软件设计师 2002 年上午试题年上午试题 38)设关系模式 R 为 R(H,I,J,K,L)，R 上的一个函数依赖集为 F=HJ,JK,IJ,JLH，分解 (38) 是无损连接的。供选择的答案：供选择的答案：(38) A. p=HK，HI，IJ，JKL，HL B. p=HIL，IKL，IJLC. p=HJ，IK，HL D. p=HI，JK，HL试题分析：试题分析：根据上述判断方法，我们列出选项 B(分解成三个关系模式 R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表 3 所示：表 3 选项 B 的初始表HIJKLHILa1a2b13b14a5IKLb21a2b23a4a5IJLb31a2a3b34a5对于函数依赖集中的 HJ、JK 对表 3 进行处理，由于属性列 H 和属性列 J 上无相同的元素，所以无法修改。但对于 IJ 在属性列 I 上对应的 1、2、3 行上全为 a2 元素，所以，将属性列 J 的第一行 b13 和第二行 b23 改为 a3。修改后如表 4 所示：【例题例题】(表表 4 选项选项 B 的中间表的中间表HIJKLHILa1a2

5、a3b14a5IKLb21a2a3a4a5IJLb31a2a3b34a5对于函数依赖集中的 JLH 在属性列 J 和 L 上对应的 1、2、3 行上为 a3、a5 元素，所以，将属性列 H 的第二行 b21 和第三行 b31 改为 a1。修改后如表 5 所示：书山有路勤为径FROM：及时雨表表 5 选项选项 B 的结果表的结果表HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5从表 5 可以看出，第二行为 a1、a2、a3、a4、a5，所以分解 p 是无损的。有一种特殊情况要注意：分解后的各个关系模式两两均无公共属性。由于是模式分解，那么任一一个分解后的关系模式覆盖的属性集不可能是分解前的整个全部属性 U，因此初始表中不存在全是 a 的行。又注意到，分解后的各个关系模式两两均无公共属性，表明任两行在任一列上都没有相同的分量，这导致整个表格无法修改，保持初始状态。而初始状态不存在全是 a 的行，因此这种特殊情况的分解是有损的。例如，函数依赖集合 FD，将关系模式 R(ABCDEF)分解成 R1(AB)、R2(CDE)、R3(F)，那么这种分解肯定

6、是有损的。考试中可能碰到这种情况，那么一眼就可以判断出结果，从而节省了时间。3. 无损连接分解的快捷判别方法无损连接分解的快捷判别方法首先要申明，这种快捷方法是有前提的，前提就是分解后的关系模式只有两个。其内容为：设 =R1，R2是 R 的一个分解，F 是 R 上的 FD 集，那么分解 相对于 F 是无损分解的充分必要条件是：(R1R2)(R1R2)或(R1R2)(R2R1)。这个“或”字很重要，这里表示(R1R2)(R1R2)、(R1R2)(R2R1)中只要有一个成立就行。这里的求交和相减运算的对象是关系模式的属性。【例题例题】关系模式 R(U，F)，其中 U=W,X,Y,Z,F=WXY,WX, XZ,YW。那么下列分解中是无损分解的是 。书山有路勤为径FROM：及时雨供选择的答案：供选择的答案：A.p=R1(WY),R2(XZ) B.p=R1(WZ),R2(XY)C.p=R1(WXY),R2(XZ) D.p=R1(WX),R2(YZ)试题分析：试题分析：A 选项，R1R2 为空，肯定不满足条件。B 选项，R1R2 为空，肯定不满足条件。C 选项，R1R2=X，R1-R2=WY，R2

7、-R1=Z，根据函数依赖集，XZ 成立，所以满足条件。D 选项，R1R2 为空，肯定不满足条件。4. 总结总结模式分解无损性判别的源泉仍然是普通的表格法。这种快捷方法只不过是根据这种表格法推断出来的而已，是它的一个特列。但是这种快捷方法却往往非常有用。软件设计师软件设计师 2002 年上午试题年上午试题 38)设关系模式 R 为 R(H,I,J,K,L)，R 上的一个函数依赖集为 F=HJ,JK,IJ,JLH，分解 (38) 是无损连接的。供选择的答案：供选择的答案：(38) A. p=HK，HI，IJ，JKL，HL B. p=HIL，IKL，IJLC. p=HJ，IK，HL D. p=HI，JK，HL试题分析：试题分析：书山有路勤为径FROM：及时雨根据上述判断方法，我们列出选项 B(分解成三个关系模式 R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表 3 所示：表 3 选项 B 的初始表HIJKLHILa1a2b13b14a5IKLb21a2b23a4a5IJLb31a2a3b34a5对于函数依赖集中的 HJ、JK 对表 3 进行处理，由于属性列 H 和属性列 J 上无相同的元素，所以无法修改。但对于 IJ 在属性列 I 上对应的 1、2、3 行上全为 a2 元素，所以，将属性列 J 的第一行 b13 和第二行 b23 改为 a3。修改后如表 4 所示：

《(软考软件设计师)模式分解的无损连接性之深入剖析》由会员wt****50分享，可在线阅读，更多相关《(软考软件设计师)模式分解的无损连接性之深入剖析》请在金锄头文库上搜索。