執行 BCNF 分解時如何跟踪功能依賴關係

我有以下關係和功能依賴集：

R(A,B,C,D,E,G,H)
F = {AB -> CD, E -> D, ABC -> DE, E -> AB, D -> AG, ACD -> BE}

我對在分解 R 時如何跟踪函式依賴關係感到非常困惑。

例如，如果我們分解：

R1 = (ABCD)
R2 = (DEGH)

然後（簡單的）：

F1 = {AB -> CD}
F2 = {E -> D}

所以我想知道的是，跟踪 F1、F2 中其餘功能依賴關係的最佳策略是什麼。

找到 ABCD 的所有子集的閉包來完成 F1 就足夠了嗎？還是應該在分解發生之前找到所有 ABCDEGH 子集的閉包？我實際上不太確定這將如何發生。例如：

解壓前：

D+ = DAG

解壓後

D+ = D? 

分解和功能依賴

一般而言，當具有依賴關係F的關係**R(T)分解為兩個關係R 1 (T 1 )、R 2 (T 2 )時，這兩個關係中的依賴關係不能立即從原始依賴關係集F . 這是因為可能存在由F**隱含的依賴關係，即在F +中，它們存在於分解的關係中。如果我們想知道分解關係中的所有依賴關係，我們應該考慮依賴關係的投影**F超過分解關係的屬性。

這是一組依賴項F的投影的正式定義：給定R和T i ⊆ T，F在T i上的投影等於π T i (F) = {X → Y ∈ F + | X,Y ⊆ T i }。換句話說，應該計算F + ，即F的閉包，然後得到具有T i中所有屬性的所有依賴項。

但是，由於*F +*的計算是一個指數任務，一組函式依賴關係的投影的計算是一個指數任務，實際上並沒有執行（部分來自具有很少屬性和依賴關係的簡單案例）。

相反*，可以用多項式算法決定的是這個問題的答案：具有依賴關係F的R(T)的分解**R 1 (T 1 )*、R 2 (T 2 )是否保留了依賴關係？（參見 J. Ullman，《數據庫系統原理》，電腦科學出版社，1983 年）。

根據定義，如果投影在分解關係上的依賴關係的閉包等於原始關係的閉包，則分解保留依賴關係。形式上，分解*R i (T i )*保留依賴關係當且僅當 (∪π T i ( F )) + = F +。

為什麼我們對分解關係的 FD 感興趣？

當出於特定原因進行分解時，例如為了規範化關係，我們有興趣知道分解是否保留了依賴關係（否則它不是一個好的分解）。

但是，雖然在 3NF 的合成算法中，我們保證分解總是保留依賴關係，但對於 BCNF，情況並非如此。相反，在 BCNF 中，存在實際上無法在不失去依賴關係的情況下分解關係的範例（例如，R(A,B,C), F={AB → C, C → A}）。

概括

1. 當我們為 BCNF 進行分解時，我們應該準備好失去一些依賴性（因此，在實踐中使用了 3NF）。
2. BCNF 的分析算法需要執行一個指數任務，因為在每一步都應該檢查一個分解的關係是否仍然不在 BCNF 中，並且要知道這個關係應該知道它的依賴關係的投影（或至少它的覆蓋）。

以 BCNF 為例

在您的範例中，使用經典分析算法獲得的 BCNF 如下（從F的最小覆蓋開始並產生具有依賴項投影覆蓋的分解）：

R2 < (A B H) , { } >

R3 < (A D G) , { D → A, D → G } >

R4 < (B C D E) , { E → D, E → B, C D → B, B D → C, B D → E } >

請注意，在此分解中，兩個原始依賴項：

{ A B → C D
 A B C → D E }

失去了。

引用自：https://dba.stackexchange.com/questions/169389