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

《软考软件设计师模式分解的无损连接性之深入剖析（页）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、模式分解的无损连接性之深入剖析1.无损连接分解的形式定义无损连接分解的形式定义如2设R是一个关系模式，F是R上的一个函数依赖(FD)集。R分解成数据库模式8={R1,……,Rk}。如果对R屮每一个满足F的关系r都有下式成立:心恋他O)xLx%(尸)那么称分解6相对于F是“无损连接分解”，否则称为“损失连接分解”。其中“冈”表示自然连接。从上述形式定义中町知，若直接根据定义来判断某个分解是否具有无损连接性，那么就得“对R屮每一个满足F的关系r”进行测试，看是否满足上面的等式，这显然不可操作，因为“对R屮每一个满足F的

2、关系r”进行测试就意味着“对R中所有满足F的关系T进行测试,显然是不可能的。这里所说的“关系”就是指一张具体的表。因此，必须寻求其它的可操作性方法來判别分解的无损连接性。2.无损连接分解的普通判别方法——表格法设关系模式R=Al,・.・,An,R上成立的FD集F,R的一个分解p={Rl,...,Rk}o无损连接分解的判断步骤如下：⑴构造一张k行n列的表格，每列对应一个属性Aj(l

3、看成模式R的一个关系，反复检查F中每个FD在表格屮是否成立，若不成立，则修改表格中的元索。修改方法如下：对于F中一个FD：X—Y,如果表格中冇两行在X分量上相等，在Y分量上不相等，那么把这两行在Y分量上改成相等。如果Y的分量中有一个是aj,那么另一个也改成aj;如果没有aj,那么用其屮的一个bij替换另一个(尽量把ij改成较小的数，亦即取i值较小的那个)。若在修改的过程中，发现表格中有一行全是a,即al,a2,...,an,那么可立即断定p相对于F是无损连接分解，此时不必再继续修改。若经过多次修改肓到表格不能修改之

4、后，发现表格屮不存在有一行全是a的情况，那么分解就是有损的。特别要注意，这里有个循环反复修改的过程，因为一次修改可能导致农格能继续修改。修改过程中要特别注意，若某个bij被改动，那么它所在列的所有bij都需耍做相应的改动。为了明确这一点，举例说明。例如，我们根据FD44H->F“K—U來修改表格Z前时的表格如表1所示（已经过多次修改，非初始表，空的单元表示省略）：HIJKLR1b12b35R2ala2a4b25R3albl2a4b35R4bl2b35R2、R3所在行的H分量都为al,根据FD“H->I”，需要修改

5、这两行对丿应的I分量，而R2所在行的I分量为a2,因此，要将R3所在行的I分量bl2修改为a2,注意到，Rl、R4所在行的H分量也为bl2,因此，这两行对应的I分量也必须修改为a2。R2、R3所在行的K分量都为a4,根据FD“K->L”，需要修改这两行对应的L分量，于是将R3所在行的L分fib35修改为较小的b25,同时注意到，Rl、R4所在行的L分量也为b35,因此，这两行対应的L分量也必须修改为b25o修改后的表格如表2所示：H/JKLR1a2b25R2ala2a4b25R3ala2a4b25R4a2b25【例

6、题】（软件设计师2002年上午试题38）设关系模式R为R(H,I,J,K,L),R上的一个函数依赖集为F={H->J,J->K,I->J,JLtH},分解(38)是无损连接的。供选择的答案：(38)A.p={HK,HI,IJ,JKL,HL}B.p={HIL,IKL,IJL}C.p={HJ,IK,HL}D.p={HI,JK,HL}试题分析：根据上述判断方法，我们列出选项B(分解成三个关系模式Rl(HIL)、R2(IKL)、R3(IJL))的初始表如表3所示：表3选项B的初始表HIJKLHILala2b!3bl4a51

7、KLb21a2b23a4a5IJLb31a2a3b34a5対于函数依赖集中的H-J、J-K対表3进行处理，由于属性列H和属性列J上无相同的元素，所以无法修改。但对于I-J在属性列I上对应的1、2、3行上全为a2元素，所以,将属性列J的笫一行bl3和第二行b23改为a3。修改后如表4所示：【例题】(表4选项B的中间表HIJKLHILala2a3bl4a5IKLb21a2a3a4a5IJLb31a2a3b34a5对于函数依赖集小的JL->H在属性列J和L上对应的1、2、3行上为a3、a5元素，所以，将属性列H的第二行b

8、21和第三行b31改为alo修改示如表5所示:表5选项B的结果表HIJKLHILala2a3bl4a5IKLala2a3a4a51JLala2a3b34a5从表5可以看出，第二行为al、a2>a3>a4>a5,所以分解p是无损的。有一种特殊情况要注意：分解后的各个关系模式两两均无公共属性。由于是模式分解,那么任一一个分解后的关系模式覆盖的属性集不可能是分解而