Keys: super, candidate, primary, alternate, foreign

A key is a set of attributes whose values pick out exactly one tuple of a relation. Any set of attributes that does this is a superkey. A superkey from which no attribute can be removed without losing that property is a candidate key. The designer chooses one candidate key as the primary key, and the candidates not chosen are the alternate keys. A foreign key is different in kind: it is a set of attributes in one relation whose values must match a key of another relation (or of the same one), and it is how relations refer to each other. This lesson defines each kind with one running example, counts superkeys with two short rules checked by a program, and then turns to the practical choice every schema faces: a natural key from the real world, or a surrogate key such as an identity column, a UUIDv4 or a UUIDv7.

Superkeys and candidate keys

Take student(roll_no, email, name, programme), where the college’s rules say that no two students share a roll number and no two share an email address. A superkey is any set of attributes whose values no two tuples can share in any instance the rules allow. {roll_no} is a superkey, and so is {roll_no, name}: if roll numbers never repeat, a roll number together with a name never repeats either. Every relation has at least one superkey, the set of all its attributes, because a relation never contains the same tuple twice.

A key is a rule about every instance the database may ever hold, not a fact about the rows that happen to be there. Data can prove that a set of attributes is not a key, with two rows that agree on it, but no amount of data can prove that it is one:

"""Which attribute sets are unique in one instance of student? Data can rule a key out, never prove one."""
from itertools import combinations

ATTRIBUTES = ("roll_no", "email", "name", "programme")
rows = [
    (101, "asha@uni.example", "Asha", "BTech"),
    (102, "bilal@uni.example", "Bilal", "MSc"),
    (103, "chitra@uni.example", "Chitra", "BTech"),
    (104, "dev@uni.example", "Dev", "PhD"),
]


def unique_sets(rows):
    """The minimal attribute sets whose values no two rows share."""
    found = []
    for size in range(1, len(ATTRIBUTES) + 1):
        for names in combinations(range(len(ATTRIBUTES)), size):
            if any(set(names) >= set(smaller) for smaller in found):
                continue  # a smaller unique set is inside it: not minimal
            values = [tuple(row[i] for i in names) for row in rows]
            if len(set(values)) == len(rows):
                found.append(names)
    return [{ATTRIBUTES[i] for i in names} for names in found]


def show(label, rows):
    print(label)
    for s in unique_sets(rows):
        print("   ", "{" + ", ".join(sorted(s)) + "}")


show("Unique in the first 4 rows:", rows)
rows.append((105, "dev.k@uni.example", "Dev", "MSc"))
show("After a second student called Dev joins:", rows)

Unique in the first 4 rows:
    {roll_no}
    {email}
    {name}
After a second student called Dev joins:
    {roll_no}
    {email}
    {name, programme}

With four students, {name} is unique, so the data alone would accept it as a key. One more student called Dev breaks it. The program then reports {name, programme} as unique, which is just as accidental. Only the rules about the real world, here the college’s promise about roll numbers and email addresses, can say which sets are keys.

A candidate key is a superkey with nothing to spare: remove any attribute and it stops being a superkey. {roll_no} and {email} are the candidate keys of student; {roll_no, name} is a superkey but not a candidate, because it still works without name. Codd’s 1970 paper called such a key “nonredundant”: in a combination of domains, no single one may be “superfluous in uniquely identifying each element”. Minimal is not the same as smallest. In exam_seat(hall, seat, roll_no), where each seat of each hall holds one student and each student sits once, both {hall, seat} and {roll_no} are candidate keys, of two sizes, and neither contains the other.

An attribute that belongs to at least one candidate key is a prime attribute; the others are non-prime. In exam_seat, all three attributes are prime. The distinction matters in the normal forms, which are defined in terms of how non-prime attributes depend on the keys.

Primary, alternate and foreign keys

When a relation has several candidate keys, one of them becomes the primary key. Codd wrote that “one of them is arbitrarily selected and called the primary key”; in practice the choice goes to the key that is short, never changes and is never missing. Entity integrity from the previous lesson applies to it: no part of a primary key may be NULL.

The other candidate keys are the alternate keys, and they are still keys. Declare each one UNIQUE NOT NULL, or the database does not know about it: without UNIQUE it accepts two students with one email address, and with UNIQUE alone it accepts any number of students with no email at all, because NULLs are not equal to each other.

