Databases

a database is a data structure that survives a power cut, shared by programs that don’t trust each other, queried in a language older than most of its users. the relational model has been declared dead roughly once a decade since 1970 and has outlived every announced successor. 𐃏 this page covers the model, the algebra underneath SQL, normalisation, the storage structures that make queries fast, and the machinery that keeps concurrent transactions honest.

the relational model#

codd’s 1970 move: store everything as relations — sets of tuples over named, typed attributes — and let the system, not the programmer, decide how to navigate them.

• a relation is a set of tuples; a tuple is one row; an attribute is a named column with a domain. “table” is the implementation-flavoured word for the same thing.
• a superkey is any attribute set that uniquely identifies tuples; a candidate key is a minimal superkey; the primary key is the candidate key you commit to; a foreign key is an attribute set referencing another relation’s key.
• integrity constraints are the guarantees the DBMS enforces so your application doesn’t have to:
  • domain: values come from the attribute’s type (mark INTEGER, CHECK (year BETWEEN 1 AND 6)),
  • entity: no part of a primary key may be null — you cannot half-identify a row,
  • referential: every foreign key value must exist in the referenced relation — no enrolments for students who don’t exist (Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S., 2019).

the deep idea is data independence: queries are written against the logical schema, and the physical layout (indexes, partitions, storage order) can change underneath without breaking a single query.

relational algebra#

SQL is syntax; relational algebra is the semantics the optimiser actually manipulates. six primitive operators generate the whole language (Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S., 2019):

everything else is sugar: the natural join is \(R \bowtie S = \pi_{\ldots}(\sigma_{R.A = S.A}(R \times S))\), and intersection is \(R \cap S = R \setminus (R \setminus S)\). the optimiser exploits algebraic identities — pushing a selection below a join is legal because \(\sigma_{\theta}(R \bowtie S) = \sigma_{\theta}( R) \bowtie S\) whenever \(\theta\) touches only \(R\)’s attributes, and it is usually the single biggest win in a query plan.

SQL, actually run#

schema, inserts, a join, an aggregate, and a window function — the five things that cover most daily SQL. python’s built-in sqlite3 (engine version 3.50) executes all of it:

import sqlite3

con = sqlite3.connect(":memory:")
con.execute("PRAGMA foreign_keys = ON")   # off by default; REFERENCES is decorative without it
cur = con.cursor()
cur.executescript("""
CREATE TABLE students (
    sid   INTEGER PRIMARY KEY,
    name  TEXT NOT NULL,
    year  INTEGER CHECK (year BETWEEN 1 AND 6)
);
CREATE TABLE courses (
    cid   TEXT PRIMARY KEY,
    title TEXT NOT NULL,
    uoc   INTEGER DEFAULT 6
);
CREATE TABLE enrolments (
    sid   INTEGER REFERENCES students,
    cid   TEXT    REFERENCES courses,
    mark  INTEGER,
    PRIMARY KEY (sid, cid)              -- composite key
);

INSERT INTO students VALUES (1,'ada',3),(2,'grace',2),(3,'edsger',4),(4,'barbara',3);
INSERT INTO courses  VALUES ('COMP3311','databases',6),('COMP3331','networks',6),
                            ('COMP3231','operating systems',6);
INSERT INTO enrolments VALUES (1,'COMP3311',91),(1,'COMP3331',84),(2,'COMP3311',78),
                              (2,'COMP3231',88),(3,'COMP3331',95),(3,'COMP3231',72),
                              (4,'COMP3311',85);
""")

print("-- join: who is enrolled in what")
for row in cur.execute("""
    SELECT s.name, c.title, e.mark
    FROM enrolments e
    JOIN students s ON s.sid = e.sid
    JOIN courses  c ON c.cid = e.cid
    ORDER BY s.name, c.cid"""):
    print(row)

print("-- aggregate: course averages, hardest first")
for row in cur.execute("""
    SELECT cid, COUNT(*) AS n, ROUND(AVG(mark),1) AS avg_mark
    FROM enrolments GROUP BY cid
    HAVING COUNT(*) >= 2
    ORDER BY avg_mark"""):
    print(row)

print("-- window: rank within each course without collapsing rows")
for row in cur.execute("""
    SELECT cid, sid, mark,
           RANK() OVER (PARTITION BY cid ORDER BY mark DESC) AS rk,
           ROUND(AVG(mark) OVER (PARTITION BY cid), 1)       AS course_avg
    FROM enrolments ORDER BY cid, rk"""):
    print(row)

