Relational Database Models

Learning Objectives

• Define a relation, tuple, and attribute in formal relational model terms and translate them to tables, rows, and columns
• Distinguish between superkeys, candidate keys, primary keys, composite keys, and foreign keys, and pick the right one in a schema
• Explain entity integrity, referential integrity, and domain constraints, and identify when a schema violates them
• Write CREATE TABLE statements with primary key and foreign key constraints that correctly model a one-to-many relationship
• Apply core relational algebra operations (selection, projection, join, union, set difference) to answer a query both algebraically and in SQL
• Map an entity-relationship diagram to a set of normalized relational tables

Quick Answer

The relational model is a way of organizing data into tables (formally called relations), where each row is a unique record and each column holds one type of attribute. It was proposed by Edgar F. Codd in 1970 and is still the foundation of nearly every SQL database in use today — PostgreSQL, MySQL, Oracle, SQL Server. It matters because it gives you a mathematically grounded, predictable way to store data without duplication, enforce correctness through keys and constraints, and query it declaratively (you say what you want, not how to fetch it). Understanding relations, keys, and integrity rules is the prerequisite for everything else in database design — normalization, indexing, transactions, and query optimization all build on this foundation.

What Is a Relation, Really?

Before "table" became the everyday word, Codd used the term relation — borrowed from set theory, not from "relationships between tables" (a common point of confusion). A relation is formally a set of tuples, where:

• A relation is the table itself — an unordered collection of tuples that all share the same structure.
• A tuple is one row — a single, complete record. In the Students relation, a tuple might be (101, 'John Doe', 20, 'CS').
• An attribute is a column — a named property that every tuple has a value for, drawn from a fixed domain (the set of legal values, e.g., Age must be a positive integer).
• The degree of a relation is its number of attributes; the cardinality is its number of tuples.

Because a relation is mathematically a set, two consequences follow that trip people up: there's no guaranteed row order (SQL engines only guarantee order if you ORDER BY), and in the strict theoretical model, duplicate rows aren't allowed. Real SQL databases relax that last rule for practicality (tables can have duplicate rows unless you add a key), which is one of the small but important gaps between the pure relational model and what you actually type into psql.

Keys: How You Uniquely Identify a Row

Keys are the mechanism that makes relations useful instead of just being big bags of data. Here's the hierarchy, from broadest to most specific:

• Superkey — any set of attributes that uniquely identifies a tuple. {Student_ID} is a superkey, but so is {Student_ID, Name} — it's still unique, just carrying extra baggage.
• Candidate key — a minimal superkey: remove any attribute and it stops being unique. A table can have multiple candidate keys (e.g., Student_ID and, separately, Email, if both are guaranteed unique).
• Primary key — the candidate key the designer chooses as the main identifier. Every other candidate key becomes an alternate key. A primary key cannot be NULL and must be unique for every row (this is the entity integrity rule below).
• Composite key — a primary or candidate key made of more than one attribute, because no single column is unique on its own. A classic example: in an Enrollments table, neither Student_ID nor Course_ID alone is unique, but the pair (Student_ID, Course_ID) is.
• Foreign key — an attribute (or set of attributes) in one table that references the primary key of another table (or, less commonly, the same table). This is the mechanism that lets relations actually relate to each other.

A student misconception worth killing early: a foreign key does not have to be unique in its own table. In Orders, Customer_ID is a foreign key referencing Customers.Customer_ID, but the same customer can place many orders — so Customer_ID repeats freely in Orders. Uniqueness is a property of the table being referenced, not the referencing column.

Integrity Constraints

Constraints are rules the database engine enforces automatically so that bad data can never get committed in the first place.

• Entity integrity: every table must have a primary key, and no primary key value (or any part of a composite one) may be NULL. This guarantees every row is individually addressable.
• Referential integrity: a foreign key value must either match an existing primary key value in the referenced table, or be NULL (if the column allows it). You cannot have an order pointing to a customer that doesn't exist. Databases enforce this and will reject an INSERT or raise an error on a DELETE that would orphan a row, unless you've defined a cascade rule.
• Domain constraints: a column's values must come from its declared type and any additional rules (CHECK, NOT NULL, UNIQUE). Age INT CHECK (Age > 0) is a domain constraint in action.

