Databases & Data Systems

One booking through tables, queries, indexes, transactions and recovery

About this course

Relational databases from the data model to the storage engine — SQL, schema design, indexes, query execution and planning, transactions and isolation, crash recovery, and replicated, partitioned data systems.

What you will be able to do

  • Write SQL queries with joins, grouping and missing values, and predict the result rows
  • Design a schema with keys and constraints, and normalize it to remove redundancy
  • Explain how pages, buffer pools, B+ trees and hash indexes serve a query, and compare candidate plans
  • Determine whether a concurrent schedule is serializable under locking or snapshot isolation
  • Reconstruct a crash recovery from a log, and state what replication and partitioning do and do not guarantee

What this course covers

  • Storage identity vs. location layers
  • Slotted-page layout and byte accounting
  • Compaction, slot indirection, and the stale-offset pitfall
  • Buffer pool residency and LRF replacement
  • Pin counts and replacement eligibility
  • Dirty-copy obligation before frame reuse
  • Scope limits and connection to real systems
  • Histories, programs, and the serializability question
  • Enumerating legal interleavings
  • Conflicts and the precedence graph
  • Conflict equivalence via adjacent commuting swaps
  • Conflict serializability theorem (acyclicity ↔ serial witness)
  • Precedence graphs versus wait-for graphs
  • View serializability and blind writes
  • Model boundaries and scope of the analysis
  • Operator contracts: demand, state, and exhaustion
  • Filter and limit operator behaviour
  • Projection and bag semantics
  • Equality join: nested-loop and hash-join algorithms
  • Merge join: ordered inputs and equal-run expansion
  • Blocking operators: hash aggregate and full sort
  • Full revenue query execution and work accounting
  • Database invariants and record-based representation
  • Observation versus reservation: the stale-read failure
  • Atomicity: single publication point for related changes
  • Isolation: enumerating permitted concurrent histories
  • Durability and the committed-state/client-knowledge gap
  • Idempotent retry via stable request identifiers
  • Four obligations: representation, atomicity, isolation, durability
  • Four locations where information lives
  • Log sequence numbers and after-image records
  • Durable commit rule and the acknowledge operation
  • No-steal / no-force buffer policies
  • WAL guard and no-steal guard on page flushes
  • Redo-only recovery with page-LSN idempotence
  • Checkpoint and safe log retirement
  • Separating recovery replay from application retry
  • Replica state markers: received, durable, applied
  • Crash recovery and the durable prefix
  • Acknowledgment policies and the reply gate
  • Read freshness and position-gated reads
  • Failover obligations: history preservation and authority enforcement
  • Quorum intersection: safety, progress, and the CAP information problem
  • Sharding vs. replication and cross-shard transaction boundaries
  • Index entry model and lookup contract
  • B+ tree structure and search navigation
  • B+ tree insertion and leaf/root splitting
  • Separators vs. leaf entries: the duplication question
  • Hash index: bucket routing and equality check
  • Range queries: B+ tree vs. hash index
  • Compound key ordering and contiguous intervals
  • Cost units and model scope
  • Query plan equivalence and semantic correctness
  • Candidate-pair cost model
  • Predicate pushdown and its legality conditions
  • Exhaustive plan-space enumeration for three relations
  • Dynamic programming with a subset memo table
  • Cardinality estimation errors and preference reversal
  • Independence assumption failures and index eligibility
  • Lock-based admission and the lock table model
  • Compatibility rules: S and X modes
  • Lock lifetime and the two-phase discipline
  • Hold-until-commit safety theorem
  • Wait-for graphs and diagnosing deadlock
  • Resource acquisition order as a deadlock mitigation
  • Three-owner wait cycle and separating safety from progress
  • Scope limits of the lock model and connection to real systems
  • Relations as sets of typed tuples
  • Projection and information loss
  • Superkeys and candidate keys: instance vs. schema
  • Boundary cases in key definitions
  • Primary keys, foreign keys, and constraint scope
  • Inner join result vs. source validity
  • Capacity equation as a beyond-structural constraint
  • Invariants: seat sum and identity correspondence
  • Request identity and payload binding
  • Grouping related writes in one transaction
  • Separating commitment from client knowledge
  • Stored result as retry resolution mechanism
  • Outbox pattern and the external effect boundary
  • Consumer inbox deduplication: one intent, one effect
  • Multi-version concurrency and snapshot basics
  • Version visibility rule
  • Snapshot lifetime policies
  • Write-set validation and first-committer-wins
  • Write-skew anomaly and serialization failure
  • Guard-key repair for disjoint-write anomaly
  • Version retention and oldest-reader boundary
  • Query design as five explicit decisions
  • Filtering rows with WHERE
  • Output shape, provenance, and column selection
  • Row multiplicity: ordinary SELECT vs DISTINCT
  • Predicate grouping and operator precedence
  • Ordering, tie-breaking, and ORDER BY placement
  • Computed expressions, bound parameters, and boundary testing
  • Outer join predicate placement and row preservation
  • Distinguishing absence from missing data using request identity
  • Aggregate expressions count different populations
  • Known zero vs. absent booking vs. unknown price
  • Three-valued logic and NULL in SQL filters
  • Fan-out multiplication when joining independent child tables
  • Summarise-then-join pattern and HAVING for group filters
  • Functional Dependencies as Agreement Obligations
  • Attribute Closure, Superkeys, and Candidate Keys
  • Lossless Decomposition and the Unsafe Split
  • Losslessness vs. Dependency Preservation as Separate Obligations
  • Boyce-Codd Normal Form (BCNF)
  • Third Normal Form and Dependency Preservation
  • Safe Booking Decomposition: End-to-End Reconstruction

Syllabus

  1. The Relational Model and SQL

    1. L1 · Two Customers, One Last Seat
    2. L2 · Relations, Keys, and Constraints
    3. L3 · SQL: From Questions to Results
    4. L4 · Joins, Grouping, and Missing Values
    5. L5 · Schema Design and Normalization

  2. Storage and Indexes

    1. L6 · Records, Pages, and Buffer Pools
    2. L7 · B+ Trees and Hash Indexes

  3. Query Processing

    1. L8 · Executing a Query
    2. L9 · Choosing a Query Plan

  4. Transactions and Concurrency

    1. L10 · Transactions and Serializability
    2. L11 · Locks, Deadlocks, and Isolation
    3. L12 · Versions, Snapshots, and Conflicts

  5. Recovery and Distributed Data

    1. L13 · Logging and Crash Recovery
    2. L14 · Replication, Partitions, and Data-System Choices
    3. L15 · One Booking Through the Database