Keys: Super, Candidate, Primary, Foreign & Alternate

By the end of this lesson you will be able to look at any table and name its super keys, candidate keys, primary key, alternate keys and foreign keys. You will also be able to count super keys quickly, which is a favourite GATE question.

A key is a set of one or more attributes that identifies a tuple, or links one table to another. Keys are what make a relational database trustworthy. Without them, two rows can look identical and nobody can tell which one is the real Aarav.

Why we need keys

Think of the Indian Railways PNR number. Thousands of passengers may be called "Rohan Mehta", travelling on the same day, even on the same train. The PNR is different for every booking, so the railway can always find the right ticket. In a database, a key plays the role of the PNR.

We will use one relation for the whole lesson:

students(roll_no, aadhaar_no, email, name, branch, dept_id)

In this college, each student has a unique roll number, a unique Aadhaar number and a unique college email. Names and branches repeat.

Super key

A super key is any set of attributes whose values are different for every tuple. If you know the values of a super key, you can point to exactly one row.

All of these are super keys of students:

• {roll_no}
• {roll_no, name}
• {email, branch}
• {roll_no, aadhaar_no, email, name, branch, dept_id} (all attributes together are always a super key)

{name, branch} is not a super key, because two CSE students can both be called Priya.

A super key may carry extra attributes that are not needed. {roll_no, name} identifies a student, but so does roll_no alone. The name part is extra baggage.

Candidate key

A candidate key is a minimal super key: remove any attribute from it and it stops being a super key. In other words, it has no extra baggage.

For students, the candidate keys are:

• {roll_no}
• {aadhaar_no}
• {email}

{roll_no, name} is a super key but not a candidate key, because you can drop name and still identify the student.

A candidate key can have more than one attribute. Then it is called a composite key. In an enrolments(roll_no, course_code, grade) relation, one student takes many courses and one course has many students. Only the pair {roll_no, course_code} is unique, so the pair is the candidate key.

Primary key and alternate keys

The designer picks one candidate key to be the primary key: the main identifier that other tables will refer to. The candidate keys that were not chosen become alternate keys.

How do you choose? Prefer a key that is short, never NULL, and never changes. An email can change when a student asks for a new one. Aadhaar is sensitive personal data you would not want copied into every other table. The roll number is short, stable and harmless, so it wins.

A primary key may not contain NULL. Alternate keys are declared with UNIQUE in SQL, so the DBMS still prevents duplicates in them.

Step 1: declare the keys in SQL. Run this and you should see the two students back.

CREATE TABLE students (
  roll_no INTEGER PRIMARY KEY,
  aadhaar_no VARCHAR(12) NOT NULL UNIQUE,
  email VARCHAR(80) NOT NULL UNIQUE,
  name VARCHAR(40) NOT NULL,
  branch VARCHAR(10) NOT NULL
);

INSERT INTO students (roll_no, aadhaar_no, email, name, branch) VALUES
  (101, '111122223333', 'priya.101@college.example', 'Priya', 'CSE'),
  (102, '444455556666', 'priya.102@college.example', 'Priya', 'CSE');

SELECT roll_no, email, name, branch FROM students;

roll_no | email                     | name  | branch
--------+---------------------------+-------+-------
101     | priya.101@college.example | Priya | CSE
102     | priya.102@college.example | Priya | CSE
(2 rows)

Two students share the same name and branch, which proves {name, branch} cannot be a key. The rows stay different because roll_no, aadhaar_no and email differ.

Step 2: see the DBMS protect a key. If you insert a third student with roll number 101 again, MySQL refuses:

INSERT INTO students (roll_no, aadhaar_no, email, name, branch)
VALUES (101, '777788889999', 'kabir@college.example', 'Kabir', 'ME');

ERROR 1062 (23000): Duplicate entry '101' for key 'students.PRIMARY'

Try the same insert in the editor and SQLite also refuses it, with its own message about a UNIQUE constraint.

Foreign key

A foreign key is an attribute (or set of attributes) in one table whose values must match a key in another table. It is how tables point to each other.

departments(dept_id, dept_name)          students(roll_no, name, dept_id)
            -------                                 -------        |
               ^                                                   |
               +------------- foreign key references --------------+

