Finding a minimal cover of \(F\)¶

Algorithm¶

Input:

A relation schema \(R\).
A set of functional dependencies \(F\).

Output:

A minimal cover \(G\) of \(F\) (i.e., \(G \equiv F\) and \(G\) is minimal).

Procedure¶

Split right-hand sides (decomposition rule):
- Rewrite each FD \(X \to A_1 A_2 \dots A_n\) as separate FDs: \(X \to A_1\), \(X \to A_2\), …, \(X \to A_n\).
- After this step, every FD has a single attribute on the right-hand side.
Minimize left-hand sides (remove extraneous attributes):
- For each FD \(X \to A\) where \(|X| > 1\), try removing each attribute \(B \in X\) one at a time.
- To check if \(B\) is extraneous: compute \((X \setminus \{B\})^+_F\).
- If \(A \in (X \setminus \{B\})^+_F\), then \(B\) is extraneous and can be removed from the LHS.
- Continue until no more attributes can be removed from any LHS.
Remove redundant dependencies:
- For each FD \(X \to A\), let \(G = F \setminus \{X \to A\}\) and compute \(X^+_G\).
- If \(A \in X^+_G\), then \(X \to A\) is redundant and can be eliminated.
- Continue until no more FDs can be removed.
Return \(G\) (the resulting set of FDs).

Important observation¶

It is crucial to perform Step 2 before Step 3. While in general the result is still correct, there are cases where reversing the order produces a set that is not a minimal cover (see Example 2 below).

Example 1¶

Given:

Schema: \(R = (A, B, C, D, E, H)\)
Functional dependencies: \(F = \{AB \to CD,\ C \to E,\ AB \to E,\ ABC \to D\}\)

Find a minimal cover \(G\) of \(F\).

Step 1 — Split right-hand sides¶

Decompose FDs with multiple attributes on the RHS:

\(AB \to CD\) becomes \(AB \to C\) and \(AB \to D\).

After splitting:

\[F = \{AB \to C,\ AB \to D,\ C \to E,\ AB \to E,\ ABC \to D\}\]

Step 2 — Minimize left-hand sides¶

For each FD with multiple attributes on the LHS, check if any attribute is extraneous.

Check \(AB \to C\):

Test if \(A\) is extraneous: compute \((A)^+_F = \{A\}\). Since \(C \notin \{A\}\), \(A\) is not extraneous.
Test if \(B\) is extraneous: compute \((B)^+_F = \{B\}\). Since \(C \notin \{B\}\), \(B\) is not extraneous.

The LHS cannot be reduced.

Check \(AB \to D\):

Test if \(A\) is extraneous: compute \((A)^+_F = \{A\}\). Since \(D \notin \{A\}\), \(A\) is not extraneous.
Test if \(B\) is extraneous: compute \((B)^+_F = \{B\}\). Since \(D \notin \{B\}\), \(B\) is not extraneous.

The LHS cannot be reduced.

Check \(AB \to E\):

Test if \(A\) is extraneous: compute \((A)^+_F = \{A\}\). Since \(E \notin \{A\}\), \(A\) is not extraneous.
Test if \(B\) is extraneous: compute \((B)^+_F = \{B\}\). Since \(E \notin \{B\}\), \(B\) is not extraneous.

The LHS cannot be reduced.

Check \(ABC \to D\):

We already have \(AB \to D\) in \(F\).
Since \(D\) can be derived from \(AB\) alone, the dependency \(ABC \to D\) is subsumed and can be eliminated.

After Step 2:

\[F = \{AB \to C,\ AB \to D,\ C \to E,\ AB \to E\}\]

Step 3 — Remove redundant dependencies¶

For each FD, check if it can be derived from the others.

Check \(AB \to C\):

Let \(G = \{AB \to D,\ C \to E,\ AB \to E\}\).
Compute \((AB)^+_G = \{A, B, D, E\}\).
Since \(C \notin (AB)^+_G\), the dependency \(AB \to C\) is not redundant.

Check \(AB \to D\):

Let \(G = \{AB \to C,\ C \to E,\ AB \to E\}\).
Compute \((AB)^+_G = \{A, B, C, E\}\).
Since \(D \notin (AB)^+_G\), the dependency \(AB \to D\) is not redundant.

