Chapter 20 of 41

Canonical Cover

Suppose a designer hands you this list of functional dependencies for a relation R(A, B, C, D, E):

A → B,   A → C,   B → C,   AB → D,   D → E,   AD → E

Six FDs. But look closely. A → C is not really needed, because A → B and B → C already give it. In AB → D, is B needed if A alone determines B? And AD → E looks pointless when D → E is already there.

Every FD the database must enforce costs work on every insert and update, and messy FD sets make normalization harder to do by hand. So we want the smallest, cleanest set of FDs that says exactly the same thing. That set is called a canonical cover.

This chapter uses attribute closure heavily, so make sure you are comfortable with the previous chapter, Attribute Closure & Candidate Keys.


First: When Do Two FD Sets Say the Same Thing?

Before simplifying F, we need a precise meaning for "says the same thing".

F covers G if every FD in G can be derived from F (G ⊆ F+). F and G are equivalent (F ≡ G) if F covers G and G covers F, i.e. F+ = G+.

We never compute F+ fully. Instead, for each FD X → Y in G, compute X+ under F and check that Y is inside. Then do the same in the other direction.

Example 1: Equivalent

F = { A → B,  AB → C,  D → AC,  D → E }
G = { A → BC, D → AE }

Does F cover G?

A → BC :  A+ under F = {A, B, C}            contains BC  ✓
D → AE :  D+ under F = {A, B, C, D, E}      contains AE  ✓

Does G cover F?

A → B  :  A+ under G = {A, B, C}            contains B   ✓
AB → C :  (AB)+ under G = {A, B, C}         contains C   ✓
D → AC :  D+ under G = {A, B, C, D, E}      contains AC  ✓
D → E  :  D+ under G                        contains E   ✓

Both directions pass, so F ≡ G. G is just a tidier way of writing F.

Example 2: Not Equivalent

F = { A → B,  B → C }
G = { A → BC }

F covers G: under F, A+ = {A, B, C}, which contains BC. But G does not cover F: under G, B+ = {B}, so B → C cannot be derived. F says something G does not (that B alone determines C), so they are not equivalent.

Always check both directions. One-directional checks are the most common mistake in equivalence questions.


Extraneous Attributes

An attribute in an FD is extraneous if we can remove it without changing F+. There are two places it can hide.

Extraneous on the Left Side

In X → Y, an attribute A ∈ X is extraneous if (X − A) → Y can be derived from F. Test: compute (X − A)+ using F itself (unchanged); if it contains Y, A is extraneous.

Why is it safe? Making the LHS smaller makes the FD stronger (it applies in more situations). So we must check that the stronger FD is already implied by F; if it is, nothing new has been claimed.

F = { A → B,  AB → C }

Is B extraneous in AB → C?
A+ under F = {A, B, C}  contains C   → yes, replace AB → C with A → C

Extraneous on the Right Side

In X → Y, an attribute A ∈ Y is extraneous if A can still be derived from X after removing it. Test: build F' = F with X → Y replaced by X → (Y − A); compute X+ using F'; if it contains A, A is extraneous.

Here the situation is reversed. Removing A from the RHS makes the FD weaker, so we might lose information. We must check that A is still derivable without the part we removed. That is why the test uses F', not F.

F = { A → BC,  B → C }

Is C extraneous in A → BC?
F' = { A → B,  B → C }
A+ under F' = {A, B, C}  contains C   → yes, replace A → BC with A → B

Remember the asymmetry: LHS test uses F as it is; RHS test uses the modified F'. If you test an RHS attribute using the original F, it will always look extraneous, because the FD you are testing is still there to derive it.


What Is a Canonical Cover?

A canonical cover Fc of a set of FDs F is a set of FDs such that Fc is equivalent to F, no FD in Fc contains an extraneous attribute, and the left side of every FD in Fc is unique.

So a canonical cover has three properties:

  1. Equivalent to F: it implies exactly the same FDs.

  2. No extraneous attributes on either side.

  3. Unique left sides: no two FDs share the same LHS (they are merged with the union rule).

A whole FD can also disappear. If every RHS attribute of an FD turns out to be extraneous, its RHS becomes empty and the FD is dropped; such an FD was redundant, fully implied by the others.


