Databases

Definition

A Database Management System (DBMS) is software that provides an abstraction over secondary storage (disks, SSDs). It hides the details of how data is stored on physical media behind a standardised interface (e.g., SQL) that can be shared by many concurrent applications.

The narrow waist model

The DBMS sits at a “narrow waist” in the software stack:

• Above the interface: diverse applications (web apps, transaction processing, analytics, reporting tools) — all written to the same API.
• Below the interface: diverse storage engines, file formats, indexing strategies, and hardware — all interchangeable without changing the applications.

This arrangement decouples application development from implementation details. The application programmer writes queries against a logical schema; the DBMS handles the physical storage.

CRUD operations

Every DBMS provides four fundamental operations on data:

Management operations

Beyond CRUD, a DBMS typically offers management-level operations:

• Create or alter the schema (tables, columns, types, constraints)
• Create views (virtual tables for access control or convenience)
• Physical reorganisation of stored data
• Re-indexing for query performance
• Backup and recovery
• Statistics generation for query planning

These management operations are mostly beyond the scope of the Part IA course. The course focuses on the application writer’s point of view: data models and query languages.

Why use a DBMS?

Summary

• A DBMS provides an abstraction layer between applications and physical storage.
• The narrow waist model gives both application portability and implementation flexibility.
• The core data operations are Create, Read, Update, Delete.
• This course studies the DBMS from the application writer’s perspective: modelling data and writing queries.

From punched cards to key-value stores

Fixed-field records were the earliest digital data format, inherited from punched cards. Each field occupies a predetermined range of character positions on a line. This is efficient for machines to parse but inflexible: changing a field width requires rewriting every record.

Comma/character-separated value (CSV) records use delimiters to separate fields. This is more flexible than fixed-width, but still imposes a simple row-and-column structure and struggles with embedded delimiters or line breaks within field values.

The in-core associative store

The simplest possible database is an in-core associative store — a dictionary (or collection) held in primary memory with just two operations:

store(key, value)
retrieve(key)

There are no constraints on the order of invocations. The associative store can be implemented with a hash table, balanced tree, or any other dictionary data structure. It is ephemeral (lost when the process exits) and limited by the size of RAM.

Database terminology

Students are expected to understand all of the following glossary terms by the midpoint and endpoint of the course:

Schemas

A schema defines the shape of the data:

Table: Students
  Name:     string, not null
  CRSID:    string, not null, primary key
  College:  string
  Year:     integer, range [1, 4]

The schema is enforced by the DBMS. Any insert or update that violates a constraint is rejected. This is in contrast to schema-free systems (e.g., document databases), where the application must enforce its own consistency.

Summary

• Data can be represented as fixed-field records, delimited records, or in-core dictionaries.
• The core vocabulary of databases — field, record, schema, key, index, query, update, transaction — underpins everything that follows in the course.
• A schema is a contract: the DBMS guarantees that all data conforms to it.

Interfaces as liberation

An interface is a contract that liberates application writers from low-level details. It represents an abstraction of the resources and services used by applications. In an ideal world, implementations can change without requiring changes to applications.

In practice, this ideal is often undermined by:

• Performance concerns: a naive abstraction may perform poorly on a particular implementation, forcing the application writer to become aware of what lies beneath.
• Mission creep: the interface specification grows over time, adding features that tie applications to specific implementations.
• Specification change: the interface itself is revised, breaking existing applications.

Standard interfaces are everywhere

The narrow waist pattern recurs in many engineered systems:

In each case, the interface decouples the consumers of a service from the providers. New providers can enter below the interface; new consumers can enter above it.

The DBMS logical arrangement

Applications interact only with the DBMS. The DBMS uses the operating system’s file system, which in turn uses device drivers to access physical storage. Some high-performance DBMSs bypass the file system and manage raw storage devices directly.

Storage interface primitives

Primary storage (RAM) provides a simple word-level interface:

write(address, word)
read(address)

Secondary storage (disk/SSD) provides a block-level interface:

write(blkaddress, block)
read(blkaddress) → option(block)
trim(blkaddress)
sync()

• read returns an option: the block might not exist (unlike RAM, where every address always contains something).
• trim tells the device that a block is no longer needed (used by SSDs for garbage collection).
• sync flushes buffered writes to persistent media.

Storage configurations

Most general-purpose DBMSs use the serialised-to-filesystem configuration. In-core databases (e.g., Redis) are used where latency is critical and the dataset fits in RAM.

Summary

• An interface is an abstraction that decouples consumers from providers.
• The narrow waist model appears in many engineered systems, not just databases.
• The DBMS sits between user applications and the file system/device drivers.
• Secondary storage differs from primary storage in providing block-level access with optional read results.

Storage classifications

Databases can be classified along three axes:

By medium

By persistence

By scale

Write patterns

Consistency models

ACID (strong consistency)

Atomicity, Consistency, Isolation, Durability. Every transaction is an indivisible unit: it either completes entirely or has no effect. After a transaction commits, all subsequent reads see its effects. This is the traditional model in relational DBMSs.

BASE (relaxed consistency)

Basically Available, Soft state, Eventual consistency. The system may not be immediately consistent after an update, but if updates cease, all replicas will eventually converge. This model is common in distributed NoSQL systems.

Data arrangement

Consistency checks

A DBMS can enforce several kinds of constraint:

Summary

• Databases are classified by storage medium (in-core vs. secondary), persistence (ephemeral vs. persistent), and scale.
• Write patterns range from read-optimised to append-only.
• ACID provides strong guarantees; BASE trades consistency for availability and partition tolerance.
• Consistency checks — domain, referential, atomicity, entity — protect data quality.

Why distribute data?

A distributed database stores data across multiple machines connected by a network. The motivations are:

The cost of distribution: consistency

After an update is applied to one replica, there is a massive overhead in ensuring that all other replicas reflect the change immediately. If a user reads from a stale replica, they see outdated data.

There is a multitude of successively-relaxed consistency models that trade stronger guarantees for better performance:

• Linearizability (strongest, hardest to achieve)
• Sequential consistency
• Causal consistency
• Read-your-writes consistency
• Monotonic reads
• Eventual consistency (weakest, easiest to achieve)

The CAP theorem

Formulated by Eric Brewer in 2000, the CAP theorem states that a distributed database can provide at most two of the following three guarantees simultaneously:

It is impossible, with current technology, to achieve all three. In practice, network partitions are inevitable, so the real choice is between CP (consistency over availability) and AP (availability over consistency).

A system can sit anywhere on the edges of this triangle, but not at the centre.

Approximating CAP is the subject of the Part IB Concurrency and Distributed Systems course.

BASE: the alternative to ACID

When a system chooses AP over CP, it adopts the BASE model as an alternative to ACID:

Comparison

Summary

• Distribution provides scalability, fault tolerance, and lower latency — at the cost of consistency.
• The CAP theorem says you can have at most two of Consistency, Availability, and Partition tolerance.
• BASE (Basically Available, Soft state, Eventual consistency) is the practical alternative to ACID for distributed systems.

Overview

The course covers three data models. The relational model has been the industry mainstay for over 48 years; the other two are representatives of the NoSQL movement.

All three primarily hold discrete data. The Lent term MLRD course deals with soft/continuous decision making.

Relational model

Data is stored in 2-D tables:

• Each row is a record (tuple).
• Each column is a field (attribute).
• The schema indicates field names, data formats, and which column(s) comprise the key.
• Row and column ordering is unimportant.
• SQL is the main query language.

Example table:

The primary key (underlined in schema diagrams) is CRSID.

The relational model has been the industry mainstay since the 1970s due to its strong theoretical foundation (relational algebra, normalisation) and robust ACID transaction support.

Document-oriented model

Also called aggregate-oriented database. Instead of splitting data across normalised tables, related data is stored together as a single document.

• Optimised for read-oriented databases with few updates.
• Uses semi-structured data (typically JSON).
• No rigid schema: different documents can have different fields.
• Queries are expressed in the host programming language or via path expressions.

Example document (JSON):

{
  "name": "Alice",
  "crsid": "abc12",
  "college": "King's",
  "papers": [
    {"code": "CS1", "title": "Foundations of CS"},
    {"code": "CS2", "title": "Software Engineering"}
  ]
}

Graph-oriented model

Data is represented as nodes (entities) and edges (relationships). Both nodes and edges can carry properties.

• Query languages tend to have path-oriented capabilities.
• Extensive support for standard graph techniques: shortest path, breadth-first search, PageRank.
• Well-suited to highly connected data (social networks, recommendation engines, transport networks).

Example (Cypher):

CREATE (alice:Student {name: 'Alice', crsid: 'abc12'})
CREATE (bob:Student {name: 'Bob', crsid: 'def34'})
CREATE (alice)-[:FRIEND_OF]->(bob)

Three database systems used in the course

Examination

For examination purposes, students must learn everything in the slide deck and know all glossary terms. A relational database consists of 2-D tables; the schema indicates field names, data formats, and which column(s) comprise the key (conventionally underlined). Row and column ordering is unimportant.

Summary

