Hamish Burke | 2025-05-27

Related to: #databases

Minimal Cover

• Set of Functional Dependency's equivalent to the original, where every dependency has a single attribute on the right, no left-side attribute is extraneous, and no dependency is redundant

1. For every FD $X\to YZ$, replace with $X\to Y$ and $X\to Z$

• (Reverse of Armstrong Inference Rules reflexivity rule)

2. For each FD $X\to A$ and each attribute $B$ in $X$

• $X^{\prime }=X-\{B\}$
• Compute Attribute Closure $X^{\prime }\star$ under current FD set
• If $A\in X^{\prime }\star$, remove $B$ from $X$

3. For each FD $X\to A$ in turn

• Let $F^{\prime }=F$ without $X\to A$
• Compute $X\star$ under $F^{\prime }$
• If $A\in X\star$, delete $X\to A$ from $F$

Minimal Cover Example

• $R=\{A,B,C,D\}$
• $F=\{A\to BC,B\to C,AC\to D\}$

1. $F=\{A\to B,A\to C,B\to C,AC\to D\}$
2. For $AC\to D$, test $C$ extraneous
   1. $X^{\prime }=\{A\}$
   2. $A\star =A,B,C,D$
   3. $D\in A\star$, $C$ is extraneous
   4. Replace $AC\to D$ with $A\to D$
3. $F=\{A\to B,A\to C,A\to D,B\to C\}$
   1. $F^{\prime }=\{A\to C,A\to D,B\to C\}$
      1. $X\star =ACD$, $B$ not in $X\star$, keep $A\to B$
   2. $F^{\prime }=\{A\to B,A\to D,B\to C\}$
      1. $X\star =ABCD$, $C\in X\star$, so remove $A\to C$
   3. $F^{\prime }=\{A\to B,A\to C,B\to C\}$
      1. $X\star =ABC$, $D$ not in $X\star$
   4. $F^{\prime }=\{A\to B,A\to C,A\to D\}$
      1. $X\star =B$, $C$ not in $X\star$
4. Minimal cover FD: $F=\{A\to B,A\to D,B\to C\}$