Check \(C \to E\):

Let \(G = \{AB \to C,\ AB \to D,\ AB \to E\}\).
Compute \((C)^+_G = \{C\}\).
Since \(E \notin (C)^+_G\), the dependency \(C \to E\) is not redundant.

Check \(AB \to E\):

Let \(G = \{AB \to C,\ AB \to D,\ C \to E\}\).
Compute \((AB)^+_G\):
1. Start: \((AB)^+_G = \{A, B\}\)
2. Using \(AB \to C\): add \(C\) → \(\{A, B, C\}\)
3. Using \(AB \to D\): add \(D\) → \(\{A, B, C, D\}\)
4. Using \(C \to E\): add \(E\) → \(\{A, B, C, D, E\}\)
Since \(E \in (AB)^+_G\), the dependency \(AB \to E\) is redundant and can be eliminated.

Result¶

The minimal cover of \(F\) is:

\[G = \{AB \to C,\ AB \to D,\ C \to E\}\]

Summary table¶

Step	Action	Current \(F\)
0	Initial	\(\{AB \to CD,\ C \to E,\ AB \to E,\ ABC \to D\}\)
1	Split RHS	\(\{AB \to C,\ AB \to D,\ C \to E,\ AB \to E,\ ABC \to D\}\)
2	Minimize LHS	\(\{AB \to C,\ AB \to D,\ C \to E,\ AB \to E\}\)
3	Remove redundant	\(\{AB \to C,\ AB \to D,\ C \to E\}\)

Visualization¶

Before (original \(F\)):

graph LR
    AB["AB"] --> C
    AB --> D
    C --> E
    AB --> E
    ABC["ABC"] --> D

After (minimal cover \(G\)):

graph LR
    AB["AB"] --> C
    AB --> D
    C --> E

Example 2 (importance of step order)¶

Given:

\(F = \{AB \to C,\ C \to B,\ A \to B\}\)

Correct order (Step 2 then Step 3)¶

Step 2 — Minimize LHS:

Check \(AB \to C\):
- \((A)^+_F = \{A, B, C\}\) (using \(A \to B\), then \(AB \to C\)).
- Since \(C \in (A)^+_F\), attribute \(B\) is extraneous.
- Reduce \(AB \to C\) to \(A \to C\).

After Step 2: \(F = \{A \to C,\ C \to B,\ A \to B\}\)

Step 3 — Remove redundant FDs:

\(A \to C\): only dependency determining \(C\), not redundant.
\(C \to B\): let \(G = \{A \to C,\ A \to B\}\). Compute \((C)^+_G = \{C\}\). Since \(B \notin (C)^+_G\), not redundant.
\(A \to B\): let \(G = \{A \to C,\ C \to B\}\). Compute \((A)^+_G = \{A, C, B\}\). Since \(B \in (A)^+_G\), redundant — eliminate.

Minimal cover: \(G = \{A \to C,\ C \to B\}\)

Wrong order (Step 3 then Step 2)¶

Step 3 first — Remove redundant FDs:

\(AB \to C\): only dependency determining \(C\) from \(AB\), not redundant.
\(C \to B\): let \(G = \{AB \to C,\ A \to B\}\). Compute \((C)^+_G = \{C\}\). Since \(B \notin (C)^+_G\), not redundant.
\(A \to B\): let \(G = \{AB \to C,\ C \to B\}\). Compute \((A)^+_G = \{A\}\). Since \(B \notin (A)^+_G\), not redundant.

After Step 3: \(F = \{AB \to C,\ C \to B,\ A \to B\}\) (unchanged)

Step 2 second — Minimize LHS:

Check \(AB \to C\):
- \((A)^+_F = \{A, B, C\}\).
- Reduce \(AB \to C\) to \(A \to C\).

After Step 2: \(F = \{A \to C,\ C \to B,\ A \to B\}\)

This is NOT a minimal cover!

The dependency \(A \to B\) is redundant because:

\[(A)^+_{\{A \to C,\ C \to B\}} = \{A, C, B\}\]

So \(A \to B\) can be derived from \(\{A \to C,\ C \to B\}\), violating the third property of minimal covers.