• The three data models are relational (tables + SQL), document-oriented (JSON + path queries), and graph-oriented (nodes/edges + Cypher).
• The relational model dominates industry; the NoSQL models address specific use cases (semi-structured data, highly connected data).
• The course uses SQLite, TinyDB, and Neo4j as concrete exemplars.

Origins of ER modelling

Entity-Relationship (ER) diagrams are a conceptual modelling technique introduced by Peter Chen in 1976. They provide an implementation-independent way to describe the data we intend to store in a database. Although ER modelling grew up around relational database systems, it helps clarify design issues for any data model: it forces you to think about what the data means before you commit to tables, columns, or SQL.

The key insight is that ER diagrams are not tied to a particular DBMS, storage engine, or even the relational model. They capture the conceptual schema — the logical structure of the data as understood by the domain expert — and this schema can later be mapped to a relational schema, a document store, or a graph database.

Entities

Entities represent the nouns of our domain — the real-world objects or concepts we want to record information about. In an ER diagram, entities are drawn as rectangles labelled with the entity type name.

An entity set is the collection of all instances of a given entity type at a particular moment. For example:

Movie = {(tt0113189, GoldenEye, 1995),
         (tt0988045, Sherlock Holmes, 2009),
         (tt0371746, Iron Man, 2008)}

Each member of the entity set is an entity instance (or simply an entity). The data model does not need to enumerate every possible instance; it only specifies the structure that any valid instance must conform to.

Attributes

Attributes represent the properties of an entity — the facts we want to record about each instance. In an ER diagram, attributes are drawn as ovals connected to their entity rectangle.

A Movie entity might have attributes: title, release_year, running_time, budget. Each attribute draws its values from a domain (a set of permissible values). The domain of release_year might be {1888, 1889, ...}; the domain of title might be variable-length strings.

Keys

A key is an attribute (or set of attributes) whose value uniquely identifies each entity instance within an entity set. In ER diagrams, key attributes are underlined.

A key must satisfy two properties:

1. Uniqueness: no two distinct entities in the set may have the same key value.
2. Minimality (ideal): no attribute can be removed from the key without destroying uniqueness.

Keys may be formed algorithmically. A CRSID (e.g., abc123) is a key for Cambridge students: it is assigned by the University and is unique within that namespace. However, relying on keys that lie outside your control is dangerous. A National Insurance number might seem like a convenient natural key, but:

• You do not issue or manage NI numbers; they can be reassigned under exceptional circumstances.
• The format could change.
• Not everyone in your system will have one (e.g., international customers).
• Data entry errors are irreversible if the key is used as a foreign key throughout the schema.

Synthetic keys

In practice, the only safe thing to use as a primary key is a synthetic key (also called a surrogate key): an identifier that is automatically generated by the database and has no meaning outside the database itself. Common examples:

The important principle: a synthetic key is an internal implementation detail. Users of the system should never see it, type it, or depend on it staying the same across database migrations. It exists purely to give each row a stable, unique address within the database.

Scope of the model

An ER diagram implicitly declares the scope of the model. Among the infinitely many possible attributes a real-world entity possesses, the diagram selects only those relevant to the application. A Movie has a plot synopsis, a colour grading, a distribution contract — but if your database is a simple viewing tracker, you model only title, year, and genre. The attributes you choose to include (and, just as importantly, to exclude) define the boundary of what your system knows about.

Summary

• ER diagrams are a conceptual design tool, independent of any particular DBMS.
• Entities (rectangles) are the objects we model; attributes (ovals) are their properties.
• A key (underlined) uniquely identifies each entity instance.
• Synthetic keys are safer than natural keys because they are under the database’s sole control.
• The model’s scope is a design decision: you declare which attributes matter for your application.

What a key does

A key uniquely identifies each entity instance within an entity set. Given a key value, there is at most one entity with that value. This property is what makes keys the foundation of data integrity: they give us a reliable way to refer to a specific row.

Natural keys

A natural key is a key formed from attributes that have real-world meaning — a National Insurance number, an email address, a vehicle registration plate, an ISBN. They seem appealing because they already exist and users already understand them.

However, natural keys are dangerous for several reasons:

Once a natural key is embedded throughout a schema as foreign keys, changing it requires cascading updates to every referencing table — an operation that may be slow, dangerous under concurrent access, or impossible if the database lacks ON UPDATE CASCADE.

Synthetic keys (surrogate keys)

A synthetic key (surrogate key) is an identifier generated by the database system at insertion time. It has no meaning outside the database and is never exposed to end users.

Common implementations:

The synthetic key approach has clear advantages:

• Stable: it never changes once assigned.
• Guaranteed unique: the DBMS enforces uniqueness.
• Under your control: you define the generation policy, not an external agency.
• Simple: often just an integer, making foreign keys compact and joins fast.

The only safe approach for large, evolving systems is to use synthetic keys for all primary keys. This is not dogmatic but practical: decades of operational experience show that natural keys eventually cause problems, and the cost of fixing them is far higher than the small upfront cost of adding a surrogate key.

Natural keys still need constraints

Using a synthetic primary key does not mean you abandon natural key constraints. A table of employees might have:

employee_id  SERIAL PRIMARY KEY,    -- synthetic
ni_number    TEXT UNIQUE NOT NULL   -- natural, still enforced

The UNIQUE constraint on ni_number ensures that business logic consistency is maintained — no two employees can share an NI number — but ni_number is not the primary key. If an NI number changes, only one column in one row needs updating, rather than every foreign key reference across the entire database.

Formal definition (relational model preview)

Let $R(X)$ be a relational schema, where $X$ is the set of attributes of $R$. Let $Z \subseteq X$ be a subset of attributes.

$Z$ is a superkey for $R$ if, for any records $u$ and $v$ in any valid instance of $R$:

$u[Z] = v[Z] \implies u[X] = v[X]$

In other words: if two records agree on all attributes in $Z$, they must be the same record (agree on all attributes in $X$).

$Z$ is a key for $R$ if:

1. $Z$ is a superkey for $R$, and
2. No proper subset of $Z$ is a superkey for $R$.

The second condition is minimality: you cannot drop any attribute from the key and still have a superkey. Every relation has at least one key (in the worst case, the set of all attributes $X$ is a superkey, and if no proper subset is a superkey, then $X$ itself is a key). One key is typically designated as the primary key for implementation purposes.

Summary

• A key guarantees that each entity instance can be uniquely identified.
• Natural keys are appealing but fragile: they are mutable, may not be universal, and lie outside the database’s control.
• Synthetic keys are stable, guaranteed unique, and under your control — the safe default for any non-trivial system.
• Natural keys should still carry UNIQUE constraints to enforce business rules.
• Formally, a superkey is a set of attributes that functionally determines all attributes; a key is a minimal superkey.

Relationships

Relationships represent the verbs of our domain — the associations between entities. In an ER diagram, relationships are drawn as diamonds connected by lines to the participating entity rectangles.

A relationship type defines a structure; relationship instances are the concrete pairings:

Martin Campbell directed GoldenEye. Guy Ritchie directed Sherlock Holmes. John McTiernan directed Die Hard.

The same relationship type (Directed) has many instances, each linking a Person entity to a Movie entity.

Cardinality: many-to-many

The cardinality of a relationship describes how many entities on each side can participate. Consider the relationship Directed between Person and Movie:

• One person can direct multiple movies.
• One movie can have multiple directors (e.g., the Wachowskis co-directing The Matrix).

This is a many-to-many relationship: any Person can be related to zero or more Movies, and any Movie can be related to zero or more Persons.

In ER diagram notation, a many-to-many relationship has no arrows — just plain lines connecting the relationship diamond to the entities:

Recursive relationships

A relationship can connect an entity set to itself. This is a recursive (or self-referencing) relationship. For example, is_sibling relates a Person to another Person:

is_sibling is symmetric: if Alice is a sibling of Bob, then Bob is a sibling of Alice. Not all recursive relationships are symmetric — is_manager_of on an Employee entity is recursive but not symmetric.

Cardinality annotations

There are numerous notations for recording cardinality on ER diagrams: arrowheads, crow’s foot notation, UML multiplicities, (min, max) pairs, and more. The detailed syntax of these notations is not examinable in the Part IA course. What matters is understanding the concept of cardinality and being able to read and reason about the nature of a relationship:

The important skill is not the precise diagramming convention but the ability to look at a relationship and determine its cardinality from the real-world rules of the domain.

Participation constraints

Beyond cardinality (how many), there is the question of participation: must an entity participate, or can it exist independently?

• Total participation (double line): every entity in the set must participate in the relationship. Example: every Module must be offered by some Department.
• Partial participation (single line): an entity may exist without participating. Example: not every Person directs a Movie.

Participation is distinct from cardinality. A relationship can be many-to-one with total participation on the “many” side, partial on the “one” side, or any combination.

Summary

• Relationships (diamonds) connect entities and represent associations in the domain.
• Many-to-many relationships have no arrows; both sides can be associated with any number of entities on the other side.
• Recursive relationships connect an entity set to itself and may or may not be symmetric.
• Cardinality notation details are not examinable, but understanding the conceptual types (many-to-many, many-to-one, one-to-one) is essential.
• Participation constraints specify whether involvement in a relationship is mandatory or optional.

