無損聯(lián)接的測試-Chase過程1

無損聯(lián)接的測試——Chase過程輸入：關系模式R=A1A2A3…An,R上成立的函數(shù)依賴集F，R上成立的函數(shù)依賴集F，R的一個分解ρ={R1,R2…Rk}。輸出：判斷ρ相對于F是否具有無損連接性。方法：（1）構造一張k行n列的表格，每列對應一個模式Ri（1≤i≤k）。如果Aj在Ri中，那么在表格的第i行第j列上填上符號aj，否則填上符號bij。（2）反復檢查F的每一個函數(shù)依賴，并修改表格中的元素，其方法如下：取F中的函數(shù)依賴X→Y，如果表格中有兩行在X的分量上相等，在Y分量上不相等，那么修改Y，使這兩行在Y分量上也相等。如果Y的分量中有一個是aj，那么另一個也修改成aj；如果沒有aj，那么用其中的一個bij替換另一個符號（盡量把下標ij改成較小的數(shù)）。一直到表格不能修改為止（這個過程稱為Chase過程）。（3）若修改到最后一張表格中有一行是全a，即a1a2…an，那么ρ相對于F是無損聯(lián)接分解。例：設R={ABCDE},R1=AD,R2=AB,R3=BE,R4=CDE,R5=AE,設函數(shù)依賴集F={A→C,B→C,C→D,DE→C,CE→A}.判斷R分解成

ρ=（R1,R2,R3,R4,R5）是否無損聯(lián)接分解。解：Chase過程的初始表-表1ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5根據(jù)A→C,對初始表-表1進行處理，將b13、b23、b53改成同一符號b13（最小下標），然后考慮B→C,將b33，b13改成同一符號b13。修改后的表格如下所示表2。ABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5根據(jù)C→D,將b24、b34、b54改成同一符號a4，修改后的表格如下表3所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5根據(jù)DE→C,將C所在列的第三、四、五行的元素均改成a3，修改后的表格如下表4所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5根據(jù)CE→A,將A所在列的第三、四、五行的元素均改成a1，修改后的表格如下表5所示。ABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5從表5中可以看出，此時第三行已是全a行，因此R分解成ρ=（

R1,R2,R3,R4,R5）是無損聯(lián)接分解。練習1

關系模式R（U，F(xiàn)），其中

U={A，B，C，D}，

F={A→B，B→C，C→D，D→A}，判斷ρ={AB，BC，CD}是否具有無損連接性？是否保持函數(shù)依賴性？解：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，所以不保持函數(shù)依賴。a3a4a4練習2設關系模式R(A,B,C,D),F是R上成立的FD集,F={A→B,