Module 16: Inside the DBMS

The theory exams ask: relational algebra, storage and B+ trees, serializability and locking protocols, logging and recovery.

1. Relational algebra and its SQL: σ = WHERE, π = SELECT DISTINCT, ⋈ = JOIN, ∪ ∩ − = UNION INTERSECT EXCEPT, and ÷ ("for every") = double NOT EXISTS.
2. Storage: pages, B+ tree maths and hashing: bfr = ⌊B/R⌋, blocks = ⌈r/bfr⌉; B+ tree order p = ⌊(B+K)/(K+P)⌋, leaf = ⌊(B−P)/(K+Pr)⌋; lookup = levels + 1 reads; hashing is for equality only.
3. Serializability, two-phase locking and timestamps: Conflict = different transactions, same item, at least one write; precedence graph with no cycle = conflict serializable; 2PL guarantees it (but can deadlock), strict 2PL also stops cascading aborts.
4. Logging and recovery: WAL, checkpoints, undo and redo: WAL: log before data, commit = commit record on disk; after a crash redo what committed (after the checkpoint), undo what didn't, newest record first.

Ends with a 13-question checkpoint (80% passes) and a project: Write the recovery manager.