Relationship attributes

Relationships can carry attributes of their own — properties that belong to the association, not to either participating entity. In an ER diagram, relationship attributes are drawn as ovals connected to the relationship diamond.

Consider the Acted_In relationship between Person and Movie:

The attribute role describes the character an actor played — it belongs to the Acted_In relationship, not to the Person (a person can play many roles) nor to the Movie (a movie has many roles).

The modelling problem

A binary relationship with a simple attribute like role works well when an actor plays a single role in a given film. But what about Jennifer Lawrence playing both Raven and Mystique in X-Men: First Class?

The straightforward solution — storing multiple roles as a comma-separated string — is a multi-valued attribute. This violates the First Normal Form (1NF) rule of atomicity: each attribute value should be a single, indivisible value. Text processing at that level (parsing comma-separated lists in SQL) is an unspeakable data modelling sin. Queries become fragile, indexing is impossible, and aggregate operations collapse.

Ternary relationships

One solution is to promote role to a full entity and make Acted_In a ternary relationship:

This cleanly models the situation: Jennifer Lawrence has two distinct Acted_In instances — one linking her to X-Men: First Class via the role “Raven”, another via the role “Mystique”.

But this raises a philosophical question: is a “role” a real-world entity in its own right? The answer depends on the application. A casting agency might reasonably model Role as an independent entity with its own attributes (character name, age range, gender, whether it requires a specific accent). A simple film database might prefer to keep the model lighter.

Decomposition into binary relationships

An alternative is to decompose the ternary relationship into binary relationships using an artificial entity (sometimes called a reifying entity or an associative entity):

Casting is an artificial entity created purely to hold the relationship data. It has a synthetic key and carries the role attribute. This approach avoids ternary relationships altogether, at the cost of introducing an extra entity.

The textbook (Lemahieu 3.2.6) discusses a risk with this decomposition: data loss. When you decompose an $n$-ary relationship into binary relationships, you may lose the ability to enforce the constraint that a particular combination of entities must be unique. Two binary relationships can independently record the same pairings without detecting a duplicate ternary instance.

Attribute or entity?

Whether to model a concept as an attribute or as an entity connected by a new relationship depends on the scope of the data model. Consider ReleaseDate:

• If every movie has at most one release date (e.g., a local cinema database), a simple attribute on Movie works well.
• If the scope is global, movies have different release dates in different countries (UK: 24 November, US: 22 November, Japan: 15 December). In that case, ReleaseDate might need to be an entity related to both Movie and Country:

The guiding principle: when a property can have multiple values per entity, or when it has meaningful relationships of its own, it should be modelled as an entity. When it is a simple, single-valued fact about an entity in the current scope, an attribute suffices.

Summary

• Relationships can carry attributes that belong to the association, not to either participant.
• Multi-valued attributes violate 1NF and lead to fragile, unindexable queries.
• Ternary relationships (or decomposed binary relationships with artificial entities) solve the multi-valued attribute problem.
• Decomposing an $n$-ary relationship into binary relationships may introduce data loss — the inability to enforce uniqueness of combined entity instances.
• The choice between “attribute” and “entity” depends on scope: single-valued and simple is an attribute; multi-valued or independently meaningful is an entity.

Many-to-one relationships

A many-to-one relationship is shown with an arrow in the ER diagram. The arrow points from the “many” side to the “one” side: each entity on the “many” side is related to at most one entity on the “one” side.

Consider the relationship Works_In between Employee and Department:

The arrow points to Department, meaning every Employee is related to at most one Department. A Department, however, can have many Employees — the relationship is many-to-one.

Formally: a relationship $R$ is many-to-one between $T$ (the source) and $S$ (the target) when an arrow points from $T$ to $S$. For each entity $t \in T$, there is at most one entity $s \in S$ such that $(t, s) \in R$.

One-to-many relationships

One-to-many is simply the inverse of many-to-one. If Works_In is many-to-one from Employee to Department, then it is one-to-many from Department to Employee. No new concept is needed — the arrow just points in the opposite direction.

In practice, you usually orient the arrow to match the natural reading: “an Employee works in one Department” (arrow to Department), “a Department contains many Employees” (no arrow from Department).

One-to-one relationships

If a relationship is both many-to-one between $S$ and $T$ and many-to-one between $T$ and $S$ (that is, two arrows, one on each side), then it is one-to-one:

Each Person has at most one Passport; each Passport belongs to at most one Person.

One-to-one relationships seldom occur in well-designed databases because they often suggest that the two entities could reasonably be merged into a single table. Why separate Person and Passport if every Person has exactly one Passport and vice versa? A legitimate reason might be:

• Access control: passport data is more sensitive and stored in a separately encrypted table.
• Optionality: not every Person has a Passport, and storing many NULL columns is wasteful.
• Modularity: the Passport table is managed by a different subsystem or microservice.

What “one-to-one” does NOT mean

A common confusion: “one-to-one cardinality” does not mean a 1-to-1 correspondence in the mathematical sense (a bijection). It does not require that every entity on one side must correspond to exactly one entity on the other side. Participation is separate from cardinality.

Consider this valid database instance under the Has relationship (one-to-one between Person and Passport):

The constraint enforced by “one-to-one” is: no Person maps to more than one Passport, and no Passport maps to more than one Person. It does not enforce that every Person has a Passport, nor that every Passport has a Person.

A violation of one-to-one cardinality would be:

Alice has two passports — this breaks the rule that each Person relates to at most one Passport.

Formal notation

There are many competing diagrammatic notations for cardinality. The Part IA course does not require memorising any particular convention in detail. Here is a brief survey for awareness:

The detailed syntax of crow’s foot, UML multiplicities, and (min, max) notation is not examinable. What matters is the ability to read a diagram, identify the nature of the relationship, and reason about whether a given database instance satisfies the cardinality constraints.

Summary

• Many-to-one: an arrow points from the “many” side to the “one” side. Each source entity relates to at most one target entity.
• One-to-many: the inverse of many-to-one.
• One-to-one: arrows on both sides. Rare in practice; often signals entities that could be merged.
• One-to-one cardinality does not imply a bijection — participation is separate.
• Diagrammatic notations vary, but the conceptual understanding of cardinality is what matters for schema design.

Definition

A weak entity is an entity whose existence depends on the existence of another entity, called its identifying entity (or owner entity). A weak entity cannot be uniquely identified by its own attributes alone; it requires the identifying entity’s key as part of its identification.

In ER diagrams:

• Weak entities are drawn as double-bordered rectangles.
• The identifying relationship is drawn as a double-bordered diamond.
• The weak entity’s partial key (discriminator) is underlined with a dashed line.

Example: AlternativeTitle

Consider a film database. A Movie has a unique movie_id. The same movie might be released under different titles in different territories:

An AlternativeTitle does not exist independently; it exists only in relation to a specific Movie. If the Movie is deleted, all its alternative titles should be deleted too.

The attribute alt_id (e.g., 1, 2, 3 within each movie) is a discriminator, not a key. To uniquely identify an AlternativeTitle, you need both:

$(\text{movie\_id}, \text{alt\_id})$

Neither attribute alone suffices:

• alt_id = 1 could refer to the first alternative title of any movie.
• movie_id = tt0848228 tells you which movie, but not which of its several alternative titles.

The discriminator is unique only within the scope of a single identifying entity. The ER diagram looks like:

The double border on AlternativeTitle and the double diamond on HasAltTitle signal the weak entity pattern.

Relational implementation

When a weak entity is mapped to a relational schema, its table includes the identifying entity’s primary key as part of its own composite primary key, plus a foreign key constraint:

CREATE TABLE AlternativeTitle (
    movie_id    INTEGER NOT NULL,
    alt_id      INTEGER NOT NULL,
    alt_title   TEXT NOT NULL,
    territory   TEXT,
    PRIMARY KEY (movie_id, alt_id),
    FOREIGN KEY (movie_id) REFERENCES Movie(movie_id)
        ON DELETE CASCADE
);

The composite primary key (movie_id, alt_id) enforces uniqueness of alternative titles within each movie. The ON DELETE CASCADE clause reflects the existential dependency: when the parent Movie is deleted, all its AlternativeTitles are automatically removed.

Identifying vs. non-identifying relationships

Not every foreign key relationship implies a weak entity. A non-identifying relationship is one where the child entity has its own independent primary key and the foreign key is just an attribute:

CREATE TABLE Employee (
    employee_id  SERIAL PRIMARY KEY,
    name         TEXT NOT NULL,
    dept_id      INTEGER REFERENCES Department(dept_id)  -- non-identifying
);

Here, Employee is a strong entity: it is identified by employee_id alone. The dept_id foreign key merely records which department the employee belongs to, but Employee could exist even if Department were deleted (assuming nullable foreign key or ON DELETE SET NULL).

When to use weak entities

Weak entities are appropriate when:

