Attribute Closure and Candidate Keys for GATE

Candidate keys are easy to miss when you try to see them by inspection. Treat the question as an algorithm instead. Start from attributes that every key must contain, compute closures to a fixed point, and test minimality separately from superkey status.

That process finds all the keys without trusting a clever-looking guess.

Attribute closure: use the fixed-point algorithm

For an attribute set X and functional dependencies F, the closure X+ is every attribute functionally determined by X under F. The procedure is short:

1. Set result = X.

2. For each FD Y -> Z, if Y is contained in result, add Z to result.

3. Repeat the full scan until a pass adds nothing.

Stopping after one scan is unsafe because a newly added attribute can enable another FD, including one that appeared earlier in your written list.

Consider relation R(A, B, C, D, E) with:

F = {A -> B, B -> C, CD -> E, E -> D}

First compute A+:

A+ = {A}
   = {A, B}       using A -> B
   = {A, B, C}    using B -> C

Neither CD -> E nor E -> D can fire. The fixed point is {A, B, C}, so A alone is not a superkey.

Now compute (AD)+:

Start:              {A, D}
Use A -> B:         {A, B, D}
Use B -> C:         {A, B, C, D}
Use CD -> E:        {A, B, C, D, E}

All attributes have been reached, so AD is a superkey. It is minimal because A+ is {A, B, C} and D+ is {D}. Removing either A or D destroys superkey status. Therefore AD is a candidate key.

Repeat the arithmetic in a different order as a check. Starting from AD, derive C through A -> B -> C, then combine C with the original D to derive E. The result is again ABCDE.

Finding all candidate keys systematically

A superkey determines every attribute in the relation. A candidate key is a minimal superkey, meaning no proper subset remains a superkey. Finding one candidate key does not answer a question asking for all of them.

Use the RHS test on the same FD set. The attributes appearing on right-hand sides are {B, C, E, D}. Attribute A never appears on any RHS, so no other attributes can derive it. A must occur in every candidate key.

Start with the mandatory set {A}. Its closure is {A, B, C}. The missing attributes are D and E. Test the smallest additions:

• We already found (AD)+ = ABCDE, so AD is a candidate key.

• For AE, start with {A, E}. A -> B adds B, B -> C adds C, and E -> D adds D. Thus (AE)+ = ABCDE. Since neither A nor E alone is a superkey, AE is also a candidate key.

No other minimal key exists. Adding B or C to A cannot supply D or E because A already derives both B and C. Any larger set containing AD or AE is a superkey but fails minimality. The complete candidate-key set is therefore:

{AD, AE}

A useful classification is:

• Attributes not on any RHS must be in every key. Here that set is {A}.

• Attributes already in the closure of the mandatory set need not be added during enumeration. Here B and C are such attributes.

• Remaining attributes are the useful choice set. Here choosing D or E completes a minimal key.

Do not turn the last line into a universal claim that an attribute appearing only on an RHS can never be in a key. E appears on an RHS here and still belongs to candidate key AE. Closure and minimality decide the final answer.

Prime and non-prime attributes

An attribute is prime if it belongs to at least one candidate key. With keys AD and AE, the prime attributes are A, D, and E. The non-prime attributes are B and C.

Prime status matters when checking normal forms. Partial dependency of a non-prime attribute on a proper subset of a composite key is central to 2NF. In 3NF, for every non-trivial FD X -> A, either X must be a superkey or A must be prime. That is why missing even one candidate key can produce a wrong normalization answer.

Continue that chain in normalization from 1NF to BCNF, where closure and keys become inputs to the decomposition decisions.

Counting candidate keys: a worked pattern

Consider R(P, Q, R, S) with:

F = {P -> Q, Q -> P, R -> S, S -> R}

P and Q determine each other, but neither pair member determines R or S. Similarly, R and S determine each other, but neither determines P or Q. A key must therefore select one attribute from {P, Q} and one from {R, S}.

The four combinations are:

PR, PS, QR, QS

Check PR: P -> Q and R -> S, so (PR)+ = {P, Q, R, S}. Neither P+ nor R+ contains all four attributes, so PR is minimal. The same symmetric argument verifies the other three pairs.

There are 2 x 2 = 4 candidate keys. This multiplication shortcut works because the two independent equivalence groups each contribute exactly one choice. Still write the combinations and verify one closure so that overlapping or cross-group dependencies do not hide an exception.

For another worked treatment of dependencies and design, see DBMS normalization explained.

How GATE tests closure and keys

Questions ask whether an FD follows from F, which sets are candidate keys, how many keys exist, or which attributes are prime. The standard traps are stopping closure too early, reporting a non-minimal superkey, assuming attributes on the RHS cannot enter a key, and finding only the first valid key.

Write the closure as a growing set and annotate the FD that fires at each step. When the question depends on current syllabus or paper instructions, check the official GATE portal of the organising IIT. The GATE CS preparation category provides the surrounding subject path.

The short version

Begin with attributes absent from every RHS, close them to a fixed point, and add the smallest useful combinations. A set becomes a candidate key only when its closure is the full relation and every attribute in the set is necessary. Enumerate all minimal alternatives before marking prime attributes.

Practise these steps under time pressure in the GATE Test Series. For every proposed key, write one full closure and one explicit minimality check.