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