【正文】 部為 A， B或 AB的函數(shù)依賴。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3. 函數(shù)依賴閉包 定義 在關(guān)系模式 RU， F中為 F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包 ，記為 F+。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) 傳遞律：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 ? 在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個合適的、能夠反映現(xiàn)實(shí)世界的模式。 定義 關(guān)系模式 RU， F∈ 1NF，如果對于 R的每個非平凡多值依賴 X→→Y（ Y ? X）， X都含有候選碼，則 R∈ 4NF。 （ 5）若 X→→Y， X→→Z，則 X→→Y∩Z。假設(shè)每個倉庫有若干個保管員，有若干種商品。 (2) 插入操作復(fù)雜： 當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組。 由語義可得到下面的函數(shù)依賴 : (S， J)→T， (S， T)→J， T→J ? 候選碼為： (S， J)和 (S， T) ? S、 T、 J都是主屬性 ， 所以 STJ∈ 3NF ? T→J， T是決定屬性集， T不是候選碼 STJ∈ BCNF S J T S T J 解決方法： 將 STJ分解為二個關(guān)系模式： SJ(S， J) ∈ BCNF， TJ(T， J)∈ BCNF T J TJ S J ST 沒有 任何屬性 對碼的部分函數(shù)依賴和傳遞函數(shù)依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 練習(xí)題 指明下列關(guān)系模式屬于第幾范式 . 1. R(X,Y,Z) F={XY→Z} 2. R(X,Y,Z) F={Y→Z,XZ→Y} 3. R(X,Y,Z) F={Y→Z,Y→X,X→YZ} 4. R(X,Y,Z) F={X→Y,X→Z} 5. R(W,X,Y,Z) F={X→Z,WX→Y} 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3NF與 BCNF的關(guān)系與區(qū)別 ? 如果關(guān)系模式 R∈ BCNF，必定有 R∈ 3NF ? 如果 R∈ 3NF，且 R只有一個候選碼，則 R必屬于 BCNF。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 SJP(S,J,P)中， S是學(xué)生， J表示課程， P表示名次。 若 R∈ BCNF ? 每一個決定屬性集（因素）都包含（候選）碼 ? R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼 ? R∈ 3NF（證明） ? 若 R∈ 3NF 則 R不一定 ∈ BCNF 證明：采用反證法。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3NF 例： 2NF關(guān)系模式 SL(Sno, Sdept, Sloc)中 函數(shù)依賴： Sno→Sdept， Sno→Sloc， Sdept→Sloc Sloc傳遞函數(shù)依賴于 Sno，即 SL中存在非主屬性對碼的傳遞函數(shù)依賴。因課程號是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個元組都要刪除。 ? 第一范式是對關(guān)系模式的最起碼的要求。若 K F U，則K稱為 R的一個 侯選碼 （ Candidate Key）。 規(guī)范化 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 : Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有 : Sno → Ssex， Sno → Sage , Sno → Sdept， Sno ←→ Sname, Sname → Ssex， Sname → Sage Sname → Sdept 若 X→Y，并且 Y→X, 則記為 X←→ Y。若對于 R(U)的 任意 一個可能的關(guān)系 r， r中不可能存在兩個元組在 X上的屬性值相等， 而在 Y上的屬性值不等， 則稱 “ X函數(shù)確定 Y” 或 “ Y函數(shù)依賴于 X”，記作 :X→Y。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 結(jié)論： ? Student關(guān)系模式不是一個好的模式。 一、概念回顧 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 二、關(guān)系模式的形式化定義 關(guān)系模式由五部分組成，即它是一個五元組： R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組 U中屬性所來自的域 DOM：屬性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴關(guān)系集合 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 三、什么是數(shù)據(jù)依賴 1. 完整性約束的表現(xiàn)形式 ? 限定屬性取值范圍：例如學(xué)生成績必須在 0100之間 ? 定義屬性 值 間的相互關(guān)連（主要體現(xiàn)于值的 相等與否 ），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 數(shù)據(jù)依賴對關(guān)系模式的影響 屬性組 U上的一組函數(shù)依賴 F： F ＝｛ Sno → Sdept, Sdept → Mname, (Sno, Cname) → Grade ｝ Sno Cname Sdept Mname Grade 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ⒊ 插入異常（ Insertion Anomalies） 該插的數(shù)據(jù)插不進(jìn)去 關(guān)系模式 StudentU, F中存在的問題 ⒈ 數(shù)據(jù)冗余太大 ——浪費(fèi)大量的存儲空間 例：每一個系主任的姓名重復(fù)出現(xiàn) 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個元組。 分解成三個關(guān)系模式 : S (SNO, SDEPT, SNO → DEPT)。 2. 函數(shù)依賴是 語義范疇 的概念。 若 X→Y，但 Y ? X, 則稱 X→Y是 非平凡的函數(shù)依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 三、完全函數(shù)依賴與部分函數(shù)依賴 定義 在關(guān)系模式 R(U)中，如果 X→Y，并且對于 X的任何一個真子集 X?，都有 X? Y, 則稱 Y完全函數(shù)依賴于 X，記作 X F Y。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 范式 ? 范式是符合某一種級別的關(guān)系模式的集合。 例 : 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方。如果這個學(xué)生選修了 K門課，則必須無遺漏地修改 K個元組中全部 Sdept、 Sloc信息。 ? 若 R∈ 3NF，則 R的每一個 非主屬性 既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 C(Cno,Cname,Po) SC(Sno,Cno,Grade) S(Sno,Sname,Sdept,Sage) 它只有一個碼 Cno，這里沒有任何屬性對Cno部分依賴或傳遞依賴，所以 C∈ 3NF。這個關(guān)系模式中顯然沒有屬性對碼傳遞依賴或部分依賴。 ? 3NF的“不徹底”性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。 ? 產(chǎn)生原因： 存在多值依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的定義 定義 設(shè) R(U)是一個屬性集 U上的一個關(guān)系模式， X、 Y和 Z是 U的子集，并且 Z＝ U－ X－ Y， 多值依賴 X→→Y成立當(dāng)且僅當(dāng)對 R的 任一關(guān)系 r，r在（ X， Z）上的每個值對應(yīng)一組 Y的值，這組值僅僅決定于 X值而與Z值無關(guān)。所以 W→→S。 ? 一般地，在 R（ U）上若有 X→→Y在 W（ W ? U）上成立，則稱 X→→Y為 R（ U）的嵌入型多值依賴 ? 只要在 R（ U）的任何一個關(guān)系 r中，元組在 X和 Y上的值滿足定義 （函數(shù)依賴），則函數(shù)依賴 X→Y在任何屬性集 W（ X Y ? W ?U）上成立。 ? 如果考慮 多值依賴 ，則屬于 4NF的關(guān)系模式規(guī)范化程度是最高的了。 （ Augmentation）：若 X→Y為 F所蘊(yùn)含，且 Z ? U，則XZ→YZ為 F所蘊(yùn)含。 若 t[X]=s[X]，由于 X→Y，有 t[Y]=s[Y]； 再由 Y→Z，有 t[Z]=s[Z]，所以 X→Z為 F所蘊(yùn)含 . 傳遞律得證。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 算法 求屬性集 X（ X ? U）關(guān)于 U上的函數(shù)依賴集 F 的閉包 XF+ 輸入： X， F 輸出： XF+ 步驟： （ 1）令 X（ 0） =X， i=0 （ 2）求 B，這里 B = { A |(? V)( ? W)(V→W?F∧ V ? X（ i） ∧ A? W)}； （ 3） X（ i+1） =B∪ X（ i） （ 4）判斷 X（ i+1） = X （ i） 嗎 ? （ 5）若相等或 X（ i） =U , 則 X（ i） 就是 XF+ , 算法終止。 (2)因?yàn)?X（ 0） ≠ X（ 1） ，所以再找出左部為 ABCD子集的那些函數(shù)依賴，又得到 AB→C， B→D， C→E， AC→B， 于是 X（ 2） =X（ 1） ∪ BCDE=ABCDE。 構(gòu)造一張二維表 r，它由下列兩個元組構(gòu)成，可以證明 r必是 R（ U， F）的一個關(guān)系 ，即 F+中的全部函數(shù)依賴在 r上成立。 引理 F+ = G+ 的充分必要條件是： F ? G+ ， 和 G ? F+ 證 : 必要性顯然，只證充分性。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 6. 最小依賴集 定義 如果函數(shù)依賴集 F滿足下列條件 ， 則稱 F為一個 極小函數(shù)依賴集 。 (1)逐一檢查 F中各函數(shù)依賴 FDi： X→Y， 若 Y=A1A2 … Ak， k 2， 則用 { X→Aj |j=1， 2， … ， k} 來取代 X→Y。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 [例 3]已知： F = {A→B， B→A， B→C， A→C， C→A}， 求 F 的極小函數(shù)依賴集 Fm 解： ： F=﹛ A→B， B→A， B→C， A→C， C→A﹜ 2. ① 在 F中去掉 A→B， (A)F+={AC}， ∵ B ? (A)F+ ， ∴ 不去掉。 ② A→C：記 G=F﹛ A→C ﹜ ， ∴ (A)G+= ﹛ ADEB﹜ ， ∴ C ? (A)G+ ， ∴ 不去掉 A→C ， F=﹛ A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 極小化過程 ( 定理 )也是檢驗(yàn) F是否為極小依賴集的一個算法 若改造后的 F與原來的 F相同，說明 F本身就是一個最小依賴集 ? 在 RU， F中可以用與 F等價(jià)的依賴集 G來取代 F 原因：兩個關(guān)系模式 R1 U， F， R2U， G，如果 F與 G等價(jià)，那么 R1的關(guān)系一定是 R2的關(guān)系。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 模式的分解 ? 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系 ， 那么這種分解就沒有 丟失信息 。 既保持函數(shù)依賴，又能無損連接。 ? 如果一個模式分解 保持了函數(shù)依賴 ，則它可以減輕或解決各種異常情況。 算法 轉(zhuǎn)換為 3NF既有無損連接性又保持函數(shù)依賴的分解 算法 轉(zhuǎn)換為 BCNF的無損連接分解 （ 分解法 ） 算法 達(dá)到 4NF的具有無損連接性的分解