Chapter 14 of 41

Keys in DBMS

In the previous chapter we saw that a relation is a set of tuples, so no two tuples can be identical. That raises a practical question: which attributes do we look at to tell one tuple from another? If you want to update one particular employee's salary, you need a way to point at exactly that row and no other.

That is the job of keys. Keys are also how tables point to each other (foreign keys), so they hold the whole database together. Interviewers love this topic because the definitions sound similar and are easy to mix up. By the end of this chapter you will be able to tell apart super keys, candidate keys, primary keys, alternate keys, composite keys, unique keys, foreign keys and surrogate keys — and count super keys like a GATE question asks.


The Example Relation

We'll use this relation for most of the definitions:

STUDENT(roll_no, email, aadhaar_no, name, dob, branch)
+---------+----------------+----------------+-------+------------+--------+
| roll_no | email          | aadhaar_no     | name  | dob        | branch |
+---------+----------------+----------------+-------+------------+--------+
|     101 | asha@uni.edu   | 2345 6789 0123 | Asha  | 2004-05-11 | CSE    |
|     102 | bilal@uni.edu  | 3456 7890 1234 | Bilal | 2003-12-02 | ECE    |
|     103 | asha.k@uni.edu | 4567 8901 2345 | Asha  | 2004-05-11 | CSE    |
+---------+----------------+----------------+-------+------------+--------+

Business rules: every student has a unique roll number, a unique university email and a unique Aadhaar number. Names, dates of birth and branches can repeat (look at the two Ashas).


Super Key

A super key is a set of one or more attributes whose values uniquely identify every tuple in the relation. No two distinct tuples can ever have the same values for all attributes of a super key.

Examples of super keys of STUDENT:

  • {roll_no}

  • {email}

  • {roll_no, name}

  • {email, branch, dob}

  • {roll_no, email, aadhaar_no, name, dob, branch} — the set of all attributes is always a super key, since a relation has no duplicate tuples.

Not super keys: {name}, {name, dob}, {name, dob, branch} — both Ashas share these values.

The important observation: if you add any attribute to a super key, it is still a super key. Adding columns can't make two rows the same. So super keys can contain lots of unnecessary attributes. That leads to the next definition.


Candidate Key

A candidate key is a minimal super key: a super key from which no attribute can be removed without losing the uniqueness property.

To check if a super key is a candidate key, try removing each attribute one at a time. If any smaller subset is still a super key, it isn't minimal.

  • {roll_no} — a single attribute; nothing to remove. Candidate key.

  • {email} and {aadhaar_no} — also candidate keys.

  • {roll_no, name} — remove name and {roll_no} is still a super key, so it's not minimal. Super key, but not a candidate key.

So STUDENT has three candidate keys: {roll_no}, {email}, {aadhaar_no}.

Minimal is not the same as smallest. A candidate key with 3 attributes is fine as long as no proper subset of it is a super key. A relation can have candidate keys of different sizes, e.g. {A} and {B, C}.

Prime and non-prime attributes

An attribute that is part of at least one candidate key is called a prime attribute; all others are non-prime. In STUDENT, roll_no, email and aadhaar_no are prime; name, dob and branch are non-prime. You'll need these terms in 1NF, 2NF & 3NF.


Primary Key

The primary key is the one candidate key chosen by the database designer to be the main way of identifying tuples. It must be unique and can never be NULL.

Every table has at most one primary key (it may be composite). Which candidate key should you choose? Good primary keys are:

  • Never NULL — every row must have it from the start. (A new student may not have an Aadhaar number linked yet.)

  • Stable — it shouldn't change. (Students change email addresses; roll numbers don't change.)

  • Short and simple — it's copied into every foreign key that references it, and indexed.

  • Not sensitive — an Aadhaar number shouldn't be spread across many tables.

So for STUDENT, roll_no is the natural choice.


Alternate Key

The candidate keys that were not chosen as the primary key are called alternate keys (or secondary candidate keys).

Here: {email} and {aadhaar_no}. In SQL you usually declare alternate keys with a UNIQUE constraint so the database still enforces their uniqueness.

