无损联接的测试——Chase过程1.ppt

无损联接的测试——Chase过程 输入：关系模式R=A1A2A3…An,R上成立的函数依赖集F，R上成立的函数依赖集F，R的一个分解ρ={R1,R2…Rk}。 输出：判断ρ相对于F是否具有无损连接性。 方法： （1）构造一张k行n列的表格，每列对应一个模式Ri（1≤i≤k）。如果Aj在Ri中，那么在表格的第i行第j列上填上符号aj，否则填上符号bij。 （2）反复检查F的每一个函数依赖，并修改表格中的元素，其方法如下：取F中的函数依赖X→Y，如果表格中有两行在X的分量上相等，在Y分量上不相等，那么修改Y，使这两行在Y分量上也相等。如果Y的分量中有一个是aj，那么另一个也修改成aj；如果没有aj，那么用其中的一个bij替换另一个符号（尽量把下标ij改成较小的数）。一直到表格不能修改为止（这个过程称为Chase过程）。 （3）若修改到最后一张表格中有一行是全a，即a1a2…an，那么ρ相对于F是无损联接分解。 例：设R={ABCDE},R1=AD,R2=AB,R3=BE,R4=CDE,R5=AE,设函数依赖集F={A →C,B →C, C→D, DE →C,CE →A}.判断R分解成ρ=（R1,R2,R3,R4,R5）是否无损联接分解。 解：Chase过程的初始表-表1 A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b23 b24 b25 BE b31 a2 b33 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b53 b54 a5 根据A →C,对初始表-表1进行处理，将b13、b23、b53改成同一符号b13（最小下标），然后考虑B →C,将b33，b13改成同一符号b13。修改后的表格如下所示表2。 A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 b24 b25 BE b31 a2 b13 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b13 b54 a5 根据C→ D,将b24、b34、b54改成同一符号a4，修改后的表格如下表3所示。 A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE b31 a2 b13 a4 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b13 a4 a5 根据DE→ C,将C所在列的第三、四、五行的元素均改成a3，修改后的表格如下表4所示。 A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE b31 a2 a3 a4 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 a3 a4 a5 根据CE→ A,将A所在列的第三、四、五行的元素均改成a1，修改后的表格如下表5所示。 A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE a1 a2 a3 a4 a5 CDE a1 b42 a3 a4 a5 AE a1 b52 a3 a4 a5 从表5中可以看出，此时第三行已是全a行，因此R分解成ρ=（ R 1,R2,R3,R4,R5）是无损联接分解。 练习1 关系模式R（U，F），其中 U={A，B，C，D}， F={A→B，B →C， C→D，D →A}， 判断ρ={AB，BC，CD}是否具有无损 连接性？是否保持函数依赖性？ 解：F={A→B , B→C , C→D , D →A} ρ={AB，BC，CD} A B C D R1(AB) a1 a2 R2(BC) a2 a3 R3(CD) a3 a4 因为存在一行有a1,a2,a3,a4，具有无损连接性。 F(AB)={ A→B }; F(BC)={ B→C }; F(CD)={ C→D}; 又因为∑Fi≠F，所以不保持函数依赖。 a3 a4 a4 练习2 设关系模式R(A, B, C, D), F是R上成立的FD集, F={A→B, C→D , D→B} 分解ρ={AD，BC，BD}。 问：ρ相对于F是否无损连接分解?(需画出chase过程的示意图) 答案：不是无损连接分解。 此练习作书面作业。