Skip to content
Tutorials Center
My learning

Topics

Lesson 79 of 79 ยท Practice and Review

DBMS Cheat Sheet

A one-page DBMS cheat sheet: ER mapping rules, relational algebra symbols, normal-form tests, isolation levels, lock matrix, cost formulas and SQL syntax.

This is the page to keep open the night before an exam or an interview. It compresses the whole tutorial into tables, rules and formulas, with a pointer to the full lesson for each block. Nothing here is new: if a line does not make sense, follow its link and read the explanation.

Three live blocks round it off: a SQL syntax reference you can run, a calculator for the cost formulas, and the lock-compatibility matrix as code.

What is on this page

Modelling ER mapping and algebra.
Design Keys, FDs and normal forms.
Transactions ACID, isolation, locks.
Performance Indexes and cost formulas.

Skim top to bottom, then dive into the lessons you are weakest in.

1 / 2

ER model to tables

Details in The Entity-Relationship Model and Mapping ER Diagrams to Tables.

ER construct Becomes
Strong entity A table; the entity key is the primary key
Composite attribute One column per simple component
Multivalued attribute A new table: the entity key plus the value, key = both
Derived attribute Usually no column (compute it), or a view
1:1 relationship A foreign key on either side, with a unique constraint (prefer the total-participation side)
1:N relationship A foreign key on the N side
M:N relationship A new table with both keys (plus relationship attributes); primary key is the combination
Weak entity A table whose key = owner key + partial key; foreign key to the owner with ON DELETE CASCADE
Specialization (ISA) Three options: one table per entity with the key shared; one table per subclass with inherited columns; or one single table with a type column
Ternary relationship A table with three foreign keys

Relational algebra symbols

See Selection, Projection and Renaming, Joins in Relational Algebra and Division, Aggregation and Extended Operators.

Operator Symbol SQL idea
Selection ฯƒ condition (R) WHERE
Projection ฯ€ attributes (R) SELECT DISTINCT cols
Rename ฯ new (R) AS
Union, intersection, difference R โˆช S, R โˆฉ S, R โˆ’ S UNION, INTERSECT, EXCEPT
Cartesian product R ร— S CROSS JOIN
Theta join R โ‹ˆ condition S JOIN ... ON
Natural join R โ‹ˆ S NATURAL JOIN / USING
Left, right, full outer join โŸ•, โŸ–, โŸ— LEFT, RIGHT, FULL JOIN
Semijoin, antijoin โ‹‰, โ–ท EXISTS, NOT EXISTS
Division R รท S double NOT EXISTS
Grouping and aggregation ฮณ GROUP BY with aggregates

Useful identities: ฯƒ commutes and cascades (ฯƒ aโˆงb = ฯƒ a ฯƒ b); push ฯƒ and ฯ€ below joins; R โ‹ˆ S = ฯƒ (R ร— S); join is associative and commutative.

Keys, dependencies and normal forms

See Functional Dependencies, Attribute Closure, Keys and Minimal Cover and BCNF and Lossless Decomposition.

Concept Rule
Armstrong's axioms Reflexivity (Y โІ X โ‡’ X โ†’ Y), augmentation (X โ†’ Y โ‡’ XZ โ†’ YZ), transitivity
Derived rules Union, decomposition, pseudotransitivity
Closure X+ Add the right side of every FD whose left side is inside the result; repeat until nothing changes
Superkey X+ = all attributes
Candidate key A minimal superkey; attributes never on a right side are in every key
Minimal cover Single-attribute right sides, no extraneous left attributes, no redundant FDs
Prime attribute Belongs to some candidate key
Normal form Test
1NF Every value is atomic
2NF 1NF and no non-prime attribute depends on part of a candidate key
3NF For every non-trivial X โ†’ A: X is a superkey, or A is prime
BCNF For every non-trivial X โ†’ A: X is a superkey
4NF For every non-trivial multivalued dependency X โ†  Y, X is a superkey

