Extraneous Attributes, Equivalence & Canonical Cover

We already have attribute closure (\(\alpha^+\)) as our go-to tool for testing superkeys and FDs. Now we use it to ask a sharper question: does every attribute in every FD actually earn its place? This leads to extraneous attributes and, from there, the canonical cover — the leanest version of an FD set.

Extraneous Attributes

An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies (\(F^+\)).

💡 In plain English: an extraneous attribute is dead weight — remove it, and the FD set means exactly the same thing. It was never pulling any weight to begin with.

Let’s consider a functional dependency \(\alpha \rightarrow \beta\) in a set \(F\):

Condition 1 (Extraneous on the Left, \(X \in \alpha\)):

If \(X \in \alpha\), compute \((\alpha - \{X\})^+_F\).
If \((\alpha - \{X\})^+_F\) contains \(\beta\), then \(X\) is an extraneous attribute on the LHS.
Removing \(X\) simplifies the dependency to \((\alpha - \{X\}) \rightarrow \beta\).

Condition 2 (Extraneous on the Right, \(X \in \beta\)):

If \(X \in \beta\), compute \(\alpha^+\) using the modified set: \[F' = (F - \{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow (\beta - \{X\})\}\]
If \(\alpha^+_{F'}\) contains \(X\), then \(X\) is an extraneous attribute on the RHS.
Removing \(X\) simplifies the dependency to \(\alpha \rightarrow (\beta - \{X\})\) (or eliminates the dependency entirely if \(\beta - \{X\} = \emptyset\)).

Example - Extraneous on the Left (Condition 1)

\(F = \{A \rightarrow C,\ AB \rightarrow C\}\)

Is \(B\) extraneous in \(AB \rightarrow C\)?

Here \(\alpha = AB\), \(\beta = C\), and \(X = B \in \alpha\).
Drop \(B\) from \(\alpha\) and compute \((AB - \{B\})^+ = A^+\).
Since \(A^+ = AC\) already contains \(\beta = C\), \(B\) is an extraneous attribute.
We can replace \(AB \rightarrow C\) with \(A \rightarrow C\).

Example - Extraneous on the Right (Condition 2)

\(F = \{A \rightarrow C,\ AB \rightarrow CD\}\)

Is \(C\) extraneous in \(AB \rightarrow CD\)?

Here \(\alpha = AB\), \(\beta = CD\), and \(X = C \in \beta\).
Form \(F' = \{A \rightarrow C,\ AB \rightarrow D\}\).
Compute \(AB^+\) under \(F'\): \(AB^+ = ABCD\).
Since \(AB^+\) contains \(X = C\), \(C\) is an extraneous attribute.
We can replace \(AB \rightarrow CD\) with \(AB \rightarrow D\).

Try it yourself — Extraneous Attribute Checker

Click Run to inspect any dependency and test whether specific LHS or RHS attributes are extraneous:

R(A, B, C, D)

A -> C
AB -> CD
B -> C

Equivalence of Functional Dependency

Two sets of functional dependencies \(F\) and \(G\) are equivalent (\(F \equiv G\)) if and only if \(F^+ = G^+\).

This requires verifying two conditions:

\(F\) covers \(G\) (\(G \subseteq F^+\)):
- All relations/dependencies in \(G\) should be satisfied while taking the closure under \(F\).
- For every \(\alpha \rightarrow \beta \in G\), \(\alpha^+_F\) must contain \(\beta\).
\(G\) covers \(F\) (\(F \subseteq G^+\)):
- All relations/dependencies in \(F\) should be satisfied while taking the closure under \(G\).
- For every \(\alpha \rightarrow \beta \in F\), \(\alpha^+_G\) must contain \(\beta\).

If both conditions hold, \(F\) is equivalent to \(G\) (\(F \equiv G\)).

Example

Let \(F_1 = \{ P \rightarrow Q,\ Q \rightarrow R,\ R \rightarrow P \}\) and \(F_2 = \{ P \rightarrow R,\ Q \rightarrow R,\ R \rightarrow Q \}\).

1. Check if \(F_1\) covers \(F_2\) (\(F_2 \subseteq F_1^+\))

Taking attribute closures of LHS of \(F_2\) using dependencies in \(F_1\):

\(P^+ = PQR\) (satisfies \(P \rightarrow R\))
\(Q^+ = QRP\) (satisfies \(Q \rightarrow R\))
\(R^+ = RPQ\) (satisfies \(R \rightarrow Q\))

\(F_1\) covers \(F_2\) because by taking the closure on \(F_1\), all dependencies in \(F_2\) are satisfied.

Example (continued)

2. Check if \(F_2\) covers \(F_1\) (\(F_1 \subseteq F_2^+\))

Taking attribute closures of LHS of \(F_1\) using dependencies in \(F_2\):

\(P^+ = PQR\) (satisfies \(P \rightarrow Q\))
\(Q^+ = QR\) (satisfies \(Q \rightarrow R\))
\(R^+ = RQ\) (does NOT satisfy \(R \rightarrow P\))

\(F_2\) does not cover \(F_1\) because taking the closure of \(R\) under \(F_2\) gives \(R^+ = RQ\), which does not contain \(P\), failing to satisfy \(R \rightarrow P \in F_1\).

Conclusion: Since \(F_2\) does not cover \(F_1\), \(F_1\) is NOT equivalent to \(F_2\) (\(F_1 \not\equiv F_2\)).

Try it yourself — Equivalence Tester

Click Run to verify covering in both directions with step-by-step closures:

R(P, Q, R)

F1:
P -> Q
Q -> R
R -> P

F2:
P -> R
Q -> R
R -> Q

Canonical Cover

💡 In plain English: the canonical cover is the FD set with all the fat trimmed off — no whole dependency that another one already implies, and no attribute inside a dependency that isn’t actually needed.

\(F_c\) is a canonical cover of \(F\) if:

\(F_c^+ = F^+\) (says exactly the same thing as \(F\))
No FD in \(F_c\) has an extraneous attribute
Every left-hand side in \(F_c\) appears only once (no two FDs share a left side — those would just merge)

How to Compute It

Combine any FDs that share the same left-hand side into one, using the union rule.
Look at each remaining FD and test both sides for extraneous attributes; remove any that are found.
Repeat steps 1–2 until nothing changes.

⚠️ Removing an extraneous attribute can create a new opportunity to merge left-hand sides that didn’t match before — so keep looping until the set is stable.

Worked Example

\(R = (A, B, C)\), \(F = \{A \rightarrow BC,\ B \rightarrow C,\ A \rightarrow B,\ AB \rightarrow C\}\)

Merge: \(A \rightarrow BC\) and \(A \rightarrow B\) share a left side → combine into \(A \rightarrow BC\). Set is now \(\{A \rightarrow BC,\ B \rightarrow C,\ AB \rightarrow C\}\).
Left-side check: is \(A\) extraneous in \(AB \rightarrow C\)? Drop it — \(B \rightarrow C\) is already in the set, so yes. Set is now \(\{A \rightarrow BC,\ B \rightarrow C\}\).
Right-side check: is \(C\) extraneous in \(A \rightarrow BC\)? Drop it and check — \(A \rightarrow B\) and \(B \rightarrow C\) together still give \(A \rightarrow C\) by transitivity. So yes, \(C\) was extraneous.

Canonical cover: \(\{A \rightarrow B,\ B \rightarrow C\}\) — the smallest set that says exactly what the original four FDs said.

Try it yourself

Click Run to compute the canonical cover \(F_c\) and inspect the reduction steps:

R(A, B, C)

A -> BC
B -> C
A -> B
AB -> C