Find a decomposition \(\rho\) that satisfies 3NF and preserves \(F\)

We are going to use the 3NF Synthesis Algorithm (also known as Bernstein's algorithm)

Algorithm

1. Handle attributes not in any FD:

   • Let \(S\) = attributes not appearing in any FD
   • If \(S \neq \emptyset\): add \(R_S = S\) to \(\rho\), and remove \(S\) from \(R\) for remaining steps

   Example: If \(R = \{A, B, C, D, E\}\) and \(F = \{B \to D, D \to C\}\), then \(A, E\) don't appear in any FD, so create \(\rho = \{\{A, E\}\}\) and continue with \(R' = \{B, C, D\}\).

2. Find minimal cover \(F_{\text{min}}\) of \(F\) (see here)

   Example: let \(R = \{A, B, C, D, E, G\}\), where \(G\) does not appear in any FD. The minimal cover is \(F_{\text{min}} = \{A \to B, A \to C, B \to D, CD \to E\}\).

3. Group FDs with same LHS (Left-Hand Side), merge RHS (Right-Hand Side):

   • \(X \to A\) and \(X \to B\) becomes \(X \to AB\)
   • Create relation scheme \(R_i\) for \(\rho\): \(R_i = X \cup \{RHS\ attributes\}\)

   Example:

   • \(A \to B, A \to C\) \(\implies\) \(A \to BC\) \(\implies\) \(R_1 = \{A, B, C\}\)
   • \(B \to D\) \(\implies\) \(R_2 = \{B, D\}\)
   • \(CD \to E\) \(\implies\) \(R_3 = \{C, D, E\}\)

4. Add key relation if no relation in \(\rho\) contains a key of \(R\) (original or remaining):

   • Find candidate key \(K\) of \(R\) (include attributes from step 1 if any)
   • If no relation contains \(K\), add \(R_{\text{new}} = K\) to \(\rho\)

   Example: Here \(G\) does not appear in any FD, so it must be in every key. A key of \(R\) is \(\{A, G\}\) (because \((AG)^+ = ABCDEG\)). None of \(R_1, R_2, R_3\) contains \(\{A, G\}\), so we add \(R_4 = \{A, G\}\) to \(\rho\).

5. Cleanup: Remove any relation from \(\rho\) that is a strict subset of another

   Example: After step 3, we have \(\rho = \{\{A, B, C\}, \{B, D\}, \{C, D, E\}, \{A, G\}\}\). None of these is a subset of another, so no cleanup is needed.

   However, if you had relations \(\{A, B\}\) and \(\{A, B, C\}\) in \(\rho\), you would drop \(\{A, B\}\) since it is contained in \(\{A, B, C\}\).

---

Complete Example

Given: \(R = \{A, B, C, D, E, G\}\)

\(F = \{A \to B, A \to C, B \to D, CD \to E\}\) (already minimal, so \(F_{\text{min}} = F\))

Goal: build a decomposition \(\rho\).

Step 1 — Attributes not in any FD:

• Attributes appearing in \(F\): \(\{A, B, C, D, E\}\)
• So \(S = R \setminus \{A, B, C, D, E\} = \{G\}\)
• Start \(\rho = \{\{G\}\}\) and continue with \(R' = R \setminus S = \{A, B, C, D, E\}\)

Step 2 — Minimal cover:

• \(F_{\text{min}} = \{A \to B, A \to C, B \to D, CD \to E\}\)

Step 3 — Group FDs and create relations:

• \(A \to B, A \to C\) \(\implies\) \(A \to BC\) \(\implies\) \(R_1 = \{A, B, C\}\)
• \(B \to D\) \(\implies\) \(R_2 = \{B, D\}\)
• \(CD \to E\) \(\implies\) \(R_3 = \{C, D, E\}\)

Now \(\rho = \{\{G\}, \{A, B, C\}, \{B, D\}, \{C, D, E\}\}\).

Step 4 — Add a key relation (lossless join):

• Because \(G\) is not in any FD, it must be in every key
• Check \((AG)^+\) under \(F_{\text{min}}\): \(AG \implies ABCG \implies ABCDG \implies ABCDEG = R\)
• So \(K = \{A, G\}\) is a key, and no relation in \(\rho\) contains it
• Add \(R_{\text{new}} = \{A, G\}\)

Now \(\rho = \{\{G\}, \{A, B, C\}, \{B, D\}, \{C, D, E\}, \{A, G\}\}\).

Step 5 — Cleanup:

• \(\{G\} \subset \{A, G\}\), so remove \(\{G\}\)

Result: \(\rho = \{\{A, B, C\}, \{B, D\}, \{C, D, E\}, \{A, G\}\}\) ✓ 3NF