A foreign key connects two relations. Codd defined it as a domain or combination of domains of R that is not the primary key of R but whose values are values of the primary key of some relation S, adding that S and R may be the same relation. Three consequences are easy to miss:

• A foreign key is not a key of its own relation. One student has many enrolments, so roll_no repeats in enrolment as often as needed.
• It must refer to a key. PostgreSQL requires the referenced columns to be a primary key, a unique constraint or a non-partial unique index, and SQLite likewise needs the parent columns to be the primary key or collectively unique.
• It may refer to its own table, as manager_id in an employee table refers to employee(emp_id).

Here are the three kinds of key declared in SQLite, with one insert that breaks each:

PRAGMA foreign_keys = ON;   -- SQLite checks foreign keys only after this, on every connection

CREATE TABLE department (dept_id INTEGER PRIMARY KEY, name TEXT NOT NULL UNIQUE);
CREATE TABLE student (
  roll_no INTEGER PRIMARY KEY,                                 -- the primary key
  email   TEXT NOT NULL UNIQUE,                                -- an alternate key
  name    TEXT NOT NULL,
  dept_id INTEGER NOT NULL REFERENCES department (dept_id)     -- a foreign key
);
INSERT INTO department VALUES (1, 'Computer Science'), (2, 'Physics');
INSERT INTO student VALUES (101, 'asha@uni.example', 'Asha', 1);

INSERT INTO student VALUES (101, 'asha.r@uni.example', 'Asha R', 2);  -- same primary key
INSERT INTO student VALUES (102, 'asha@uni.example', 'Asha K', 2);    -- same alternate key
INSERT INTO student VALUES (103, 'chitra@uni.example', 'Chitra', 9);  -- no department 9
INSERT INTO student VALUES (104, 'dev@uni.example', 'Dev', 1);        -- a foreign key value may repeat

SELECT s.roll_no, s.name, d.name AS department
FROM student AS s JOIN department AS d ON d.dept_id = s.dept_id
ORDER BY s.roll_no;

┌─────────┬──────┬──────────────────┐
│ roll_no │ name │    department    │
├─────────┼──────┼──────────────────┤
│ 101     │ Asha │ Computer Science │
│ 104     │ Dev  │ Computer Science │
└─────────┴──────┴──────────────────┘

Runtime error near line 13: UNIQUE constraint failed: student.roll_no
Runtime error near line 14: UNIQUE constraint failed: student.email
Runtime error near line 15: FOREIGN KEY constraint failed

The primary key refused a second 101, the alternate key refused a second asha@uni.example, and the foreign key refused a student in department 9, which does not exist. Dev’s row shares a department with Asha’s and is accepted: foreign key values may repeat. Note the first line of the script. SQLite checks foreign keys only after PRAGMA foreign_keys = ON, on every connection; the next lesson shows what happens without it.

You will meet a few more names. A composite or compound key has several attributes, such as {hall, seat}. A natural key comes from the real world and a surrogate key is made up by the system; the last two sections are about choosing between them. “Secondary key” is used both for alternate keys and for any indexed attribute, so say which one you mean.

Counting superkeys

Questions such as “how many superkeys does this relation have?” test whether the definitions are clear, and two rules answer them.

One candidate key. Let R have n attributes and a single candidate key of k attributes. A superkey must contain those k attributes, and each of the other n − k attributes can be in it or not, so there are 2^n−k superkeys. R(A, B, C, D) with the key {A} has 2³ = 8.

Several candidate keys. A set is a superkey if it contains at least one candidate key, so the count is the size of a union, and inclusion–exclusion gives it. For two keys K₁ and K₂:

• add the supersets of each key: 2^n−|K₁| + 2^n−|K₂|;
• subtract the sets counted twice, the supersets of both, which are the supersets of K₁ ∪ K₂: 2^{n−|K₁ ∪ K₂|}.

For R(A, B, C, D) with the keys {A} and {B} that is 8 + 8 − 4 = 12. Counting the other way round gives the same answer and is often quicker: R has 2⁴ = 16 attribute sets, and the sets that contain neither A nor B are the four subsets of {C, D}, so 16 − 4 = 12. Overlapping keys work the same way. With {A, B} and {B, C}, the union is {A, B, C}, so the count is 4 + 4 − 2 = 6. For three or more keys the pattern continues: add the terms for single keys, subtract those for every pair, add those for every triple, always with 2 raised to n minus the size of the union.

