關系數據庫規范化理論-資料下載頁

　　

【正文】 。稱之為引理2：引理2：X→A1 A2…Ak成立的充分必要條件是X→Ai成立（i＝1，2，…，k）。例：證明：對R（A，B，C，G，H，I），F＝｛A→B，A→C，CG→H，CG→I，B→H｝，存在：A→H，CG→HI，AG→I求證：(1)由于A→B，B→H，依傳遞律，可得A→H (2)由于CG→H，CG→I，依合成規則，可得 CG→HI（3）由于A→C，CG→I，依偽傳遞律，可得AG→I。也可另證為： 由A→C，依增廣律，得AG→CG，又CG→I，依傳遞律，得：AG→I二、閉包及其計算定義：R（U，F），由Armstrong公理從F推出的函數依賴X→Ai中Ai的屬性集合，為X的屬性閉包，記作：X＋，讀作X關于函數依賴集F的閉包。也有的書上這樣表示：XF＋＝｛A｜X→A能由F根據Armstrong公理導出｝由引理2可以推出引理3：設R（U，F），X，YU，則從F推導出X→Y的充要條件是YX＋如果要判斷X→Y是否能由F根據Armstrong公理導出，只需求出X＋，并判斷Y是否為X＋的子集即可。那么，只要求出X＋，一切問題就都解決了。書上有一個求X＋的算法。其基本思想是：首先明確X＋的含義是X所能函數決定的所有被決定因素的集合。然后，只要能證明某個屬性或屬性組函數依賴于X，便能確定它屬于X＋，因為X→X是無爭的事實，所以X應屬于X＋，然后在F中尋找其決定因素包含于X的函數依賴，若存在，則它的被決定因素也應屬于X＋，（若Y→Z,則WY→WZ,從而可分解為WY→W和WY→Z）。依次類推，找出F中所有決定因素包含于所求出的中間集的所有函數依賴，并把它們的被決定因素都并到該閉包的中間集中。直到在F中再也找不到符合上述條件的函數依賴時。所求的閉包集就是最終的閉包。下面通過一個例子來說明。例：R（U，F），其中U＝｛A，B，C，D，E，I｝，F＝｛A→D，AB→C，BI→C，ED→I，C→E｝，求(AC)＋解：（1）令X＝｛AC｝，則X（0）＝AC。（2）在F中找出左邊是AC子集的函數依賴：A→D，C→E；（3）X（1）＝X（0）∪D∪E＝ACDE；（4）很明顯X（1）≠X（0）；（5）在F中找左邊是ACDE子集的函數依賴：ED→I；（6）X（2）＝X（1）∪I =ACDEI ；（7）雖然X（2）≠X（1），但是F中未用過的函數依賴的左邊屬性已沒有X（2）的子集，所以停止計算，輸出（AC）＋＝X（2）＝ACDEI。三、函數依賴的覆蓋函數依賴集的閉包：關系模式R（U，F）中為F所邏輯蘊含的函數依賴的全體叫做F的閉包，記為F＋。函數依賴的覆蓋：設F和G是關系模式R（U）上的兩個函數依賴集，如果F＋＝G＋，則稱F和G是等價的，記作F≡G。也可以說F覆蓋G，或G覆蓋F，或F、G相互覆蓋。兩個引理：（1）F≡G的充分必要條件是FG＋、GF＋（2）任一函數依賴集，總可以為一右邊全是單屬性的函數依賴集所覆蓋。對上述引理（1）是顯而易見的。引理（2）可以這樣理解，根據函數依賴的分解規則，任一個右部為屬性組的函數依賴都可以分解為右部為單屬性的若干個函數依賴。所以，對于任一個函數依賴集，總可以找到一個右邊全是單屬性的函數依賴集覆蓋它。定義：如果函數依賴集F滿足下列條件，則稱F為一個極小函數依賴集，或稱最小依賴集或最小覆蓋。216。 F中任一函數依賴的右部都是單屬性；216。 F中任一函數依賴X→A，都不會使F與F－｛X→A｝等價。216。 F中任一函數依賴X→A，X的任一真子集Z，不會使F－｛X→A｝∪｛Z→A｝與F等價。上述第二個條件保證了F中不存在多余的函數依賴，第三個條件保證了F中每個函數依賴左部沒有多余的屬性。要注意上列條件三中的下劃線部分，并注意 Z→A不是一個函數依賴，而是指Z?X的一組Z→A。并且F－｛X→A｝∪｛Z→A｝是不確切的。定理：任一函數依賴集F均等價于一個極小的函數依賴集Fm。最小的依賴集可以上述定義為基本思想所確定的算法求解。四、關系模式的分解關系模式經分解后，應與原來的關系模式等價。即兩者對數據的使用者來說應是等價的。即對分解前后的關系，做相同內容的查詢，應產生相同的結果。這是對模式分解的基本要求。歷年來，人們對等價的概念形成了三種不同的定義：216。 分解具有“無損連接性”（Lossless join）；216。 分解具有“函數依賴保持性”（Preserve dependency）；216。 分解既要具有“無損連接性”，又要具有“函數依賴保持性”下面分別介紹無損連接性和函數依賴保持性兩個概念的含義及其判定算法。無損連接性：對關系模式分解時，原關系模式下任一合法的關系實例，在分解之后，應能通過自然連接運算恢復起來。所以無損連接性有時也稱為無損分解。（下列定義按照課時的情況選擇講解或不講）定義：設ρ＝｛R1，R2，…，Rk｝是關系模式R（U，F）的一個分解，如果對于R的任一滿足F的關系r，都有 r＝∏R1（r）?∏R2（r）?…?∏Rk（r），則稱分解ρ是滿足函數依賴集F的無損連接分解或無損分解。關于無損連接性的判斷算法很巧妙，也很容易理解，在課堂上不講，但有可能出現此類考題，請同學們自己看書學習。（）函依賴保持性：函數依賴集的投影：設有關系模式R（U，F），Z?U，則Z所涉及到的F中所有函數依賴為F在Z上的投影，記為∏Z（F），有 ∏Z（F）＝｛X→Y｜(X→Y)∈F＋且XY?Z｝函數依賴保持性：設R（U，F）的一個分解ρ＝｛R1，R2，…，Rk｝，如果F等價于∏R1（F）∪∏R2（F）∪…∪∏Rk（F） 則稱分解ρ具有函數依賴保持性。一個無損連接的分解不一定具有函數依賴保持性；同樣地，一個具有函數依賴保持性的分解也不一定具無損連接性。檢驗一個分解是否具有依賴保持性，實際上是檢驗∏R1（F）∪∏R2（F）∪…∪∏Rk（F）是否覆蓋F。（書上關于它的算法令人費解。可以不講）。在實際數據庫設計中，關系模式的分解主要有兩種準則：（1） 只滿足無損連接性；（2） 既滿足無損連接性，又滿足函數依賴保持性。準則（2）比（1）更理想，但分解時受到更多的限制。如果一個分解，只滿足函數依賴保持性，而不滿足無損連接性，是沒有實用價值的。所以無損連接性是模式分解必須滿足的條件。