Decomposition checks. Lossless: the common attributes of a binary split must be a key of at least one side (or use the chase for more pieces). Dependency preserving: every FD can be tested inside one piece. BCNF is always lossless but can lose FDs; 3NF synthesis is always lossless and dependency preserving.

ACID and isolation

See ACID Properties in Depth and Isolation Levels and Concurrency Anomalies.

Property Meaning Mechanism
Atomicity All or nothing Log plus undo
Consistency Valid state to valid state Constraints plus application logic
Isolation Looks serial Locks or MVCC
Durability Committed means safe Write-ahead log, flushed at commit
Isolation level Dirty read Non-repeatable read Phantom
Read uncommitted yes yes yes
Read committed no yes yes
Repeatable read no no yes (standard)
Serializable no no no

Other anomalies: lost update (two read-modify-writes overlap) and write skew (two transactions read overlapping data and write different rows, allowed by snapshot isolation).

Schedules. Conflicting operations: different transactions, same item, at least one write. A schedule is conflict serializable when its precedence graph has no cycle. Recoverable: commit after the transaction whose data you read. Cascadeless: read only committed data. Strict: also write only over committed data.

Locks and concurrency control

See Locks: Shared, Exclusive and Intention, Two-Phase Locking and Deadlocks: Detection, Prevention and Recovery.

  • 2PL: growing phase (acquire), then shrinking phase (release); guarantees conflict serializability. Strict 2PL keeps write locks to commit. Rigorous 2PL keeps all locks to commit.
  • Deadlock: cycle in the wait-for graph. Wait-die: an older transaction waits for a younger one, a younger one dies. Wound-wait: an older transaction wounds (aborts) a younger one, a younger one waits.
  • Timestamp ordering: a read of x fails if TS(T) < W-ts(x); a write fails if TS(T) < R-ts(x); the Thomas write rule skips an obsolete write if TS(T) < W-ts(x).
  • MVCC: readers see a snapshot, writers create versions; conflicts are detected at write or commit time.

The multiple-granularity lock matrix, as a program:

Python Lock compatibility matrix with intention locks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

IS and IX mark intent to lock something lower in the hierarchy (rows inside a table), SIX means "read the whole table, change some rows". The matrix is symmetric, which the last line checks.

Recovery

See Logging and Write-Ahead Logging and Checkpoints, ARIES and Backups.

  • WAL rule: log record on stable storage before the data page; all of a transaction's log records (including commit) before it is acknowledged.
  • Buffer policies: steal (dirty pages of uncommitted transactions may reach disk, so you need undo) and no-force (committed pages need not be written at commit, so you need redo).
  • ARIES: analysis (find dirty pages and active transactions), redo (repeat history), undo (roll back losers, writing compensation records).
  • Backups: full, incremental, differential; logical (SQL dump) versus physical (files); point-in-time recovery means a backup plus the log.

Storage and indexes

See Indexing Basics, B-Trees and B+ Trees and Hashing: Static, Extendible and Linear.

Index Strength Weakness
B+ tree Equality, ranges, ordering, prefix search Writes must maintain it
Hash Equality in about one probe No ranges or ordering
Bitmap Low-cardinality columns, analytics Poor under frequent writes
Composite Queries on the leftmost prefix Useless if the leading column is skipped
Covering Answers a query without touching the table Larger index
Partial / expression Smaller, targeted Query must match the condition
LSM tree Very fast writes Reads and compaction cost

A clustered index fixes the physical order (one per table); secondary indexes point to the row or its primary key. A B+ tree with fan-out F and N keys has about โŒˆlog_F NโŒ‰ levels.

Query processing cost formulas

See Join Algorithms, External Sorting and Aggregation and Statistics, Cost Estimation and Plan Search. Notation: b pages, n tuples, M buffer pages, r outer, s inner.

