Databases & Data

A database is tables of rows whose keys point at each other: a primary key names a row, a foreign key points at one, and the engine refuses every row that would break a pointer.

An index is a wide, shallow tree with every leaf at one depth: a lookup reads one page per level, an insert splits upward, and the root grows only at the top, so any row is a few reads away.

A join pairs the rows of two tables whose keys agree: a nested loop, a hash table, and two sorted runs find the same pairs at three prices, and the outer joins keep the rows nobody matched.

SQL says what, not how: a cost-based planner reads the table statistics, prices every way of scanning and joining in page reads, prunes the dearer plan over the same tables, and runs the cheapest.

A transaction is all or nothing and alone in the world. Interleave two transfers and an update is lost; lock what each touches until it ends and the books balance, at the price of the odd deadlock.

Write the intention to a log before touching a page, force the log at commit, and after a crash replay what was promised and undo what was not.

Writes fill a sorted table in memory, full tables flush to disk as immutable runs, runs merge downward in the background, and a read checks the layers newest first.

A rule about every row a table could hold: test it against the rows, follow what a set of attributes determines, find the candidate keys, and trim the rules to a minimal cover.

One value per cell, and no value spread over numbered copies of a column: find the lists hiding in a table, give each member a row of its own, and name the key that needs.

A composite key, and an attribute that hangs off only part of it: find the partial dependency, see the rows it makes you repeat, and split it off into a relation of its own.

A non-key attribute that fixes another: follow each rule's closure, name the chain from the key through it, see the facts it makes you repeat, and synthesize a relation for its middle.

Every determinant a superkey, no exemption: find the rule third normal form lets through, split on it, chase a tableau to prove the join is lossless, and see which rule the split cannot keep.