TechVani: Candidate Keys and Attribute Closure: 6 Solved DBMS Problems

To find a candidate key, compute an attribute set's closure until nothing changes. It must reach every attribute, and it must fail if you remove any member. Finding one working set is not the same as finding every candidate key.

This worksheet gives six original solved problems, a repeatable method and three self-tests. It complements the definitions in DBMS Part 1: relational model and keys and the design rules in DBMS Part 5: normalization. These are general BTech CSE practice questions, not an official university paper or a prediction.

1. Closure, superkey and candidate key

For relation schema R and functional dependencies F, X+ is the set of attributes determined by X using F. Start with X itself. Whenever an FD's entire left side is present, add its right side. Repeat until a full pass adds nothing.

Superkey: X+ contains every attribute of R.
Candidate key: X is a superkey and no proper subset is a superkey.
Primary key: one candidate key chosen for implementation. This worksheet asks for all candidate keys, not a primary-key choice.
Prime attribute: an attribute that belongs to at least one candidate key.

FDs are schema constraints, not coincidences in a tiny data sample. We assume the listed FDs are the constraints used for these exercises. Unstated business rules can change the answer. X+ is an attribute set; F+ is a set of implied dependencies. Do not confuse them.

Pocket reference: what each test proves

Test or term	Meaning	Does not prove
X+ = R	X is a superkey	Minimality
Every single deletion fails	A superkey X is minimal	Completeness of your key list
Absent from every FD right side	Must occur in every key	That it is a key alone
Prime attribute	Appears in at least one candidate key	Appears in every key
Primary key	One selected candidate key	The only possible candidate key

2. A reliable exam method

Write the complete attribute list and the FDs.
Find attributes absent from every FD right side. They cannot be created, so every key must include them. This is a starting point, not always a complete key.
Compute the closure of that compulsory set. If it misses attributes, add promising choices and recompute.
For every full closure, remove each member separately. If any deletion still gives full closure, the original set is not minimal.
Continue checking alternative choices. Do not stop at the first key or assume all keys have equal sizes.

closure(X, F):
    result = X
    repeat:
        old = result
        for each L → Y in F:
            if L is a subset of result:
                result = result union Y
    until result = old
    return result

You must iterate. A dependency listed earlier may become usable only after another dependency adds an attribute. For small schemas, enumerating subsets and discarding supersets of already found keys is a safe way to check completeness. Larger schemas can have many candidate keys; there is no promise of a quick shortcut.

Problem 1: A chain with one key

Given: R(A, B, C, D), F = {A → B; B → C; C → D}. Find every candidate key.

Test set	Closure steps	Result
A	A → AB → ABC → ABCD	Candidate key
AB	AB → ABC → ABCD	Superkey, not minimal
B	B → BC → BCD	Not a superkey

Trace for A: Start gives {A}; A → B gives {A, B}; B → C gives {A, B, C}; C → D gives {A, B, C, D}.

Minimality: ∅+ = {}. Every deletion misses at least one attribute, so this set is minimal.

A never appears on a right-hand side, so every key must contain A. A alone reaches all four attributes. AB is a superkey, but B is extra.

All candidate keys: A. Prime attributes: A. Non-prime attributes: B, C, D.

Problem 2: A compulsory attribute plus a choice

Given: R(A, B, C, D), F = {A → B; B → A; C → D}. Find every candidate key.

Test set	Closure steps	Result
AC	AC → ABC → ABCD	Candidate key
BC	BC → ABC → ABCD	Candidate key
A	A → AB	Not a superkey
C	C → CD	Not a superkey

Trace for AC: Start gives {A, C}; A → B gives {A, B, C}; C → D gives {A, B, C, D}.

Minimality: C+ = {C, D}; A+ = {A, B}. Every deletion misses at least one attribute, so this set is minimal.

Trace for BC: Start gives {B, C}; B → A gives {A, B, C}; C → D gives {A, B, C, D}.

Minimality: C+ = {C, D}; B+ = {A, B}. Every deletion misses at least one attribute, so this set is minimal.