Super keys  ⊇  Candidate keys  =  Primary key  +  Alternate keys
+---------------------------------------------------------------+
| SUPER KEYS  {roll_no,name}  {email,dob}  {all attributes} ... |
|   +-------------------------------------------------------+   |
|   | CANDIDATE KEYS (minimal super keys)                   |   |
|   |   +-------------------+   +------------------------+  |   |
|   |   | PRIMARY KEY       |   | ALTERNATE KEYS         |  |   |
|   |   |   {roll_no}       |   |   {email} {aadhaar_no} |  |   |
|   |   +-------------------+   +------------------------+  |   |
|   +-------------------------------------------------------+   |
+---------------------------------------------------------------+

Every primary key is a candidate key, and every candidate key is a super key — but not the other way round.


Composite Key

A composite key (or compound key) is a key made of two or more attributes.

Think of Indian Railways seat bookings. A seat number like B2-34 repeats on every train and every day. Even (train_no, seat_no) repeats daily. Only (train_no, travel_date, seat_no) identifies one booking:

CREATE TABLE seat_booking (
  train_no    INT,
  travel_date DATE,
  seat_no     VARCHAR(6),
  pnr         CHAR(10) NOT NULL,
  PRIMARY KEY (train_no, travel_date, seat_no)
);

INSERT INTO seat_booking VALUES
  (12951, '2026-12-01', 'B2-34', '4521873690'),
  (12951, '2026-12-02', 'B2-34', '8812093471');   -- same seat, different day: OK

INSERT INTO seat_booking VALUES (12951, '2026-12-01', 'B2-34', '9999999999');
ERROR 1062 (23000): Duplicate entry '12951-2026-12-01-B2-34' for key 'seat_booking.PRIMARY'

Notice that MySQL checks the combination: each column on its own may repeat. Composite keys are very common in junction tables for M:N relationships (e.g. enrolls(roll_no, course_id) from Converting ER Diagrams to Tables) and in weak entity tables.


Unique Key (SQL)

In SQL, a UNIQUE constraint guarantees that no two rows have the same non-NULL value in the column(s). It's how alternate keys are enforced. The difference from a primary key:

Point

PRIMARY KEY

UNIQUE

How many per table

At most one

Any number

NULL allowed?

No (columns become NOT NULL)

Yes, unless declared NOT NULL

Multiple NULLs?

Not applicable

Yes in MySQL — NULLs are not considered equal to each other

Purpose

Main identifier; target of foreign keys

Enforce alternate keys / business uniqueness

The sample company_db.employees table has email VARCHAR(100) UNIQUE. Meera Nair (emp_id 8) already has a NULL email. In a scratch copy of the database, we inserted a new employee, also with a NULL email — it was accepted:

SELECT emp_id, name, email FROM employees WHERE email IS NULL;
+--------+------------+-------+
| emp_id | name       | email |
+--------+------------+-------+
|      8 | Meera Nair | NULL  |
|     11 | Tanvi Shah | NULL  |
+--------+------------+-------+

But a duplicate non-NULL email is rejected:

ERROR 1062 (23000): Duplicate entry 'priya@company.com' for key 'employees.email'

This is why a nullable UNIQUE column is a "unique key" but should not be called a candidate key in practice: two rows with NULL can't be told apart by it. If you want an alternate key in the strict sense, declare it UNIQUE NOT NULL.


Foreign Key

A foreign key is an attribute (or set of attributes) in one relation whose values must match the values of a primary key (or unique key) in another relation — or be NULL.

  • The table containing the foreign key is the referencing (child) relation.

  • The table it points to is the referenced (parent) relation.

Foreign keys are how relations are linked. Here are all the foreign keys in company_db, read from MySQL's own catalog (information_schema):

SELECT TABLE_NAME, COLUMN_NAME, CONSTRAINT_NAME,
       REFERENCED_TABLE_NAME AS ref_table, REFERENCED_COLUMN_NAME AS ref_column
FROM information_schema.KEY_COLUMN_USAGE
WHERE TABLE_SCHEMA = 'company_db' AND REFERENCED_TABLE_NAME IS NOT NULL;
+------------+-------------+------------------+-------------+-------------+
| TABLE_NAME | COLUMN_NAME | CONSTRAINT_NAME  | ref_table   | ref_column  |
+------------+-------------+------------------+-------------+-------------+
| employees  | dept_id     | employees_ibfk_1 | departments | dept_id     |
| employees  | manager_id  | employees_ibfk_2 | employees   | emp_id      |
| orders     | customer_id | orders_ibfk_1    | customers   | customer_id |
+------------+-------------+------------------+-------------+-------------+

