CS fundamentals

DBMS Theory

Relational model, normalization, indexing, transactions and recovery, the DBMS questions interviews repeat.

  • Handwritten-style
  • Diagrams and tables
  • Worked examples
Start reading

Who this notebook is for

Students and freshers preparing for database questions in placements, and developers who want to know what a database does underneath SQL.

What you will be able to do

  • Find keys and functional dependencies and normalize a table to BCNF
  • Explain how a B+ tree index speeds up a query
  • Describe ACID, isolation levels and how locking and MVCC work
  • Read a query plan and say why one join order beats another

What's inside

Pick a chapter and the notebook opens right there.

  1. Relational Model & Architecture3-schema ANSI/SPARC, Physical/Logical data independence, relational integrity constraints, keys hierarchy (Super, Candidate, Primary, Surrogate)Start here
  2. Relational Algebra & Calculus5 Primitives (sigma, pi, cross product, union, diff), Theta & Natural joins, Relational Division, TRC vs DRC, Codd's Equivalence TheoremStart here
  3. ER Modeling & Schema MappingEntity/Relationship sets, Cardinality (1:1, 1:N, M:N), Weak entities & partial keys, EER Specialization, deterministic 7-step mapping pipelineStart here
  4. Functional Dependencies & KeysArmstrong's Axioms (Sound & Complete), Attribute closure algorithm (X+), 3-bucket candidate key finding, Canonical cover (Fc)Start here
  5. Normalization: 1NF to BCNFDatabase anomalies, 1NF atomicity, 2NF partial keys, 3NF transitive dependencies, BCNF strict superkey rule, Lossless join (Heath's Theorem)Start here
  6. Advanced Normalization & DenormMulti-Valued Dependencies (4NF), Join Dependencies (5NF/PJNF), DKNF, Pragmatic denormalization patterns, Materialized viewsStart here
  7. Storage Engine & Buffer PoolDatabase page anatomy (8KB/16KB), Slotted-page tuple format, Buffer pool frames, LRU-K & Clock replacement, Row vs Column storesStart here
  8. Tree Indexing: B-Trees & B+ TreesHigh fan-out search trees, B+ tree leaf doubly-linked list, Node split copy-up vs push-up, Underflow borrowing & merge, Clustered indexesStart here
  9. Hash, Bitmap & LSM-Tree IndexingStatic vs Dynamic extendible hashing, Bitmap indexes for OLAP, LSM-Trees (MemTable, SSTable, Bloom filters, Compaction)Start here
  10. Query Processing & Join AlgorithmsVolcano iterator model, Block Nested Loop, Sort- Merge Join, Grace Hash Join 3(M+N) cost derivation, Broadcast vs Shuffle joinsStart here
  11. Query Optimization & EXPLAINCost-Based Optimizer (CBO), Selinger dynamic programming, Equi-depth histograms, EXPLAIN ANALYZE interpretation, Parameter sniffingStart here
  12. Transactions & ACID PropertiesTransaction lifecycle, STEAL/NO-FORCE buffer policies, WAL invariants, ANSI isolation phenomena (Dirty, Fuzzy, Phantom reads)Start here
  13. Concurrency & SerializabilityConflict serializability & precedence graphs, View serializability & blind writes, Cascading vs Cascadeless vs Strict schedules, OCCStart here
  14. Two-Phase Locking & DeadlocksGrowing & shrinking phases, Strict 2PL, Multiple Granularity Locking (IS, IX, SIX), Wait-For Graphs, Wait-Die vs Wound-Wait, Next-Key locksStart here
  15. MVCC & Snapshot IsolationReaders never block writers, xmin/xmax tuple headers, Read Views, PostgreSQL VACUUM & table bloat, TxID wraparound, SSI write skewStart here
  16. Crash Recovery & The ARIES AlgorithmFuzzy checkpointing, ARIES 3 passes (Analysis, Redo, Undo), Repeating history, Compensation Log Records (CLRs), Crash during recoveryStart here
  17. Distributed DBs, Replication & CAPSharding & Consistent Hashing, Primary-Replica, Two- Phase Commit (2PC), Paxos & Raft consensus, CAP Theorem & PACELC, Spanner TrueTimeStart here
  18. FAANG DBMS Drills & Master Cheat SheetTop 10 High-frequency interview drills, mathematical formula cheat sheet, SQL tuning rules, system diagnostic views, readiness matrixStart here

Practice this

Put it to work on LakeBench.

Common questions

How is this different from learning SQL?
SQL is the language. This notebook is the theory behind it: how tables are designed, stored, indexed and kept correct when many users write at once.
Does it help with the DBMS questions freshers get asked?
Yes. It covers keys, normalization, transactions and indexes in the order interviews ask them, with a drills chapter at the end.
Can I read a sample before I commit?
Yes. The contents pages and the first pages of every notebook can be read online, so you can judge the style before going further.

More in CS fundamentals

All notebooks