These three constraints together are what let you trust the data without manually auditing it — the database itself refuses invalid states.

Modeling It: An ER Diagram

Here's a small, realistic schema — students enrolling in courses — modeled first conceptually, then as relations.

This is the standard pattern for resolving a many-to-many relationship: Students and Courses relate many-to-many (a student takes many courses, a course has many students), so a resolving table (Enrollments) sits between them, holding a composite primary key made of both foreign keys plus any attributes that describe the relationship itself (like grade).

ER-to-Relational Mapping Rules

When you go from a conceptual ER diagram to actual tables, a few rules govern the translation:

1. Strong entity → becomes its own table; its identifying attribute becomes the primary key.
2. One-to-many relationship (e.g., a Department has many Employees) → put a foreign key on the "many" side. Employees.Dept_ID references Departments.Dept_ID. No new table needed.
3. Many-to-many relationship → create a new junction/associative table (like Enrollments above) whose primary key is the composite of both foreign keys.
4. One-to-one relationship → the foreign key can go on either side; typically it's placed on the table that's optional or dependent (e.g., Passport referencing Person).
5. Multivalued attribute (e.g., a student having multiple phone numbers) → becomes its own table, since a single column can't hold repeating values in first normal form.

Turning This Into SQL

CREATE TABLE Students (
    student_id  INT PRIMARY KEY,
    name        VARCHAR(100) NOT NULL,
    age         INT CHECK (age > 0),
    department  VARCHAR(50)
);

CREATE TABLE Courses (
    course_id   INT PRIMARY KEY,
    title       VARCHAR(150) NOT NULL,
    credits     INT NOT NULL CHECK (credits BETWEEN 1 AND 6)
);

CREATE TABLE Enrollments (
    student_id   INT NOT NULL,
    course_id    INT NOT NULL,
    enrolled_on  DATE NOT NULL DEFAULT CURRENT_DATE,
    grade        CHAR(2),
    PRIMARY KEY (student_id, course_id),
    FOREIGN KEY (student_id) REFERENCES Students(student_id)
        ON DELETE CASCADE,
    FOREIGN KEY (course_id) REFERENCES Courses(course_id)
        ON DELETE RESTRICT
);