1. Existential dependency: the entity cannot meaningfully exist without the owner.
2. Identification dependency: the entity’s own attributes are insufficient for a global unique key.
3. Cascade semantics: deletion of the owner should logically delete the owned entities.

Common examples:

In each case, the weak entity makes no sense without its owner — a LineItem without an Order is meaningless, and its line_number = 1 is only meaningful within the scope of a specific order.

Summary

• A weak entity depends on an identifying (owner) entity for its existence and identification.
• Drawn with double borders; the identifying relationship uses a double diamond.
• A discriminator (partial key) is unique only within the scope of one owner.
• In SQL, the weak entity’s table uses a composite primary key (owner’s key + discriminator) with a foreign key constraint.
• Weak entities differ from ordinary foreign-key relationships: the owner’s key is part of the weak entity’s own identity, not just an attribute.

The IsA relationship

An entity hierarchy (also called an IsA hierarchy, generalisation/specialisation, or superclass/subclass) models the situation where one entity type is a refinement of another. The sub-entity (child) is a specific kind of the super-entity (parent).

Consider a university database:

Temporary_Employee and Contract_Employee are both kinds of Employee. They inherit all attributes (including the key employee_id) and all relationships of the parent entity. The sub-entities add attributes specific to their subtype (hourly_rate for temporary staff, contract_id for contract staff).

Key properties

There are several important properties of the IsA hierarchy:

1. Attribute inheritance: sub-entities automatically possess all attributes of their parent. There is no need to repeat employee_id or name in the sub-entity definitions.
2. Relationship inheritance: any relationship the parent participates in is also inherited by the sub-entities. If Employee has a Works_In relationship with Department, then both Temporary_Employee and Contract_Employee also have that relationship.
3. No separate key: sub-entities do not have their own key or discriminator. They are identified by the parent’s key. A Temporary_Employee with employee_id = 142 is the same real-world entity as the Employee with employee_id = 142.
4. Multiple inheritance: an entity can have multiple parent types (though this is rare in practice and some modelling disciplines discourage it).

Coverage constraints

An IsA hierarchy may specify whether the sub-entities cover all possible instances of the parent:

There may also be a disjointness constraint:

Relational mapping strategies

There are three standard approaches for mapping an entity hierarchy to relational tables. Choosing among them involves trade-offs between query complexity, storage efficiency, and constraint enforcement.

Strategy 1: Single table with type tag

Put all attributes — parent and all sub-entities — into one table, with a discriminator column and nullable sub-entity columns:

CREATE TABLE Employee (
    employee_id  SERIAL PRIMARY KEY,
    name         TEXT NOT NULL,
    emp_type     TEXT NOT NULL CHECK (emp_type IN ('temp', 'contract')),
    hourly_rate  NUMERIC,       -- NULL for contract employees
    contract_id  TEXT           -- NULL for temporary employees
);

Strategy 2: Separate tables for sub-entities

One table for the parent, and one table for each sub-entity containing only the sub-entity-specific columns, with the parent’s key as both primary key and foreign key:

CREATE TABLE Employee (
    employee_id  SERIAL PRIMARY KEY,
    name         TEXT NOT NULL
);

CREATE TABLE Temporary_Employee (
    employee_id  INTEGER PRIMARY KEY REFERENCES Employee(employee_id),
    hourly_rate  NUMERIC NOT NULL
);

CREATE TABLE Contract_Employee (
    employee_id  INTEGER PRIMARY KEY REFERENCES Employee(employee_id),
    contract_id  TEXT NOT NULL
);

Strategy 3: One table per concrete sub-entity

Separate tables for each concrete sub-entity, each containing all inherited attributes plus its own specific attributes. No table for the abstract parent:

CREATE TABLE Temporary_Employee (
    employee_id  SERIAL PRIMARY KEY,
    name         TEXT NOT NULL,
    hourly_rate  NUMERIC NOT NULL
);

CREATE TABLE Contract_Employee (
    employee_id  SERIAL PRIMARY KEY,
    name         TEXT NOT NULL,
    contract_id  TEXT NOT NULL
);

Multi-level hierarchies

IsA hierarchies can extend to multiple levels. For example:

Employee
  └── Academic_Staff
        ├── Lecturer
        └── Professor
  └── Administrative_Staff
        ├── Registrar
        └── Technician

The same mapping strategies apply recursively. A multi-level hierarchy mapped with Strategy 2 would require joins through several tables to reconstruct a complete entity; the performance cost must be weighed against the schema clarity.

Summary

• An IsA hierarchy models generalisation/specialisation: sub-entities inherit attributes and relationships from the parent.
• Sub-entities have no independent key; they are identified by the parent’s key.
• Coverage constraints (total vs. partial) and disjointness constraints (disjoint vs. overlapping) refine the hierarchy.
• Three mapping strategies exist: single table with type tags, separate sub-entity tables, or one table per concrete sub-entity.
• The choice involves trade-offs: query complexity, NULL handling, constraint enforcement, and key uniqueness.

Codd’s radical idea

In the 1970s, Edgar Codd proposed a simple but powerful idea: give users a model of data and a language for manipulating that data which is completely independent of the details of its representation and implementation. This model is based on mathematical relations.

By separating the logical view of data from the physical storage, Codd’s relational model decouples development of the DBMS from the development of database applications. Users query the database in terms of the relations they see; the DBMS decides how to execute those queries on whatever storage structures it uses internally.

Cartesian products

Let $S$ and $T$ be sets. The Cartesian product of $S$ and $T$ is:

$S \times T = \{(s, t) \mid s \in S, t \in T\}$

That is, the set of all ordered pairs where the first element comes from $S$ and the second from $T$.

Example.

$\{A, B\} \times \{3, 4, 5\} = \{(A, 3), (A, 4), (A, 5), (B, 3), (B, 4), (B, 5)\}$

Six pairs total, since $|S \times T| = |S| \times |T| = 2 \times 3 = 6$.

Binary relations

A binary relation over $S \times T$ is any set $R$ with:

$R \subseteq S \times T$

That is, a relation is simply a subset of the Cartesian product. In the example above, one possible relation is:

$R = \{(A, 3), (B, 4), (B, 5)\}$

This particular $R$ contains three of the six possible pairs. There is no requirement that every element of $S$ or $T$ appears in $R$, nor that any particular pairing pattern holds.

Domains and database relations

In database parlance, the sets $S$ and $T$ are referred to as domains. A domain is the set of all possible values that a given column may take (the type of the column).

We are interested in finite relations $R$ that are explicitly stored in the database. This distinguishes database relations from mathematical relations studied in logic, such as those arising from integer linear programming constraints, where relations may be infinite or defined by a predicate rather than explicitly enumerated.

Why finite relations?

A database stores a finite number of rows. The relational model is grounded in set theory, but the sets we work with are finite and explicit — we can inspect every tuple, insert and delete tuples, and compute results by applying operations to the tuples themselves. The theory of relational algebra (covered in later notes) relies on relations being sets of known tuples.

Summary

• Codd’s relational model separates the logical model of data from physical implementation.
• A Cartesian product $S \times T$ is the set of all ordered pairs from $S$ and $T$.
• A binary relation over $S \times T$ is any subset $R \subseteq S \times T$.
• In databases, $S$ and $T$ are called domains; relations are finite and explicitly stored.

From binary to n-ary

A binary relation involves two domains. Database tables rarely have only two columns. The generalisation is straightforward: if we have $n$ sets (domains) $S_1, S_2, \ldots, S_n$, then an n-ary relation $R$ is:

$R \subseteq S_1 \times S_2 \times \cdots \times S_n = \{(s_1, s_2, \ldots, s_n) \mid s_i \in S_i\}$

Each element of $R$ is an n-tuple, a sequence of $n$ values drawn from the respective domains.

Tabular presentation

N-ary relations are naturally displayed as tables:

Here $n = 3$. Each row is a tuple (Alice, abc123, 20). The three columns correspond to the three domains: string, string, integer.

The problem with positional columns

In the mathematical definition, columns are identified by position: the first column corresponds to $S_1$, the second to $S_2$, and so on. In a query language, writing “select column 3” is error-prone and unreadable.

Named columns and attribute names

Database relations use named columns: we associate a name $A_i$ (called an attribute name) with each domain $S_i$.

Instead of tuples $(s_1, s_2, \ldots, s_n)$, we use records: sets of pairs each associating an attribute name $A_i$ with a value in domain $S_i$. A record is:

$\{(A_1, s_1), (A_2, s_2), \ldots, (A_n, s_n)\}$

where $s_i \in S_i$.

Column order does not matter

In a mathematical tuple, the order of components matters: $(A, 3) \neq (3, A)$. In a record with named attributes, the order of the pairs does not matter:

$\{(\text{name}, \text{Alice}), (\text{age}, 20)\} = \{(\text{age}, 20), (\text{name}, \text{Alice})\}$

This matches how SQL works: SELECT name, age FROM Students and SELECT age, name FROM Students both produce valid results; the column order in the output is determined by the SELECT clause, not by any underlying ordering.

Schema notation

A database relation $R$ is therefore defined as a finite set:

