Database Management Systems

Overview

Study this unit as a pipeline. Design comes first: an ER model captures requirements in pictures, the relational model turns those pictures into tables, and normalisation refines the tables until redundancy is controlled. Querying comes next: relational algebra is the formal language that defines what a query means, and SQL is the practical language that expresses it, with grouping, subqueries and views layered on top. Concurrency and recovery come last because they assume you already understand transactions: without a clear idea of a transaction as a unit of work, serializability has nothing to be serializable about.

For exam preparation, practise three hand skills until they are mechanical. First, closure: given a set of functional dependencies, list the closure of an attribute set by repeatedly adding right-hand sides whose left-hand sides are already present. Second, decomposition: given a relation and its dependencies, find the violating dependency, split on it, and re-check each piece. Third, precedence graphs: given a schedule, draw an edge from one transaction to another for every conflicting pair in order, and check for a cycle.

ER model & relational algebra

The entity-relationship model describes a domain before any table exists. An entity is a distinguishable object or concept, such as a student or a course; an entity set is a collection of similar entities. An attribute is a property of an entity, such as a name or a date of birth. A key attribute, or combination of attributes, identifies each entity uniquely within its set. Attributes may be simple or composite, single-valued or multi-valued, stored or derived. A relationship associates entities from two or more entity sets, for example enrolment linking students and courses. The cardinality of a relationship states how many entities on each side may participate: one-to-one, one-to-many, many-to-one, or many-to-many. Participation may be total, meaning every entity must take part, or partial, meaning participation is optional. A weak entity cannot be identified by its own attributes alone and depends on an owner entity through an identifying relationship; its key combines its partial key with the owner key. The extended ER model adds specialisation into subclasses, generalisation into a superclass, and aggregation, which treats a relationship as an entity.

The relational model converts this picture into tables. A relation is a table with a fixed schema: attributes as columns, tuples as rows. A superkey is any attribute set that identifies each tuple uniquely; a candidate key is a minimal superkey, with no attribute removable without losing uniqueness; the primary key is the candidate key chosen as the identifier. A foreign key is an attribute set in one relation that refers to the primary key of another relation. Integrity constraints protect meaning: entity integrity forbids nulls in any part of the primary key; referential integrity forbids a foreign key value that has no matching primary key value, unless it is null where the design permits; domain constraints restrict values to their declared types and allowed ranges; key constraints enforce uniqueness.

Relational algebra is the formal query language of this model. Selection picks rows satisfying a condition. Projection picks columns, discarding duplicates in the set-based model. The Cartesian product pairs every tuple of one relation with every tuple of the other. Natural join combines the product with equality on common attributes and keeps one copy of each shared attribute. Theta join generalises this to an arbitrary condition; equijoin is the special case where the condition is equality. Union, intersection and difference are set operations requiring union-compatible relations with the same attributes. Rename changes a relation or attribute name, which is essential when a query joins a relation with itself. Division answers for-all questions: the division of a relation by another returns the values that are paired with every value in the divisor, such as students who have taken all courses in a given set.

How this is examined: expect questions that convert an ER description into cardinality and keys, that identify a weak entity and its key, that translate a query between algebra and SQL, and that recognise division as the operator for for-all questions. Draw the diagram, label every cardinality, and name the key of every entity before answering.

SQL & normalisation

SQL divides into data definition and data manipulation. Data definition language creates and changes schema: CREATE TABLE defines columns, types, primary keys, foreign keys and constraints; ALTER TABLE adds, drops or modifies columns and constraints; DROP TABLE removes a table. Data manipulation language changes and reads data: INSERT adds rows, UPDATE changes existing rows, DELETE removes rows, and SELECT reads them. SELECT is the workhorse: FROM names the tables, WHERE filters rows, GROUP BY groups rows for aggregation, HAVING filters groups, ORDER BY sorts the result, and DISTINCT removes duplicate rows. Aggregate functions such as COUNT, SUM, AVG, MIN and MAX summarise a group; a column in the SELECT list that is neither aggregated nor grouped is an error in strict SQL, though some systems tolerate it.

Joins combine tables. An inner join returns only matched pairs. A left outer join returns all rows from the left table, filling unmatched right columns with nulls; a right outer join mirrors this, and a full outer join returns all rows from both sides. A self-join joins a table to itself using aliases, for example to find employees and their managers from one employee table. A subquery is a query nested inside another: it may appear in WHERE with IN, EXISTS, ANY or ALL, or in FROM as a derived table. A correlated subquery refers to the outer query and is evaluated once per outer row, while an uncorrelated subquery is evaluated once. Set operations in SQL are UNION, which removes duplicates, UNION ALL, which keeps them, INTERSECT and EXCEPT, all requiring compatible column lists. A view is a named stored query that behaves like a virtual table: it simplifies access and can restrict columns, but an update through a view is permitted only when the view is updatable, which generally excludes views with joins, grouping or DISTINCT. An index, commonly a B-tree, speeds retrieval on a key at the cost of slower updates and extra storage; it does not change query results.

Normalisation rests on functional dependencies. A functional dependency X determines Y, written X arrow Y, means that any two tuples agreeing on X must agree on Y. Armstrong axioms generate all implied dependencies: reflexivity says that if Y is a subset of X then X determines Y; augmentation says that if X determines Y then XZ determines YZ; transitivity says that if X determines Y and Y determines Z then X determines Z. The closure of an attribute set X is the set of all attributes functionally determined by X; it is computed by starting with X and repeatedly adding the right-hand side of any dependency whose left-hand side is already contained in the closure, until nothing changes. A candidate key is a minimal set whose closure is all attributes. A canonical cover is a minimal equivalent set of dependencies: every right-hand side is a single attribute, no left-hand side contains an extraneous attribute, and no dependency is redundant.

