Identifying Keys — Identify primary keys and foreign keys...

SECTION 1

Historical Context & Motivation

Before relational databases existed, data was stored in flat files and hierarchical or network models that made cross-referencing records brittle and error-prone. A programmer who wanted to link a customer to their orders had to hard-code pointer chains or navigate complex record-level associations, and any structural change could cascade through the entire codebase. The concept of keys emerged as a principled solution to this problem: a declarative mechanism for uniquely identifying rows and establishing reliable links between tables. The journey from ad-hoc file systems to the rigorous relational algebra we use today was driven by a handful of seminal contributions that shaped how we think about data integrity.

1970

Codd's Relational Model

Edgar F. Codd published "A Relational Model of Data for Large Shared Data Banks" at IBM, introducing the idea that data should be organized into relations (tables) with tuples (rows) uniquely identified by key attributes. This paper laid the mathematical foundation for primary keys.

1974

System R & SEQUEL

IBM's System R prototype implemented Codd's ideas with the SEQUEL query language (later renamed SQL). The prototype enforced primary key uniqueness at the storage-engine level, proving that declarative key constraints were practical.

1979

Oracle V2 & Commercial Adoption

Oracle released the first commercially available SQL-based RDBMS, bringing primary key and foreign key concepts into production enterprise systems. Referential integrity became a selling point for data reliability.

1986

SQL-86 Standard (ANSI/ISO)

The first ANSI SQL standard formalized PRIMARY KEY and FOREIGN KEY syntax as part of the Data Definition Language (DDL), ensuring portability of key constraints across vendors.

1992

SQL-92 & Cascading Actions

The SQL-92 standard expanded foreign key semantics with ON DELETE CASCADE and ON UPDATE CASCADE, giving database architects fine-grained control over how referential integrity violations are resolved.

The core question that motivated all of this work remains central today: how do you guarantee that every record in a database is uniquely addressable, and that relationships between records remain consistent as data changes? Primary keys and foreign keys are the answer that the relational model provides, and understanding them conceptually is a prerequisite for designing sound schemas.

SECTION 2

Core Principles & Definitions

At its heart, the relational model treats a database as a collection of relations (tables), where each relation has a heading (a set of attribute names and types) and a body (a set of tuples). To manipulate data reliably, we need two guarantees: every tuple must be distinguishable from every other tuple in the same relation, and a tuple in one relation that references a tuple in another relation must point to something that actually exists. These guarantees are enforced by primary keys and foreign keys, respectively.

Candidate Key

Any minimal set of attributes whose values are guaranteed to be unique across all tuples in a relation. A relation may have multiple candidate keys; one is chosen as the primary key.

Primary Key (PK)

The candidate key selected as the principal identifier for a relation. It must be unique and NOT NULL for every row. Most implementations also create a clustered index on the primary key.

Foreign Key (FK)

An attribute (or set of attributes) in one relation whose values must match the primary key (or a unique key) of another relation. Foreign keys enforce referential integrity — no orphan references allowed.

Referential Integrity

The guarantee that for every foreign key value in a child table, a matching primary key value exists in the referenced parent table. Violations are rejected at the database engine level.

Surrogate vs. Natural Key

A natural key uses real-world attributes (e.g., SSN, ISBN). A surrogate key is a system-generated identifier (e.g., auto-increment integer or UUID) with no business meaning.

✦ KEY TAKEAWAY

Think of a primary key like a student ID card at a university. Every student receives a unique ID number — no two students share the same one, and every student must have one. A foreign key is like writing that student's ID number on a library checkout slip: the library doesn't create its own identity for the student, but references the existing one. If the university removed a student record while the library still listed that ID, you'd have an orphan reference — exactly the kind of inconsistency that foreign key constraints prevent.

SECTION 3

Visual Explanation — Table Relationships

The following diagram illustrates two relations — students and enrollments — and the key constraints that bind them. The primary key column in each table is marked with a key icon, while the foreign key in the child table is connected by an arrow to the primary key it references in the parent table.

The dashed pink arrow from enrollments.student_id to students.student_id represents the foreign key constraint. Every value in the FK column must match an existing PK value in the parent table, or be NULL if the column permits it.

Notice that enrollments has its own primary key (enrollment_id), which uniquely identifies each enrollment record. The student_id column in enrollments is a foreign key — it does not need to be unique within enrollments (a student can enroll in many courses), but every value it stores must correspond to some student_id already present in students. This one-to-many cardinality — one student, many enrollments — is the most common relationship pattern in relational design.

SECTION 4

How Keys Work — Formal Properties

While keys are a conceptual construct, their properties can be stated formally. Understanding these properties helps you distinguish between candidate keys, super keys, and the chosen primary key, and it clarifies exactly what a foreign key constraint guarantees at the logical level.

