Normal Forms

• If a relation is in a certain normal form, it is known that certain kinds of problems are avoided/minimized
  • This can be used to decide whether decomposing the relation will help

Boyce-Codd Normal Form (BCNF)

• If for all $X\to A$ in $F^{+}$, $X\to A$ is trivial ($X$ contains $A$) or $X$ contains a key for $R$
• Relation $R$ is in BCNF if the only non-trivial FDs that hold over $R$ represent key constraints
• Ensures that no redundancy can be detected using FD information alone
  • Most desirable normal form in terms of redundancy
• Decomposition into
  • Given: Relation $R$ with FDs $F$
  • Look among the given FDs for a BCNF violation $X\to B$
    • If any FD following from $F$ violates BCNF, then there will surely be an FD in $F$ itself that violates BCNF
  • Compute $X^{+}$
    • Not all attributes, or else $X$ is a superkey
  • Decompose $R$ using $X\to B$
    • Replace $R$ by relations with schemas:
      • $R_1=X^{+}$
      • $R_2=R-(X^{+}-X)$
    • Project given FDs $F$ onto the two new relations
    • Lossless decomposition
• Steps
  1. Find keys of relation $R$
  2. Find a BCNF violation FD $X\to A$
  3. Compute $X^{+}$
  4. Decompose to $R_1$ and $R_2$
  5. Find projecting FDs
• Problem
  • When $AB\to C$ and $C\to B$
  • There are two keys, $\{A,B\}$ and $\{A,C\}$
  • $C\to B$ is a BCNF violation, so we must decompose into $AC,BC$
  • After decomposing you can no longer guarantee that $AB\to C$

3rd Normal Form (3NF)

• Modifies the BCNF condition so it does not have the decomposition problem
• An attribute is prime if it is the member of any key
• $X\to A$ violates 3NF iff $X$ is not a superkey and $A$ is not prime
• Allows for some redundancy (it is a compromise when BCNF is not possible)
  • Should be used when a lossless-join, dependency preserving decomposition into BCHNF is not possible
• To ensure dependency preservation
  • Use a minimal cover for $F$ (the fewest possible functional dependencies that still produces $F^{+}$)
  • If any $X\to A$ in the minimal cover is not preserved, add $XA$ to a relation