Normal forms classify designs by which dependencies are allowed. A relation is in first normal form when every attribute value is atomic, with no repeating groups or multi-valued attributes. Second normal form adds that the relation is in first normal form and every non-prime attribute is fully functionally dependent on every candidate key, which removes partial dependencies on part of a composite key. Third normal form adds that no non-prime attribute is transitively dependent on any candidate key. Boyce-Codd normal form strengthens this: for every non-trivial dependency X determines Y, X must be a superkey. Every BCNF relation is in third normal form, but the reverse does not hold: a relation can satisfy third normal form through a prime attribute on the right-hand side while violating BCNF. Fourth normal form concerns multi-valued dependencies rather than functional dependencies and is tested less often, but its idea is the same: a non-trivial multi-valued dependency must be determined by a superkey.

Decomposition must satisfy two properties. Lossless join means the original relation can be recovered exactly by joining the pieces; a binary decomposition into R1 and R2 is lossless when the common attributes form a superkey of at least one piece. Dependency preservation means every original dependency is enforced by the dependencies within the pieces, without needing a join to check it. It is not always possible to achieve BCNF, losslessness and dependency preservation together; third normal form synthesis guarantees the latter two, which is why it is often the practical stopping point. Anomalies explain why this matters: an insertion anomaly forces dummy data to record a fact, a deletion anomaly loses unrelated facts when a row is deleted, and an update anomaly requires changing many rows for one fact. Normalisation removes each anomaly by placing each fact in exactly one place.

How this is examined: expect closure computations, candidate-key identification, normal-form classification of a given relation, a decomposition step with a losslessness check, and SQL questions on joins, grouping, HAVING versus WHERE, correlated subqueries, and views. Always compute the closure before naming a key, and always check the common attributes before claiming a decomposition is lossless.

Transactions & concurrency

A transaction is a unit of work that must satisfy ACID properties. Atomicity means the transaction executes entirely or not at all; a failure part-way must leave no partial effects. Consistency means a transaction moves the database from one valid state to another, preserving constraints and invariants. Isolation means concurrently executing transactions behave as if they ran one after another, even though they are interleaved. Durability means the effects of a committed transaction survive crashes. A schedule is an interleaving of the operations of several transactions. A serial schedule runs transactions one after another with no interleaving; a serializable schedule is one whose effect equals that of some serial schedule, which is the correctness criterion for concurrency control.

Conflict serializability is the practical test. Two operations conflict when they belong to different transactions, access the same data item, and at least one is a write. Read-read pairs do not conflict; read-write and write-write pairs do. The precedence graph of a schedule has a node per transaction and an edge from Ti to Tj whenever an operation of Ti conflicts with and precedes an operation of Tj. The schedule is conflict serializable exactly when this graph has no cycle, and any topological order of the graph is an equivalent serial order. View serializability is a weaker, more general condition based on reads-from relationships and final writes; every conflict-serializable schedule is view serializable, but not conversely, and testing view serializability is computationally harder, so systems rely on conflict serializability. Non-serializable schedules exhibit lost updates, dirty reads, unrepeatable reads and phantom reads, defined in the table below.

Locking is the standard mechanism. A shared lock permits reading; an exclusive lock permits reading and writing, and no other transaction may hold a conflicting lock on the same item. Two-phase locking requires that a transaction acquire all locks before releasing any: a growing phase of acquisitions followed by a shrinking phase of releases. This protocol guarantees conflict serializability. Strict two-phase locking additionally holds exclusive locks until commit or abort, which also prevents dirty reads and makes abort safe by avoiding cascading rollback. Rigorous two-phase locking holds all locks, shared and exclusive, until commit or abort. Two-phase locking alone does not prevent deadlock: two transactions waiting on each other locks form a cycle in the wait-for graph. Deadlock is handled by prevention, for example ordering lock acquisition or using wait-die and wound-wait rules based on timestamps, by detection with a wait-for graph cycle check followed by aborting a victim, or by timeout. Fine lock granularity permits more concurrency but costs more lock management; coarse granularity is cheaper but blocks more work.

Timestamp ordering is an alternative that needs no locks. Each transaction receives a unique timestamp at start. Each data item carries a read timestamp, the largest timestamp of a transaction that read it, and a write timestamp, the largest timestamp of a transaction that wrote it. A read is permitted only if the reader timestamp is at least the write timestamp; otherwise the transaction aborts and restarts with a new timestamp. A write is permitted only if its timestamp is at least both the read and write timestamps; an obsolete write may be ignored under the Thomas write rule. Timestamp ordering guarantees serializability in timestamp order and is deadlock-free because no transaction waits, but it can abort transactions more often than locking. Multiversion concurrency control keeps several versions of each item so readers can read a consistent old version without blocking writers.

Recovery restores the database after a failure. The write-ahead logging rule states that a log record for a change must reach stable storage before the changed database page does, and a commit record must reach stable storage before the transaction is considered committed. Recovery then uses undo and redo: undo rolls back transactions that had not committed at the crash, restoring old values from the log; redo reapplies the changes of committed transactions whose pages may not have reached disk. A checkpoint writes buffered pages to disk and records a checkpoint marker, bounding how far back recovery must scan. Shadow paging keeps a shadow page table for the old database and a current table for the new version; committing is the atomic switch of tables, so no log is needed, but it is less common in large systems.

How this is examined: expect a schedule to be tested for conflict serializability with a graph, a statement about which locking variant prevents which anomaly, a deadlock scenario with a remedy, a timestamp-ordering decision for a read or write, and a recovery question asking whether undo, redo, both or neither apply to a transaction given its commit status at crash time.

Normal forms compared

Locking variants compared

Join types compared

Serializability and anomalies