C cannot be produced by any dependency, so every key contains C. Choose A or B: each produces the other. C supplies D. Neither A nor C alone covers the relation.

All candidate keys: AC, BC. Prime attributes: A, B, C. Non-prime attributes: D.

Problem 3: Composite left sides must match in full

Given: R(A, B, C, D, E), F = {AB → C; C → D; D → E}. Find every candidate key.

Test set	Closure steps	Result
AB	AB → ABC → ABCD → ABCDE	Candidate key
A	A	Not a superkey
B	B	Not a superkey
AC	AC → ACD → ACDE	Not a superkey

Trace for AB: Start gives {A, B}; AB → C gives {A, B, C}; C → D gives {A, B, C, D}; D → E gives {A, B, C, D, E}.

Minimality: B+ = {B}; A+ = {A}. Every deletion misses at least one attribute, so this set is minimal.

A and B never appear on a right-hand side, so both are compulsory. AB triggers AB → C, then C → D and D → E. Having A without B is not enough to use AB → C.

All candidate keys: AB. Prime attributes: A, B. Non-prime attributes: C, D, E.

Problem 4: A cycle does not make every attribute a key

Given: R(A, B, C, D), F = {A → B; B → C; C → A}. Find every candidate key.

Test set	Closure steps	Result
AD	AD → ABD → ABCD	Candidate key
BD	BD → BCD → ABCD	Candidate key
CD	CD → ACD → ABCD	Candidate key
A	A → AB → ABC	Not a superkey
D	D	Not a superkey

Trace for AD: Start gives {A, D}; A → B gives {A, B, D}; B → C gives {A, B, C, D}.

Minimality: D+ = {D}; A+ = {A, B, C}. Every deletion misses at least one attribute, so this set is minimal.

Trace for BD: Start gives {B, D}; B → C gives {B, C, D}; C → A gives {A, B, C, D}.

Minimality: D+ = {D}; B+ = {A, B, C}. Every deletion misses at least one attribute, so this set is minimal.

Trace for CD: Start gives {C, D}; C → A gives {A, C, D}; A → B gives {A, B, C, D}.

Minimality: D+ = {D}; C+ = {A, B, C}. Every deletion misses at least one attribute, so this set is minimal.

D never appears on a right-hand side, so it is compulsory. A, B and C can each reach the whole cycle, but none can produce D. Pair D with any one member of the cycle.

All candidate keys: AD, BD, CD. Prime attributes: A, B, C, D. Non-prime attributes: none.

Problem 5: Reject an oversized superkey

Given: R(A, B, C, D), F = {A → BC; B → A}. Find every candidate key.

Test set	Closure steps	Result
AD	AD → ABCD	Candidate key
BD	BD → ABD → ABCD	Candidate key
BCD	BCD → ABCD	Superkey, not minimal
CD	CD	Not a superkey

Trace for AD: Start gives {A, D}; A → BC gives {A, B, C, D}.

Minimality: D+ = {D}; A+ = {A, B, C}. Every deletion misses at least one attribute, so this set is minimal.

Trace for BD: Start gives {B, D}; B → A gives {A, B, D}; A → BC gives {A, B, C, D}.

Minimality: D+ = {D}; B+ = {A, B, C}. Every deletion misses at least one attribute, so this set is minimal.

D is compulsory. Either A or B gives A, B and C; AD and BD are the keys here. BCD is not minimal because BD already works. This problem does not have a three-attribute candidate key; a larger superkey is not a larger key.

All candidate keys: AD, BD. Prime attributes: A, B, D. Non-prime attributes: C.

See full closure and minimality separately

The diagram uses Problem 6, where A determines BC and the pair BC determines A. The BC determinant is one set: B alone and C alone cannot trigger it.

A path:
  {A} -- A -> BC --> {A,B,C}
  delete A: {} stays {}
  result: A is a candidate key

BC path:
  {B,C} -- BC -> A --> {A,B,C}
  delete B: {C} stays {C}
  delete C: {B} stays {B}
  result: BC is a candidate key

AB path:
  {A,B} -- A -> BC --> {A,B,C}
  delete B: {A} still reaches R
  result: superkey, NOT minimal