The Algorithm

Fc = F
repeat
    1. Union:  replace X → Y1 and X → Y2 by X → Y1Y2   (merge same LHS)
    2. Find an FD X → Y in Fc with an extraneous attribute
          (either in X or in Y, using the tests above)
    3. If found, delete that attribute from X → Y
       (drop the FD if its RHS becomes empty)
until Fc does not change
return Fc

The loop matters. Removing one extraneous attribute can create new duplicates (step 1) or make another attribute extraneous, so we keep going until a full check finds nothing.


Full Worked Example

Back to the FD set from the start of the chapter:

R(A, B, C, D, E)
F = { A → B,  A → C,  B → C,  AB → D,  D → E,  AD → E }

Step 1: Union of Same LHS

A → B and A → C share the LHS A:

F = { A → BC,  B → C,  AB → D,  D → E,  AD → E }

Step 2: Extraneous Attributes on the Left

Only AB → D and AD → E have more than one attribute on the left. First compute the closures we need, under the current F:

A+ = {A, B, C, D, E}     (A → BC, AB → D, D → E)
B+ = {B, C}
D+ = {D, E}

AB → D:

Remove A?  B+ = {B, C}           has no D  → A is needed
Remove B?  A+ = {A, B, C, D, E}  has D     → B is extraneous
New FD: A → D

AD → E:

Remove A?  D+ = {D, E}           has E     → A is extraneous
New FD: D → E          (the LHS is now a single attribute, nothing more to remove)

Now apply the union rule again. A → D merges with A → BC, and the second D → E is a duplicate:

F = { A → BCD,  B → C,  D → E }

Step 3: Extraneous Attributes on the Right

Test each attribute of A → BCD with F' (that attribute removed):

Remove B:  F' = { A → CD, B → C, D → E }
           A+ = {A, C, D, E}            no B   → B is needed

Remove C:  F' = { A → BD, B → C, D → E }
           A+ = {A, B, D, C, E}         has C  → C is extraneous
           Now: A → BD

Remove D:  F' = { A → B, B → C, D → E }
           A+ = {A, B, C}               no D   → D is needed

The single-attribute FDs B → C and D → E are also checked: without B → C, B+ = {B}; without D → E, D+ = {D}. Both are needed.

Step 4: Repeat Until Nothing Changes

One more pass over { A → BD, B → C, D → E } finds no extraneous attribute and no duplicate LHS, so we are done.

Fc = { A → BD,  B → C,  D → E }

We went from 6 FDs to 3, and the result says exactly the same thing. A quick sanity check: under Fc, A+ = {A, B, C, D, E}, the same as under the original F, so A is still the only candidate key. (We verified the equivalence of F and Fc in both directions with a short script.)


A Canonical Cover Is Not Unique

Different orders of removing attributes can lead to different, equally correct answers.

F = { A → B,  B → A,  A → C,  B → C }
After union: { A → BC,  B → AC }

Path 1: test C in A → BC first. With F' = { A → B, B → AC }, A+ = {A, B, C}, so C is extraneous.

Fc1 = { A → B,  B → AC }

Now C in B → AC is not extraneous any more (without it, B+ = {A, B}), because we already removed the other way of reaching C.

Path 2: test C in B → AC first. With F' = { A → BC, B → A }, B+ = {A, B, C}, so C is extraneous.

Fc2 = { A → BC,  B → A }

Both are canonical covers of F (no extraneous attributes, unique LHS, and each is equivalent to F). In exams, any valid canonical cover is accepted, but you must be able to show that yours is equivalent and has nothing extraneous.


Why "Repeat Until No Change" Matters

Consider:

F = { C → A,  E → A,  AC → E }

Suppose you first look for whole redundant FDs. None is redundant: removing C → A leaves C+ = {C}, removing E → A leaves E+ = {E}, and removing AC → E leaves (AC)+ = {A, C}.

Now check the LHS of AC → E: C+ = {A, C, E} contains E, so A is extraneous, and the FD becomes C → E.

F = { C → A,  E → A,  C → E }       ← union: { C → AE, E → A }