Uniqueness & Minimality of Candidate Keys

UNIQUENESS CONSTRAINT

∀ t₁, t₂ ∈ R : t₁[K] = t₂[K] → t₁ = t₂

For any two tuples t₁ and t₂ in relation R, if their projections on the key attribute set K are equal, then the tuples are identical. This is the formal definition of a superkey. A candidate key is a superkey with the additional property of minimality — removing any attribute from K would violate uniqueness.

REFERENTIAL INTEGRITY CONSTRAINT

∀ t ∈ S : t[FK] IS NOT NULL → ∃ r ∈ R : r[PK] = t[FK]

For every tuple t in the referencing relation S, if the foreign key attribute FK is not null, then there must exist some tuple r in the referenced relation R whose primary key PK equals the FK value. This is the formal statement of referential integrity.

Entity Integrity Rule

Codd's entity integrity rule states that no component of a primary key may be null. The rationale is straightforward: if a primary key's purpose is to uniquely identify a tuple, then allowing nulls would make identification impossible, because NULL ≠ NULL in SQL's three-valued logic. This rule applies strictly to primary keys; other candidate keys (alternate keys) may permit nulls in some SQL implementations, though doing so is generally discouraged.

Cascading Referential Actions

When a row in the parent table is deleted or its primary key is updated, the RDBMS must decide what to do with dependent rows in child tables. SQL defines several referential actions: CASCADE propagates the change to all dependent rows; SET NULL sets the FK column to null; SET DEFAULT reverts it to a default value; RESTRICT (and its close cousin NO ACTION) rejects the operation outright. Choosing the right action depends on the domain semantics of the relationship.

SECTION 5

Classification of Keys

The terminology around keys can be confusing because multiple overlapping terms exist. The following diagram and table clarify how super keys, candidate keys, primary keys, alternate keys, and foreign keys relate to one another in a Venn-diagram–style hierarchy.

The nesting shows that every candidate key is a super key, and the primary key is a specifically designated candidate key. Foreign keys are separate — they belong to a different table and reference a primary (or unique) key rather than being one.

Comparison of relational key types and their formal properties

Key Type	Unique?	Minimal?	NOT NULL?	Cross-table?
Super Key	Yes	Not necessarily	Not required	No
Candidate Key	Yes	Yes	Not required	No
Primary Key	Yes	Yes	Yes (required)	No
Alternate Key	Yes	Yes	Varies by DBMS	No
Foreign Key	Not necessarily	N/A	Not required	Yes — references another table

🔗 Composite Keys

A key — whether primary or foreign — can consist of multiple columns. For example, an enrollments table might use the composite key (student_id, course_code, semester) as a natural primary key, meaning the combination of all three must be unique even though individual columns repeat.

SECTION 6

Worked Example — Designing Keys for a Library System

Suppose you are designing a database for a university library. The system must track books, members, and loans. Walk through the following steps to identify appropriate primary keys and foreign keys.

Library Database Key Identification

Step 1 — List the entities and their attributesIdentify the core entities: books(isbn, title, author, year_published), members(member_id, name, email, join_date), and loans(loan_id, isbn, member_id, checkout_date, return_date). Each entity becomes a table.

Step 2 — Identify candidate keys for each tableFor books, the ISBN is globally unique in the real world, so {isbn} is a candidate key. For members, {member_id} is a surrogate candidate key and {email} is a natural candidate key (assuming emails are unique). For loans, {loan_id} is a surrogate candidate key, and the composite {isbn, member_id, checkout_date} could also serve as a natural candidate key.

Step 3 — Choose primary keysSelect one candidate key per table as the primary key. For books, choose isbn (natural key, universally standardized). For members, choose member_id (surrogate, stable even if a member changes email). For loans, choose loan_id (surrogate, simpler than a three-column composite).

PKs → books(isbn), members(member_id), loans(loan_id)

Step 4 — Identify foreign keysThe loans table references both books and members. Therefore, loans.isbn is a foreign key referencing books.isbn, and loans.member_id is a foreign key referencing members.member_id.

FKs → loans(isbn) → books(isbn), loans(member_id) → members(member_id)

Step 5 — Choose referential actionsIf a book is removed from the catalog, what happens to existing loan records? If historical records matter, use ON DELETE RESTRICT to prevent deletion of a book with active loans. For member deletion, ON DELETE SET NULL might be appropriate if you want to keep anonymized loan history. These choices depend on business requirements, not purely on schema design.

ON DELETE RESTRICT for loans.isbn; ON DELETE SET NULL for loans.member_id (if anonymized history is needed)

SECTION 7

Surrogate vs. Natural Keys — Trade-offs

One of the most debated design decisions in relational databases is whether to use surrogate or natural primary keys. Both approaches are valid, but they carry different implications for performance, maintainability, and semantic clarity. The table below summarizes the key differences.

