Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 79 ยท Database Design Theory

Attribute Closure, Keys and Minimal Cover

Compute attribute closure, find every candidate key and build a canonical minimal cover of an FD set, with a complete live Python implementation.

Functional Dependencies told you what an FD is and how Armstrong's axioms derive new ones. Deriving by hand does not scale, so this lesson introduces three algorithms that every normalization method rests on: attribute closure (what does a set of attributes determine?), candidate key finding (which minimal sets determine everything?) and minimal cover (what is the smallest, cleanest set of FDs equivalent to the one we were given?).

All three are short enough to implement in Python, and you will run each one in your browser. Later lessons reuse them to test normal forms and to decompose schemas.

Three tools, one toolbox

Closure X+ Everything X determines.
Candidate keys Minimal sets whose closure is everything.
Minimal cover The smallest equivalent FD set.

Closure is the engine; the other two call it again and again.

1 / 2

Attribute closure

For a set of attributes X and a set of FDs F, the closure X+ is the set of all attributes A such that X -> A follows from F. The algorithm is a fixed-point loop:

  1. Start with result = X.
  2. For every FD L -> R in F where L is a subset of result, add R to result.
  3. Repeat step 2 until nothing new is added.

Why is this correct? Every attribute we add is justified by transitivity (we hold the left side, so we get the right side), so it is sound. And when the loop stops, no FD can add anything more, so the set is complete. The loop ends because the result only grows and there are finitely many attributes.

Two uses follow at once:

  • Does X -> Y follow from F? Compute X+ and check whether Y is inside.
  • Is X a superkey? Compute X+ and check whether it equals the whole attribute set.

Take R(A, B, C, D, E) with F = { A -> B, BC -> D, D -> E }. The closure of AC starts as {A, C}. A -> B fires and adds B. Now BC is available, so BC -> D adds D. Then D -> E adds E. The closure is {A, B, C, D, E}, so AC is a superkey.

Finding all candidate keys

A candidate key is a minimal superkey: a set whose closure is everything and from which you cannot remove any attribute. Trying all subsets works for small schemas, but a few observations prune the search sharply:

  • An attribute that never appears on any right side can only be obtained by being in the key, so it belongs to every candidate key.
  • An attribute that appears on right sides but never on a left side can always be derived and is never needed in a key (when the rest of the key already works).
  • Everything else is in the "middle": try subsets of the middle attributes in order of size, always together with the must-have attributes, and skip any set that contains an already found key (it would not be minimal).
Python Attribute closure and candidate keys in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In example 2, B never appears on a right side, so every key contains B. The cycle C -> D -> A then lets C, D or A each complete the key, which gives three candidate keys: AB, BC and BD. A relation with several candidate keys picks one as the primary key; the others are alternate keys. All of their attributes are called prime attributes, which matters for 3NF in 1NF, 2NF and 3NF.

Finding all candidate keys is, in the worst case, exponential: a schema can have an enormous number of keys. Real tables are small and structured, so the pruning above is plenty. It is still a good reason to keep tables narrow.

Equivalent FD sets

Two FD sets F and G are equivalent when they have the same closure F+ = G+: each says exactly the same thing. To test it, check that every FD of G is implied by F (closure on the left side contains the right side), and every FD of F is implied by G. Equivalent sets may look very different, and design algorithms prefer the tidiest one.

Minimal (canonical) cover

A minimal cover Fc of F is an equivalent set that is as small and simple as possible:

  1. every right side is a single attribute;
  2. no left side contains an extraneous attribute (one you could drop without changing what is implied);
  3. no FD is redundant (implied by the others).

The standard procedure follows those three rules in order.

  1. Split each X -> ABC into X -> A, X -> B, X -> C (decomposition).
  2. Remove extraneous left attributes. For an FD L -> A with more than one attribute in L, an attribute B in L is extraneous if A is in the closure of L - {B} computed with the full current F.
  3. Remove redundant FDs. For each FD L -> A, drop it if A is in the closure of L computed with all the other FDs.

Order matters: do the left-side reduction before deleting redundant FDs. A minimal cover is not unique; different orders of processing can give different (equally valid) results. What is guaranteed is that all of them are equivalent to the original.

Python Minimal cover and equivalence checking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk through the first case by hand to see why the output makes sense. Splitting gives A->B, A->C, B->C, AB->C (the repeated A->B is dropped). In AB -> C, A is extraneous because B -> C already holds, so it shrinks to B -> C, a duplicate. Finally A -> C is redundant, since A -> B and B -> C already give it. Two FDs remain: A -> B and B -> C. In the second set, AB -> C shrinks to B -> C because B -> A hands you A for free. Then B -> A itself becomes redundant, since B -> C and C -> A already give it. The result is a clean cycle A -> B -> C -> A, in which every attribute determines the other two.

Why the minimal cover matters

Decomposition algorithms (BCNF and Lossless Decomposition) and 3NF synthesis work from the minimal cover because it produces one small relation per determinant, with no wasted attributes and no redundant relations. A designer also learns something from the exercise: if the cover has an FD whose left side you cannot justify in business terms, the requirements need another look.

A final reminder about limits. Closure, keys and minimal cover reason only about the FDs you declare. If the real-world rule course -> instructor is missing from F, every algorithm will happily treat the schema as fine. Collecting the right FDs from the people who know the business is the human part of design, and no program replaces it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Given F = { A -> B, B -> C } on R(A, B, C), what is the closure of A?

    Start with {A}. A -> B adds B, then B -> C adds C. The closure always includes the starting attributes themselves.
  2. 2. On R(A, B, C, D) with F = { A -> B, C -> D }, which attributes must be in every candidate key?

    A and C are never derived by any FD, so only being in the key can supply them. The closure of AC is ABCD, so AC is the only candidate key.
  3. 3. Which is NOT a requirement of a minimal cover?

    A minimal cover must be equivalent to F, with single-attribute right sides, no extraneous left attributes and no redundant FDs. It is not about the number of attributes in the schema, and it need not be unique.
  4. 4. How do you test whether two FD sets F and G are equivalent?

    Equivalence means F+ equals G+. Implication of each FD is tested by computing a closure.

Summary

  • The closure X+ is computed by repeatedly adding the right side of every FD whose left side is already inside; X -> Y is implied exactly when Y is inside X+.
  • X is a superkey when X+ is all attributes, and a candidate key when it is also minimal.
  • Attributes never on a right side belong to every key; attributes never on a left side belong to none (unless forced), which prunes the search.
  • Two FD sets are equivalent when each implies the other.
  • A minimal cover has single-attribute right sides, no extraneous left attributes and no redundant FDs; it is equivalent to the original but not unique.
  • These algorithms only know the FDs you give them.

Next: 1NF, 2NF and 3NF.