The usual mistake is to stop after the first step and add the counts for each key; with the keys {A} and {B} that gives 16 instead of 12. This program counts both ways, by checking every attribute set and by the formula, for four worked cases and then for 500 random relations:

"""Count superkeys two ways, by checking every attribute set and by the counting rules, and compare them."""
import random
from itertools import combinations


def by_brute_force(attributes, keys):
    """Every subset of the attributes that contains at least one candidate key."""
    count = 0
    for size in range(len(attributes) + 1):
        for subset in combinations(attributes, size):
            if any(key <= set(subset) for key in keys):
                count += 1
    return count


def by_formula(attributes, keys):
    """Inclusion-exclusion: add 2^(n - |K|) for each key, subtract the sets counted twice, and so on."""
    n = len(attributes)
    total = 0
    for r in range(1, len(keys) + 1):
        for group in combinations(keys, r):
            union = set().union(*group)
            total += (-1) ** (r + 1) * 2 ** (n - len(union))
    return total


for attributes, keys in [("ABCD", ["A"]), ("ABCD", ["A", "B"]), ("ABCD", ["AB", "BC"]), ("ABCDEF", ["AB", "CD", "EF"])]:
    key_sets = [set(k) for k in keys]
    print(f"R({','.join(attributes)}) with keys {', '.join(keys)}: "
          f"{by_brute_force(attributes, key_sets)} by checking, {by_formula(attributes, key_sets)} by formula")

rng = random.Random(42)
agree = 0
for _ in range(500):
    n = rng.randint(1, 8)
    attributes = "ABCDEFGH"[:n]
    keys = [set(rng.sample(attributes, rng.randint(1, n))) for _ in range(rng.randint(1, 3))]
    agree += by_brute_force(attributes, keys) == by_formula(attributes, keys)
print(f"500 random schemas of 1 to 8 attributes with 1 to 3 keys: the two counts agree in {agree} of 500")

R(A,B,C,D) with keys A: 8 by checking, 8 by formula
R(A,B,C,D) with keys A, B: 12 by checking, 12 by formula
R(A,B,C,D) with keys AB, BC: 6 by checking, 6 by formula
R(A,B,C,D,E,F) with keys AB, CD, EF: 37 by checking, 37 by formula
500 random schemas of 1 to 8 attributes with 1 to 3 keys: the two counts agree in 500 of 500

The brute-force count checks all 2ⁿ attribute sets, which is quick for the eight attributes or fewer used here but doubles with every attribute; the formula needs one term per group of keys instead. In R(A, B, C, D, E, F) with the keys AB, CD and EF, 37 of the 64 attribute sets are superkeys.

Natural keys and surrogate keys

A natural key is an identifier that exists outside the database: an ISBN for a book, an email address for a user, a two-letter ISO country code. It means something to people and is unique without any help from you. A surrogate key is a value the system makes up, usually a number or a UUID, that means nothing and therefore never needs to change. Natural keys have three common weaknesses. They change: people change their email addresses. They get reused: a phone number that is given up is later issued to someone else. And they can be long, composite or personal data that should not be copied into every table that refers to them.

Most schemas use a surrogate as the primary key and keep the natural key as an alternate key. PostgreSQL makes an identity column with GENERATED ALWAYS AS IDENTITY; its documentation explains that such a column takes its values from an implicit sequence, is implicitly NOT NULL, and rejects a value you supply unless the INSERT says OVERRIDING SYSTEM VALUE. In SQLite, a column declared exactly INTEGER PRIMARY KEY becomes another name for the row’s built-in rowid, and a type such as INT or BIGINT does not do this. The surrogate does not replace the natural key’s rule, though:

-- A surrogate key alone: the same book can be stored twice under two ids.
CREATE TABLE book (book_id INTEGER PRIMARY KEY, isbn TEXT NOT NULL, title TEXT NOT NULL);
INSERT INTO book (isbn, title) VALUES ('978-0-00-000000-2', 'Database Systems');
INSERT INTO book (isbn, title) VALUES ('978-0-00-000000-2', 'Database Systems');
SELECT book_id, isbn FROM book;