students.dept_id is a foreign key that references departments.dept_id. The table holding the foreign key is the referencing (child) table. The table it points to is the referenced (parent) table. Every non-NULL dept_id in students must exist in departments. A foreign key does not have to be unique: many students share one department.

Step 3: join the two tables through the foreign key. You should see each student with the full department name.

CREATE TABLE departments (
  dept_id INTEGER PRIMARY KEY,
  dept_name VARCHAR(60) NOT NULL UNIQUE
);

CREATE TABLE students (
  roll_no INTEGER PRIMARY KEY,
  name VARCHAR(40) NOT NULL,
  dept_id INTEGER NOT NULL,
  FOREIGN KEY (dept_id) REFERENCES departments (dept_id)
);

INSERT INTO departments (dept_id, dept_name) VALUES
  (1, 'Computer Science'), (2, 'Electronics'), (3, 'Mechanical');

INSERT INTO students (roll_no, name, dept_id) VALUES
  (101, 'Aarav', 1), (102, 'Meera', 1), (103, 'Farhan', 2);

SELECT s.roll_no, s.name, d.dept_name
FROM students s
JOIN departments d ON d.dept_id = s.dept_id
ORDER BY s.roll_no;

roll_no | name   | dept_name
--------+--------+-----------------
101     | Aarav  | Computer Science
102     | Meera  | Computer Science
103     | Farhan | Electronics
(3 rows)

What happens if a row points to a department that does not exist is the job of referential integrity, covered in Integrity Constraints. SQL syntax for all these keys is in Constraints & Keys.

Natural and surrogate keys

A natural key comes from the real world, such as Aadhaar number or vehicle registration number. A surrogate key is an invented number with no meaning outside the database, such as an auto-generated student_id. Many designers use a surrogate primary key and keep natural keys as alternate keys with UNIQUE. The surrogate never changes, even when the real-world value does.

Advanced: counting super keys (GATE)

GATE often asks: "How many super keys does R have?" Use this reasoning.

A set of attributes is a super key exactly when it contains at least one candidate key. So fix the candidate key, and every other attribute may be either in or out.

1. One candidate key with k attributes, relation with n attributes: the remaining n − k attributes are each in or out, so there are 2^(n − k) super keys.
2. Two candidate keys K1 and K2: count super keys containing K1, add those containing K2, then subtract those containing both (they were counted twice). The ones containing both must contain K1 ∪ K2.

Count = 2^(n - |K1|) + 2^(n - |K2|) - 2^(n - |K1 U K2|)

Example 1: R(A, B, C, D), candidate key {A}
           2^(4-1) = 8 super keys

Example 2: R(A, B, C, D, E), candidate keys {A} and {B}
           2^4 + 2^4 - 2^3 = 16 + 16 - 8 = 24

Example 3: R(A, B, C, D, E), candidate keys {A, B} and {C, D}
           2^3 + 2^3 - 2^1 = 8 + 8 - 2 = 14

Example 4: R(A, B, C, D), candidate keys {A} and {B, C}
           2^3 + 2^2 - 2^1 = 8 + 4 - 2 = 10

For three candidate keys, extend the same idea with inclusion and exclusion: add the three singles, subtract the three pairs, add back the triple.

Common mistakes

• Calling every unique-looking column a key. A key comes from the meaning of the data, not from today's rows. Ten students may have different names today, but names are not a key.
• Forgetting minimality. {roll_no, name} is a super key, not a candidate key.
• Thinking a foreign key must be unique. It usually repeats: many students, one department.
• Choosing a primary key that can change or be NULL. Phone numbers and emails change; pick something stable.

Key points

• A super key is any attribute set that uniquely identifies tuples.
• A candidate key is a minimal super key; a composite key has more than one attribute.
• The primary key is the chosen candidate key; the others are alternate keys, declared UNIQUE in SQL.
• A foreign key in a child table must match a key value in the parent table, or be NULL if allowed.
• With one candidate key of k attributes in n, there are 2^(n − k) super keys; use inclusion and exclusion for more keys.

CREATE TABLE rooms (
  hostel_code VARCHAR(5) NOT NULL,
  room_no INTEGER NOT NULL,
  floor INTEGER NOT NULL,
  warden_phone VARCHAR(15),
  PRIMARY KEY (hostel_code, room_no)
);