Both A and BC are minimal under set inclusion. A has fewer members, but that does not make BC redundant: A is not a subset of BC.

Problem 6: A real different-size key case

Given: R(A, B, C), F = {A → BC; BC → A}. Find every candidate key.

Test set	Closure steps	Result
A	A → ABC	Candidate key
BC	BC → ABC	Candidate key
B	B	Not a superkey
C	C	Not a superkey
AB	AB → ABC	Superkey, not minimal

Trace for A: Start gives {A}; A → BC gives {A, B, C}.

Minimality: ∅+ = {}. Every deletion misses at least one attribute, so this set is minimal.

Trace for BC: Start gives {B, C}; BC → A gives {A, B, C}.

Minimality: C+ = {C}; B+ = {B}. Every deletion misses at least one attribute, so this set is minimal.

A alone covers the relation. BC also covers it, and deleting B or C breaks that ability. Both are candidate keys even though one has one attribute and the other has two. Minimal means no unnecessary member, not globally smallest cardinality.

All candidate keys: A, BC. Prime attributes: A, B, C. Non-prime attributes: none.

Why there are no others: Sets containing A and extra members are not minimal because A alone works. Without A, neither B nor C works alone; BC does. This covers every subset of ABC.

3. Why one-member deletion checks are enough

Closure is monotone: adding starting attributes cannot reduce the closure. If some proper subset Y of a superkey X were also a superkey, then X with any member outside Y removed would still contain Y and would still be a superkey. Therefore, showing that every single deletion fails proves minimality. It does not prove that you found all the other keys.

4. Common mistakes and fixes

Using AB → C when only A is known: the whole determinant AB must be available.
Stopping after one pass: keep applying dependencies until a complete pass changes nothing.
Calling every full closure a candidate key: full closure proves superkey status; minimality is a separate test.
Keeping only the smallest key: in Problem 6, A and BC are both minimal. BC must not be discarded just because A is shorter.
Choosing attributes based on the current rows: a sample may look unique by accident. Use the stated schema constraints.
Forgetting alternative keys: prime attributes come from the union of all candidate keys, not just your favourite key.

5. Self-test: try before opening the answers

R(A,B,C,D), F = {A → B; B → C; CD → A}. Find every candidate key.
R(A,B,C,D,E), F = {AB → C; C → D; D → B}. Find every candidate key.
R(A,B,C), F = {A → B; B → C}. Is AB a candidate key? Find all candidate keys.

Show checked answers and minimality tests

Self-test 1

All candidate keys: AD, BD, CD.

AD: AD → ABD → ABCD. Deleting members gives D+ = {D}; A+ = {A, B, C}.

BD: BD → BCD → ABCD. Deleting members gives D+ = {D}; B+ = {B, C}.

CD: CD → ACD → ABCD. Deleting members gives D+ = {D}; C+ = {C}.

D is compulsory; A, B and C each combine with D to reach all attributes. No other minimal combination remains.

Self-test 2

All candidate keys: ABE, ACE, ADE.

ABE: ABE → ABCE → ABCDE. Deleting members gives BE+ = {B, E}; AE+ = {A, E}; AB+ = {A, B, C, D}.

ACE: ACE → ACDE → ABCDE. Deleting members gives CE+ = {B, C, D, E}; AE+ = {A, E}; AC+ = {A, B, C, D}.

ADE: ADE → ABDE → ABCDE. Deleting members gives DE+ = {B, D, E}; AE+ = {A, E}; AD+ = {A, B, C, D}.

A and E are compulsory. Neither creates B, C or D, so add one of B, C or D; these three attributes form a cycle once a suitable composite determinant is available. The keys are ABE, ACE and ADE.

Self-test 3

All candidate keys: A.

A: A → AB → ABC. Deleting members gives ∅+ = {}.

AB is a superkey but not a candidate key: removing B leaves A, which still determines everything.

6. How this connects to normalization

