1.4Keys: super, candidate, primary, foreign
The idea
A super key identifies a row uniquely. A candidate key is a super key with nothing removable. One candidate key is chosen as the primary key. A foreign key points to a key of another table.
Think of it like this: A student can be identified by roll number, or by (name, birthday, mother's name): both are super keys, but only the minimal ones are candidate keys.
Why it exists
Counting super keys and candidate keys is a stock GATE question.
How it works
- Super key: closure contains every attribute.
- Candidate key: a super key where removing any attribute breaks it.
- With n attributes and a single candidate key of size k there are 2^(n−k) super keys.
- With two keys use inclusion-exclusion: 2^(n−|K1|) + 2^(n−|K2|) − 2^(n−|K1∪K2|).
Worked example: R(A, B, C, D, E) has only the candidate key A. How many super keys?
Every set containing A: 2⁴ = 16.
Now play with it
- →Use the subset grid above: green are candidate keys, yellow are the other super keys.
- →Change the key sizes in the calculator and check the formula.
Every subset of the attributes. Green = candidate key (minimal), yellow = super key but not minimal, grey = not a key.
Method: attributes that never appear on a right side must be in every key; start with them, take the closure, and add attributes only if something is still missing.
A super key is any attribute set that contains a candidate key: 2^(n−k) sets contain a given k-attribute key. For two keys, subtract the sets that contain both.
Check yourself
R has n = 5 attributes and its only candidate key is {A, B}. The number of super keys is
Exam notes (the dense version)
A super key uniquely identifies a row. A candidate key is a minimal super key. The primary key is the chosen candidate key (not NULL). A foreign key refers to a candidate key of another (or the same) table. If a relation of n attributes has one candidate key of size k, it has 2^(n−k) super keys. The primary key can never be NULL; a foreign key may be.
Previous year questions: ER Model, Relational Model & Keys (9)
PYQs are grouped by topic, so this is the full set for ER Model, Relational Model & Keys; try the ones that match this subtopic. Open all 9 on the topic page.