Surrogate vs. natural key comparison

Criterion	Surrogate Key	Natural Key
Stability	Highly stable — value never changes because it has no business meaning.	May change if the real-world attribute changes (e.g., SSN correction, email change).
Readability	Opaque — an integer like 47382 conveys no meaning to a human reader.	Self-documenting — ISBN, email, or country code instantly conveys identity.
Storage / Index Size	Typically 4–8 bytes (INT/BIGINT). Compact B-tree indexes.	Variable — a VARCHAR(255) email uses more space and produces larger indexes.
Join Performance	Integer comparisons are fast; foreign keys are small.	String comparisons are slower; composite natural keys amplify the overhead.
Schema Dependency	Adds an extra column that has no business meaning — slight denormalization.	Uses existing data — no extra column needed.

✦ KEY TAKEAWAY

In practice, most production systems default to surrogate keys (auto-increment integers or UUIDs) because they are stable, compact, and insulate the schema from changes in business rules. Natural keys are still valuable as alternate keys enforced by UNIQUE constraints — they give you the best of both worlds: a fast, immutable join target plus a human-readable uniqueness guarantee.

SECTION 8

Connection to Normalization & Advanced Constraints

Keys are not an isolated concept — they are the foundation upon which database normalization is built. The normal forms (1NF through BCNF and beyond) rely on the notion of functional dependencies, and a functional dependency X → Y means that X is a determinant — a potential key or part of one. Identifying candidate keys correctly is the prerequisite for determining whether a relation is in Second Normal Form (2NF), Third Normal Form (3NF), or Boyce-Codd Normal Form (BCNF).

From keys to advanced relational theory

This Lesson	Advanced Topic
Primary key guarantees uniqueness within a single table.	Functional dependencies generalize this: X → Y means X determines Y, even for non-key attributes. This powers normalization theory.
Foreign key enforces referential integrity between two tables.	CHECK constraints, triggers, and assertions can enforce arbitrary cross-table business rules beyond simple FK references.
Composite keys use multiple columns.	Partial dependencies (where a non-key attribute depends on part of a composite key) are the specific violation that 2NF eliminates.
Surrogate keys simplify joins.	In distributed systems, UUIDs or Snowflake IDs replace auto-increment to avoid coordination overhead across shards.

As you progress through SQL Foundations and into database design courses, you will encounter these advanced topics. The conceptual understanding of primary and foreign keys you build here will serve as the anchor point for all of them. In particular, recognizing candidate keys in a relation is the first step in any normalization procedure, and understanding referential integrity is essential for reasoning about transaction isolation, concurrency control, and distributed consistency.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain the difference between a candidate key and a primary key. Why can a table have multiple candidate keys but only one primary key?

PROBLEM 2 — BASIC APPLICATION

Consider a table courses(course_code, title, department, credits) and a table sections(section_id, course_code, instructor, room, semester). Identify the primary key and any foreign keys for each table.

PROBLEM 3 — INTERMEDIATE

A flight_bookings table has columns: (booking_id, passenger_id, flight_number, seat_number, booking_date). Passengers are stored in passengers(passenger_id, name, passport_number), and flights in flights(flight_number, departure_city, arrival_city, departure_time). Identify all primary keys, foreign keys, and at least one alternate candidate key across these three tables. Also, what would be a suitable composite candidate key for flight_bookings if booking_id did not exist?

PROBLEM 4 — APPLIED

You are designing an e-commerce database. The order_items table stores individual line items and has columns (order_id, product_id, quantity, unit_price). There is no surrogate key. Determine the primary key and foreign keys. Then explain what referential action (CASCADE, SET NULL, RESTRICT) you would choose for ON DELETE on each foreign key and why.

PROBLEM 5 — CRITICAL THINKING

A colleague proposes using email as the primary key for a users table, arguing that it is already unique and human-readable. Three other tables (posts, comments, likes) reference this key via foreign keys. Analyze the long-term consequences of this design. Under what circumstances could it cause problems, and what alternative design would you recommend?

SUMMARY

Lesson Summary

A primary key is a candidate key — a minimal, unique attribute set — that has been designated as the official row identifier for a table. It enforces entity integrity by requiring that all component values be non-null. A foreign key is a column (or set of columns) in a child table whose values must match an existing primary key (or unique key) in a parent table, thereby enforcing referential integrity. Together, these two constraints form the backbone of the relational model, preventing orphan records and guaranteeing addressability.

When designing schemas, choose between surrogate keys (stable, compact, immutable) and natural keys (human-readable, self-documenting) based on domain requirements, and always define appropriate referential actions (CASCADE, RESTRICT, SET NULL) to handle deletions and updates gracefully. Understanding keys at a conceptual level is the gateway to normalization, functional dependencies, and sound database architecture.