第10章數(shù)據(jù)依賴和關(guān)系模式的規(guī)范化(編輯修改稿)
2024-08-16 07:11 本頁面
【文章內(nèi)容簡(jiǎn)介】 ， No1 physics及 Li， No2 chemistry， 則必有元組 Li， No2 physics及 Li， No1 chemistry。 推廣這個(gè)概念，還可以發(fā)現(xiàn)其他依賴關(guān)系，連 接依賴（ Join Dependency,JD）就是其中之一。 定義 1010 設(shè) X1， X2， … ， Xn是關(guān)系 R的屬性集 U的子 集，且 ∪ Xi＝ U。若對(duì) R的任一值，Ｒ＝ ∞ R[Xi]均成立， 則稱 R具有連接依賴，記為 ∞ （ X1， X2， … ， Xn)。 注： ∞ 表示連接操作 關(guān)系模式的分解及其問題 在 題。同樣，多值依賴和連接依賴也會(huì)引起類似的問題。 解決這些問題的途徑，就是按照前面曾提到過的 “ 一地一 事 ” 原則，對(duì)關(guān)系模式進(jìn)行分解，使其語義單純化。 定義 1011 設(shè)有一關(guān)系模式 R(U)，若用一關(guān)系模式的集 合｛ R1(U1)， R2(U2),… ,Rk(Uk)｝來取代，其中， U＝ ∪ Uｉ ，則稱此關(guān)系模式的集合為Ｒ的一個(gè)分解，用 ρ =｛ R1， R2,… ,Rk｝表示。 定義 1012 F在屬性集 Ui（ 為Ｕ的真子集 ） 上的投影定 義為 ∏Ｕ i(F)＝ ｛ X→Y ｜ X→Y∈F +∧XY 為 Ui的子集 ｝ 定義 1013 設(shè) ρ＝ ｛ R1， R2,… ,Rn｝ 是 R的一個(gè)分解 ， r是 R 的任一個(gè)值 ， 如果滿足條件 r＝ ∏ U1(r)∞ ∏ U2(r)… ∏ Uk(r) 則稱 ρ是無損連接分解或簡(jiǎn)稱無損分解 。 定義 1014 設(shè) ρ=｛ R1， R2,… ,Rn｝ 是 R的一個(gè)分解 ， 如 ∪∏ Ui(F)|=Ｆ ， 則稱分解 ρ 保持函數(shù)依賴 ， 或簡(jiǎn)稱保持 依賴 。 關(guān)系模式經(jīng)分解后與原來的關(guān)系等價(jià)。所謂 “ 等價(jià) ”不是 “ 等同 ” ， “ 等價(jià) ” 是指兩者對(duì)數(shù)據(jù)的使用者來說應(yīng)是等價(jià)的，即對(duì)分解前后的數(shù)據(jù)，做同樣內(nèi)容的查詢，應(yīng)產(chǎn)生同樣的結(jié)果。這是對(duì)模式分解的最基本的要求，否則，不能進(jìn)行分解。 如果硬要進(jìn)行分解的話，那就意味著分解前后的模式代表著兩個(gè)不同的現(xiàn)實(shí)世界。因此，無損分解應(yīng)是關(guān)系模式分解時(shí)所必須滿足的條件。不是任意的分解都是無損的。 關(guān)系分解還帶來保持依賴的問題。不滿足保持依賴條件，并不意味著某些函數(shù)依賴真正丟失了，而是某些函數(shù)依賴的有關(guān)屬性分散在不同的關(guān)系中，不能被Ｆ的所有投影所蘊(yùn)涵。不同關(guān)系的屬性間的函數(shù)依賴關(guān)系并不是不可能存在的，問題在于這種函數(shù)依賴所代表的語義約束不如在一個(gè)關(guān)系中容易檢查，一般須在檢查前對(duì)有關(guān)的關(guān)系做一次連接運(yùn)算。此外，不保持依賴還會(huì)引起一些更新異常，這可以通過下面的例子說明。 【 例 103】 取圖 101的一部分組成關(guān)系模式 R（ C＃， TN， D），其函數(shù)依賴關(guān)系見圖 106，即 F＝｛ C＃ → TN， TN→D ｝。 C＃ → Ｄ為Ｆ所邏輯蘊(yùn)涵，如圖 106中虛線所示。如果 R分解為兩個(gè)關(guān)系 R1（ C＃， TN）， R2（ C＃， D），則由于Ｃ＃是Ｒ的主鍵，故 R1和R2中都含有Ｃ＃。如前所述，這樣的分解是無損分解。但函數(shù)依賴 TN→ Ｄ不能被｛Ｃ＃ → TN，Ｃ＃ → Ｄ｝所邏輯蘊(yùn)涵，故分解 ρ ＝｛ R1， R2｝不保持依賴。 TN和Ｄ分屬于 R1和 R2。 R2中某門課的系名 D應(yīng)是 R1中教該門課的教師所在系。如果 R1中的教師所在的系變了，則需要修改 R2中相應(yīng)的屬性Ｄ的值。更有甚者，如果一位教師不教課，則無法表示這位教師所在系的信息。 綜上所述 ， 關(guān)系模式的分解主要有兩種準(zhǔn)則： （ １ ） 只滿足無損分解要求； （ ２ ） 既滿足無損分解要求 ， 又滿足保持依賴要求 。 準(zhǔn)則（２）要比準(zhǔn)則（１）理想，但分解要受到更多的限制。當(dāng)然，只滿足保持依賴，而不滿足無損分解要求的分解是存在的。 下面進(jìn)一步討論無損分解和保持依賴的性質(zhì)及其判別方法 。 首先介紹一些記號(hào)。設(shè) ρ =｛ R1， R2,… ,Rn｝是 R的一個(gè)分解 ,r為 R的一個(gè)值， ∏ Ri(r)為 r在 Ri的屬性（即Ui）上的投影 ,t為 r中的一個(gè)元組 ,t[Ri]＝ t[Ui]是 t在Ri的屬性上的投影。定義 mρ為 mρ(r)= ∞∏ Ri(r) 引理 106 設(shè) ρ =｛ R1， R2,… ,Rn｝ 是 R的一個(gè)分解 ， r為 R 的一個(gè)值 ， ri＝ ∏ Ri(r)， 則有 : （ １ ） r是 mρ(r)的子集； （ ２ ） 如果 s= mρ(r) ,則 ∏ Ri(s)＝ ri。 （３） mρ mρ(r)= mρ(r) . 【 例 104】 設(shè)有兩個(gè)關(guān)系模式 R1（ AB） 和 R2（ BC） ，r1， r2為其值。若 r1＝｛ a1b1｝ ,r2＝｛ b1c1， b2c2｝ ，則s＝ r1∞ r2＝｛ a1b1 c1｝， ∏ Ｒ 2(s)=｛ b1c1｝為 r2的子集。 r2中的元組 b2c2由于在 r1中找不到匹配對(duì)象而不出現(xiàn)在 s中。這些通過連接而被淘汰的元組稱為不連接（ dangling）元組。在圖 106所示的關(guān)系 R(C＃ ,TN,D)中，如果一位教師不教課，則其所屬的系也不能在此關(guān)系中表示。如果分解為 R1(C＃ ,TN)和 R3(TN,D)兩個(gè)關(guān)系，就可以解決此問題。實(shí)際上，對(duì)應(yīng)不教課教師的元組是以 R3中的不連接元組出現(xiàn)的。從中也可看出，為什么通過分解可以消除更新異常。 下面介紹無損分解的測(cè)試算法 。 算法 102 檢驗(yàn)一個(gè)分解是否無損分解 。 輸入：關(guān)系模式 R(A1,A2,… ,An） ； R上的函數(shù)依賴集 F；R上的分解 ρ ＝ ｛ R1,R2,… ,Rk｝ 。 輸出： ρ 是否無損分解 。 方法：建立 k n的矩陣 M（ 見圖 107） ,其中每列對(duì)應(yīng)于 R的一個(gè)屬性 ， 每行對(duì)應(yīng)于 ρ 中的一個(gè)關(guān)系模式 。 Ｍ矩陣各元素的值由下面的規(guī)則確定： ??????ijijijjUAbUAajiM ],[ 對(duì)Ｆ中的每一函數(shù)依賴Ｘ → Ｙ反復(fù)進(jìn)行下面的檢查和處理 ， 直至Ｍ無可改變?yōu)橹?。 檢查Ｘ中的屬性所對(duì)應(yīng)的列 ， 找出Ｘ相等的那些行 。 如果找到Ｘ相等的兩個(gè)行 （ 或多行 ） ， 就把對(duì)應(yīng)行中Ｙ的屬性所對(duì)應(yīng)的符號(hào)改成一致 ， 即如果其中之一為 aj， 則其他的也改成aj 。如果這兩個(gè)符號(hào)為 bij和ｂ lｊ ， 則將它們統(tǒng)一成 bij和ｂ lｊ 。 如此進(jìn)行到Ｍ無可改變時(shí)，如果發(fā)現(xiàn)某一行變成了a1， a2,… ,an，則 ρ 是無損分解，否則， ρ 不是無損分解。 【 例 105】 設(shè)有關(guān)系模式Ｒ （ ABCDE） ， ρ ＝ ｛ R1（ AD） ,R2（ AB） ,R3（
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1