Databases

ER model

The entity-relationship model: entities and entity sets, attribute kinds (simple, composite, multivalued, derived, key), relationship sets and their degree, cardinality ratios (1:1, 1:N, M:N) and participation (total or partial), keys of relationship sets, weak entity sets with identifying relationships and partial keys, specialisation and generalisation (ISA) with disjointness and totality, and counting the relationship sets allowed by a cardinality constraint.

ER to relational mapping

Turning an ER diagram into relation schemas: strong and weak entity sets, multivalued attributes, one-to-many relationships by a foreign key, many-to-many relationships by a relation of their own, one-to-one relationships, specialisation hierarchies in three ways, and counting the tables (with the minimum number of tables when relations can be merged), checked by loading random ER instances into a real database.

Relational model and keys

The relational model: relation schemas and instances, tuples, domains, degree and cardinality, why a relation is a set; superkeys, candidate keys, primary keys, prime attributes and alternate keys, counting superkeys; foreign keys and referential integrity with the referential actions (cascade, set null, restrict) run on a real database engine, entity integrity, NULL values, and the difference between a relation and a SQL table.

Relational algebra

The six basic operators of relational algebra (selection, projection, union, set difference, Cartesian product, rename), the derived operators (intersection, theta join, natural join), set semantics and union compatibility, evaluating expressions step by step on real relations, the bounds on the sizes of results, algebraic laws that always hold, and writing queries in algebra.

Joins, division and expression trees

Joins in depth (theta, equi, natural, left/right/full outer joins and semijoin) with their treatment of NULL, the division operator and its expression with the basic operators, grouping and aggregation, query evaluation as an expression tree, and the heuristic optimisation rules (push selections and projections down, combine a selection with a product into a join, order joins) with measured intermediate sizes.

Tuple relational calculus

The tuple relational calculus: tuple variables ranging over relations, atoms and formulas with connectives and the quantifiers there exists and for all, free and bound variables, queries of the form { t | P(t) }, translating every relational algebra operator (selection, projection, union, difference, product, join, division) into calculus, queries with negation and universal quantification, safe versus unsafe expressions, and the equivalence of safe calculus with relational algebra.

Safe expressions and domain calculus

The domain relational calculus (variables range over attribute values, atoms like R(x, y)), how it differs from the tuple calculus, what makes a calculus expression safe (its answer is finite and does not depend on the domain, only on the values in the database and the query), unsafe expressions and why, a syntactic test that is sufficient but not necessary, Codd's theorem (safe tuple calculus, safe domain calculus and relational algebra have the same power), and the translation of the algebra operators into safe formulas.

SQL: DDL and basic queries

SQL as a language: defining tables (data types, NOT NULL, PRIMARY KEY, UNIQUE, FOREIGN KEY, DEFAULT), changing data (INSERT, UPDATE, DELETE), the SELECT-FROM-WHERE query and its meaning in relational algebra, DISTINCT and the bag semantics of SQL, expressions and aliases, ORDER BY and LIMIT, pattern and range conditions (LIKE, BETWEEN, IN, IS NULL), NULL in conditions, and the set operations UNION, INTERSECT and EXCEPT with their ALL forms; every statement shown was executed on a real SQL engine.

Joins, grouping and aggregates

Joins in SQL (cross, inner with ON, USING and NATURAL, left/right/full outer, self joins) with the number of rows each produces, the aggregate functions COUNT, SUM, AVG, MIN and MAX and how they treat NULL and empty sets, GROUP BY and HAVING, the logical order of evaluation of a query (FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY), and typical traps such as COUNT(*) against COUNT(column) with outer joins; every statement shown was executed on a real SQL engine.

Nested queries, views and NULL

Subqueries in SQL (IN, NOT IN, EXISTS, NOT EXISTS, scalar comparison, ANY and ALL, correlated and uncorrelated, derived tables and WITH), expressing 'for all' with a double NOT EXISTS, views (definition, use, updatability, security and logical independence), and the three-valued logic of NULL (truth tables, the NOT IN trap, how WHERE, GROUP BY, DISTINCT and aggregates treat NULL); every statement shown was executed on a real SQL engine.

Integrity constraints and triggers

Integrity constraints in SQL (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY with referential actions, DEFAULT, deferred checking inside a transaction, assertions) and what each one refuses; the all-or-nothing behaviour of a statement; triggers (event, timing, row-level and statement-level, WHEN condition, OLD and NEW, BEFORE and AFTER, INSTEAD OF on views) used for auditing, derived data and rules that constraints cannot express; every statement shown was executed on a real SQL engine.

Functional dependencies and closure

Functional dependencies as constraints on a relation schema, trivial and non-trivial dependencies, Armstrong's axioms (reflexivity, augmentation, transitivity) and the derived rules, the closure of a set of attributes and the algorithm that computes it, testing whether a dependency is implied, equivalence of sets of dependencies, and why a set of dependencies can imply exponentially many others; the rules were checked against the semantic definition on all relations over small domains.

Finding candidate keys

Finding all candidate keys of a relation from its functional dependencies: the closure test for a superkey, attributes that must be in every key and attributes that are in none, the systematic search, the number of keys a schema can have (up to the central binomial coefficient), prime and non-prime attributes, and the common patterns (a cycle of dependencies makes every attribute a key); results checked against the brute-force list of all minimal superkeys.

