In the Functional Dependencies chapter we saw that a few given FDs can imply many more, and that Armstrong's axioms can prove them. But writing proofs by hand needs guesswork: which rule do I apply next?
This chapter gives you a simple, mechanical tool that removes the guesswork: attribute closure. With it you can answer, in a few lines of work:
Does an FD
X → Yfollow from a set F?Is a set of attributes a superkey? A candidate key?
What are all the candidate keys of a relation?
These questions appear in almost every GATE paper and university DBMS exam, and they are the first step of every normalization problem in the chapters that follow.
What Is Attribute Closure?
The closure of an attribute set X under a set of FDs F, written X+, is the set of all attributes that are functionally determined by X, using F.
In other words, X+ answers the question: "If I know the values of X, which other attribute values are automatically fixed?"
X+ always contains X itself (by reflexivity), and it can never contain attributes outside the relation.
The Algorithm
The idea is to start with what you know and keep "firing" FDs whose left-hand side is fully known, until nothing new can be added.
closure(X, F):
result = X
repeat
for each FD L → R in F:
if L ⊆ result: // we know every attribute of L
result = result ∪ R // so we also know R
until result does not change in a full pass
return resultWhy is this correct? Every time we add R, it is because X → L (already derived) and L → R (given), so X → R by transitivity. And when the loop stops, no FD can add anything more, so nothing implied has been missed. The result is exactly the set of attributes A for which X → A is in F+.
Since each pass adds at least one attribute (or stops), there are at most n passes over m FDs, so the simple version runs in O(n × m) FD checks for n attributes.
Worked Example: Step by Step
R(A, B, C, D, E, F, G)
F = { A → B, BC → DE, AEF → G, D → F }
Find (AC)+We scan the FDs in the order given, and repeat until a pass adds nothing.
Start: result = {A, C}
Pass 1:
A → B A ⊆ result → add B result = {A, B, C}
BC → DE B, C ⊆ result → add D, E result = {A, B, C, D, E}
AEF → G F is not known yet → skip
D → F D ⊆ result → add F result = {A, B, C, D, E, F}
Pass 2:
AEF → G A, E, F ⊆ result → add G result = {A, B, C, D, E, F, G}
Pass 3: nothing new → stop
(AC)+ = {A, B, C, D, E, F, G}Notice that AEF → G was skipped in the first pass because F was not known yet. That is why the algorithm must keep looping until a full pass changes nothing. Stopping after one pass is a common exam mistake.
For comparison, with the same F:
A+ = {A, B} (A → B, and then nothing else fires)
C+ = {C} (no FD has just C on the left)Use 1: Testing Whether an FD Is Implied
X → Y is in F+ if and only if Y ⊆ X+.
With the same F:
Does
AC → Ghold? (AC)+ contains G, so yes.Does
A → Dhold? A+ = {A, B} does not contain D, so no.
No proofs, no guessing. Compute one closure and look.
Use 2: Testing Superkeys and Candidate Keys
From the previous chapter, K is a superkey if K → R. Using closure:
K is a superkey if K+ contains every attribute of R.
K is a candidate key if K is a superkey and no proper subset of K is a superkey. It is enough to check the subsets obtained by removing one attribute, because if a smaller subset were a superkey, every set between it and K would be too.
In our example, (AC)+ = all of R, so AC is a superkey. A+ = {A, B} and C+ = {C} are not, so AC is a candidate key.
Use 3: Finding All Candidate Keys
Trying every subset of attributes works, but with n attributes there are 2n − 1 subsets. A little reasoning cuts this down dramatically.
Step 1: Classify the Attributes
Look at where each attribute appears in F:
Attribute appears in | Conclusion | Why |
|---|---|---|
Only the LHS, never any RHS | In every key | Nothing can determine it, so the key must contain it |
Neither side | In every key | Same reason: no FD produces it |
Only the RHS, never any LHS | In no key | It never helps determine anything, so a minimal key never needs it |
Both sides | Maybe | Must be tested |
Call the attributes that must be in every key the core.
Step 2: Compute the Closure of the Core
If core+ = R, the core is the only candidate key. Done.
Step 3: Extend the Core
Otherwise, add "maybe" attributes to the core, one at a time first, then two at a time, and so on. Skip any combination that contains an already-found key (it cannot be minimal) and any attribute already in core+ (adding it changes nothing).
Example 1: One Key
R(A, B, C, D, E, F, G)
F = { A → B, BC → DE, AEF → G, D → F }Only LHS : A, C → core = {A, C}
Only RHS : G → never in a key
Both : B, D, E, F (B is on the RHS of A → B and the LHS of BC → DE)
core+ = (AC)+ = ABCDEFG = R → the only candidate key is ACExample 2: Several Keys
R(A, B, C, D, E)
F = { AB → C, C → D, D → B, D → E }Step 1, classify:
A : LHS only → core
E : RHS only → never in a key
B, C, D : both sides → maybeStep 2: A+ = {A}. Not a key, so we must extend.
Step 3: try A plus one "maybe" attribute:
(AB)+ : AB → C, C → D, D → E = {A, B, C, D, E} ✓ key
(AC)+ : C → D, D → B, D → E = {A, B, C, D, E} ✓ key
(AD)+ : D → B, D → E, AB → C = {A, B, C, D, E} ✓ keyEvery larger combination contains one of these, so we stop.
Candidate keys = { AB, AC, AD }The Key-Swapping Shortcut
Once you have one key, look for FDs that produce part of it. If K is a key and some FD X → B has B ∈ K, then (K − B) ∪ X is also a superkey (it determines B, and therefore everything K did). It may or may not be minimal, so check it.
AB is a key.
D → B → replace B by D : AD is a superkey (and minimal) ✓
C → D, and D appears in key AD → replace D by C : AC ✓This shortcut finds keys quickly, but always confirm each candidate with a closure and check minimality.
Example 3: A Tougher One
R(A, B, C, D, E, G)
F = { A → B, BC → D, E → C, D → A }Classify:
E : LHS only → core
G : appears in no FD at all → core
A, B, C, D : on both sides → maybeClosure of the core:
(EG)+ : E → C = {C, E, G} not a keyC is already in (EG)+, so adding C cannot help. Try the others:
(AEG)+ : A → B, E → C, BC → D = {A, B, C, D, E, G} ✓
(BEG)+ : E → C, BC → D, D → A = {A, B, C, D, E, G} ✓
(CEG)+ : E → C = {C, E, G} ✗
(DEG)+ : D → A, A → B, E → C = {A, B, C, D, E, G} ✓Candidate keys = { AEG, BEG, DEG }The attribute G is easy to forget because it appears in no FD. But since nothing determines G, it must be part of every key.
Example 4: A Cycle
R(A, B, C, D)
F = { A → B, B → C, C → D, D → A }Every attribute is on both sides, so the core is empty. Each single attribute reaches all the others around the cycle:
A+ = B+ = C+ = D+ = {A, B, C, D}
Candidate keys = { A, B, C, D }Prime and Non-Prime Attributes
An attribute is prime if it belongs to at least one candidate key. Otherwise it is non-prime.
Example | Candidate keys | Prime | Non-prime |
|---|---|---|---|
Example 1 | AC | A, C | B, D, E, F, G |
Example 2 | AB, AC, AD | A, B, C, D | E |
Example 3 | AEG, BEG, DEG | A, B, D, E, G | C |
Example 4 | A, B, C, D | A, B, C, D | none |
This distinction is essential for normal forms: 2NF and 3NF are defined in terms of non-prime attributes, so you must find all candidate keys before you can classify a relation. Missing a key means misclassifying a prime attribute as non-prime.
Counting Superkeys
Every superset of a candidate key is a superkey. So:
One candidate key of k attributes in a relation of n attributes: the other n − k attributes can be present or absent freely, giving 2n−k superkeys.
Several keys: use inclusion-exclusion so supersets of two keys are not counted twice.
Example 2 has n = 5 and keys AB, AC, AD. Every superkey must contain A and at least one of B, C, D, while E is free:
(2^3 − 1) choices for {B, C, D} × 2 choices for E = 7 × 2 = 14 superkeysWith inclusion-exclusion you get the same answer: supersets of AB, AC, AD each number 23 = 8; of each pairwise union (ABC, ABD, ACD) 22 = 4; of ABCD 21 = 2. So 3 × 8 − 3 × 4 + 2 = 14.
Another quick one: R(A, B, C, D) with keys A and B gives 23 + 23 − 22 = 12 superkeys.
Doing It in Code
Here is a short Python program that implements attribute closure and a brute-force search for candidate keys. Brute force is fine for exam-sized relations and is a great way to check your hand work.
from itertools import combinations
def closure(attrs, fds):
"""Return the closure of attrs under the list of FDs (lhs, rhs)."""
result = set(attrs)
changed = True
while changed:
changed = False
for lhs, rhs in fds:
if set(lhs) <= result and not set(rhs) <= result:
result |= set(rhs)
changed = True
return result
def candidate_keys(relation, fds):
keys = []
for size in range(1, len(relation) + 1):
for combo in combinations(relation, size):
if any(set(k) <= set(combo) for k in keys):
continue # superset of a key: not minimal
if closure(combo, fds) == set(relation):
keys.append(''.join(combo))
return keys
R = 'ABCDEG'
F = [('A', 'B'), ('BC', 'D'), ('E', 'C'), ('D', 'A')]
print('EG+ =', ''.join(sorted(closure('EG', F))))
print('AEG+ =', ''.join(sorted(closure('AEG', F))))
print('Candidate keys:', candidate_keys(R, F))Output:
EG+ = CEG
AEG+ = ABCDEG
Candidate keys: ['AEG', 'BEG', 'DEG']Because the search goes in order of size and skips supersets of keys already found, every set it reports is minimal.
Common Mistakes
Stopping after one pass. An FD skipped early may fire later.
Forgetting attributes that appear in no FD. They belong to every key.
Stopping at the first key. Many relations have several; normalization needs all of them.
Reporting a superkey as a candidate key without checking minimality.
Splitting LHS attributes during closure.
BC → Dfires only when both B and C are known.
Interview and Exam Questions
Q1. What is the closure of an attribute set?
X+ is the set of all attributes functionally determined by X under the given FDs.
Q2. How do you check whether X → Y is implied by F?
Compute X+ under F. The FD is implied if and only if Y ⊆ X+.
Q3. How do you check whether X is a candidate key?
X+ must equal all of R, and for every attribute A in X, (X − {A})+ must not equal R.
Q4. An attribute appears only on the right side of FDs. Can it be in a candidate key?
No. It is determined by other attributes and never helps determine anything, so any key containing it would not be minimal.
Q5. R(A, B, C, D) with F = { AB → C, C → D, D → A }. Find the candidate keys.
B is never on a right side, so it is in every key. B+ = {B}. (AB)+, (BC)+ and (BD)+ are all ABCD, so the keys are AB, BC and BD, and all four attributes are prime.
Q6. How many superkeys does R(A, B, C, D, E) have if its only candidate key is AB?
25−2 = 8.
Summary
X+ is everything X determines; compute it by repeatedly firing FDs whose LHS is known, until a full pass adds nothing.
X → Yis implied by F exactly when Y ⊆ X+.X is a superkey when X+ = R, and a candidate key when additionally no attribute can be removed.
To find all keys: attributes never on an RHS (including those in no FD) are in every key; RHS-only attributes are in none; extend the core with the rest, smallest combinations first.
Prime attributes belong to some candidate key; this classification drives 2NF and 3NF.
Superkeys are supersets of candidate keys and can be counted with powers of 2 and inclusion-exclusion.
Next, in Canonical Cover, we use attribute closure to strip a set of FDs down to its simplest equivalent form.