Normalization: R(A, B, C, D, E, F, G, H, I, J)
Database Management, Spring 2026
Original Relation:
R (A, B, C, D, E, F, G, H, I, J)
Primary Key: {A, B, C}（題目已給定）
Additional Functional Dependencies（額外的功能相依）:
FD1: AB → DE
FD2: A → D
FD3: J → C
FD4: BC → FGH
FD5: GH → I
Implicit FD: ABC → DEFGHIJ (from PK).（隱含 FD：主鍵決定所有屬性。）
Step 0: Verify Primary Key（驗證主鍵）
Compute {A, B, C}+（計算閉包）
- Start: {A, B, C}
- FD2: A → D ⇒ {A, B, C, D}
- FD1: AB → DE ⇒ {A, B, C, D, E}
- FD4: BC → FGH ⇒ {A, B, C, D, E, F, G, H}
- FD5: GH → I ⇒ {A, B, C, D, E, F, G, H, I}
- Implicit: ABC → J ⇒ {A, B, C, D, E, F, G, H, I, J}
{A, B, C}+ = all attributes ✓
Primary Key = {A, B, C} confirmed.（主鍵 = {A, B, C} 確認。）
Step 1: 2NF — Remove Partial Dependencies（消除部分相依）
Check for Partial Dependencies（檢查部分相依）
PK = {A, B, C} (composite). A non-key attribute has a partial dependency if it depends on a proper subset of the PK.（非鍵屬性若只依賴 PK 的一部分，就是部分相依。）
✗ Partial Dep 1 (FD2): A → D
D depends on A alone (proper subset of {A,B,C}).（D 只依賴 A。）
✗ Partial Dep 2 (FD1): AB → DE ⇒ AB → E (since A→D already)
E depends on AB (proper subset of {A,B,C}).（E 依賴 AB。D 已由 FD2 處理。）
✗ Partial Dep 3 (FD4): BC → FGH
F, G, H depend on BC (proper subset of {A,B,C}).（F, G, H 依賴 BC。）
Not partial:
- FD3: J → C — J is not part of the PK, so this is not a partial dependency.（J 不是 PK 的一部分，不是部分相依。）
- FD5: GH → I — GH is not a subset of PK.（GH 不是 PK 的子集。）
2NF Decomposition（2NF 分解）:
R1 (A, D)
PK: {A} | FD2: A → D
R2 (A, B, E)
PK: {A, B} | AB → E (from FD1, D removed)
R3 (B, C, F, G, H)
PK: {B, C} | FD4: BC → FGH
R_main (A, B, C, I, J)
PK: {A, B, C} | Remaining non-key attributes: I, J（剩餘非鍵屬性）
✓ 2NF satisfied: No partial dependencies remain in any relation.（所有部分相依已消除。）
Step 2: 3NF — Remove Transitive Dependencies（消除遞移相依）
Check each relation（逐一檢查）
R1 (A, D):
✓ A → D, A is PK. No transitive dep.（無遞移相依。）
R2 (A, B, E):
✓ AB → E, {A,B} is PK. No transitive dep.（無遞移相依。）
R3 (B, C, F, G, H):
PK = {B,C}. Check FD5: GH → I — but I is not in R3. Any other transitive deps?
✓ BC → FGH, {B,C} is PK. No non-key attribute determines another non-key attribute within R3.（R3 內無遞移相依。）
R_main (A, B, C, I, J):
PK = {A,B,C}. Check for transitive dependencies:（檢查遞移相依：）
✗ Transitive Dep 1 (FD5): ABC → (via BC→FGH, GH→I) → I
But wait — in R_main, F/G/H are not present (they're in R3). However, GH → I is still a valid FD. Since I is determined by GH (non-key of R_main), and GH is derivable from ABC, this is transitive.
Actually, within R_main itself, the projected FDs are: ABC → IJ. No intermediate non-key determines I within R_main alone.（在 R_main 內部，沒有中間非鍵屬性決定 I。）
✗ Transitive Dep 2 (FD3): J → C
J is a non-key attribute that determines C (a prime/key attribute). In strict 3NF, this is acceptable since C is a prime attribute. However, this violates BCNF (J is not a superkey).（J 是非鍵屬性，決定 C（主屬性）。在 3NF 中可接受（C 是 prime attribute），但違反 BCNF。）
For R_main: The only non-key attributes are I and J. Within R_main, there's no non-key → non-key transitive chain. So R_main is in 3NF.（R_main 中沒有非鍵→非鍵的遞移鏈，滿足 3NF。）
However, we should also extract FD5 (GH → I) as a separate relation since it applies to the original R:（但 GH → I 仍是原始 R 的有效 FD，應獨立成 relation：）
R4 (G, H, I)
PK: {G, H} | FD5: GH → I
3NF Result（3NF 結果）:
R1 (A, D) — PK: {A}
R2 (A, B, E) — PK: {A, B}
R3 (B, C, F, G, H) — PK: {B, C}
R4 (G, H, I) — PK: {G, H}
R5 (A, B, C, J) — PK: {A, B, C}
✓ 3NF satisfied: No non-prime attribute transitively depends on any key.（沒有非主屬性遞移相依於任何鍵。）
Step 3: BCNF
Check: Is every determinant a superkey?（每個決定因子是否都是 superkey？）
✓ R1 (A, D): A → D, A is PK. ✓
✓ R2 (A, B, E): AB → E, {A,B} is PK. ✓
✓ R3 (B, C, F, G, H): BC → FGH, {B,C} is PK. ✓
✓ R4 (G, H, I): GH → I, {G,H} is PK. ✓
✗ R5 (A, B, C, J): J → C (FD3)
J is NOT a superkey of R5 (PK is {A,B,C}). This violates BCNF!
（J 不是 R5 的 superkey，違反 BCNF！）
BCNF Decomposition of R5（R5 的 BCNF 分解）:
Decompose R5 using the violating FD: J → C（用違反的 FD 來分解 R5：）
R5a (J, C)
PK: {J} | FD3: J → C
R5b (A, B, J)
PK: {A, B, J} | Remaining after removing C（移除 C 後的剩餘）
Note: After BCNF decomposition, the PK changes from {A,B,C} to {A,B,J} in R5b, because C is now derived via J→C in R5a.（注意：BCNF 分解後，R5b 的 PK 變成 {A,B,J}，因為 C 可透過 R5a 的 J→C 推導。）
Dependency preservation check: FD3 (J→C) is preserved in R5a. However, the implicit FD ABC→J cannot be checked within a single relation — it requires a join of R5a and R5b. This is a known trade-off of BCNF: it may sacrifice dependency preservation.（這是 BCNF 的已知取捨：可能犧牲相依性保留。）
✓ All relations now in BCNF. Every determinant is a superkey.（所有 relation 現在都滿足 BCNF。）
Final Results（最終結果）
3NF Decomposition（3NF 分解）— 5 relations
| Relation | Schema | PK | FK | FD |
|---|
| R1 | A, D | {A} | — | A → D |
| R2 | A, B, E | {A, B} | A → R1 | AB → E |
| R3 | B, C, F, G, H | {B, C} | — | BC → FGH |
| R4 | G, H, I | {G, H} | — | GH → I |
| R5 | A, B, C, J | {A, B, C} | A→R1, AB→R2, BC→R3 | J → C (non-BCNF) |
BCNF Decomposition（BCNF 分解）— 6 relations
| Relation | Schema | PK | FK | FD |
|---|
| R1 | A, D | {A} | — | A → D |
| R2 | A, B, E | {A, B} | A → R1 | AB → E |
| R3 | B, C, F, G, H | {B, C} | C → R5a (via J) | BC → FGH |
| R4 | G, H, I | {G, H} | — | GH → I |
| R5a | J, C | {J} | — | J → C |
| R5b | A, B, J | {A, B, J} | A→R1, J→R5a | — |
Verification（驗證）
- Lossless Join（無損連接）: Both decompositions can reconstruct R. ✓
- 3NF Dependency Preservation（3NF 相依性保留）: All 5 FDs preserved. ✓
- BCNF Trade-off（BCNF 取捨）: ABC → J may not be directly verifiable without joining R5a and R5b. ✗ (known BCNF limitation)
Database Management, Spring 2026 — 1134542 俞綱皓