Schema

A relational schema defines the static structure of a database: which tables exist, what columns they have, and how they relate. It is the foundation on which all queries and transactions operate. Designing a good schema is the first step in any persistent-data system: it determines storage cost, query performance, and the integrity guarantees the database can enforce.

Authoritative sources

Database System Concepts, Ch. 1–2 (Silberschatz, Korth, Sudarshan)

Database Systems: The Complete Book, Ch. 1 (Garcia-Molina, Ullman, Widom)

Tables and attributes

A table (relation) $R$ is a set of tuples (rows), each with the same set of typed attributes (columns). (In SQL, tables are bags/multisets that allow duplicate rows; see Relational Algebra.) The schema of $R$ is the list of attribute names and their domains.

Primary key ( $PK$ ): a minimal set of attributes that uniquely identifies each row.
Foreign key ( $FK$ ): an attribute (or set) in $R$ that references the $PK$ of another table $S$ , enforcing referential integrity.
NOT NULL / UNIQUE / CHECK: additional column-level constraints.

Data types

Each attribute is declared with a data type (domain) that constrains the values it can hold. The choice of type affects storage size, index efficiency, and query semantics:

Category	Examples	Design consideration
Integers	SMALLINT, INTEGER, BIGINT	Match the expected range; BIGINT costs 8 bytes vs 4 for INTEGER
Fixed-point / exact	NUMERIC(p,s), DECIMAL	Use for money; avoids floating-point rounding
Floating-point	REAL, DOUBLE PRECISION	Use for measurements; never for exact arithmetic
Strings	CHAR(n), VARCHAR(n), TEXT	CHAR pads to n; VARCHAR stores actual length; TEXT has no limit
Temporal	DATE, TIME, TIMESTAMP	DATE = calendar day; TIMESTAMP = instant (with optional timezone)
Binary	BLOB, BYTEA	Unstructured payloads; not indexable in most engines

A common rule: choose the narrowest type that safely covers the domain. An INTEGER (4 bytes) is preferable to BIGINT (8 bytes) when values fit, because smaller types pack more rows per page and compare faster.

Details

Referential integrity: if $R.fk$ references $S.pk$ , then every value of $R.fk$ must either be NULL or match some $S.pk$ value. Deleting a row from $S$ that is referenced by $R$ is rejected (or cascaded, depending on the ON DELETE clause).

Composite keys: a primary key can span multiple attributes, e.g., $(student_id, course_id)$ for an enrollment table. The whole tuple must be unique; no single attribute need be.

Surrogate keys: in practice, databases often add an auto-incrementing integer $id$ as the $PK$ even when a natural key exists, to keep indexes small and stable.

Type choice in practice:

Use NUMERIC(10,2) for currency, never FLOAT, because $0.1 + 0.2 \neq 0.3$ in binary floating-point.
Use VARCHAR(255) for names (bounded, indexable) and TEXT for free-form descriptions (unbounded).
Use TIMESTAMP WITH TIME ZONE for events that must be comparable across timezones; DATE for “which day” queries.

Example problem

A hospital stores patient records. A patient’s age is at most 150, their diagnosis code is a 5-character string, and their admission timestamp must be comparable across servers in different timezones. Which types do you choose?

Solution

Age: SMALLINT (2 bytes, range −32768 to 32767, more than enough for 0–150).
Diagnosis code: CHAR(5) (fixed-length, always exactly 5 characters, compact for indexing).
Admission: TIMESTAMP WITH TIME ZONE (stores an absolute instant; displays in the viewer’s local timezone).

Entity-Relationship modeling

Before writing a relational schema, designers typically model the domain with an Entity-Relationship (ER) diagram. An ER diagram captures:

Entities (rectangles): the “nouns” of the domain (e.g., Book, Member, Loan).
Attributes (ellipses): properties of an entity; the key attribute is underlined.
Relationships (diamonds): how entities interact, annotated with cardinality (1:1, 1:N, M:N).

The ER diagram is a design tool: it is not stored in the database. The next step is mapping the ER model to relational tables.

Mapping rules