-- Keep the surrogate key for joins, and declare the natural key UNIQUE as well.
CREATE TABLE book2 (book_id INTEGER PRIMARY KEY, isbn TEXT NOT NULL UNIQUE, title TEXT NOT NULL);
INSERT INTO book2 (isbn, title) VALUES ('978-0-00-000000-2', 'Database Systems');
INSERT INTO book2 (isbn, title) VALUES ('978-0-00-000000-2', 'Database Systems');
SELECT book_id, isbn FROM book2;

┌─────────┬───────────────────┐
│ book_id │       isbn        │
├─────────┼───────────────────┤
│ 1       │ 978-0-00-000000-2 │
│ 2       │ 978-0-00-000000-2 │
└─────────┴───────────────────┘
┌─────────┬───────────────────┐
│ book_id │       isbn        │
├─────────┼───────────────────┤
│ 1       │ 978-0-00-000000-2 │
└─────────┴───────────────────┘

Runtime error near line 10: UNIQUE constraint failed: book2.isbn

The first table stored the same ISBN twice, under the ids 1 and 2, and nothing in it can say which row is the real book. The second table keeps the surrogate for joins and declares the ISBN UNIQUE, so the copy is refused.

Surrogate values have quirks of their own. Without AUTOINCREMENT, SQLite’s documentation says a new row normally gets one more than the largest rowid in the table at that moment, so deleting the newest row can hand its id to the next one:

-- INTEGER PRIMARY KEY: a new row gets one more than the largest id in the table now.
CREATE TABLE ticket (ticket_id INTEGER PRIMARY KEY, subject TEXT);
INSERT INTO ticket (subject) VALUES ('Login fails'), ('Wrong invoice'), ('Refund');
DELETE FROM ticket WHERE ticket_id = 3;
INSERT INTO ticket (subject) VALUES ('Password reset');
SELECT ticket_id, subject FROM ticket;

-- AUTOINCREMENT: never reuses an id that has existed, at the cost of a bookkeeping table.
CREATE TABLE ticket2 (ticket_id INTEGER PRIMARY KEY AUTOINCREMENT, subject TEXT);
INSERT INTO ticket2 (subject) VALUES ('Login fails'), ('Wrong invoice'), ('Refund');
DELETE FROM ticket2 WHERE ticket_id = 3;
INSERT INTO ticket2 (subject) VALUES ('Password reset');
SELECT ticket_id, subject FROM ticket2;
SELECT name, seq FROM sqlite_sequence;

┌───────────┬────────────────┐
│ ticket_id │    subject     │
├───────────┼────────────────┤
│ 1         │ Login fails    │
│ 2         │ Wrong invoice  │
│ 3         │ Password reset │
└───────────┴────────────────┘
┌───────────┬────────────────┐
│ ticket_id │    subject     │
├───────────┼────────────────┤
│ 1         │ Login fails    │
│ 2         │ Wrong invoice  │
│ 4         │ Password reset │
└───────────┴────────────────┘
┌─────────┬─────┐
│  name   │ seq │
├─────────┼─────┤
│ ticket2 │ 4   │
└─────────┴─────┘

Ticket 3 was deleted and the next ticket became 3 again, which would confuse anyone holding the old ticket number. With AUTOINCREMENT, SQLite records the largest id ever used in its table sqlite_sequence and moves on to 4. The documentation also advises against AUTOINCREMENT unless it is really needed, because the bookkeeping costs CPU time, memory, disk space and disk I/O, so use it only when ids must never come back. And any counter tells its readers something: an order number of 10,452 suggests how many orders came before it.

UUIDs as keys: version 4 or version 7

A UUID is a 128-bit identifier defined by RFC 9562. Any program can make one without asking a central sequence, so an app server, a phone or an offline client can create rows with their final keys, and data from several databases can be merged without clashes. Two versions matter for keys. UUIDv4 is random: 122 of its bits are random and the rest say which version and variant it is. UUIDv7 begins with a 48-bit count of milliseconds since the start of 1970, followed by random bits, so UUIDv7 values made later sort later.

