Finding Candidate Keys from FDs

Last lesson closed on a reversal. Two words carry it, so both are worth restating. A functional dependency X → Y is a rule saying “fix the values in X and the values in Y are pinned down along with them”. The closure X⁺ is everything you can pin down by starting from X and firing those rules over and over until nothing new appears.

Computing X⁺ confirms a key you already suspect — you start with X, watch the 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. In plain words, it does two jobs at once — it is enough on its own, and it carries nothing spare. 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 on its own makes K a superkey: enough to reach every room. Condition 2 trims that superkey down until nothing can be dropped.

Superkey versus candidate key is the distinction most people have to read twice, so here it is in one line: every candidate key is a superkey, but most superkeys are not candidate keys. Bolt any spare attribute onto a key and you still reach every room, so the result is still a superkey — just a wasteful one. If {A, C} is a key of R(A,B,C,D,E), then {A, C, E} and even all five attributes together are superkeys too. “Candidate” is exactly the promise that nothing in the bundle is dead weight.

A relation can own more than one candidate key. 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.

The search in action

Step 4 is the step nobody has watched happen, so here it is on real letters. Take R(A, B, C, D) with F = {A → B, B → A, C → D}. Classification: C is LHS-only, D is RHS-only, A and B are both.

Start from K = {C} — but C⁺ = {C, D}, short of A and B, so step 3 does not fire. Add one “both” attribute at a time: {A, C}⁺ = {A, B, C, D} ✓ and {B, C}⁺ = {A, B, C, D} ✓. Two candidate keys, {A, C} and {B, C}.

Most exam problems halt at step 3, or after a single one-attribute extension like that one. 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}. That 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 belong to none.
• 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? What exactly does each rung forbid?