无损联接的测试-Chase过程1

无损联接的测试——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过程的初始表-表1ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5根据A→C,对初始表-表1进行处理，将b13、b23、b53改成同一符号b13（最小下标），然后考虑B→C,将b33，b13改成同一符号b13。修改后的表格如下所示表2。ABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5根据C→D,将b24、b34、b54改成同一符号a4，修改后的表格如下表3所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5根据DE→C,将C所在列的第三、四、五行的元素均改成a3，修改后的表格如下表4所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5根据CE→A,将A所在列的第三、四、五行的元素均改成a1，修改后的表格如下表5所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5从表5中可以看出，此时第三行已是全a行，因此R分解成ρ=（

R1,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}ABCDR1(AB)a1a2R2(BC)a2a3R3(CD)a3a4因为存在一行有a1,a2,a3,a4，具有无损连接性。F(AB)={A→B};F(BC)={B→C};F(CD)={C→D};又因为∑Fi≠F，所以不保持函数依赖。a3a4a4练习2设关系模式R(A,B,C,D),F是R上成立的FD集,F={A→B,