Finding candidate keys

Why it exists

Candidate keys decide the normal form of a schema (which attributes are prime), the superkeys the number of which GATE asks to count, and the way a table is stored and indexed. The question "find all candidate keys of $R$ with the dependencies $F$" appears in almost every paper.

Prerequisites

You need attribute closures and implication (functional dependencies) and the notions of superkey and candidate key (relational model and keys).

Precise definitions

For a schema $R$ with dependencies $F$:

• $K \subseteq R$ is a superkey iff $K^+ = R$.
• $K$ is a candidate key iff it is a superkey and no proper subset of $K$ is a superkey (it is minimal).
• An attribute is prime if it belongs to some candidate key, otherwise non-prime.

How it works

Two quick rules

Look at where each attribute occurs in the dependencies:

1. An attribute that appears on no right side can never be derived: it is in every candidate key.
2. An attribute that appears only on right sides (never on a left side) is derived from others and is useless for deriving anything: it is in no candidate key.

Attributes of the first kind form the core. If $\text{core}^+ = R$, the core is the only candidate key. Otherwise add attributes from the "middle" group (those on both sides) one at a time, or in groups of increasing size, until the closure is all of $R$; keep only minimal sets.

The procedure

1. Compute the core (attributes on no right side). Compute $\text{core}^+$.
2. If it is $R$: the single candidate key is the core. Stop.
3. Otherwise try the core plus one of the remaining candidate attributes; then plus two; and so on. A set is a candidate key if its closure is $R$ and it contains no smaller candidate key found earlier.
4. The sets found are all the candidate keys. The prime attributes are the union of the keys.

Examples, found with this procedure and compared with the list of all minimal superkeys:

For $R(A, B, C, D, E)$ with $F = \{A \to B,\ BC \to E,\ DE \to A\}$: $C$ and $D$ appear on no right side, so they are in every key; $CD^+ = CD$ is not enough. Add one more attribute: $A$ gives $ACD^+ = ABCDE$ (key), $B$ gives $BCD^+$: $BC \to E$ then $DE \to A$, all of $R$ (key), $E$ gives $CDE^+$: $DE \to A$, $A \to B$ (key). Three candidate keys, $ACD$, $BCD$, $CDE$; every attribute is prime.

For $R(A, B, C)$ with $\{AB \to C,\ C \to B\}$: $A$ is in every key ($A$ is on no right side). $A^+ = A$. Add $B$: $AB^+ = ABC$ (key). Add $C$: $AC^+ = ABC$ (key). Keys $AB$ and $AC$; $B$ and $C$ are prime although $C \to B$ has a non-key left side (this matters for 3NF).

A cycle of dependencies

$A \to B$, $B \to C$, $C \to D$, $D \to A$: every attribute determines all the others around the cycle, so $A$, $B$, $C$ and $D$ are each a candidate key. Cycles are the typical way to get many keys.

How many candidate keys can there be

No candidate key contains another (they form an antichain of subsets of $R$), so by Sperner's theorem (quoted) a schema with $n$ attributes has at most $\binom{n}{\lfloor n/2 \rfloor}$ candidate keys. The bound is reached: for $R(A, B, C, D)$ with the six dependencies $AB \to CD$, $AC \to BD$, $AD \to BC$, $BC \to AD$, $BD \to AC$, $CD \to AB$ the candidate keys are exactly the six pairs, $\binom{4}{2} = 6$ (checked by program).

Counting superkeys

Once the candidate keys are known, count superkeys by inclusion–exclusion over the keys (relational model and keys): with the single key $ACD$ among five attributes there are $2^{5-3} = 4$ superkeys; with the three keys $ACD$, $BCD$, $CDE$ the superkeys are the sets that contain at least one of them.

Checking a proposed key

To check that $K$ is a candidate key: (1) $K^+ = R$; (2) for every attribute $a \in K$, $(K - \{a\})^+ \ne R$. Checking minimality needs only the subsets with one attribute removed: a superkey contained in $K$ is contained in some $K - \{a\}$, and every superset of a superkey is a superkey, so if any proper subset of $K$ were a superkey, some $K - \{a\}$ would be one.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Prime attributes and superkeys decide the normal form (normal forms); the closure is described on the previous page.

PYQs

Consider a relational database schema with a relation R(A,
B, C, D). If {A, B} and {A, C} are the only two candidate
keys of the relation R, then the number of super keys of
relation R is ______ (answer in integer)

Consider a relation R(A,B,C,D,E) with the following three
functional dependencies.

AB→C; BC→D; C→E

The number of super keys in the relation R is...

Which of the following is NOT a super key in a relational
schema with attributes V, W, X, Y ,Z and primary key
VY?

A prime attribute of a relation scheme R is an attribute that
appears:

Consider the relation scheme R = (E, F, G, H, I, J, K, L,
M, N) and the set of functional dependencies {{E,F} →
{G}, {F} → {I,J}, {E,H} → {K,L}, {K} → {M}, {L}
→ {N}} on R. What is the key for R?

Given an instance of the STUDENTS relation as shown
below.

For (StudentName, StudentAge) to be the key for

this instance, the value X should NOT be equal to______

Relation R has eight attributes ABCDEFGH. Fields of R
contain only atomic values.

F = {CH → G, A → BC, B → CFH, E → A, F → EG}
is a set of functional dependencies (FDs) so that F+ is
exactly the set of FDs that hold for R.

How many candidate keys does the relation R have?

Consider a relation R with five attributes V, W, X, Y,
and Z. The following functional dependencies hold:
VY→
W,
WX
→
Z,
and
ZY
→
V.
Which of the following is a candidate key for R?

Consider a relation schema R = (A, B, C, D, E, H) on
which the following functional dependencies hold:
 { A → B, BC → D, E → C, D → A }.
What are the candidate keys of R?

Self-check

Revision card

References