Operation Page I/O cost
Full scan b_r
Tuple nested loop join b_r + n_r ร— b_s
Block nested loop join b_r + โŒˆb_r / (M โˆ’ 2)โŒ‰ ร— b_s
Index nested loop join b_r + n_r ร— c (c = cost of one index probe)
Sort-merge join sort costs + b_r + b_s (sort cost can be skipped for sorted inputs)
Hash join 3 (b_r + b_s) when the build side partitions fit
External sort 2 b ร— (1 + โŒˆlog_{Mโˆ’1} โŒˆb / MโŒ‰โŒ‰)
Python The formulas as a calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Try changing M or the table sizes. The tuple-at-a-time nested loop costs two million page reads against a few thousand for the others, which is the whole argument for block, index and hash joins. The sort-merge number counts a full write of each sorted result; real engines often feed the last merge pass straight into the join, which makes it a little cheaper.

SQL quick reference

For the full syntax, see the SQL tutorial. The block below runs every core construct once.

SQL SQL syntax at a glance

Press Run (or Ctrl + Enter) to see the result here.

Need Syntax
Create a table CREATE TABLE t (id INTEGER PRIMARY KEY, x TEXT NOT NULL, fk INTEGER REFERENCES u(id))
Add an index CREATE INDEX idx ON t(col1, col2)
Change a row UPDATE t SET x = 1 WHERE id = 5
Transaction BEGIN; ...; COMMIT; or ROLLBACK;
Plan EXPLAIN QUERY PLAN SELECT ... (SQLite), EXPLAIN elsewhere
Grant access (server engines) GRANT SELECT ON t TO role

Evaluation order of a query: FROM and joins, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY, LIMIT. NULL is never equal to anything, including itself: use IS NULL; aggregates other than COUNT(*) ignore nulls.

Distributed systems

See Replication, Sharding and Distributed Transactions and CAP, BASE and Consistency Models.

  • CAP: during a partition choose consistency or availability. PACELC: otherwise, latency or consistency.
  • Quorums: with N replicas, reads from R and writes to W overlap when R + W > N.
  • Replication copies data (availability, read scaling). Sharding splits data (write and capacity scaling). Consistent hashing limits data movement when nodes change.
  • Two-phase commit: prepare (vote), then commit or abort; blocks if the coordinator fails at the wrong moment.
  • OLTP is many small transactions on rows; OLAP is few large scans of columns, usually with a star schema.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How is a many-to-many relationship mapped to tables?

    An M:N relationship needs its own table with a foreign key to each side; the pair of keys (plus anything that makes a row unique) forms the primary key.
  2. 2. A relation is in BCNF when...

    BCNF is the strictest of these tests: no exception for prime right sides.
  3. 3. Which isolation level still allows phantom reads according to the SQL standard?

    The standard's repeatable read prevents dirty and non-repeatable reads but allows phantoms; only serializable prevents all three.
  4. 4. A transaction holds an IX lock on a table. Which request is compatible?

    IX is compatible only with IS and IX. A table-level S, SIX or X would conflict with the intention to change rows inside.
  5. 5. Using the formulas, which join is cheapest for two large unsorted tables with a decent amount of memory?

    Hash join reads and writes each input once during partitioning and reads once more to join, about 3(b_r + b_s).

Summary

  • ER to tables: entities become tables, 1:N puts a foreign key on the N side, M:N gets its own table, weak entities borrow the owner's key.
  • Closure drives everything in design theory: superkeys, candidate keys, minimal covers and normal-form tests are all closure computations.
  • 3NF allows prime right sides, BCNF does not; BCNF may lose dependencies, 3NF synthesis never does.
  • ACID is enforced by logging, locking or multiversioning and the write-ahead rule; isolation levels trade anomalies for concurrency.
  • Intention locks let a lock manager mix table-level and row-level locking safely.
  • B+ trees give logarithmic lookups and ordered scans; join and sort costs are simple page-count formulas.

You have reached the end of the DBMS tutorial. Revisit the weak spots with Exercises with Solutions and DBMS Interview Questions, or start again from What Is a Database?.