Things to notice:

  • A foreign key can reference its own table. employees.manager_id points to employees.emp_id — a self-referencing (recursive) foreign key. Vikram's manager_id is 4, which is Sneha's emp_id.

  • A foreign key can be NULL (unless declared NOT NULL). Aarav has no manager, Ishita has no department yet, and order 1008 is a guest order with a NULL customer_id.

  • A foreign key is not unique in the child table. Many employees share dept_id 10.

  • Names don't have to match. manager_id references emp_id; only the domains (data types) must be compatible.

The rule a foreign key enforces is called referential integrity. What happens when you violate it, and the options like ON DELETE CASCADE, are covered in the next chapter, Integrity Constraints.


Surrogate Key vs Natural Key

  • A natural key comes from real-world data: roll number, PAN, email, ISBN.

  • A surrogate key is an artificial identifier with no business meaning, typically generated by the DBMS: an auto-increment number or a UUID.

CREATE TABLE ticket (
  ticket_id INT AUTO_INCREMENT PRIMARY KEY,     -- surrogate key
  pnr       CHAR(10) NOT NULL UNIQUE,           -- natural key, kept as alternate key
  passenger VARCHAR(50) NOT NULL
);
INSERT INTO ticket (pnr, passenger) VALUES ('4521873690', 'Asha'), ('8812093471', 'Bilal');
SELECT * FROM ticket;
+-----------+------------+-----------+
| ticket_id | pnr        | passenger |
+-----------+------------+-----------+
|         1 | 4521873690 | Asha      |
|         2 | 8812093471 | Bilal     |
+-----------+------------+-----------+

Why use surrogate keys? Natural keys sometimes change (a person changes email), are long (a 3-column composite key copied into every child table), or are sensitive. A surrogate key is short, stable and meaningless. The trade-off: you must still put a UNIQUE constraint on the natural key, or duplicates of the same real-world thing can slip in with different surrogate ids.


Keys Are About the Schema, Not the Current Data

A key is a rule about all possible valid instances, not just the rows you see today. Looking at data can disprove a key but can never prove one.

SELECT city, COUNT(*) AS cnt FROM employees GROUP BY city HAVING COUNT(*) > 1 ORDER BY city;
+-----------+-----+
| city      | cnt |
+-----------+-----+
| Bengaluru |   2 |
| Mumbai    |   2 |
+-----------+-----+

Duplicates exist, so {city} is definitely not a key. Now try {name, salary}:

SELECT name, salary, COUNT(*) AS cnt FROM employees GROUP BY name, salary HAVING COUNT(*) > 1;