Notice the two different ON DELETE behaviors: deleting a student cascades and removes their enrollments (they're gone, so their enrollment records are meaningless), but deleting a course is restricted if enrollments reference it — you'd have to handle that explicitly, since erasing course history silently is usually undesirable.

Relational Algebra: The Theory Behind Every Query

Relational algebra is the formal, mathematical query language that SQL is compiled down to conceptually. Every SQL query is really a combination of these operations:

• Selection (σ) — filters rows by a condition. σ(department = 'CS')(Students) in SQL is SELECT * FROM Students WHERE department = 'CS';
• Projection (π) — picks specific columns, discarding the rest. π(name, age)(Students) is SELECT name, age FROM Students;
• Union (∪) — combines rows from two relations with the same schema, removing duplicates. SELECT student_id FROM CS_Majors UNION SELECT student_id FROM Honors_Students;
• Set difference (−) — rows in one relation but not another. SELECT student_id FROM Students EXCEPT SELECT student_id FROM Enrollments; finds students enrolled in nothing.
• Cartesian product (×) — pairs every row of one relation with every row of another. Rarely used directly, but it's conceptually what an unfiltered JOIN starts from.
• Join (⋈) — a filtered Cartesian product that matches rows on a common condition, almost always a foreign-key-to-primary-key match.

-- Selection + Projection
SELECT name, age FROM Students WHERE department = 'CS';

-- Join: find every student's enrolled course titles
SELECT s.name, c.title, e.grade
FROM Students s
JOIN Enrollments e ON s.student_id = e.student_id
JOIN Courses c ON e.course_id = c.course_id;

-- Insert, update, delete
INSERT INTO Students (student_id, name, age, department)
VALUES (103, 'Alice Johnson', 21, 'CS');

UPDATE Students SET age = 22 WHERE student_id = 101;

DELETE FROM Students WHERE student_id = 102;

The join in that middle query is doing exactly what the ER-to-relational mapping predicted: Enrollments is the junction table stitching Students and Courses together, and the join reassembles the many-to-many relationship at query time.

Key Terms

Term	Definition
Relation	A table: a set of tuples sharing the same attributes, in Codd's formal terminology.
Tuple	A single row in a relation, representing one complete record.
Attribute	A named column in a relation, drawn from a defined domain.
Domain	The set of legal, atomic values an attribute may take (e.g., positive integers for Age).
Superkey	Any attribute set that uniquely identifies a tuple, possibly with redundant attributes.
Candidate key	A minimal superkey — no attribute can be removed without losing uniqueness.
Primary key	The candidate key chosen to uniquely and permanently identify rows; cannot be NULL.
Foreign key	An attribute referencing the primary key of another (or the same) table, establishing a relationship.
Composite key	A primary or candidate key composed of two or more attributes together.
Entity integrity	The rule that primary key values must be unique and never NULL.
Referential integrity	The rule that foreign key values must match an existing referenced primary key, or be NULL.
Relational algebra	The formal, procedural mathematical language underlying SQL query execution.

Common Mistakes

Misconception 1: "A foreign key must be unique in its own table." Why it's wrong: people confuse "foreign key" with "primary key" because both sound like identifiers. Correct understanding: a foreign key can repeat as many times as needed in the referencing table (many orders can share one customer); uniqueness is required only in the table being referenced, not the one holding the foreign key.

Misconception 2: "Every table needs a foreign key to be 'relational.'" Why it's wrong: this comes from over-literally reading "relational database" as "tables full of relationships to each other." Correct understanding: the word "relation" refers to the mathematical set-of-tuples structure of a single table, not to foreign key links. A single standalone table with no foreign keys is still perfectly relational.

Misconception 3: "NULL in a foreign key column violates referential integrity." Why it's wrong: students assume any mismatch with the primary key table is an integrity violation. Correct understanding: NULL is explicitly allowed in a foreign key (unless you add NOT NULL) and represents "not yet assigned" or "not applicable" — referential integrity only requires that non-NULL foreign key values match an existing primary key.

Comparison and Connections

Key Type	Uniqueness Required?	Can Be NULL?	Number Allowed per Table	Purpose
Superkey	Yes (possibly with redundant columns)	Depends on columns	Many	Any uniquely identifying set
Candidate key	Yes, minimally	Depends on columns	One or more	Eligible to become the primary key
Primary key	Yes	No	Exactly one (may be composite)	Official row identifier
Alternate key	Yes	Depends	Zero or more	Candidate keys not chosen as primary
Foreign key	No	Yes (unless restricted)	Zero or more	Links to another table's primary key

Relational Algebra Operation	SQL Equivalent	What It Does
Selection (σ)	WHERE	Filters rows
Projection (π)	Column list in SELECT	Filters columns
Union (∪)	UNION	Combines rows from two compatible relations
Set Difference (−)	EXCEPT / MINUS	Rows in one relation but not another
Cartesian Product (×)	Cross join (no condition)	Pairs every row with every row
Join (⋈)	JOIN ... ON	Cartesian product filtered by a matching condition

Practice Questions

Recall

1. What is the difference between a candidate key and a primary key? Answer: every candidate key is a minimal unique identifier, but only one is chosen to be the primary key; the rest become alternate keys.
2. Name the three types of integrity constraints in the relational model. Answer: entity integrity, referential integrity, and domain constraints.

Understanding

3. Why can a foreign key value repeat in its own table but not violate any rule? Answer: uniqueness is a property enforced on the primary key of the referenced table; the referencing column is allowed to have many rows pointing to the same primary key value, which is exactly how one-to-many relationships work.
4. Explain why a many-to-many relationship needs a junction table instead of a direct foreign key. Answer: a single foreign key column can only point to one row, so it can't represent "many on both sides"; a junction table with a composite key of both foreign keys can have as many rows as needed to represent every pairing.

Application

5. Design the primary key for a Flight_Seats table that tracks which seat on which flight is assigned to which passenger. Answer: a composite key of (flight_id, seat_number) — that pair is unique per flight, while passenger_id is a foreign key, not part of the identifying key.
6. Write the FOREIGN KEY clause needed so that deleting a Department also deletes all its Employees. Answer: FOREIGN KEY (dept_id) REFERENCES Departments(dept_id) ON DELETE CASCADE.

Analysis

7. A table has columns (SSN, Email, Name) where both SSN and Email are guaranteed unique. Identify all candidate keys and explain what happens if you pick Email as the primary key. Answer: both {SSN} and {Email} are candidate keys since each alone is a minimal unique identifier. If Email is chosen as primary key, SSN becomes an alternate key — still enforced as unique, just not the main identifier the table is built around.
8. A student says the query SELECT * FROM Students, Courses; is a join. Evaluate this claim. Answer: it's technically a Cartesian product, not a meaningful join — it pairs every student with every course regardless of enrollment, producing a huge, mostly meaningless result set; a real join needs a WHERE or ON condition matching foreign key to primary key.

FAQ

Is "relation" just another word for "table"? Practically, yes — in everyday SQL conversation the terms are interchangeable. Formally, "relation" is Codd's mathematical term for a set of tuples, while "table" is the physical/implementation-level term used in actual databases, which relax some of the strict set rules (like disallowing duplicate rows).

Can a table have more than one primary key? No — a table has exactly one primary key, though that key can be composite (made of multiple columns). It can, however, have multiple candidate keys, and any candidate key not chosen becomes an alternate key enforced with a UNIQUE constraint.

Why do we need foreign keys if the application code could just check relationships itself? Because application-level checks are fragile — someone forgets a check, a script bypasses the app layer, or a race condition slips through. Foreign key constraints are enforced by the database engine itself for every write, from every source, which is a much stronger guarantee.

What's the practical difference between relational algebra and SQL? Relational algebra is a formal, closed mathematical language used to reason about and optimize queries; SQL is the practical, declarative language you actually write, which a database's query optimizer translates into a relational algebra execution plan internally.

Do NULLs break relational algebra's logic? They complicate it. Pure relational algebra assumes every value is known, but NULL represents "unknown" or "not applicable," which forces SQL to use three-valued logic (TRUE, FALSE, UNKNOWN) for comparisons — this is why WHERE age = NULL never matches anything; you need WHERE age IS NULL.

Should every table have a surrogate key like an auto-incrementing ID instead of a natural key? It depends, but surrogate keys (like an INT or UUID that has no business meaning) are common in practice because natural keys (like Email or SSN) can change or turn out not to be as unique as assumed. Composite keys made of foreign keys in junction tables are an exception — they're natural and appropriate there.

Quick Revision

• A relation = a table; a tuple = a row; an attribute = a column; a domain = the legal values for an attribute.
• Superkey → candidate key (minimal superkey) → primary key (chosen candidate key).
• A composite key uses more than one column together because no single column is unique alone.
• A foreign key references another table's primary key and does not need to be unique itself.
• Entity integrity: primary keys can never be NULL and must be unique.
• Referential integrity: non-NULL foreign key values must match an existing primary key.
• Domain constraints: values must match the column's type and any CHECK/NOT NULL rules.
• Many-to-many relationships need a junction table with a composite primary key of both foreign keys.
• Relational algebra operations: selection (σ, filters rows), projection (π, filters columns), union, set difference, Cartesian product, join.
• A join is a Cartesian product narrowed by a matching condition — without the condition, it's just a cross product.
• ON DELETE CASCADE removes dependent rows automatically; ON DELETE RESTRICT blocks the delete if dependents exist.
• SQL is the practical language you write; relational algebra is the theory the database engine reasons with internally.

Related Topics

Prerequisites

• Basic understanding of what a database is and why data needs structured storage
• Familiarity with sets and basic set operations (union, intersection, difference)

Related Topics

• Entity-Relationship (ER) Modeling
• SQL Fundamentals (DDL, DML, DQL)
• Database Normalization (1NF, 2NF, 3NF, BCNF)

Next Topics

• Normalization and Functional Dependencies
• Joins and Subqueries in Depth
• Transactions and ACID Properties
• Indexing and Query Optimization