ER element	Relational mapping
Entity with key	One table; key becomes the `PK`
1:N relationship	`FK` in the "many" table pointing to the "one" table
M:N relationship	A separate junction table with `FK`s to both entities; the pair of `FK`s forms the `PK`
Relationship with its own attributes	The junction table also carries those attributes

Details

Step 1 – Identify entities and keys. Walk through the domain description and list every distinct “thing” that has its own identity. For each, pick a natural key or decide on a surrogate.

Step 2 – Identify relationships and cardinality. For every pair of entities that interact, determine whether the relationship is 1:1, 1:N, or M:N. A common test: can one instance of A relate to multiple instances of B? Can one instance of B relate to multiple instances of A?

Step 3 – Map to tables. Apply the mapping rules above. Every M:N relationship becomes a junction table. Every 1:N relationship adds a foreign key to the “many” side.

Step 4 – Add relationship attributes. If the relationship itself has data (e.g., a loan has a date), those attributes go in the junction table.

Example: Library system.

Entities: Book (key: book_id), Member (key: member_id), Loan (key: loan_id).
Relationships: Book —(1:N)→ Loan (a book can be loaned many times over its lifetime); Member —(1:N)→ Loan (a member can borrow many books over time).
The Book–Member interaction is M:N over time, so it is captured by the Loan entity (a “weak entity” or junction).

The ER diagram for this example:

Mapping result:

books(book_id PK, title, author, isbn)
members(member_id PK, name, email)
loans(loan_id PK, book_id FK→books, member_id FK→members, borrowed_at, returned_at)

Authoritative sources

Database System Concepts, Ch. 2 (ER modeling)

Example problem

Model a university: a Student can enroll in many Courses; a Course can have many Students; each enrollment records a grade. What tables do you create?

Solution

Entities: Student (key: student_id), Course (key: course_id).
Relationship: Student ↔ Course is M:N, with attribute grade.
Mapping: three tables.

students(student_id PK, name, email)
courses(course_id PK, title, credits)
enrollments(student_id FK→students, course_id FK→courses, grade,
           PK(student_id, course_id))

The composite key (student_id, course_id) enforces that a student cannot enroll in the same course twice.

Normal forms

Normal forms are canonical forms that eliminate redundancy and update anomalies:

1NF: all attributes are atomic (no nested collections, no multi-valued columns).
2NF: 1NF + no partial dependency (every non-key attribute depends on the whole composite $PK$ , not just a part).
3NF: 2NF + no transitive dependency (non-key attributes depend only on the $PK$ , not on other non-key attributes).
BCNF: for every non-trivial dependency $X \to Y$ , $X$ is a superkey.

Details

Why normalize? Redundancy causes update anomalies:

Insert anomaly: cannot add a fact without also adding unrelated data.
Update anomaly: changing a department name in one row but not another creates inconsistency.
Delete anomaly: removing a row loses unrelated information.

Normal forms eliminate these by ensuring each fact is stored in exactly one place.

Functional dependencies: a dependency $X \to Y$ holds if two tuples that agree on $X$ must also agree on $Y$ . The closure $X^+$ (all attributes determined by $X$ ) is computed by the Armstrong axioms (reflexivity, augmentation, transitivity).

The following diagram shows a transitive dependency that violates 3NF:

Concrete example of a 2NF violation:

Consider a table enrollments(student_id, course_id, course_title, grade) with PK (student_id, course_id).

course_title depends only on course_id (a part of the PK) → partial dependency → violates 2NF.
Fix: split into courses(course_id PK, course_title) and enrollments(student_id, course_id FK, grade).

Denormalization: in practice, read-heavy systems (OLAP, reporting) denormalize (join tables, add redundant columns) to reduce join cost. The trade-off is write amplification and update anomalies. A common pattern: keep the OLTP schema normalized, and build a denormalized read replica or materialized view for analytics.

Authoritative sources

Database System Concepts, Ch. 6 (Normalization)

Database Systems: The Complete Book, Ch. 10 (Functional Dependencies)

Example problem

A table orders(order_id, customer_id, customer_city, product_id, product_price, quantity) has PK order_id. Identify all normal-form violations and propose a fix.

Solution

