Functional Dependencies and Normalization: From Closure to 3NF and BCNF

Normalization is not a ritual of splitting wide tables. It is a way to place each fact where its determinant can enforce it once.

Functional dependency means determination

X → Y means that any two legal rows agreeing on X must also agree on Y. It is a rule about all valid states, not an observation about today’s sample.

For relation R(A,B,C,D,E) with:

A  → BC
CD → E
B  → D
E  → A

we can test whether A is a key by computing its closure.

A⁺ = {A}
A → BC  => {A,B,C}
B → D   => {A,B,C,D}
CD → E  => {A,B,C,D,E}

A⁺ contains every attribute, so A is a superkey. Because no proper subset of the single attribute exists, it is also a candidate key.

In plain terms: closure is controlled reachability. Start with what you know, repeatedly apply rules, and stop when no new attribute can be reached.

Candidate keys are minimal superkeys

“Minimal” means no attribute can be removed while retaining full closure. It does not mean the key has the fewest characters among all possible keys.

In the example, E⁺ reaches A, then every other attribute, so E is another candidate key. Finding one key does not prove it is the only one.

Minimal cover simplifies the rule set

A minimal cover normally follows three steps:

Split right-hand sides so each dependency has one attribute on the right.
Remove extraneous attributes from left-hand sides.
Remove dependencies implied by the others.

After every removal, recompute closure using the remaining set. Intuition is not enough because indirect paths are easy to miss.

BCNF asks who determines

A relation is in BCNF when every non-trivial dependency X → Y has a superkey on the left. If B → D holds in the example but B is not a superkey, one B value’s D fact is repeated across several rows.

Decompose on the violation:

R1(B,D)
R2(A,B,C,E)

This decomposition is lossless because the common attribute B functionally determines R1.

Why 3NF is sometimes the practical answer

BCNF removes more redundancy, but a BCNF decomposition can lose dependency preservation. 3NF allows a dependency whose right-hand attribute is prime, which can preserve all original constraints in individual tables.

The 3NF synthesis procedure uses a minimal cover, creates one relation per determinant group, removes contained relations, and adds a candidate-key relation if none exists.

The tradeoff is precise:

BCNF prioritizes elimination of dependency-based redundancy.
3NF prioritizes a lossless, dependency-preserving decomposition.

What normalization does not decide

Normalization does not select indexes, partitioning, caches, or API shapes. A normalized model can still be slow. Denormalization can be sensible for a measured read path, but it creates a synchronization obligation that should be named explicitly.

Review card

An FD is a rule over all legal instances.
Closure tests implication and superkeys.
A candidate key is a minimal superkey.
Recompute closure while reducing a minimal cover.
BCNF requires every determinant to be a superkey.
3NF may preserve dependencies that BCNF decomposition loses.
Denormalization trades read simplicity for update responsibility.

正規化不是把寬 table 切小的儀式，而是讓每個 fact 只放在能決定它的 determinant 之下，並且只維護一次。

Functional dependency 表示決定關係

X → Y 表示任何兩筆合法資料只要 X 相同，Y 就必須相同。它是對所有合法狀態的規則，不是觀察今天 sample 得到的巧合。

假設 relation R(A,B,C,D,E) 有：

A  → BC
CD → E
B  → D
E  → A

可以用 closure 測試 A 是否為 key：

A⁺ = {A}
A → BC  => {A,B,C}
B → D   => {A,B,C,D}
CD → E  => {A,B,C,D,E}

A⁺ 包含所有 attribute，所以 A 是 superkey。它只有一個 attribute，已經不能再移除，因此也是 candidate key。

白話來說： Closure 是有規則的可達性搜尋。從已知 attribute 開始，反覆套用 FD，直到再也到不了新 attribute。

Candidate key 是最小 superkey

「最小」是指移除任何 attribute 都不再有完整 closure，不是所有可能 key 中字數最短的那一個。

在例子裡，E⁺ 可以先到 A，再到其他全部 attribute，所以 E 也是 candidate key。找到一個 key 不代表已經找到所有 key。

Minimal cover 簡化規則集合

Minimal cover 通常分三步：

拆開右側，讓每條 FD 右邊只有一個 attribute。
移除左側 extraneous attribute。
移除可由其他 FD 推導的 redundant dependency。

每次嘗試移除後，都要使用剩餘 FD 重新計算 closure。只靠直覺很容易漏掉間接路徑。

BCNF 在問誰能決定資料

Relation 符合 BCNF 的條件是：每條 non-trivial FD X → Y 的左側 X 都必須是 superkey。例子裡若 B → D 成立但 B 不是 superkey，同一個 B 對應的 D fact 就會重複出現在多列。

可依違規 FD 分解：

R1(B,D)
R2(A,B,C,E)

共同 attribute B 可以決定 R1，因此這個 decomposition 是 lossless。

為什麼有時選 3NF

BCNF 消除更多 redundancy，但 BCNF decomposition 可能失去 dependency preservation。3NF 允許右側是 prime attribute 的特殊情況，因此有機會讓原始 constraint 都能在單一 table 中檢查。

3NF synthesis 使用 minimal cover，依 determinant group 建 relation，移除被包含的 relation；如果沒有任何 relation 含 candidate key，再補一個 key relation。

取捨很明確：

BCNF 優先消除 dependency 導致的 redundancy。
3NF 優先得到 lossless 且 dependency-preserving 的 decomposition。

正規化不負責哪些事

Normalization 不會替你決定 index、partition、cache 或 API shape。Normalized model 仍可能很慢。為已量測的 read path 做 denormalization 可以合理，但一定會新增同步責任，必須明確記錄。

複習卡

FD 是對所有合法 instance 的規則。
Closure 用來測 implication 與 superkey。
Candidate key 是最小 superkey。
簡化 minimal cover 時要反覆重算 closure。
BCNF 要求每個 determinant 都是 superkey。
3NF 可能保留 BCNF decomposition 會失去的 dependency。
Denormalization 用更新責任交換讀取簡單度。