And now C → A has become redundant (C → E → A). Removing A from C → AE:

Fc = { C → E,  E → A }

If you had stopped after the first round, you would have kept an unnecessary FD. Simplifying one FD can make another one removable, so always loop.


Canonical Cover vs Minimal Cover

Different textbooks use slightly different names and forms, which confuses many students:

Property

Canonical cover

Minimal cover (minimal set of FDs)

Equivalent to F

Yes

Yes

No extraneous LHS attributes

Yes

Yes

No redundant FDs

Yes

Yes

Right side

Can have several attributes; LHS must be unique

Exactly one attribute per FD

Example result for our worked example

A → BD, B → C, D → E

A → B, A → D, B → C, D → E

They carry the same information. To turn a canonical cover into a minimal cover, split each RHS with the decomposition rule; to go the other way, merge FDs with the same LHS using the union rule. When a question asks for a "minimal cover", give single-attribute right sides.


Where Canonical Covers Are Used

  • Enforcing constraints cheaply: fewer and smaller FDs mean fewer checks on every insert and update.

  • 3NF decomposition: the standard 3NF synthesis algorithm starts from a canonical cover and creates one table for each FD X → Y (with attributes XY), then adds a table holding a candidate key if no table already contains one. The result is always lossless and dependency preserving. For our worked example that gives R1(A, B, D), R2(B, C), R3(D, E), and R1 already contains the key A.

  • Checking dependency preservation and reasoning about designs, where a clean FD set is much easier to work with (see the Lossless Join & Dependency Preservation chapter).

  • Spotting candidate keys faster, since redundant FDs no longer distract you.


Common Mistakes

  • Testing an RHS attribute with the original F. The FD being tested is still there, so the attribute always looks extraneous. Use F'.

  • Testing an LHS attribute with F'. For LHS checks use the full current F.

  • Removing two attributes at once based on two separate tests. Each removal changes F, so re-test after every change.

  • Forgetting the final union step, leaving two FDs with the same LHS.

  • Stopping after one pass.

  • Checking equivalence in only one direction.

  • Thinking there is only one correct answer. Canonical covers are not unique.


Interview and Exam Questions

Q1. What is a canonical cover?

A simplified set of FDs that is equivalent to the original set, contains no extraneous attributes, and has a unique left side for each FD.

Q2. How do you test whether attribute A is extraneous in the LHS of X → Y?

Compute (X − A)+ using the current F. If it contains Y, A is extraneous.

Q3. How do you test whether attribute A is extraneous in the RHS of X → Y?

Replace X → Y by X → (Y − A) to get F', compute X+ using F', and check whether it contains A.

Q4. Is the canonical cover unique?

No. Different removal orders can give different canonical covers, all equivalent to F.

Q5. How do you check whether two FD sets F and G are equivalent?

For each FD X → Y in G, check Y ⊆ X+ under F; then for each FD in F, check the same under G. They are equivalent only if both directions succeed.

Q6. Find the canonical cover of F = { A → BC, B → C, A → B, AB → C }.

Union gives { A → BC, B → C, AB → C }. In AB → C, B is extraneous (A+ contains C), giving A → C, which merges into A → BC. In A → BC, C is extraneous because A → B and B → C. Answer: { A → B, B → C }.

Q7. What is the difference between a canonical cover and a minimal cover?

Both are equivalent to F with nothing extraneous or redundant. A minimal cover has exactly one attribute on each right side; a canonical cover merges FDs with the same left side.


Summary

  • F and G are equivalent if each covers the other; check every FD of one using attribute closure under the other.

  • An LHS attribute A of X → Y is extraneous if (X − A)+ under F contains Y.

  • An RHS attribute A of X → Y is extraneous if X+ under F' (with A removed from that FD) still contains A.

  • A canonical cover is equivalent to F, has no extraneous attributes, and has unique left sides. Compute it by union, remove extraneous attributes one at a time, and repeat until nothing changes.

  • Canonical covers are not unique; a minimal cover is the same idea with single-attribute right sides.

With FDs, closures, keys and covers in hand, you are ready for the next chapter, Normalization & Anomalies, where we see what goes wrong in badly designed tables and how FDs tell us how to fix them.