customer_city depends on customer_id, not on order_id → transitive dependency → violates 3NF.
product_price depends on product_id, not on order_id → transitive dependency → violates 3NF.

Fix (3NF):

customers(customer_id PK, customer_city)
products(product_id PK, product_price)
orders(order_id PK, customer_id FK, product_id FK, quantity)

Indexes

For how B-trees and hash tables work internally, see Key-Value Stores. For how the optimizer chooses to use an index at query time, see SQL & Query Planning.

An index is a secondary data structure that accelerates lookup by a column (or set of columns).

B-tree index on column $c$ : $O(\log n)$ lookup by $c$ , supports range queries ( $c > 5$ , $c BETWEEN 3 AND 7$ ).
Hash index on column $c$ : $O(1)$ expected equality lookup only.
Composite index on $(c_1, c_2, \ldots)$ : ordered by $c_1$ , then $c_2$ , etc. Supports prefix queries ( $c_1 = 5$ ), but not $c_2$ alone.
Covering index: includes all columns needed by a query, avoiding a table lookup (“index-only scan”).

Details

Write overhead: every INSERT, UPDATE, or DELETE must also update every index on the affected columns. A table with 5 indexes pays 5× the index-maintenance cost on writes. For write-heavy workloads, LSM-tree indexes (see Key-Value Stores) batch writes and merge in the background.

Index selection heuristics:

Equality predicates on the leading column benefit most.
Range predicates on the leading column are supported by B-trees but not hash indexes.
A composite index $(a, b)$ serves queries on $a$ alone or $(a, b)$ , but not $b$ alone.
The leftmost prefix rule: the index can only be used if the query constrains the leading column(s) with equality (or a range on the last constrained column).

Partial indexes: an index on a subset of rows (e.g., WHERE status = 'active') is smaller and faster to maintain, at the cost of not serving queries on the excluded rows.

B-tree structure (simplified, order-3):

Authoritative sources

Database System Concepts, Ch. 10 (Indexing)

Example problem

A table events(event_id, user_id, created_at, status) is queried with:

WHERE user_id = 42 AND created_at > '2025-01-01'
WHERE status = 'pending'

Which composite index serves query 1 efficiently? Can the same index serve query 2?

Solution

Query 1: a composite B-tree index on (user_id, created_at) works. The equality on user_id narrows to a range of created_at values within that user’s slice.
Query 2: the same index does not help, because status is not the leading column. A separate index on status (or a partial index WHERE status = 'pending') is needed.

Interactive normalization checker

The simulation below lets you drag attributes between tables and see which normal form is violated. Try moving dept_name into the employees table to observe a transitive dependency (3NF violation), or split a composite key to see a partial dependency (2NF violation).

Quizz

Example problem

Problem: Design a schema for a library system with books, members, and loans. A book can be loaned to at most one member at a time. A member can have many loans (over time). Each loan records the date borrowed and the date returned.

First, sketch the ER diagram, then map it to relational tables, then verify the result is in 3NF.

Solution

ER diagram:

Relational schema:

books(book_id PK, title, author, isbn)
members(member_id PK, name, email)
loans(loan_id PK, book_id FK→books, member_id FK→members, borrowed_at, returned_at)

Why this is 3NF:

books: title and author depend on book_id (the PK). No transitive dependency.
members: name and email depend on member_id. No transitive dependency.
loans: all non-key attributes depend on loan_id. The composite $(book_id, member_id, borrowed_at)$ could serve as an alternative PK, but a surrogate loan_id keeps the PK small.

Constraint: “at most one active loan per book” is enforced by a partial unique index: UNIQUE(book_id) WHERE returned_at IS NULL.

Index: a B-tree on loans(book_id) supports the query “is this book currently available?” in $O(\log n)$ . A B-tree on loans(member_id) supports “what does this member currently have?”.

Schema §

Tables and attributes §

Data types §

Entity-Relationship modeling §

Mapping rules §

Normal forms §

Indexes §

Interactive normalization checker §

Quizz §

Schema

Tables and attributes

Data types

Entity-Relationship modeling

Mapping rules

Normal forms

Indexes

Interactive normalization checker

Quizz