Finding the Minimal Cover of Functional Dependencies

A minimal cover (also known as a canonical cover) of a set of functional dependencies (FDs) F is a set of FDs G such that:

• Every FD in G is implied by F ($G^+ \subseteq F^+$).
• Every FD in F is implied by G ($F^+ \subseteq G^+$), meaning $F$ and $G$ are equivalent ($F^+ = G^+$).
• Every FD in G has a single attribute on the right-hand side (RHS).
• For every FD $X \to A$ in G, the set $G - \{X \to A\}$ is not equivalent to G. (No redundant FDs).
• For every FD $X \to A$ in G, the set $(X - \{B\}) \to A$ for any attribute $B \in X$ is not implied by G. (Left-hand side is minimal).

To find a minimal cover for a given set of FDs F, we follow these steps:

Steps to Compute the Minimal Cover

Step 1: Ensure Single Attribute on RHS

We start with the given set of functional dependencies:

$F = \{A \to B, ABCD \to E, EF \to G, EF \to H, ACDF \to EG\}$

Split any FD with multiple attributes on the RHS into multiple FDs, each with a single attribute on the RHS. The FD $ACDF \to EG$ is split into $ACDF \to E$ and $ACDF \to G$.

The new set of FDs, F$_1$, is:

$F_1 = \{A \to B, ABCD \to E, EF \to G, EF \to H, ACDF \to E, ACDF \to G\}$

Step 2: Eliminate Redundant Functional Dependencies

Next, we check if any FD in F$_1$ is redundant. An FD $X \to Y$ is redundant if it can be derived from the other FDs in the set, i.e., if Y is in the closure of X ($X^+$) computed using the remaining FDs.

Let's check each FD in F$_1$:

• $A \to B$: To check if $A \to B$ is redundant, we compute the closure of A using $F_1 - \{A \to B\} = \{ABCD \to E, EF \to G, EF \to H, ACDF \to E, ACDF \to G\}$. $A^+ = \{A\}$. Since B is not in $A^+$, $A \to B$ is not redundant.
• $ABCD \to E$: To check if $ABCD \to E$ is redundant, we compute the closure of ABCD using $F_1 - \{ABCD \to E\} = \{A \to B, EF \to G, EF \to H, ACDF \to E, ACDF \to G\}$. $(ABCD)^+$ using this set: $\{A, B, C, D\} \xrightarrow{A \to B} \{A, B, C, D\}$. No other FDs apply directly. E is not in $(ABCD)^+$. So $ABCD \to E$ is not redundant in this step.
• $EF \to G$: To check if $EF \to G$ is redundant, we compute the closure of EF using $F_1 - \{EF \to G\} = \{A \to B, ABCD \to E, EF \to H, ACDF \to E, ACDF \to G\}$. $(EF)^+$ using this set: $\{E, F\} \xrightarrow{EF \to H} \{E, F, H\}$. No other FDs apply. G is not in $(EF)^+$. So $EF \to G$ is not redundant.
• $EF \to H$: To check if $EF \to H$ is redundant, we compute the closure of EF using $F_1 - \{EF \to H\} = \{A \to B, ABCD \to E, EF \to G, ACDF \to E, ACDF \to G\}$. $(EF)^+$ using this set: $\{E, F\} \xrightarrow{EF \to G} \{E, F, G\}$. No other FDs apply. H is not in $(EF)^+$. So $EF \to H$ is not redundant.
• $ACDF \to E$: To check if $ACDF \to E$ is redundant, we compute the closure of ACDF using $F_1 - \{ACDF \to E\} = \{A \to B, ABCD \to E, EF \to G, EF \to H, ACDF \to G\}$. $(ACDF)^+$ using this set:
  • Start with $\{A, C, D, F\}$.
  • Using $A \to B$, add B. Set is $\{A, B, C, D, F\}$.
  • Using $ABCD \to E$ (since ABCD is in $\{A, B, C, D, F\}$), add E. Set is $\{A, B, C, D, E, F\}$.
  • E is in $(ACDF)^+$. So $ACDF \to E$ is redundant. Remove it.
  The current set of FDs is now $\{A \to B, ABCD \to E, EF \to G, EF \to H, ACDF \to G\}$.
• $ACDF \to G$: To check if $ACDF \to G$ is redundant, we compute the closure of ACDF using the current set minus $ACDF \to G$: $\{A \to B, ABCD \to E, EF \to G, EF \to H\}$. $(ACDF)^+$ using this set:
  • Start with $\{A, C, D, F\}$.
  • Using $A \to B$, add B. Set is $\{A, B, C, D, F\}$.
  • Using $ABCD \to E$ (since ABCD is in $\{A, B, C, D, F\}$), add E. Set is $\{A, B, C, D, E, F\}$.
  • Using $EF \to G$ (since EF is in $\{A, B, C, D, E, F\}$), add G. Set is $\{A, B, C, D, E, F, G\}$.
  • G is in $(ACDF)^+$. So $ACDF \to G$ is redundant. Remove it.
  The set of FDs after eliminating redundant ones is F$_2$:

$F_2 = \{A \to B, ABCD \to E, EF \to G, EF \to H\}$