-- join: who is enrolled in what
('ada', 'databases', 91)
('ada', 'networks', 84)
('barbara', 'databases', 85)
('edsger', 'operating systems', 72)
('edsger', 'networks', 95)
('grace', 'operating systems', 88)
('grace', 'databases', 78)
-- aggregate: course averages, hardest first
('COMP3231', 2, 80.0)
('COMP3311', 3, 84.7)
('COMP3331', 2, 89.5)
-- window: rank within each course without collapsing rows
('COMP3231', 2, 88, 1, 80.0)
('COMP3231', 3, 72, 2, 80.0)
('COMP3311', 1, 91, 1, 84.7)
('COMP3311', 4, 85, 2, 84.7)
('COMP3311', 2, 78, 3, 84.7)
('COMP3331', 3, 95, 1, 89.5)
('COMP3331', 1, 84, 2, 89.5)

the window function is the one worth internalising: GROUP BY collapses rows to one per group, while OVER (PARTITION BY ...) computes the same aggregate but keeps every row — rank and group average side by side with the raw mark. 𐃏

normalisation#

redundancy is the disease; update, insertion, and deletion anomalies are the symptoms. functional dependencies are the diagnostic tool.

a functional dependency \(X \to Y\) holds when tuples agreeing on attribute set \(X\) must agree on \(Y\). armstrong’s axioms (reflexivity, augmentation, transitivity) generate all implied dependencies.

a worked decomposition#

start with one wide relation recording marks, one row per enrolment:

\begin{equation*} \text{enrol}(\underline{\text{sid}}, \underline{\text{cid}}, \text{sname}, \text{ctitle}, \text{dept}, \text{head}, \text{mark}) \end{equation*}

with dependencies

\begin{align*} \text{sid} &\to \text{sname} \\ \text{cid} &\to \text{ctitle}, \text{dept} \\ \text{dept} &\to \text{head} \\ \text{sid}, \text{cid} &\to \text{mark} \end{align*}

• 1NF demands atomic values and no repeating groups — storing a student’s courses as a comma-separated string violates it; one row per enrolment fixes it. the relation above is already 1NF.
• 2NF bans partial dependencies: non-key attributes depending on part of the composite key. sname depends on sid alone, ctitle and dept on cid alone. redundancy is visible: ada’s name is repeated once per enrolment, and you cannot record a course before anyone enrols (insertion anomaly). decompose:

\begin{equation*} \text{student}(\underline{\text{sid}}, \text{sname}), \quad \text{course}(\underline{\text{cid}}, \text{ctitle}, \text{dept}, \text{head}), \quad \text{enrol}(\underline{\text{sid}}, \underline{\text{cid}}, \text{mark}) \end{equation*}

• 3NF bans transitive dependencies: cid determines dept, dept determines head, so head is stored once per course instead of once per department — change a head of department and you update many rows or corrupt the data. split again:

\begin{equation*} \text{course}(\underline{\text{cid}}, \text{ctitle}, \text{dept}), \quad \text{department}(\underline{\text{dept}}, \text{head}) \end{equation*}

• BCNF tightens 3NF: for every nontrivial \(X \to Y\), \(X\) must be a superkey. the classic residual case: \(\text{tute}(\text{sid}, \text{cid}, \text{tutor})\) where each tutor teaches exactly one course (\(\text{tutor} \to \text{cid}\)) and each student has one tutor per course (\(\text{sid}, \text{cid} \to \text{tutor}\)). tutor is not a superkey, so BCNF says split into \(\text{tutorof}(\underline{\text{tutor}}, \text{cid})\) and \(\text{assigned}(\underline{\text{sid}}, \underline{\text{tutor}})\) — but now the dependency \(\text{sid}, \text{cid} \to \text{tutor}\) spans two tables and can no longer be checked without a join. BCNF is not always dependency-preserving; 3NF always is. every decomposition above is lossless (the shared attributes are keys of one side), which is the non-negotiable property (Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S., 2019).

normalise until it hurts, denormalise until it works — but know which dependencies you are knowingly breaking.

indexing#

why B+-trees and not binary trees#

disks and SSDs are read in pages (4–16 KiB), and each random page fetch is the expensive unit. a balanced binary tree on \(10^8\) keys is \(\log_2 10^8 \approx 27\) levels deep — 27 page fetches if each node lands on a different page, which they do, because a binary node is a few dozen bytes rattling around alone. the fix: make each node exactly one page wide and branch as hard as the page allows (Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S., 2019).

a B+-tree keeps all records (or record pointers) in the leaves, threaded into a sorted linked list; internal nodes hold only separator keys and child pointers, and every leaf sits at the same depth.

fanout arithmetic. take a 4 KiB page, 8-byte keys, 8-byte pointers. an internal node holding \(n\) child pointers needs \(n-1\) keys: \(8n + 8(n-1) \le 4096\) gives \(n \approx 256\). for \(N = 10^8\) keys with 256-entry leaves:

• leaves: \(\lceil 10^8 / 256 \rceil = 390{,}625\)
• level above: \(\lceil 390{,}625 / 256 \rceil = 1{,}526\)
• above that: \(\lceil 1{,}526 / 256 \rceil = 6\), then a root of 6 pointers.