That ordering matters for indexes. RFC 9562 notes that UUID versions which are not time-ordered, such as UUIDv4, “have poor database-index locality”: each new key lands at a random place in the index. A B-tree index keeps its keys in order across pages, and a page that fills up is split into two half-full pages. When every new key is the largest so far, it goes to the rightmost page and earlier pages stay full; PostgreSQL even fills a B-tree page only to its fillfactor, 90 % by default, when it extends the index at the right, to leave room for later updates. Random keys split pages all over the index instead. Measured on PostgreSQL 18.6, a primary-key index on 100,000 rows filled by INSERT … SELECT FROM generate_series(1, 100000) took about 4.45 MB with gen_random_uuid() keys, 3.18 MB with uuidv7() keys and 2.26 MB with a bigint identity column (sizes from pg_relation_size).

SQLite stores an ordinary table as a B-tree ordered by its rowid, and a WITHOUT ROWID table as a B-tree ordered by its primary key, so you can run the same experiment in the browser:

-- The same 100,000 keys inserted twice, once in ascending order and once in a shuffled order, into an ordinary
-- rowid table and into a WITHOUT ROWID table keyed by 16-byte values, the size of a UUID. Only the order differs.
CREATE TABLE rowid_ascending (id INTEGER PRIMARY KEY, payload BLOB);
CREATE TABLE rowid_shuffled  (id INTEGER PRIMARY KEY, payload BLOB);
CREATE TABLE blob16_ascending (id BLOB PRIMARY KEY, n INTEGER) WITHOUT ROWID;
CREATE TABLE blob16_shuffled  (id BLOB PRIMARY KEY, n INTEGER) WITHOUT ROWID;

-- The shuffle: a Lehmer generator, x(k+1) = 48271 * x(k) mod (2^31 - 1), gives each row a pseudo-random sort key.
CREATE TEMP TABLE source AS
WITH RECURSIVE lcg(n, x) AS (
  SELECT 1, 48271 UNION ALL SELECT n + 1, (x * 48271) % 2147483647 FROM lcg WHERE n < 100000)
SELECT n, x AS shuffle, unhex(printf('%012x%020x', 1760000000000 + n, n)) AS key16 FROM lcg;

CREATE TEMP TABLE size_log (step TEXT, pages INTEGER);
INSERT INTO size_log SELECT 'before', page_count FROM pragma_page_count();
INSERT INTO rowid_ascending SELECT n, zeroblob(16) FROM source ORDER BY n;
INSERT INTO size_log SELECT 'rowid table, ascending order', page_count FROM pragma_page_count();
INSERT INTO rowid_shuffled SELECT n, zeroblob(16) FROM source ORDER BY shuffle;
INSERT INTO size_log SELECT 'rowid table, shuffled order', page_count FROM pragma_page_count();
INSERT INTO blob16_ascending SELECT key16, n FROM source ORDER BY n;
INSERT INTO size_log SELECT 'WITHOUT ROWID, ascending order', page_count FROM pragma_page_count();
INSERT INTO blob16_shuffled SELECT key16, n FROM source ORDER BY shuffle;
INSERT INTO size_log SELECT 'WITHOUT ROWID, shuffled order', page_count FROM pragma_page_count();

-- Pages of 4,096 bytes that each table took.
SELECT now.step, now.pages - prev.pages AS pages_added
FROM size_log AS prev JOIN size_log AS now ON now.rowid = prev.rowid + 1;

┌────────────────────────────────┬─────────────┐
│              step              │ pages_added │
├────────────────────────────────┼─────────────┤
│ rowid table, ascending order   │ 612         │
│ rowid table, shuffled order    │ 672         │
│ WITHOUT ROWID, ascending order │ 691         │
│ WITHOUT ROWID, shuffled order  │ 666         │
└────────────────────────────────┴─────────────┘

The keys and the rows are identical in each pair; only the order of the inserts differs. In the ordinary table the 100,000 keys took 612 pages of 4,096 bytes when inserted in ascending order and 672 when shuffled, about 10 % more: the extra pages are empty space left inside pages by splits. The WITHOUT ROWID table, keyed by 16-byte values the size of a UUID, shows the opposite: 691 pages for the ascending order and 666 for the shuffled one. How much key order saves depends on how an engine fills and splits its pages, so measure on the engine you use before you trust a rule of thumb.