Step 3: Minimize the Left-Hand Side (LHS)

For each FD $X \to Y$ in F$_2$, we check if removing any attribute from X still results in an FD that is implied by F$_2$. If $X' \to Y$ is implied by F$_2$ for $X' \subset X$, then we can replace $X \to Y$ with $X' \to Y$. We repeat this until no attribute can be removed from any LHS.

Let's check each FD in F$_2$:

• $A \to B$: The LHS is a single attribute, so it cannot be minimized further.
• $ABCD \to E$: The LHS is ABCD. We check if any subset of ABCD can determine E using F$_2$.
  • Check $ACD \to E$: Is E in $(ACD)^+$ w.r.t. F$_2$? $(ACD)^+$ using $\{A \to B, ABCD \to E, EF \to G, EF \to H\}$: $\{A, C, D\} \xrightarrow{A \to B} \{A, B, C, D\} \xrightarrow{ABCD \to E} \{A, B, C, D, E\}$. Yes, E is in $(ACD)^+$. So we can replace $ABCD \to E$ with $ACD \to E$.
  • Check $ABD \to E$: Is E in $(ABD)^+$ w.r.t. F$_2$? $(ABD)^+$ using $A \to B$ gives $\{A, B, D\}$. Cannot derive E.
  • Check $ABC \to E$: Is E in $(ABC)^+$ w.r.t. F$_2$? $(ABC)^+$ using $A \to B$ gives $\{A, B, C\}$. Cannot derive E.
  Since $ACD \to E$ is implied by F$_2$, we replace $ABCD \to E$ with $ACD \to E$. The current set of FDs is now {$A \to B, ACD \to E, EF \to G, EF \to H$}. Let's call this set M. We must now perform subsequent checks using M. We already verified above that BCD $\to$ E, ABD $\to$ E, ABC $\to$ E are not derivable from F$_2$, which is equivalent to M. The minimal LHS for this dependency is ACD.
• $EF \to G$: The LHS is EF. We check E $\to$ G and F $\to$ G using M.
  • Is G in $E^+$ w.r.t. M? $E^+ = \{E\}$. No G.
  • Is G in $F^+$ w.r.t. M? $F^+ = \{F\}$. No G.
  LHS EF cannot be minimized further.
• $EF \to H$: The LHS is EF. We check E $\to$ H and F $\to$ H using M.
  • Is H in $E^+$ w.r.t. M? $E^+ = \{E\}$. No H.
  • Is H in $F^+$ w.t.r. M? $F^+ = \{F\}$. No H.
  LHS EF cannot be minimized further.

The set of FDs after minimizing LHS is:

$M = \{A \to B, ACD \to E, EF \to G, EF \to H\}$

Verifying the Minimal Cover

The set M satisfies the conditions for a minimal cover:

• RHS is a single attribute for all FDs.
• We eliminated redundant FDs and minimized LHS, ensuring no FD or part of an LHS is redundant in M. (Detailed checks performed in steps 2 and 3).
• The set M is equivalent to the original set F.

Comparing with Options

Let's compare our derived minimal cover M with the given options:

Option 1: {$A \to B, ACD \to E, EF \to G$, and $EF \to H$}

Option 2: {$A \to B, ACD \to E, EF \to G, EF \to H$ and $ACDF \to G$} (Contains redundant $ACDF \to G$)

Option 3: {$A \to B, ACD \to E, EF \to G, EF \to H$ and $ACDF \to E$} (Contains redundant $ACDF \to E$)

Option 4: {$A \to B, ABCD \to E, EF \to H$ and $EF \to G$} (Contains $ABCD \to E$ instead of $ACD \to E$, LHS is not minimal)

Our derived minimal cover matches Option 1.

Conclusion

Based on the steps for finding the minimal cover, the set of functional dependencies $\{A \to B, ACD \to E, EF \to G, EF \to H\}$ is the minimal cover for the given set F.

Revision Table: Functional Dependencies Concepts

Additional Information: Properties and Axioms

Understanding functional dependencies and their properties is crucial in database design, particularly for normalization.

• Armstrong's Axioms: These are a set of inference rules used to derive all FDs implied by a given set of FDs. They are:
  • Reflexivity: If Y is a subset of X, then $X \to Y$. ($X \supseteq Y \implies X \to Y$)
  • Augmentation: If $X \to Y$, then $XZ \to YZ$ for any set of attributes Z.
  • Transitivity: If $X \to Y$ and $Y \to Z$, then $X \to Z$.

  Derived rules include Union ($X \to Y, X \to Z \implies X \to YZ$) and Decomposition ($X \to YZ \implies X \to Y, X \to Z$). These axioms are sound and complete.

• Finding Closure ($X^+$): The closure of an attribute set X w.r.t. FDs F can be found by repeatedly applying Armstrong's Axioms until no new attributes can be added. An algorithm for this starts with $Result = X$ and iteratively adds attributes Y to Result if there is an FD $A \to B$ in F where A is a subset of Result and B is not in Result.
• Uses of Minimal Cover: Minimal covers are used in database normalization algorithms (e.g., BCNF and 3NF decomposition) and for testing the equivalence of sets of functional dependencies.