four levels for a hundred million keys, and since the root and second level (about 7 pages) live permanently in the buffer pool, a cold lookup costs roughly two page reads — against 27 for the binary tree. the same structure answers range queries by walking the leaf chain, which a hash index cannot do.

the other index shapes#

• hash indexes map key to bucket in expected \(O(1)\) — faster than a B+-tree for pure equality lookups, useless for ranges, ORDER BY, or prefix matches, because the hash deliberately destroys ordering.
• covering indexes: if an index on (cid, mark) contains every column a query touches, the engine answers from the index alone and never visits the table — an “index-only scan”. the fastest table read is the one that doesn’t happen.
• indexes are not free: every INSERT, UPDATE, and DELETE must maintain all of them, so write-heavy tables want few, carefully chosen indexes. 𐃏

query processing#

a join \(R \bowtie S\) (with \(|R| = n\), \(|S| = m\) tuples; \(B_R\), \(B_S\) pages) can be executed three classic ways (Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S., 2019):

• nested loop is the naive double for; with an index on the inner join key it becomes index nested loop and is excellent for small outer relations.
• hash join builds a hash table on the smaller relation, probes with the larger; when neither fits in memory, both are partitioned to disk by hash first (grace hash join).
• sort-merge sorts both on the join key and zips them; it is the reason ORDER BY on the join key is sometimes free afterwards.

the optimiser picks between them using table statistics — cardinalities, histograms, index availability — which is why a stale ANALYZE can turn a millisecond plan into a minute-long one.

transactions and ACID#

a transaction is a group of statements that must behave as one indivisible action:

• atomicity — all or nothing; crash mid-transfer and the money is in exactly one account. implemented with a write-ahead log and rollback.
• consistency — every commit moves the database between constraint-satisfying states.
• isolation — concurrent transactions cannot observe each other’s intermediate garbage.
• durability — once committed, survives power loss; the WAL is fsynced before “committed” is reported.

isolation levels and their anomalies#

full serialisability costs concurrency, so SQL defines discounted tiers. what each level permits:

• dirty read: seeing another transaction’s uncommitted write.
• non-repeatable read: re-reading a row and finding it changed under you.
• phantom: re-running a predicate query and finding new rows that now match.

the table is the standard’s contract, not a description of any real engine: postgres’s “repeatable read” is snapshot isolation, which also prevents phantoms but admits write skew — two transactions each reading the condition the other is about to falsify (two doctors both going off-call because “at least one other doctor is on call”). snapshot isolation passes the table above and still is not serialisable — a genuinely non-obvious fact, explained beautifully in kleppmann’s designing data-intensive applications (https://dataintensive.net/).

2PL vs MVCC#

• two-phase locking: acquire shared/exclusive locks as you go (growing phase), release only at the end (shrinking phase — in practice, at commit: strict 2PL). guarantees serialisability, but readers block writers and vice versa, and deadlocks must be detected and a victim aborted.
• multi-version concurrency control: writers create new versions instead of overwriting; each transaction reads the snapshot that was current when it began. readers never block writers, which is why postgres, mysql/innodb, and oracle all live here. the honest price: garbage from dead versions (postgres’s vacuum), and plain snapshot isolation admits the anomalies above — postgres’s SERIALIZABLE level layers serialisation-conflict detection (SSI) on top and aborts one of the offenders, trading blocking for retries.

distribution: CAP and the NoSQL taxonomy#

once data spans machines, the network becomes part of the database. the CAP theorem: under a network partition, a distributed store must sacrifice either consistency (every read sees the latest write) or availability (every request gets a non-error answer). the folk version — “pick two of three” — is misleading, because partition tolerance is not optional: partitions happen. the real content is the C-vs-A choice during the partition, and kleppmann argues even that framing hides more than it reveals (please stop calling databases CP or AP).

the “NoSQL” label bundles four genuinely different data models. sorting the stub’s shopping list into it:

postgres and mysql are the relational workhorses the rest get compared against — and postgres’s JSONB quietly covers a large slice of the document use-case with transactions included. as for QRKDB, the last name on the stub’s list: i can find no trace of it anywhere, including in my own notes, so it stays here as a monument to writing down context, not just names. 𐃏

the deeper divide than SQL-vs-NoSQL is the consistency model: single-node transactions are a solved problem; cross-partition transactions are where the distributed-systems dragons live.

see also#

• internet networks — the layer your database listens on
• linux — fsync, pages, and the kernel under the WAL
• data structures & algorithms — B-trees and hashing in their natural habitat
• memory — the cache hierarchy that makes page-sized thinking mandatory

References#

Silberschatz, Abraham and Korth, Henry F. and Sudarshan, S. (2019). Database System Concepts, McGraw-Hill Education.