1NF to BCNF

Normal forms as conditions on functional dependencies: first normal form (atomic values), second normal form (no partial dependency of a non-prime attribute on a key), third normal form (every dependency has a superkey on the left or a prime attribute on the right), Boyce-Codd normal form (every determinant is a superkey); the redundancy and update, insertion and deletion anomalies they prevent; testing a schema (checking only the given dependencies is enough), the strict hierarchy BCNF, 3NF, 2NF, 1NF, and examples of schemas at each level.

Lossless join and dependency preservation

Decomposing a relation to reach a normal form: the lossless-join property (spurious tuples, the binary test, the chase tableau test), dependency preservation (projecting the dependencies, the polynomial test), why the two properties are independent, the BCNF decomposition algorithm (always lossless, sometimes loses a dependency) and 3NF synthesis from a minimal cover (always lossless and dependency preserving), with every test checked by brute force and by constructing counterexample relations.

File organisation and blocking factor

How records are stored on disk: blocks, records per block (the blocking factor), the number of blocks of a file for fixed-length records (unspanned and spanned), the cost of a block access, and the three basic file organisations (heap, sorted, hashed) with the number of block accesses for search, insertion, deletion and range queries; the textbook binary-search formula ceil(log2 b) against the exact count floor(log2 b) + 1, checked by measuring searches on generated files.

Ordered, primary, clustering and secondary indexes

Single-level ordered indexes (primary, clustering and secondary; dense and sparse), how many entries and index blocks each has, the number of block accesses of a search with a binary search of the index, multilevel indexes (an index on the index) and the number of levels, the rule that a file has at most one primary or clustering index but many secondary indexes, and the cost of maintaining indexes; every number was checked by building the files and indexes and counting block reads.

B trees

B trees as balanced multiway search trees: definition by order (at most m children, at least ceil(m/2) for non-root nodes), the node layout in a disk block and how the order follows from the block size, search, insertion with node splitting, deletion with borrowing and merging, the minimum and maximum number of keys for a given height and the height bounds for n keys; every operation shown is a snapshot of a real tree and the extreme trees were built node by node.

B+ trees

B+ trees, the index structure of database systems: all keys and record pointers in the leaves, inner nodes only as signposts, leaves chained for range queries; node layouts and how the orders follow from the block size, search (always as many block reads as levels), insertion (a leaf split copies the key up, an inner split moves it up), deletion (borrow or merge, separators may remain), range queries, the minimum and maximum number of keys for a height, heights for n keys, and the comparison with B trees; every animation is a snapshot of a real tree and the extreme trees were built node by node.

Transactions and ACID

What a transaction is (a unit of work made of reads, writes, commit and abort), its states, the four ACID properties and which part of the system guarantees each one, and the anomalies that appear when transactions run without control (lost update, dirty read, non-repeatable read, inconsistent summary, crash in the middle of a transfer), each shown as a schedule executed on real numbers; the SQL isolation levels are described as quoted from the standard.

Log-based recovery and checkpoints

How a database survives a crash with atomicity and durability: the write-ahead log (start, update with old and new value, commit, abort, checkpoint, compensation records), the two write-ahead rules, the buffer policies steal and force and what each makes necessary (undo, redo), immediate against deferred modification, simple checkpoints, recovery by repeating history (redo pass, undo pass), the quick redo-list and undo-list rule used in exam questions and the case where it fails, idempotence when the system crashes during recovery, and shadow paging and ARIES in outline; every table is produced by running a small database through crashes and recovering it.

Schedules, conflict and view serializability

Schedules, serial schedules and the idea of serializability as the correctness criterion for concurrent execution; conflicting operations, conflict equivalence, the precedence graph test (acyclic means conflict serializable, topological orders are the equivalent serial schedules), view equivalence and view serializability with blind writes, the relation between the two classes, and counting interleavings; every example is computed from the definitions and cross-checked by independent algorithms.

Recoverable, cascadeless and strict schedules

Why serializability is not enough once transactions can abort: reads-from, recoverable schedules (a transaction commits only after every transaction it read from), cascadeless schedules (reads only committed values), strict schedules (no read or write of an uncommitted write, which also makes before-image undo correct) and rigorous schedules, the inclusions between the classes, cascading rollback, and the independence of the recoverability classes from conflict serializability; classes are computed by definition and recomputed by a dynamic simulation.

Two-phase locking and its variants

Shared and exclusive locks and their compatibility, the lock manager with waiting, the two-phase rule (growing phase then shrinking phase) and the proof that two-phase schedules are conflict serializable in the order of the lock points, why basic 2PL still allows dirty reads and cascading aborts, strict, rigorous and conservative 2PL, lock upgrades, deadlock in locking with the wait-for graph and the ways to handle it; locking is shown with a real lock manager and random lock schedules were checked against the theorem.

Timestamp ordering

Concurrency control without locks: every transaction gets a timestamp when it starts, every item remembers the largest timestamp of a reader and of a writer, and an operation that would break the timestamp order is rejected and its transaction restarted with a new timestamp; the read and write rules, the Thomas write rule and view serializability, why the protocol is conflict serializable and deadlock free but neither recoverable nor starvation free, strict timestamp ordering, the timestamp-based deadlock prevention schemes wait-die and wound-wait for locking, multiversion timestamp ordering in outline, and a comparison with two-phase locking over all interleavings of small transaction sets.