This returns an empty result — no duplicates right now. But {name, salary} is still not a key: nothing stops the company from hiring a second "Rohan Mehta" at 95,000. Keys come from the meaning of the data (business rules, or functional dependencies, which you'll learn in Functional Dependencies), not from a snapshot.


Counting Super Keys (GATE favourite)

If you know the candidate keys, you can count super keys without listing them. A super key is any set of attributes that contains at least one candidate key.

Case 1: one candidate key

R has n attributes and one candidate key with k attributes. Those k attributes must be in the set; each of the other n − k can be in or out:

Number of super keys = 2^(n - k)

Example: R(A, B, C, D), candidate key {A}: 23 = 8 super keys (A, AB, AC, AD, ABC, ABD, ACD, ABCD).

Case 2: two candidate keys — use inclusion–exclusion

|SK(K1) or SK(K2)| = |SK containing K1| + |SK containing K2| - |SK containing K1 and K2|

Example 1: R(A, B, C, D), candidate keys {A} and {B}.

containing A       : 2^3 = 8
containing B       : 2^3 = 8
containing A and B : 2^2 = 4
Total              : 8 + 8 - 4 = 12

Example 2: R(A, B, C, D), candidate keys {A, B} and {C, D}.

containing AB      : 2^2 = 4
containing CD      : 2^2 = 4
containing ABCD    : 2^0 = 1
Total              : 4 + 4 - 1 = 7

Example 3: R(A, B, C, D, E), candidate keys {A} and {B, C}.

containing A       : 2^4 = 16
containing BC      : 2^3 = 8
containing ABC     : 2^2 = 4
Total              : 16 + 8 - 4 = 20

(All three answers were checked by a small program that lists every subset of attributes and tests whether it contains a candidate key.)

Maximum number of candidate keys

Since no candidate key can contain another, the largest possible collection of candidate keys for n attributes is all subsets of size ⌊n/2⌋, giving C(n, ⌊n/2⌋). For n = 4 that's C(4, 2) = 6.

How do you find the candidate keys when the question gives functional dependencies instead of keys? That needs attribute closure, covered in Attribute Closure & Candidate Keys.


All Keys at a Glance

Key

Definition

STUDENT example

Super key

Any attribute set that uniquely identifies tuples

{roll_no, name}

Candidate key

Minimal super key

{roll_no}, {email}, {aadhaar_no}

Primary key

Chosen candidate key; unique, not NULL

{roll_no}

Alternate key

Candidate keys not chosen as primary

{email}, {aadhaar_no}

Composite key

Key with two or more attributes

(train_no, travel_date, seat_no) in seat_booking

Unique key

SQL UNIQUE constraint; NULLs allowed

email UNIQUE

Foreign key

References a key in another (or the same) table

employees.dept_id → departments.dept_id

Surrogate key

System-generated, no business meaning

ticket_id AUTO_INCREMENT


Common Mistakes

  • "A candidate key is the super key with the fewest attributes." No — it's a super key with no redundant attribute. Several candidate keys of different sizes can exist.

  • "A primary key must be a single column." It can be composite.

  • "A foreign key must reference a primary key." In SQL it can reference any UNIQUE key too (though referencing the primary key is the norm).

  • "A foreign key can't be NULL." It can, unless you declare it NOT NULL.

  • Deciding keys from sample data. Data can only disprove a key.

  • Forgetting the empty/whole cases when counting. The set of all attributes is always a super key; the empty set is never one.


Interview and Exam Questions

What is the difference between a super key and a candidate key?

A super key is any set of attributes that uniquely identifies tuples. A candidate key is a minimal super key — removing any attribute from it destroys uniqueness. Every candidate key is a super key, but not vice versa.

Primary key vs unique key?

A table has at most one primary key and it can't contain NULL. It can have many unique keys, and a unique column can contain NULL (in MySQL, multiple NULLs). The primary key is the main identifier and the usual target of foreign keys.

Can a table have more than one primary key? More than one candidate key?

Only one primary key (possibly composite), but any number of candidate keys.

Can a foreign key refer to the same table? Give an example.

Yes, a self-referencing foreign key. employees.manager_id references employees.emp_id, since a manager is also an employee.

R(A, B, C, D, E) has candidate key {A, B}. How many super keys?

25−2 = 23 = 8.

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

Containing A: 23 = 8. Containing BC: 22 = 4. Containing ABC: 21 = 2. Total = 8 + 4 − 2 = 10.

What is a prime attribute?

An attribute that belongs to at least one candidate key. Attributes that belong to no candidate key are non-prime.

Why would you use a surrogate key?

Natural keys may change, be long or composite, or be sensitive. A surrogate key is short, stable and meaningless. You should still keep a UNIQUE constraint on the natural key.


Summary

  • Super key: uniquely identifies tuples. Candidate key: minimal super key. Primary key: the chosen candidate key (unique, not NULL). Alternate keys: the remaining candidate keys.

  • Composite key: two or more attributes. Unique key: SQL constraint that allows NULLs. Surrogate key: system-generated id.

  • Foreign key: references a key of another (or the same) table; can be NULL; enforces referential integrity.

  • Keys are properties of the schema, not of today's data.

  • Super keys with one candidate key of size k: 2n−k; with two, use inclusion–exclusion.

Keys are one kind of rule a database enforces. In Integrity Constraints we'll look at all of them together — domain, entity, key and referential integrity — and see exactly how MySQL reacts when each is violated.