Core CS · DBMS
Twenty-six superkeys, three of them minimal
A superkey is any set of columns whose values never repeat. A candidate key is a superkey you cannot make any smaller. You will find all three candidate keys in one five-row table, nominate one as primary, and then watch the database refuse six of the seven writes you push at them.
Find every candidate key, one subset at a time →01 The idea
Unique is the easy half
A key is not a special kind of column. It is a claim about the rows. Pick any set of columns, read down the table, and if no two rows ever carry the same combination of values in those columns, that set is a superkey. Nothing else is required. It does not have to be short, it does not have to mean anything, and it does not have to be declared anywhere in the schema.
Superkeys are cheap, which is why no interview question has one as its answer. Bolt an extra column onto a superkey and you get another superkey, because two rows that already differed somewhere still differ. A five-column table earns sixteen superkeys from a unique roll number alone, and the one in the next section reaches twenty-six because two more things in it are unique as well. What you actually want are the ones you cannot shrink: take a superkey, remove one column, and if what is left is still unique then the column you removed was carrying nothing. Keep removing until every column left is doing work. That set is a candidate key.
Every relation has at least one candidate key, and the reason is worth knowing. A relation is a set of rows, so no two rows are identical, so the set of all columns is always unique and some minimal part of it must be too. Most relations have more than one. When they do you nominate one as the primary key and the others keep working under the name alternate keys. Every remaining term in this lesson is a label on top of those three. Composite says the key spans more than one column. Foreign says the values must already exist somewhere else. Surrogate says you manufactured the column instead of finding it.
02 Worked example
Five students, and every key hiding in them
One relation, five rows, five columns. Treat these rows as the whole world for the rest of the lesson. Seat numbers are allotted per department and restart at 1 in each one, and the college issues one email address per student.
-- STUDENT(roll, email, dept, seat, name) roll email dept seat name S1 asha.k@clg.edu CSE 1 Asha S2 asha.m@clg.edu CSE 2 Asha S3 ravi.p@clg.edu ECE 1 Ravi S4 ravi.s@clg.edu MEC 1 Ravi S5 nita.j@clg.edu ECE 2 Nita -- two students called Asha, two called Ravi, and seat 1 appears three timesRead line 3 against line 4. S1 and S2 share a department and share a name, so neither dept nor name nor the pair of them together can tell those two rows apart. Read line 3 against line 5: both are seat 1, in different departments. Read line 5 against line 6: both are Ravi, both are seat 1, in different departments. Those three collisions are not accidents of this sample. They are what the rules of a college allow, which is what makes them evidence rather than coincidence.
Node 2 is the only step in that chain anybody gets wrong. Node 1 is a property of the data and takes no judgement. Nodes 3, 4 and 5 are declarations you type. Node 2 is a test, and the test is not “is this set unique” but “is anything inside it already unique”. {roll, name} passes node 1 and fails node 2, because {roll} on its own was already enough.
The three survivors here are {roll}, {email} and {dept, seat}. Section 03 puts each one into a schema and gives it the name an interviewer will ask for. The console in section 04 walks every column set in this table until all 31 of them are decided, and then attacks the three that survived.
03 Mechanics
Seven names, and the single test behind each one
These seven words describe the same five rows from seven angles. The middle column is what decides the question in an interview, because each one is a one-line test you can run on a table you have just been handed. Two of the seven are not about uniqueness at all: composite is about size, and surrogate is about where the column came from.
| Key | The exact test | In our STUDENT rows | Declared as |
|---|---|---|---|
| Superkey | Its combination of values is different on every row. Nothing is asked about size. | 26 of the 32 column sets, including {roll, name} and {email, dept, seat, name} |
Nothing. It is a property of the data, not a constraint. There is no CREATE SUPERKEY. |
| Candidate key | A superkey with no proper subset that is also a superkey. Remove any column and two rows collide. | {roll}, {email}, {dept, seat} |
One PRIMARY KEY, and one UNIQUE for each remaining candidate key. |
| Primary key | The candidate key you nominated. Unique, and NOT NULL in every one of its columns. | {roll} |
PRIMARY KEY (roll), which is UNIQUE plus NOT NULL in one word. |
| Alternate key | A candidate key that was not nominated. It did not stop being a key and it is still enforced. | {email} and {dept, seat} |
UNIQUE (email) and UNIQUE (dept, seat). |
| Composite key | Any key of two or more columns. Size is the only test, so it says nothing about which role the key plays. | {dept, seat} — seat restarts per department, so neither half works alone |
Written at table level, because a constraint beside a column can only name that column. |
| Foreign key | A column set whose non-null values must already appear as a value of a declared key in the referenced table. | mentor → student(roll), pointing back into this same table |
REFERENCES student(roll). Nullable unless you add NOT NULL. |
| Surrogate key | A candidate key you manufactured, carrying no meaning outside the database. | none yet — every key above was found in the data, not invented |
GENERATED ALWAYS AS IDENTITY, AUTO_INCREMENT, or a sequence. |
Here is the whole thing as a schema. One new column joins the five from section 02: mentor holds the roll number of a senior student, and the table it points at is the table it lives in.
CREATE TABLE student ( roll TEXT PRIMARY KEY, -- the nominated candidate key email TEXT NOT NULL UNIQUE, -- alternate key dept TEXT NOT NULL, seat INT NOT NULL, name TEXT NOT NULL, mentor TEXT REFERENCES student(roll), -- foreign key into this same table UNIQUE (dept, seat) -- alternate key, and composite);-- there is no line here for the other 23 superkeys, and there never will be.-- "unique, with spare columns bolted on" is not worth checking on every write.Line 2 is two constraints wearing one keyword. PRIMARY KEY means unique and not null together, and the not-null half is the part candidates forget. It has a name, entity integrity, and the reason is mechanical rather than stylistic: the primary key is how every other row and every other table refers to this row, and null means “no value here”. A row whose identifier is partly missing cannot be referred to at all. For a composite primary key that applies to every column of it, not just to one of them.
Line 7 is the self-referencing foreign key. It is an ordinary foreign key that happens to name its own table, and the database checks it using the same primary key index it already built for line 2. S1 has no mentor, and that is legal: a foreign key may be null, because null there means “this row refers to nothing”, which is a perfectly good state. Referential integrity only ever checks the non-null values. What is refused by default is deleting a student that another row points at, because the pointer would be left aimed at nothing.
Line 8 has to sit at table level, after the columns, because a constraint written beside a column can only speak about that column. That is a syntax rule rather than a semantic one, and it matters: seat INT UNIQUE on line 5 would be a far stronger and quite wrong claim, saying seat numbers never repeat across the whole college.
Two vendor differences worth naming, because interviewers do. UNIQUE does not imply NOT NULL anywhere, and under the standard two nulls never compare equal, so a bare UNIQUE column accepts many nulls in PostgreSQL, MySQL and Oracle. SQL Server accepts exactly one, and there you declare a filtered unique index instead. Line 3 spells NOT NULL out beside UNIQUE for that exact reason, because UNIQUE on its own would have let a hundred students sit in this table with no email at all. And SQLite, because of a long-standing bug it keeps for backward compatibility, allows nulls in a PRIMARY KEY column unless it is an INTEGER PRIMARY KEY or the table is declared WITHOUT ROWID. Quote the standard in an interview, then name the exception.
05 Cheat sheet
Seven definitions, and the seven ways they get said wrong
The middle column is what you say. The right-hand column is the version most candidates give, and every one of them is wrong in a way the interviewer is specifically listening for.
| Key | Say this | Not this |
|---|---|---|
| Superkey | Any column set whose values never repeat. Minimality is not required. | "a set that identifies a row" — true of every candidate key too, so it separates nothing |
| Candidate key | A superkey with no smaller superkey inside it. | "a key that could become the primary key" — leaves out minimality, which is the entire test |
| Primary key | The candidate key you nominated: unique, and not null in every column. | "the unique identifier of a row" — a UNIQUE column is that too, and it still accepts a null |
| Alternate key | A candidate key that was not nominated, declared UNIQUE and enforced on every write. | "a backup key" — nothing ever falls back to it; it is checked as hard as the primary key |
| Composite key | Any key of two or more columns. | "a primary key joined to a foreign key" — size is the only test, and role has nothing to do with it |
| Foreign key | Columns whose non-null values must exist as a value of a declared key in the referenced table. | "another table's primary key copied in" — it may reference any UNIQUE key, and it may be null |
| Surrogate key | A generated candidate key with no meaning outside the database. | "an auto-increment id" — that is one implementation; the definition is meaninglessness, not the counter |
06 Where & why
What real databases do with the key you chose
Choosing a primary key is not a paper exercise. It decides how rows are physically stored in some engines, what happens the day the value it is built on changes, and what the database does when you decline to choose at all.
Most production tables carry a generated integer primary key — GENERATED ALWAYS AS IDENTITY in PostgreSQL, AUTO_INCREMENT in MySQL — and keep the natural key beside it as a UNIQUE alternate key so the real-world rule is still enforced. Dropping that UNIQUE once the surrogate exists is the mistake to watch for: the table then happily stores the same student twice under two different generated ids, and the surrogate cannot tell you that anything is wrong.
InnoDB stores every table clustered on its primary key. Declare none and it takes the first UNIQUE NOT NULL index instead; if there is not one of those either, it manufactures a hidden six-byte row id you can never see, query or join on. A wide or frequently changed primary key is therefore a physical cost and not only a modelling choice, because every secondary index carries a copy of it.
A UNIQUE constraint here accepts at most one null across the whole column rather than many, so an alternate key on an optional column behaves differently from every other mainstream engine. When you genuinely want “unique among the rows that have a value”, you declare a filtered unique index with a WHERE clause instead of a plain constraint.
Every ordinary SQLite table already carries a hidden 64-bit rowid, which is a surrogate key whether you declared one or not, and it is why INTEGER PRIMARY KEY is a special case in that engine. Oracle has had identity columns since 12c; before that the standard pattern was a SEQUENCE plus a trigger, which is the same surrogate assembled by hand.
07 Interview questions
What they actually ask
Keys are the first thing asked about the relational model and the place a sloppy answer does the most damage, because one missing word turns a correct definition into a wrong one. Expect to be handed a small table and asked for its candidate keys out loud.
What is a superkey?
Superkey versus candidate key. What is the actual difference?
How do you find all the candidate keys of a relation?
Can a relation have more than one candidate key?
Why can no part of a primary key be null?
Primary key versus a UNIQUE constraint. Are they the same thing?
What is a composite key?
What is a foreign key, and can it be null?
What is a self-referencing foreign key?
Surrogate key versus natural key. Which do you actually use?
What is entity integrity, and what is referential integrity?
Can a table have no key at all?
08 Practice problems
Six to work through
For every one: test uniqueness first, then minimality, and never the other way round. Naming a key before you have checked what is inside it is exactly how a superkey gets called a candidate key.