After finding all keys, mark prime attributes before applying the formal 3NF test. BCNF requires every nontrivial FD determinant to be a superkey. Knowing one primary key is not enough to classify every dependency. Continue with the worked 3NF and BCNF notes; for a different DBMS exercise, try the SQL NULL, COUNT and LEFT JOIN worksheet. The Exam Numericals Hub collects subject-wise practice.

Run all nine candidate-key checks

This standalone Python 3 script enumerates subsets from small to large and computes closure to a fixed point. It checks all six problems and all three self-tests, repeats with reversed FD order and asserts one-member deletion failure for each answer. It is a small-schema checker, not a fast method for large attribute sets: subset enumeration is exponential. The empty set is included.

from itertools import combinations

def closure(seed, fds):
    known = set(seed)
    while True:
        before = known.copy()
        for left, right in fds:
            if set(left) <= known:
                known.update(right)
        if known == before:
            return known

def candidate_keys(attrs, fds):
    found = []
    for size in range(len(attrs) + 1):
        for members in combinations(attrs, size):
            key = set(members)
            if any(previous <= key for previous in found):
                continue
            if closure(key, fds) == set(attrs):
                found.append(key)
    return ["".join(sorted(key)) or "empty" for key in found]

cases = [
    ("1", "ABCD", [("A", "B"), ("B", "C"), ("C", "D")]),
    ("2", "ABCD", [("A", "B"), ("B", "A"), ("C", "D")]),
    ("3", "ABCDE", [("AB", "C"), ("C", "D"), ("D", "E")]),
    ("4", "ABCD", [("A", "B"), ("B", "C"), ("C", "A")]),
    ("5", "ABCD", [("A", "BC"), ("B", "A")]),
    ("6", "ABC", [("A", "BC"), ("BC", "A")]),
    ("test 1", "ABCD", [("A", "B"), ("B", "C"), ("CD", "A")]),
    ("test 2", "ABCDE", [("AB", "C"), ("C", "D"), ("D", "B")]),
    ("test 3", "ABC", [("A", "B"), ("B", "C")]),
]
for name, attrs, fds in cases:
    keys = candidate_keys(attrs, fds)
    assert keys == candidate_keys(attrs, list(reversed(fds)))
    for key in keys:
        assert closure(key, fds) == set(attrs)
        assert all(closure(set(key) - {a}, fds) != set(attrs) for a in key)
    print(name + ": " + ", ".join(keys))

Executed output:

1: A
2: AC, BC
3: AB
4: AD, BD, CD
5: AD, BD
6: A, BC
test 1: AD, BD, CD
test 2: ABE, ACE, ADE
test 3: A

Exam and interview quick answers

Why must an attribute absent from all right sides occur in every key? Closure can only add attributes named on FD right sides. That attribute must be present at the start.
Does an empty compulsory set mean there are no keys? No. Problem 6 has no compulsory attribute, but A and BC are keys.
Can a candidate key contain three or more attributes? Yes. Self-test 2 has ABE, ACE and ADE; key size depends on the FDs.
Can the empty set be a key? Yes, if the stated FDs let its closure reach the whole schema, for example an empty determinant that determines every attribute. None of these nine cases does.
Why not stop after one FD pass? A later dependency may enable one already passed. Repeat until no new attribute is added.
Why does the checker skip supersets of a found key? Such a superset cannot be minimal, because its proper subset already determines R.
Can you infer all FDs from a few unique rows? No. Uniqueness in a sample does not establish a schema constraint.
Does choosing a primary key change the candidate-key list? No. It selects one existing candidate key; it does not remove the others.

References and answer checks

The problems, traces and self-tests on this page are original. Every candidate-key list was checked by enumerating every subset of its relation and running closure to a fixed point. Minimality was checked by containment and by one-member deletion.

Revision line: full closure proves superkey; failed deletions prove minimality; checking alternatives proves completeness.

Once you can find keys, try the next step: BCNF vs 3NF decomposition problems.

Learn the tech. Build the idea.

Latest Posts

Circuit Notebook theme

Exam Notes

📚 BTech CSE Exam Notes

Exam Numericals & Study Series

Pages

Start here and stay in touch

Browse Topics

Popular Posts

Candidate Keys and Attribute Closure: 6 Solved DBMS Problems