Superkey, candidate key, primary key, alternate key; counting superkeys

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. If x is NULL, what is x = x? from Lesson 2.1.2
2. What does "no duplicate tuples" imply about any relation? from Lesson 2.1.1
3. How many attribute groups of 5 attributes contain A or B? from Lesson 0.2.4

1 · The Hook

Every relation has no duplicate tuples, so all attributes together always tell tuples apart. But we want something smaller and more useful: the fewest attributes that identify a row, like roll for STUDENT. GATE's favourite counting question lives here: "R has n attributes and these candidate keys; how many superkeys?"

2 · Predict First

STUDENT(roll, name, dept, cgpa). Roll is unique. Which of these identify a student: {roll}, {roll, name}, {name}, {roll, name, dept, cgpa}? Which are as small as possible?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

{roll}, {roll, name} and {roll, name, dept, cgpa} all identify a student, because each contains roll. {name} does not (names can repeat). Only {roll} is minimal: you cannot remove anything from it. Sets that identify are superkeys; minimal ones are candidate keys.

Superkey

A superkey of R is a set of attributes SK such that no two distinct tuples in any valid state of R have the same values for SK. In symbols: for all t₁ ≠ t₂, t₁[SK] ≠ t₂[SK].

• The set of all attributes is always a superkey (no duplicate tuples).
• Any superset of a superkey is a superkey.

Candidate key

A candidate key is a minimal superkey: a superkey from which no attribute can be removed without losing uniqueness. A relation can have several candidate keys: STUDENT(roll, aadhaar, name, …) has {roll} and {aadhaar}. A candidate key can be composite: ENROLL(roll, cid, grade) has candidate key {roll, cid}.

"Minimal" means no proper subset is a superkey, not "fewest attributes overall". {roll, cid} is minimal even if another candidate key had one attribute.

Primary key and alternate keys

• The primary key (PK) is the one candidate key the designer chooses to identify tuples. It is underlined in schemas. Its attributes may never be NULL.
• The other candidate keys are alternate keys (also "secondary" or "unique" keys).
• An attribute that belongs to some candidate key is called prime (Lesson 4.2.3 uses this heavily).

Keys are rules about all states

A key is a constraint declared by the designer for every valid state. A single instance can disprove a key (two tuples with the same values) but can never prove one.

Counting superkeys

With n attributes:

• One candidate key with k attributes: superkeys = its supersets = 2ⁿ⁻ᵏ.
• Two candidate keys K₁, K₂: |supersets of K₁| + |supersets of K₂| − |supersets of K₁ ∪ K₂| = 2ⁿ⁻|K₁| + 2ⁿ⁻|K₂| − 2ⁿ⁻|K₁∪K₂|.
• Three candidate keys: inclusion–exclusion with three terms, three pair-unions and one triple-union (Lesson 0.2.4).

Example: R(A, B, C, D) with candidate keys {A} and {B}: 2³ + 2³ − 2² = 8 + 8 − 4 = 12 superkeys.

Maximum number of candidate keys

Candidate keys cannot contain one another, so they are like subsets of the attributes none of which contains another. The maximum for n attributes is C(n, ⌊n/2⌋): all groups of half the attributes. For n = 4 that is C(4, 2) = 6.

4 · Visual

R(A, B, C, D)   candidate keys {A} and {B}

Superkeys containing A        : A, AB, AC, AD, ABC, ABD, ACD, ABCD   (2^3 = 8)
Superkeys containing B        : B, AB, BC, BD, ABC, ABD, BCD, ABCD   (2^3 = 8)
Counted twice (contain A and B): AB, ABC, ABD, ABCD                  (2^2 = 4)

Superkeys = 8 + 8 - 4 = 12        Not superkeys: C, D, CD, and the empty set

5 · Worked Examples

Example 1 Easy

ENROLL(roll, cid, grade): a student takes a course once; a student takes many courses; a course has many students. Find all candidate keys and all superkeys.

Solution

Candidate key {roll, cid}: neither alone is unique, the pair is. Superkeys: {roll, cid} and {roll, cid, grade}: 2³⁻² = 2.

Example 2 Medium

This instance of R(A, B, C) is given: (1, x, p), (2, x, q), (3, y, p). Which of {A}, {B}, {C}, {B, C} can be ruled out as keys from this instance? Can any be confirmed?

Solution

{B} is ruled out (x appears twice) and {C} is ruled out (p twice). {A} and {B, C} are unique in this instance, so they might be keys, but no instance can confirm a key; that is a design rule.

Example 3 GATE

R(A, B, C, D, E) has candidate keys {A, B} and {C, D}. How many superkeys does R have?

Solution

Contain AB: 2³ = 8. Contain CD: 2³ = 8. Contain both, i.e. ABCD: 2¹ = 2. Superkeys = 8 + 8 − 2 = 14.

8 · Connect the Dots

Lesson 2.1.1 showed that all attributes together always identify tuples; this lesson shrank that to candidate keys and chose a primary key. Next: a key from one table stored inside another table, the foreign key, which is how tables refer to each other.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Counting superkeys

R(A, B, C, D, E, F) has exactly one candidate key {A, B}. How many superkeys does R have?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Counting superkeys

R(A, B, C, D) has candidate keys {A, B} and {B, C}. How many superkeys?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Definitions

A candidate key is:

1. (A) the key with the fewest attributes
2. (B) a key that may contain NULL in every attribute
3. (C) a minimal superkey
4. (D) any superkey

Q4 · MSQ · 2 mark(s) — Keys

STUDENT(roll, aadhaar, name, dept): roll and aadhaar are each unique. Which are true?

1. (A) {roll, name} is a superkey.
2. (B) {roll} and {aadhaar} are candidate keys.
3. (C) {roll, aadhaar} is a candidate key.
4. (D) If roll is the primary key, aadhaar is an alternate key.

Q5 · NAT · 1 mark(s) — Max candidate keys

What is the maximum number of candidate keys a relation with 4 attributes can have?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

superkeycandidate key (minimal superkey)primary key (PK)alternate keyprime attributecounting superkeysmax candidate keys C(n, ⌊n/2⌋)