$R \subseteq \{\{(A_1, s_1), (A_2, s_2), \ldots, (A_n, s_n)\} \mid s_i \in S_i\}$

The schema of $R$ is the set of attribute-name/domain pairs. Schema notation:

$R(A_1 : S_1,\; A_2 : S_2,\; \ldots,\; A_n : S_n)$

Example schema.

$\text{Students}(\text{name} : \text{string},\; \text{sid} : \text{string},\; \text{age} : \text{integer})$

Row order

Just as column order does not matter, row order does not matter in the relational model. A relation is a set of records. SQL results are unordered unless you explicitly include ORDER BY.

In practice, rows are stored in some physical order on disk (often a B-tree on the primary key), but the relational model does not expose or rely on that ordering.

Summary

• An n-ary relation generalises binary relations to $n$ domains.
• Database relations use named columns (attribute names) rather than positional columns.
• Column order and row order do not matter at the logical level.
• A schema declares the attribute names and their types.

Definition

A relational database query language takes a collection of relation instances $R_1, R_2, \ldots, R_k$ as input and returns a single relation instance as output:

$Q(R_1, R_2, \ldots, R_k)$

To meet Codd’s goals, the query language should be high-level: the user specifies what data they want, not how to retrieve it. The language is independent of physical data representation — indexes, file structures, and access paths are managed internally by the DBMS.

Relational Algebra (RA)

The Relational Algebra is the formal basis for relational query languages. It provides a small set of operations that take relations as input and produce relations as output. Because each operation returns a relation, operations can be composed to form complex queries.

Abstract syntax

Where:

• $p$ is a Boolean predicate over attribute values (e.g., $A > 12$, $B = \text{'CS'}$).
• $X$ is a set of attribute names to keep.
• $M$ is a renaming map, e.g., $\{B \mapsto B'\}$.

Well-formedness conditions

A query $Q$ must be well-formed: all column names of the result must be distinct. This imposes constraints on certain operators:

• In $Q_1 \times Q_2$, the two sub-queries cannot share any column names (they must be disjoint).
• In $Q_1 \cup Q_2$, $Q_1 \cap Q_2$, and $Q_1 - Q_2$, the two sub-queries must share all column names (they must be union-compatible).

If needed, $\rho$ is used to rename columns to satisfy these conditions.

SQL

SQL (Structured Query Language) is the dominant relational query language. It originated at IBM in the early 1970s and has been standardised across multiple revisions:

SQL contains several sub-languages:

• Query Language (QL): SELECT, FROM, WHERE, GROUP BY, etc.
• Data Definition Language (DDL): CREATE TABLE, ALTER TABLE, DROP TABLE.
• Data Manipulation Language (DML): INSERT, UPDATE, DELETE.
• Data Control Language (DCL): GRANT, REVOKE.
• System Administration Language: backup, restore, user management.

Why study RA if we have SQL?

1. RA’s simple syntax and semantics make it easier to reason about complex queries. Understanding what a query means in RA helps debug SQL.
2. The RA lends itself to Tripos questions. It provides a compact, unambiguous notation for defining queries — ideal for exam settings.
3. SQL is vast and continually evolving. RA captures its core relational logic in a handful of operators.

Summary

• A query language maps a collection of relation instances to a single relation instance.
• RA provides the formal mathematical basis: six core operations plus renaming.
• SQL is the practical language, standardised from SQL-86 through SQL:2023.
• RA is studied for clarity and exam support; SQL is used in practice.

Selection ($\sigma$)

Selection picks the rows of a relation that satisfy a Boolean predicate. It does not change the columns or their names.

$\sigma_{\text{predicate}}(R)$

Example. Given a relation Employees(name, department, salary):

$\sigma_{\text{salary} > 50000}(\text{Employees})$

returns all employees earning more than 50,000. The result has the same schema as Employees.

SQL translation.

SELECT DISTINCT *
FROM Employees
WHERE salary > 50000;

The asterisk denotes all fields — there is no projection. DISTINCT is needed because SQL defaults to multiset semantics (see Lecture 7), whereas RA operates on sets.

Predicates can be combined with $\land$, $\lor$, $\neg$:

$\sigma_{\text{salary} > 50000\;\land\;\text{department} = \text{'CS'}}(\text{Employees})$

SQL:

SELECT DISTINCT *
FROM Employees
WHERE salary > 50000 AND department = 'CS';

Projection ($\pi$)

Projection picks specified columns and eliminates duplicate rows. It corresponds to the mathematical operation of projecting a relation onto a subset of its attributes.

$\pi_{A_1, A_2, \ldots, A_k}(R)$

Example.

$\pi_{\text{name}, \text{department}}(\text{Employees})$

returns all (name, department) pairs in the database, with duplicates removed. If two employees share the same name and department, the projection contains that pair only once.

SQL translation.

SELECT DISTINCT name, department
FROM Employees;

Note the misleading keyword: SELECT in SQL performs projection, not selection. In RA, projection is $\pi$, selection is $\sigma$. The SQL WHERE clause corresponds to RA $\sigma$ (selection); the SQL SELECT clause corresponds to RA $\pi$ (projection).

A projection with no selection:

SELECT DISTINCT name, department FROM Employees;
-- no WHERE clause -- so no RA selection, despite the 'SELECT' keyword

Renaming ($\rho$)

Renaming changes column names. It does not alter data.

$\rho_{\{A \mapsto C,\; B \mapsto D, \ldots\}}(R)$

Example.

$\rho_{\{\text{name} \mapsto \text{fullName},\; \text{salary} \mapsto \text{annualPay}\}}(\text{Employees})$

produces a relation with columns fullName, department, annualPay instead of name, department, salary.

SQL translation.

SELECT name AS fullName, department, salary AS annualPay
FROM Employees;

SQL implements renaming with the AS keyword. Renaming is frequently needed to make schemas compatible for set operations or products.

Combined use

RA operators compose naturally. To find the departments of highly-paid employees:

$\pi_{\text{department}}(\sigma_{\text{salary} > 50000}(\text{Employees}))$

SQL:

SELECT DISTINCT department
FROM Employees
WHERE salary > 50000;

The RA expression reads inside-out: first filter rows, then project columns and deduplicate. SQL reads more like linear prose: decide what columns, from what table, subject to what condition.

Operator precedence (convention)

In RA expressions, unary operators ($\sigma$, $\pi$, $\rho$) bind tighter than binary operators ($\times$, $\cup$, $-$, $\cap$). When writing queries, use parentheses to make the evaluation order explicit.

Summary table

Union-compatible schemas

For union, intersection, and difference to be defined, the two relations must have union-compatible schemas: the same number of columns, with the same column names and the same (or compatible) domain types.

Given $R(A, B, C)$ and $S(A, B, C)$, the set operations are well-formed. If the schemas differ, $\rho$ must be used first to rename columns.

Union ($\cup$)

$R \cup S$ returns all tuples that appear in $R$ or in $S$ (or both). Since RA operates on sets, duplicates are eliminated.

$R \cup S = \{t \mid t \in R \lor t \in S\}$

SQL.

(SELECT * FROM R)
UNION
(SELECT * FROM S);

SQL’s UNION eliminates duplicates by default (set semantics). To keep duplicates, use the non-standard UNION ALL.

Intersection ($\cap$)

$R \cap S$ returns all tuples that appear in both $R$ and $S$.

$R \cap S = \{t \mid t \in R \land t \in S\}$

SQL.

(SELECT * FROM R)
INTERSECT
(SELECT * FROM S);

Intersection can be expressed in terms of difference:

$R \cap S = R - (R - S) = S - (S - R)$

In practice, SQL’s INTERSECT is clearer and the optimiser will handle the equivalent transformation if needed.

Difference ($-$)

$R - S$ returns all tuples that appear in $R$ but not in $S$.

$R - S = \{t \mid t \in R \land t \notin S\}$

SQL.

(SELECT * FROM R)
EXCEPT
(SELECT * FROM S);

Note: SQL uses the keyword EXCEPT rather than MINUS (some other database systems use MINUS).

Difference is not commutative: $R - S \neq S - R$ in general.

Set semantics vs multiset semantics

The RA operators work over sets of tuples. A tuple that appears multiple times in a source table appears at most once in the RA result. This is a key distinction:

SQL defaults to multiset (bag) semantics. The DISTINCT keyword forces set semantics. This distinction is covered in detail in Lecture 7. For now, assume that SQL queries in these notes use SELECT DISTINCT where needed to match RA set behaviour.

Worked example

Given relations:

$R$:

$S$:

Union $R \cup S$:

Intersection $R \cap S$:

Difference $R - S$:

Difference $S - R$:

Summary

• Union, intersection, and difference require union-compatible schemas.
• All three eliminate duplicates in RA (set semantics).
• SQL: UNION, INTERSECT, EXCEPT.
• Difference is non-commutative; intersection can be expressed via difference.

Product ($\times$)

The RA product is based on the Cartesian product but adapted for database relations. Given $R(A_1, \ldots, A_m)$ and $S(B_1, \ldots, B_n)$, the product $R \times S$ returns a relation over the combined attributes $A_1, \ldots, A_m, B_1, \ldots, B_n$.

Mathematically, the Cartesian product of two relations (as sets of tuples) would return pairs of tuples:

$\{(t, u) \mid t \in R, u \in S\}$

The RA product instead returns tuples formed by concatenating the fields of each pair:

$\{t \cdot u \mid t \in R, u \in S\}$

where $\cdot$ denotes tuple concatenation.

Example. Suppose:

$R$:

$S$:

$R \times S$:

If $R$ has $m$ rows and $S$ has $n$ rows, the product has $m \times n$ rows.

Column name disjointness

A critical constraint: the schemas of $R$ and $S$ must have disjoint column names. If both relations have a column called id, the product would have two columns both called id, which is not a valid relation.

When column names overlap, renaming is required first. For example, if $R(A, B)$ and $S(B, C)$ share column $B$:

$\rho_{\{B \mapsto B'\}}(S)$

produces $S'(B', C)$, and then:

$R \times S'$

produces a valid relation over $(A, B, B', C)$.

SQL translations

There are two equivalent SQL formulations of the product:

Explicit syntax (preferred).

SELECT A, B, C, D
FROM R CROSS JOIN S;

Implicit syntax (comma-separated tables).

SELECT A, B, C, D
FROM R, S;

Both produce the same result. The CROSS JOIN form makes the intent more explicit.

The product is rarely used alone

The product itself is of limited practical use. Its value comes from combining it with selection to form a join. Selecting the product rows where matching columns are equal gives the natural join or equi-join:

$\sigma_{B = B'}(R \times \rho_{\{B \mapsto B'\}}(S))$

This pattern is so common that SQL provides a dedicated JOIN ... ON syntax, and RA has the derived $\bowtie$ (natural join) operator (see following note).

Combining product with renaming

When writing RA expressions involving product, the standard pattern is:

1. Rename overlapping columns in one or both sub-queries with $\rho$.
2. Apply $\times$ to the renamed sub-queries.
3. Apply $\sigma$ to select matching rows.
4. Apply $\pi$ to remove duplicate columns.

Example. Find all pairs of students and lecturers in the same college:

$\pi_{\text{name}, \text{lname}}(\sigma_{\text{Students.college} = \text{Lecturers.college}}(\text{Students} \times \rho_{\{\text{name} \mapsto \text{lname},\; \text{college} \mapsto \text{lcollege}\}}(\text{Lecturers})))$

But this is verbose. The natural join $\bowtie$ (next note) simplifies it.

Summary

• $R \times S$ concatenates tuples; the result has $|R| \times |S|$ rows.
• Column names of $R$ and $S$ must be disjoint; use $\rho$ when they overlap.
• SQL: CROSS JOIN or comma-separated tables in FROM.
• The product is typically combined with selection to form a join.

Definition

The natural join (denoted $\bowtie$) is the RA operator that combines two relations by equating columns with the same name and eliminating duplicate columns from the output.

Schema notation

When we write the schema of $R$ as $R(A, B)$, we mean that the schema is $R(A \cup B)$ where $A$ and $B$ are disjoint sets of attributes. The notation splits the schema into parts for clarity: $A$ are the attributes unique to $R$, $B$ are the shared attributes.

Formal definition

Given $R(A, B)$ and $S(B, C)$, where $B$ is the set of attributes shared by both relations, the natural join $R \bowtie S$ is a relation over attributes $A \cup B \cup C$ defined as:

$R \bowtie S = \{t \mid \exists u \in R,\; v \in S,\; u.[B] = v.[B] \land t = u.[A] \cup u.[B] \cup v.[C]\}$

That is: for every pair of tuples $(u, v)$ from $R$ and $S$ where the shared attributes match ($u.[B] = v.[B]$), the result tuple $t$ combines $u$‘s unique attributes ($u.[A]$), the shared attributes ($u.[B]$, which equals $v.[B]$), and $v$‘s unique attributes ($v.[C]$).

The shared attributes $B$ appear once in the result, not twice.

RA expression for natural join

The natural join can be expressed in terms of primitive RA operators:

$R \bowtie S = \pi_{A, B, C}\left(\sigma_{B = B'}\left(R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)\right)\right)$

The steps:

1. Rename the shared columns in $S$ to distinguish them from those in $R$: $\rho_{\vec{B} \mapsto \vec{B'}}(S)$.
2. Take the Cartesian product: $R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)$.
3. Select rows where the shared columns are equal: $\sigma_{B = B'}(\cdots)$.
4. Project to remove the duplicate columns: $\pi_{A, B, C}(\cdots)$.

The notation $B = B'$ abbreviates the conjunction of equalities on each attribute in $B$: $u.B_1 = v.B'_1 \land \cdots \land u.B_n = v.B'_n$.

SQL translation

SQL provides NATURAL JOIN:

SELECT *
FROM R
NATURAL JOIN S;

This automatically equates all columns with the same name. More commonly, explicit joins are used:

SELECT *
FROM R
INNER JOIN S ON R.B = S.B;

Worked example

Students(name, sid, cid) — student name, ID, and the college ID they belong to.

Colleges(cid, cname) — college ID and college name.

Students $\bowtie$ Colleges:

The join matches on the shared cid column. Alice and Carol are both matched to Churchill. Bob is matched to King’s. College C3 (Trinity) has no students, so it does not appear in the result. If a student had a cid with no matching college, that student would also be excluded.

Join variations in SQL

Beyond the natural join, SQL supports several join types. These go beyond core RA but are essential in practice:

When NULL values are present in the data, the behaviour of joins becomes more nuanced — see the textbook (Lemahieu 7.3.1.5) for details.

Join conditions beyond equality

The natural join only handles equality on shared columns. SQL generalises this with arbitrary join predicates:

SELECT *
FROM Employees e
JOIN Departments d ON e.dept_id = d.dept_id AND e.salary > d.budget;

In RA, a non-equality join must be expressed via product and selection:

$\sigma_{\text{dept\_id} = \text{dept\_id}' \;\land\; \text{salary} > \text{budget}}(R \times \rho_{\{\ldots\}}(S))$

Summary

• $R \bowtie S$ equates shared columns and eliminates duplicates.
• RA definition: $\pi_{A,B,C}(\sigma_{B=B'}(R \times \rho_{\vec{B} \mapsto \vec{B'}}(S)))$.
• SQL: NATURAL JOIN or INNER JOIN ... ON.
• Outer joins (LEFT, RIGHT, FULL) preserve unmatched rows with NULLs.
• Non-equality join predicates require product + selection in RA.

The naive approach

Consider a directed E/R model with two entity sets — Movies and People — connected by a Directed relationship. A naive implementation puts everything into a single table:

DirectedComplete(movie_id, title, year, person_id, name, birthYear)

This seems convenient: one query, one table, all the data. But it introduces severe problems.

Data redundancy

Each row in DirectedComplete stores a (movie, director) pair. If a director has directed five films, their name and birth year appear in five separate rows. This duplication is the root cause of the three classical update anomalies.

Insertion anomaly

An insertion anomaly occurs when we cannot insert a legitimate piece of data without also providing data that we do not yet have — or that is entirely unrelated.

The schema forces us to fabricate nonexistent data or leave it incomplete — both unacceptable.

Deletion anomaly

A deletion anomaly occurs when deleting one fact inadvertently destroys another, independent fact.

Suppose we delete the last film directed by a particular person from the table. We lose not only the fact that the person directed that film, but also the person’s name and birth year — information that we might still need. The person still exists in the real world, but they vanish from our database.

Update anomaly

An update anomaly occurs when a single conceptual change requires multiple physical updates — and failing to apply them all leaves the database in an inconsistent state.

If a director’s name is misspelled in the database, we must correct it in every row where they appear. A transaction that updates only some of those rows (perhaps because of a bug, a partial failure, or concurrent access) creates inconsistent data: the same person appears with two different names in different rows.

This is not merely a theoretical concern. In a production system, a transaction that must scan and lock many rows to make a conceptually simple update degrades throughput and increases the likelihood of deadlocks.

The “one fact, one place” principle

All three anomalies stem from the same root cause: a single fact is stored in multiple places. The fundamental rule of good relational design is:

Each fact should be stored in exactly one place in the database.

When facts are duplicated, any update to that fact must be propagated to all copies. The database system cannot do this automatically — it is the schema designer’s responsibility to avoid duplication in the first place.

Performance implications

Beyond correctness, data redundancy has direct performance consequences:

In a database supporting many concurrent read and write operations, the combination of lock contention and write amplification from redundant schemas can be catastrophic for throughput.

The remedy

The solution is to decompose the single big table into smaller tables — one per entity set and one per relationship. This is the subject of the next note.

Summary

• A single-table implementation of an E/R model introduces data redundancy.
• Redundancy causes insertion, deletion, and update anomalies.
• The principle “one fact, one place” guides good schema design.
• Redundancy also harms write throughput and increases lock contention.
• The answer is to break tables down.

The decomposition strategy

To eliminate redundancy, we decompose DirectedComplete into three tables: one for each entity set and one for the relationship.

Movies(movie_id, title, year)
People(person_id, name, birthYear)
Directed(movie_id, person_id)

Entity tables

Each E/R entity becomes a relational table. The entity’s attributes become the table’s columns. The entity’s key becomes the table’s primary key.

Each row in Movies stores exactly one movie. Each row in People stores exactly one person. No duplication.

Relationship tables

Each E/R relationship also becomes a relational table. For the Directed relationship (a many-to-many relationship between Movies and People), we create:

Directed(movie_id, person_id)

The key of Directed is the combination (movie_id, person_id). This is called an “all-key” table because every column is part of the primary key. This pattern is standard for many-to-many relationships: the relationship table has no attributes of its own beyond the foreign keys to the participating entities.

A concrete example

Suppose the database contains the following:

Movies:

People:

Directed:

Each fact is stored in exactly one place. Lana Wachowski’s name appears only once, in the People table. If we need to correct it, we update one row.

Reconstructing the original view

The original DirectedComplete table can be reconstructed using a SQL JOIN:

SELECT movie_id, title, year, person_id, name, birthYear
FROM movies
  JOIN directed ON directed.movie_id = movies.movie_id
  JOIN people ON people.person_id = directed.person_id;

The join combines the three tables on their common key columns, producing exactly the same columns we had in DirectedComplete — but without the redundancy.

The fundamental trade-off

The decomposed design is the “good” design: we accept the cost of writing JOIN queries in exchange for eliminating redundancy and its associated anomalies. JOINs are the price we pay for a well-normalised schema.

Both entities and relationships are tables

A key insight: in the relational model, both E/R entities and E/R relationships are implemented as tables. There is no separate construct for relationships. A relationship table is distinguished only by its content — it contains foreign keys referencing entity tables.

Summary

• Decompose a big table into one table per entity set and one per relationship.
• Entity tables store attributes; relationship tables store foreign keys.
• Many-to-many relationships produce all-key tables.
• JOINs reconstruct the combined data when needed.
• The cost of JOINs is the price of eliminating redundancy and anomalies.

Defining a superkey

Let $R(X)$ be a relational schema, where $X$ is the set of attributes (columns) of $R$. Let $Z \subseteq X$ be a subset of those attributes.

$Z$ is a superkey for $R$ if, for any two records $u$ and $v$ in any valid instance of $R$:

$u[Z] = v[Z] \implies u[X] = v[X]$

In words: if two records agree on all attributes in $Z$, they must be the same record. No two distinct rows in a valid instance of $R$ can have identical values for all attributes in $Z$.

The entire set of attributes $X$ is trivially a superkey for any relation, since $u[X] = v[X]$ tautologically implies $u[X] = v[X]$.

Defining a key

$Z$ is a key (or candidate key) for $R$ if:

1. $Z$ is a superkey for $R$, and
2. No proper subset of $Z$ is a superkey for $R$.

The second condition is minimality: you cannot remove any attribute from $Z$ and still have a superkey. A key is a minimal superkey.

Notation

The notation $R(\underline{Z}, Y)$ indicates that $Z$ is a key for $R$, and that $R$‘s full set of attributes is $Z \cup Y$. The underline marks the key.

For a table with multiple candidate keys, one is designated as the primary key. The others remain alternate keys.

Example: Movies table

Schema: Movies(movie_id, title, year)

• $\{\text{movie\_id}\}$ is a superkey: no two movies share the same movie_id.
• $\{\text{movie\_id}\}$ is also a key: removing the only element leaves the empty set, which is not a superkey.
• $\{\text{movie\_id}, \text{title}\}$ is a superkey but not a key (it is not minimal: you can drop title).
• $\{\text{title}, \text{year}\}$ might be a key if we assume no two films share both title and year — but this is a design choice, not a formal guarantee.

Example: Directed table (all-key)

Schema: Directed(movie_id, person_id)

• $Z_1 = \{\text{movie\_id}\}$: not a superkey. A film can have multiple directors, so $u[\text{movie\_id}] = v[\text{movie\_id}]$ does not force $u = v$.
• $Z_2 = \{\text{person\_id}\}$: not a superkey. A person can direct multiple films.
• $Z_3 = \{\text{movie\_id}, \text{person\_id}\}$: is a superkey. A given (movie, person) pair appears at most once in the Directed relationship.
• $Z_3$ is also a key: neither subset alone is a superkey.
• No proper subset of $Z_3$ is a superkey, so $Z_3$ is minimal. This is an all-key table.

Example: People table

Schema: People(person_id, name, birthYear)

• $\{\text{person\_id}\}$ is a key (assuming synthetic keys).
• $\{\text{name}, \text{birthYear}\}$ might be a key if name+birthYear is unique — but it is not safe to rely on.

Multiple keys

A relation can have more than one key. A table of UK citizens might have both:

• $\{\text{ni\_number}\}$ (National Insurance number)
• $\{\text{person\_id}\}$ (synthetic key)

Both are keys (minimal superkeys), and either could be chosen as primary key. In practice, synthetic keys are preferred (see the note on synthetic keys in Lecture 2).

Formal property: every relation has a key

Since the set of all attributes $X$ is always a superkey, we can always find a key by starting with $X$ and iteratively removing attributes while the result remains a superkey. The resulting minimal subset is a key. In the worst case, $X$ itself is the only key (e.g., an all-key relationship table).

Superkey vs. key summary

Connection to normalisation

The concept of a key becomes critical in normalisation (Lecture 5). A relation is in a normalised form if all non-key attributes are functionally dependent on the key — and no other set of attributes. This is a preview: the key is the anchor for all other data in the row.

Summary

• A superkey is any set of attributes that uniquely identifies rows.
• A key is a minimal superkey.
• $\{\text{all attributes}\}$ is always a superkey.
• All-key tables occur for many-to-many relationship tables.
• Every relation has at least one key.
• The key is the foundation of normalisation: all data should depend on the key, the whole key, and nothing but the key.

Motivation

Once we decompose a schema into multiple tables, we need a mechanism to express that a value in one table refers to a value in another. This is the role of the foreign key. Think of a foreign key as a sort of pointer — it does not store the target data, only the identifier that locates it.

Defining a foreign key

Let $R(\underline{Z}, Y)$ be a relational schema where $Z$ is the key of $R$. Let $S(W)$ be another relational schema, and suppose $Z \subseteq W$ — that is, the attributes of $Z$ appear as a subset of the attributes of $S$.

We say that $Z$ represents a foreign key in $S$ referencing $R$ if, for any valid instance of the database:

$\pi_Z(S) \subseteq \pi_Z(R)$

In words: every value of $Z$ that appears in table $S$ must also appear as a key value in table $R$. The projection of $S$ onto $Z$ is a subset of the projection of $R$ onto $Z$.

Referential integrity

A database is said to have referential integrity when all foreign key constraints are satisfied. The DBMS enforces these constraints: any INSERT or UPDATE that would cause a foreign key value to reference a nonexistent target is rejected.

Referential integrity is one of the two fundamental integrity constraints of the relational model. The other is entity integrity: no part of a primary key may be NULL.

Example: Has_Genre

Consider the many-to-many relationship between Movies and Genres:

Has_Genre(movie_id, genre_id)

This table has two foreign key constraints:

Formally:

$\pi_{\text{movie\_id}}(\text{Has\_Genre}) \subseteq \pi_{\text{movie\_id}}(\text{Movies})$ $\pi_{\text{genre\_id}}(\text{Has\_Genre}) \subseteq \pi_{\text{genre\_id}}(\text{Genres})$

These constraints prevent dangling references. You cannot classify a nonexistent film into a genre. You cannot assign a nonexistent genre to a film.

Dangling references: a real-world analogy

A dangling reference is like a GP surgery’s database listing a patient’s doctor as “Dr. Yeti Goosecreature” when no such doctor exists on the staff table. The foreign key constraint catches this: the INSERT into the patient table would fail because doctor_id does not exist in the Doctors table. The system rejects the operation and demands correction.

Primary key vs. foreign key

Foreign keys in all-key tables

In an all-key relationship table such as Directed(movie_id, person_id), every column is both part of the primary key and a foreign key. The primary key constraint guarantees that no duplicate (movie, person) pairs exist; the foreign key constraints guarantee that both the movie and the person actually exist.

Multiple foreign keys to the same table

A table can have multiple foreign keys referencing the same target table. Consider a Transfers table in a banking database:

Transfers(id, from_account, to_account, amount)

Both from_account and to_account are foreign keys referencing Accounts(account_id). They play different roles but point to the same table.

ON DELETE and ON UPDATE actions

When a referenced row is deleted or its key is updated, the DBMS must decide what happens to the referencing rows. The SQL standard defines several actions:

The default in most DBMSs is RESTRICT. Choosing the right action depends on the semantics of the relationship.

Checking referential integrity

A DBMS checks referential integrity at the end of each statement (or at the end of each transaction, depending on the constraint mode). If a statement would leave the database in a state violating a foreign key constraint, the statement is rolled back and an error is returned to the client.

Summary

• A foreign key is a set of attributes in table $S$ that must match the key of some row in table $R$.
• Referential integrity means all foreign key constraints are satisfied.
• The DBMS enforces FK constraints by rejecting invalid inserts and updates.
• All-key tables consist solely of foreign keys that together form the primary key.
• ON DELETE and ON UPDATE actions control cascading behaviour when referenced rows change.

Translating entity tables to SQL

An entity table from the E/R model becomes a CREATE TABLE statement. The primary key is declared with PRIMARY KEY.

Simple entity with a synthetic key

CREATE TABLE genres (
  genre_id INTEGER NOT NULL,
  genre     TEXT    NOT NULL,
  PRIMARY KEY (genre_id)
);

• INTEGER / TEXT are SQL types. The course uses varchar(n) for variable-length strings up to $n$ characters.
• NOT NULL ensures the column cannot be NULL.
• PRIMARY KEY (genre_id) declares genre_id as the primary key. This implies both UNIQUE and NOT NULL.

Entity with multiple attributes

CREATE TABLE movies (
  movie_id VARCHAR(16)  NOT NULL,
  title    VARCHAR(255) NOT NULL,
  year     INTEGER      NOT NULL,
  PRIMARY KEY (movie_id)
);

CREATE TABLE people (
  person_id VARCHAR(16)  NOT NULL,
  name      VARCHAR(255) NOT NULL,
  birthYear INTEGER,
  PRIMARY KEY (person_id)
);

Translating relationship tables to SQL

Many-to-many (all-key) relationship

CREATE TABLE directed (
  movie_id  VARCHAR(16) NOT NULL REFERENCES movies (movie_id),
  person_id VARCHAR(16) NOT NULL REFERENCES people (person_id),
  PRIMARY KEY (movie_id, person_id)
);

• REFERENCES movies (movie_id) declares a foreign key constraint: every movie_id in directed must exist in movies.movie_id.
• PRIMARY KEY (movie_id, person_id) declares a composite key spanning both columns.
• Both columns are foreign keys. Together they form the primary key. This is the canonical all-key pattern.

Relationship with a foreign key to a single-column key

CREATE TABLE has_genre (
  movie_id VARCHAR(16) NOT NULL REFERENCES movies (movie_id),
  genre_id INTEGER     NOT NULL REFERENCES genres (genre_id),
  PRIMARY KEY (movie_id, genre_id)
);

Short form: REFERENCES movies (movie_id) is equivalent to FOREIGN KEY (movie_id) REFERENCES movies (movie_id). The short form can only be used when the foreign key is a single column, and only as a column constraint. The long form is needed for multi-column foreign keys:

CREATE TABLE some_table (
  col_a INTEGER NOT NULL,
  col_b INTEGER NOT NULL,
  FOREIGN KEY (col_a, col_b) REFERENCES other_table (col_c, col_d)
);

Combined example: a small schema

A schema for a film database with movies, people, genres, directors, and genre assignments:

CREATE TABLE movies (
  movie_id VARCHAR(16)  NOT NULL,
  title    VARCHAR(255) NOT NULL,
  year     INTEGER      NOT NULL,
  PRIMARY KEY (movie_id)
);

CREATE TABLE people (
  person_id VARCHAR(16)  NOT NULL,
  name      VARCHAR(255) NOT NULL,
  birthYear INTEGER,
  PRIMARY KEY (person_id)
);

CREATE TABLE genres (
  genre_id INTEGER NOT NULL,
  genre    TEXT    NOT NULL,
  PRIMARY KEY (genre_id)
);

CREATE TABLE directed (
  movie_id  VARCHAR(16) NOT NULL REFERENCES movies  (movie_id),
  person_id VARCHAR(16) NOT NULL REFERENCES people  (person_id),
  PRIMARY KEY (movie_id, person_id)
);

CREATE TABLE has_genre (
  movie_id VARCHAR(16) NOT NULL REFERENCES movies  (movie_id),
  genre_id INTEGER     NOT NULL REFERENCES genres  (genre_id),
  PRIMARY KEY (movie_id, genre_id)
);

Naming conventions

Foreign key column names typically match the primary key column names they reference. This convention makes schemas self-documenting:

• directed.movie_id references movies.movie_id
• has_genre.genre_id references genres.genre_id

When a table has two foreign keys to the same target table, distinguish them by role:

CREATE TABLE transfers (
  id            INTEGER     NOT NULL PRIMARY KEY,
  from_account  VARCHAR(16) NOT NULL REFERENCES accounts (account_id),
  to_account    VARCHAR(16) NOT NULL REFERENCES accounts (account_id),
  amount        DECIMAL     NOT NULL
);

Here from_account and to_account both reference accounts(account_id) but their column names reflect their distinct roles.

Enforcing constraints

The DBMS enforces the declared constraints at statement boundaries:

Overline notation

In some schema diagrams, foreign keys are indicated visually with overlines. For example, if table $W$ has attributes $A, B, Z, C$, and $Z$ is a foreign key to table $R$, we might write $W = \overline{A}.B.\overline{Z}.C$, where the overline on $Z$ marks it as a foreign key and the overline on $A$ marks $A$ as part of the primary key.

Composite foreign keys

A foreign key can span multiple columns if the referenced table has a composite key:

CREATE TABLE enrolment (
  student_id  INTEGER NOT NULL,
  course_id   INTEGER NOT NULL,
  year        INTEGER NOT NULL,
  PRIMARY KEY (student_id, course_id),
  FOREIGN KEY (course_id, year) REFERENCES course_offerings (course_id, year)
);

Here (course_id, year) references the composite key of course_offerings.

Summary

• CREATE TABLE defines a relation with columns, types, and constraints.
• PRIMARY KEY declares the key; $X$ is a minimal superkey.
• REFERENCES (or FOREIGN KEY ... REFERENCES) declares a foreign key constraint.
• NOT NULL prevents NULL values.
• The DBMS enforces all constraints, rejecting invalid operations.
• Naming conventions make foreign key relationships obvious.

The clean approach

Given a relationship $R$ between entity tables $S(\underline{Z}, W)$ and $T(\underline{X}, Y)$, the default approach is to create a separate table:

$R(X, Z, U)$

where $U$ are any relationship-specific attributes (e.g., a salary paid to an actor for a particular film). Both $X$ and $Z$ serve as foreign keys to $T$ and $S$ respectively.

Many-to-many (M:N)

For a many-to-many relationship, the separate-table approach is mandatory. The key of $R$ is $(X, Z)$ — both foreign keys together form the primary key. If the relationship has attributes $U$, they are included as non-key columns.

Example: Directed(movie_id, person_id) with key (movie_id, person_id).

One-to-many (1:M)

For a one-to-many relationship, we have two options.

Option 1: Separate table. Create $R(X, Z, U)$ as above. The key is $X$ (the “many” side), since each entity on the many side participates in at most one relationship. Requires a JOIN to navigate.

Option 2: Expand the “many” side table. Expand $T$ to $T(\underline{X}, Y, Z, U)$, adding the foreign key $Z$ and relationship attributes $U$ directly. Rows that do not participate in the relationship store NULL in $Z$ and $U$.

The expansion approach saves a join but introduces NULL columns and violates normalisation principles: $Z$ (the foreign key) functionally depends on $X$ (the key of the expanded table), but $Z$ is not itself a key. A later lecture covers normal forms in detail.

One-to-one (1:1)

For a one-to-one relationship, either side can absorb the foreign key. Choose the side where NULL values are less common.

Relationship attributes

When a relationship carries its own attributes, the clean approach uses a separate relationship table:

E/R diagram: Actor(id, name) — PerformsIn(character, salary) — Movie(id, title)

Relational schema:

Actors(actor_id, name)
Movies(movie_id, title)
PerformsIn(actor_id, movie_id, character, salary)

The character and salary columns belong to the relationship, not to either entity. Placing them in Actors or Movies would be incorrect: an actor can play different characters in different films for different salaries.

Merging multiple relationships

Sometimes multiple relationships between the same entity sets are merged into a single table with a type discriminator. The course example is has_position:

has_position(movie_id, person_id, role, character_name, position_in_credits)

This single table combines what could have been five separate tables: Directed, ActedIn, Produced, Composed, Wrote. The role column is a type discriminator (e.g., 'director', 'actor', 'producer').

Advantages:

• One table instead of five — simpler conceptual model.
• Queries across all roles require only one table.
• Adding a new role type requires only a new value in the role column, not a new table.

Disadvantages:

• character_name is NULL for non-actor roles; position_in_credits might be NULL for some roles.
• Redundancy: if we know role = 'director', we can deduce that character_name is NULL. This is a violation of normalisation principles — the value of one non-key column (role) determines whether another column (character_name) must be NULL.
• Foreign key constraints cannot easily express “an actor must have a character name” at the schema level. This logic moves to application code or triggers.

The type-tag redundancy problem

Consider two separate relationship tables:

R(X, Z, U)     -- e.g., directed roles
Q(X, Z, V)     -- e.g., acted roles

Now squash them into one:

RQ(X, Z, type, U, V)