Finding Candidate Keys from FDs

Last lesson closed on a reversal. Computing X⁺ confirms a key you already suspect — you start with X, watch its closure grow, and check whether it swallows every attribute. That is the easy direction. The hard one ran the other way: handed nothing but a tangle of functional dependencies, how do you find all the keys, not merely test a guess? That hunt is what this lesson is about.

Picture a school’s attendance register. To point at exactly one pupil, what do you need to know? The roll number alone will do it. So will a full name together with a date of birth and a home town, if the school is small enough that no two such pupils collide. Each of these is a little bundle of facts that pins down one row and no other.

A single table can carry several such bundles at once. Before you crown one of them the primary key, you would like the honest list of all of them — and guessing is not a method. The functional dependencies already hold the answer; we only need a procedure that reads it off. GATE leans on exactly this almost every year — how many candidate keys does R have, or which of these is one — so the procedure is worth owning cold.

Here is the picture to carry. Treat each attribute as a room, and each FD X → Y as a one-way door: once you are standing in all the rooms of X, that door swings open and lets you into Y. A bundle that pins down a row is then a set of rooms you can start in and, walking through doors, reach every room in the building. The smallest such starting set is the thing we are hunting.

A candidate key, defined

That smallest reach-everything starting set has a name: a candidate key. Precisely, it is a set of attributes K such that:

1. K⁺ (its attribute closure) is the full set of attributes — K determines everything.
2. No proper subset of K already determines everything — K is minimal.

Condition 1 makes K a superkey: enough to reach every room. Condition 2 trims that superkey down until nothing can be dropped. A relation can own more than one candidate key, and a key with n attributes does not promise that some (n-1)-attribute key also exists — minimality is checked subset by subset, never assumed.

The shortcut: where each attribute appears

Before computing a single closure, look at where each attribute lives in the FDs. That one glance answers the question the last lesson left hanging — which attributes are forced into every key, and which can never appear in one.

• LHS-only — appears on some left-hand side, never on any right-hand side. Must sit in every candidate key. Nothing in the FDs produces it, so the only way to have it in your closure is to start holding it.
• RHS-only — appears only on right-hand sides. Cannot sit in any candidate key. It is always producible from something else, so including it can never be minimal.
• Both / neither — the optional middle. You may need some of these, and only here does any real searching happen.

The procedure

The classification turns into four mechanical steps.

1. Classify every attribute as LHS-only, RHS-only, or both.
2. Let K = the set of all LHS-only attributes. Compute K⁺.
3. If K⁺ is every attribute, then K is the one and only candidate key. Stop — nothing smaller can work (you cannot drop a mandatory attribute), and nothing else can be minimal.
4. Otherwise, add ONE “both” attribute at a time to K and recompute. If a single addition completes the closure, that set is a candidate key. If none does, try pairs, then triples — always keeping minimality by skipping any superset of a key you already found.

Most exam problems halt at step 3, or after a single one-attribute extension. The cost lives entirely in the “both” bucket; the smaller that bucket, the shorter the hunt.

How GATE asks this

• NAT — “How many candidate keys does R have?” Run the procedure; count.
• MCQ — “Which of the following is a candidate key of R?” For each option, ask two questions: is it a superkey, and is it minimal (drop each attribute, recompute the closure)?
• MSQ — properties of candidate keys themselves: LHS-only inclusion, RHS-only exclusion, minimality, multiplicity.

Worked example

R(A, B, C, D, E) with F = {A → B, BC → D, D → E}. Find all candidate keys.

Step 1 — classify. Scan each attribute against the three FDs.

• A: left of A → B. Never on any RHS. → LHS-only.
• C: left of BC → D. Never on any RHS. → LHS-only.
• B: left of BC → D; right of A → B. → both.
• D: left of D → E; right of BC → D. → both.
• E: only right of D → E. → RHS-only.

Step 2 — start from the mandatory set. The LHS-only attributes are A and C, so K = {A, C}.

Step 3 — compute K⁺, one firing at a time.

1. Start closure = {A, C}.
2. A → B: A is in, so add B → {A, B, C}.
3. BC → D: B and C are both in, so add D → {A, B, C, D}.
4. D → E: D is in, so add E → {A, B, C, D, E}. Every attribute is in; stop.

{A, C}⁺ reaches everything, so {A, C} is a superkey. It holds both LHS-only attributes, and those are mandatory in any candidate key — so it cannot be shrunk. Therefore {A, C} is the unique candidate key.

No extensions are worth trying. Any other superkey would also have to contain {A, C}, which makes it a superset of the key we found — and a superset is never minimal.

In one breath

A candidate key is a minimal superkey: its closure spans the whole relation, and no proper subset already does. Sort the attributes by where they live in the FDs — LHS-only ones belong to every key, RHS-only ones to none, and the rest are the only attributes you ever search over. Start from the LHS-only set, grow its closure, and extend through the “both” bucket only if you must.

Practice

A question to carry forward

You can now hand back, for any table, the full list of its candidate keys. That list quietly sorts every attribute into two camps: the prime attributes, which belong to at least one candidate key, and the non-prime ones, which belong to none. Hold onto that split — it is about to do real work.

Because a table can be technically correct and still feel badly built: the same department head copied onto every employee row, a customer’s whole order crammed into one cell, a fact you cannot record until some unrelated fact exists. Here is the thread onward: given the keys you just found and the prime/non-prime labels they imply, is there a precise ladder of “how clean is this design” that you can test a table against — and what exactly does each rung forbid?