PostgreSQL 18 added uuidv7(), and its release notes call the value “temporally sortable”; gen_random_uuid() and the new alias uuidv4() make version 4 values, and uuid_extract_timestamp() reads the time back out of a version 7 value. Python 3.14 added uuid.uuid7() too:

"""UUIDv7 sorts by creation time and carries that time; UUIDv4 is random (Python 3.14's uuid module)."""
import datetime
import uuid

v7 = [uuid.uuid7() for _ in range(1000)]
v4 = [uuid.uuid4() for _ in range(1000)]
print("1,000 UUIDv7 values, made one after another, already in sorted order:", v7 == sorted(v7))
print("1,000 UUIDv4 values, made one after another, already in sorted order:", v4 == sorted(v4))

# The sample UUIDv7 from PostgreSQL 18's documentation of uuidv7().
sample = uuid.UUID("019535d9-3df7-79fb-b466-fa907fa17f9e")
print("version:", sample.version)
print("first 48 bits as a number of milliseconds:", sample.time)
created = datetime.datetime.fromtimestamp(sample.time / 1000, tz=datetime.UTC)
print("created at (UTC):", created.isoformat(timespec="milliseconds"))

1,000 UUIDv7 values, made one after another, already in sorted order: True
1,000 UUIDv4 values, made one after another, already in sorted order: False
version: 7
first 48 bits as a number of milliseconds: 1740365184503
created at (UTC): 2025-02-24T02:46:24.503+00:00

A thousand UUIDv7 values made one after another were already sorted, and the version 4 values were not. The last lines decode the sample UUIDv7 from PostgreSQL’s documentation and print the moment it was made, to the millisecond. That is the privacy cost of UUIDv7: anyone who sees the key can read when the row was created. RFC 9562 calls embedded timestamps “a very small attack surface” that signals the order of creation, recommends UUIDv4 for any security-related use, and forbids using a UUID as a security capability: a value that gives access to whoever holds it. A secret link still needs a random token of its own.

Four kinds of primary key compared:

• Identity column: 8 bytes as bigint, made by the database in order, so new keys go to the right end of the index. It hints at how many rows came before, and every row must get its number from one place. Choose it when one database creates every row.
• UUIDv4: 16 bytes that any program can make without coordination. New keys land anywhere in the index and split pages all over it, so indexes grow larger and slower, but the key reveals nothing. Choose it for keys made on many machines, or for ids that must not hint at anything.
• UUIDv7: 16 bytes that any program can make without coordination, landing near the right end of the index. The key reveals the millisecond it was made. Choose it for keys made on many machines when that time may be public.
• Natural key: as long as the identifier is, made by the outside world, and as revealing as its meaning. Its risk is change or reuse in the real world. Choose it only for a stable, short identifier that you would declare UNIQUE anyway.

Interview questions

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

A superkey is any set of attributes whose values never repeat across the tuples of a relation, in every instance the rules allow, so it identifies each tuple. A candidate key is a minimal superkey: removing any one of its attributes would let two tuples share the remaining values. In student(roll_no, email, name), if roll numbers and emails are both unique, {roll_no, name} is a superkey but not a candidate key, because {roll_no} alone already works; {roll_no} and {email} are the candidate keys. Every candidate key is a superkey, and every superkey contains at least one candidate key. One candidate key is chosen as the primary key; the others become alternate keys.

Key takeaways

• A superkey identifies every tuple; a candidate key is a superkey with no attribute to spare; minimal is not the same as smallest.
• Keys are rules about every allowed instance. Data can refute a key with two matching rows but can never prove one.
• The primary key is the candidate chosen; declare every alternate key UNIQUE NOT NULL so the database enforces it.
• A foreign key refers to a primary key or UNIQUE columns; its values may repeat and it may refer to its own table.
• One key of k attributes in n gives 2^n−k superkeys; for several keys, use inclusion–exclusion or count the sets that contain no key and subtract.
• A surrogate primary key still needs the natural key declared UNIQUE, or duplicates of real things slip in.
• Identity columns are compact and ordered but reveal counts; UUIDv4 reveals nothing but scatters index inserts; UUIDv7 keeps inserts ordered but reveals creation times.