Hands-on lab — Day 87: Joins and Relationships

-- Day 087 · Step 1 — the single wide table, and the three anomalies it causes.
--
-- This is the "before" picture. One table holds everything the library knows
-- about a book AND everything it knows about that book's author, so an author
-- who wrote two books has their details written down twice.
--
-- Run with:  sqlite3 library.db < examples/01_wide_table.sql

DROP TABLE IF EXISTS catalog_wide;

CREATE TABLE catalog_wide (
  title             TEXT    NOT NULL,
  published_year    INTEGER NOT NULL,
  author_name       TEXT    NOT NULL,
  author_birth_year INTEGER NOT NULL
);

INSERT INTO catalog_wide (title, published_year, author_name, author_birth_year) VALUES
  ('The C Programming Language',  1978, 'Brian W. Kernighan',      1942),
  ('The C Programming Language',  1978, 'Dennis M. Ritchie',       1941),
  ('The Practice of Programming', 1999, 'Brian W. Kernighan',      1942),
  ('The Practice of Programming', 1999, 'Rob Pike',                1956),
  ('The Mythical Man-Month',      1975, 'Frederick P. Brooks Jr.', 1931);

.mode column
.headers on

.print ''
.print '--- the wide table: note Kernighan appears twice ---'
SELECT * FROM catalog_wide ORDER BY title, author_name;

-- ANOMALY 1 — UPDATE. The library learns the author prefers the shorter form
-- of his name. Someone updates "the C book" and stops, because that is the row
-- they were looking at.
.print ''
.print '--- update anomaly: rename the author on one book only ---'
UPDATE catalog_wide
   SET author_name = 'Brian Kernighan'
 WHERE title = 'The C Programming Language'
   AND author_name = 'Brian W. Kernighan';

-- The database now holds two different names for one human being, with no
-- error, no warning and nothing marking which one is right.
SELECT DISTINCT author_name, author_birth_year
  FROM catalog_wide
 WHERE author_birth_year = 1942;

-- ANOMALY 2 — INSERT. Record an author the library has catalogued no books for.
-- There is no way to do it: every column about a book is NOT NULL, because a
-- row in this table IS a book. The author cannot exist without one.
.print ''
.print '--- insertion anomaly: an author with no catalogued book has no home ---'
.print 'no row can be written for Donald E. Knuth without inventing a book'

-- ANOMALY 3 — DELETE. The library withdraws its only copy of the Brooks book.
-- Deleting the book deletes the only record that Frederick P. Brooks Jr. exists.
.print ''
.print '--- deletion anomaly: withdraw a book, lose an author ---'
DELETE FROM catalog_wide WHERE title = 'The Mythical Man-Month';
SELECT count(*) AS brooks_rows_remaining
  FROM catalog_wide
 WHERE author_name LIKE '%Brooks%';

-- Day 087 · Step 2 — the same information, split into five tables.
--
-- Each table holds facts about exactly one kind of thing, and every fact is
-- written down in exactly one place. The relationships between the things are
-- carried by foreign keys.
--
--   authors        one row per person
--   books          one row per book
--   book_authors   the junction table: many books to many authors
--   members        one row per library member (self-referencing: who referred whom)
--   loans          one row per borrowing event (many loans to one book, many to one member)
--
-- Run with:  sqlite3 library.db < examples/02_schema.sql

PRAGMA foreign_keys = ON;

DROP TABLE IF EXISTS loans;
DROP TABLE IF EXISTS book_authors;
DROP TABLE IF EXISTS members;
DROP TABLE IF EXISTS books;
DROP TABLE IF EXISTS authors;

CREATE TABLE authors (
  author_id  INTEGER PRIMARY KEY,
  name       TEXT    NOT NULL UNIQUE,
  birth_year INTEGER
);

CREATE TABLE books (
  book_id        INTEGER PRIMARY KEY,
  title          TEXT    NOT NULL,
  published_year INTEGER NOT NULL
);

-- The junction table. Its primary key is the PAIR, which is what stops the
-- same author being attached to the same book twice.
CREATE TABLE book_authors (
  book_id   INTEGER NOT NULL REFERENCES books(book_id)     ON DELETE CASCADE,
  author_id INTEGER NOT NULL REFERENCES authors(author_id) ON DELETE RESTRICT,
  PRIMARY KEY (book_id, author_id)
);

-- referred_by points back at this same table: a self-referencing foreign key.
-- It is nullable, because the first members were referred by nobody.
CREATE TABLE members (
  member_id   INTEGER PRIMARY KEY,
  name        TEXT    NOT NULL,
  joined_on   TEXT    NOT NULL,
  referred_by INTEGER REFERENCES members(member_id)
);

-- The key lives on the MANY side. One book has many loans, so book_id is here,
-- in loans — not a list of loans inside books.
CREATE TABLE loans (
  loan_id     INTEGER PRIMARY KEY,
  book_id     INTEGER NOT NULL REFERENCES books(book_id),
  member_id   INTEGER NOT NULL REFERENCES members(member_id),
  borrowed_on TEXT    NOT NULL,
  returned_on TEXT
);

-- A foreign key does not create an index. Without these, every join and every
-- referential-integrity check on the child side is a full table scan.
CREATE INDEX idx_book_authors_author ON book_authors(author_id);
CREATE INDEX idx_loans_book          ON loans(book_id);
CREATE INDEX idx_loans_member        ON loans(member_id);

-- Day 087 · Step 3 — seed the five tables.
--
-- The books and authors are real and checkable. The members and the loans are
-- invented for this lab; no real person's borrowing history is used anywhere.
--
-- Three deliberate gaps are built into this data, because they are what the
-- outer joins later in the lab are for:
--
--   * Donald E. Knuth is an author with NO catalogued book  (the insertion
--     anomaly, now possible)
--   * "The Practice of Programming" has NEVER been borrowed
--   * Eli Nakamura is a member who has NEVER borrowed anything
--
-- Run with:  sqlite3 library.db < examples/03_seed.sql

PRAGMA foreign_keys = ON;

DELETE FROM loans;
DELETE FROM book_authors;
DELETE FROM members;
DELETE FROM books;
DELETE FROM authors;

INSERT INTO authors (author_id, name, birth_year) VALUES
  (1, 'Brian W. Kernighan',      1942),
  (2, 'Dennis M. Ritchie',       1941),
  (3, 'Frederick P. Brooks Jr.', 1931),
  (4, 'Stuart J. Russell',       1962),
  (5, 'Peter Norvig',            1956),
  (6, 'Rob Pike',                1956),
  (7, 'Donald E. Knuth',         1938);

INSERT INTO books (book_id, title, published_year) VALUES
  (101, 'The C Programming Language',                 1978),
  (102, 'The Mythical Man-Month',                     1975),
  (103, 'Artificial Intelligence: A Modern Approach', 1995),
  (104, 'The Practice of Programming',                1999);

INSERT INTO book_authors (book_id, author_id) VALUES
  (101, 1),
  (101, 2),
  (102, 3),
  (103, 4),
  (103, 5),
  (104, 1),
  (104, 6);

INSERT INTO members (member_id, name, joined_on, referred_by) VALUES
  (1, 'Ada Okafor',     '2026-01-05', NULL),
  (2, 'Bruno Salgado',  '2026-01-19', 1),
  (3, 'Chandra Iyer',   '2026-02-02', 1),
  (4, 'Dana Whitfield', '2026-03-11', 2),
  (5, 'Eli Nakamura',   '2026-04-01', NULL);

INSERT INTO loans (loan_id, book_id, member_id, borrowed_on, returned_on) VALUES
  (1, 101, 1, '2026-05-04', '2026-05-18'),
  (2, 102, 1, '2026-05-20', NULL),
  (3, 101, 2, '2026-06-01', '2026-06-14'),
  (4, 103, 3, '2026-06-03', NULL),
  (5, 101, 4, '2026-07-07', '2026-07-20'),
  (6, 102, 2, '2026-07-15', NULL);

-- Day 087 · Step 4 — the SQLite fact that surprises everybody.
--
-- SQLite compiles foreign-key support in, but leaves ENFORCEMENT OFF by
-- default, for backwards compatibility. Every connection starts with it off
-- and must turn it on for itself. A REFERENCES clause you never enforce is a
-- comment with punctuation.
--
-- This script proves it twice: once by inserting a loan pointing at a member
-- who does not exist, and once by trying the identical insert with the pragma
-- on. Run it as one shell session so both halves share ONE connection:
--
--   sqlite3 library.db < examples/04_foreign_keys.sql

.headers on
.mode column

.print ''
.print '--- 1. what the pragma says on a brand-new connection ---'
SELECT 'PRAGMA foreign_keys' AS setting, foreign_keys AS value FROM pragma_foreign_keys;

.print ''
.print '--- 2. insert a loan for member 999, who does not exist ---'
INSERT INTO loans (loan_id, book_id, member_id, borrowed_on, returned_on)
VALUES (900, 101, 999, '2026-08-16', NULL);
SELECT changes() AS rows_inserted;

.print ''
.print '--- 3. the orphan row is really there ---'
SELECT loan_id, book_id, member_id FROM loans WHERE loan_id = 900;

.print ''
.print '--- 4. and the database will tell you, if you ask it to check ---'
PRAGMA foreign_key_check;

.print ''
.print '--- 5. clean up, enable enforcement, and try the identical insert ---'
DELETE FROM loans WHERE loan_id = 900;
PRAGMA foreign_keys = ON;
SELECT 'PRAGMA foreign_keys' AS setting, foreign_keys AS value FROM pragma_foreign_keys;

.print ''
.print '--- 6. the same statement, now rejected ---'
INSERT INTO loans (loan_id, book_id, member_id, borrowed_on, returned_on)
VALUES (900, 101, 999, '2026-08-16', NULL);

-- Day 087 · Step 5 — every join in the lesson, against the seeded library.
--
-- Run with:  sqlite3 library.db < examples/05_joins.sql

PRAGMA foreign_keys = ON;
.headers on
.mode column

.print ''
.print '=== 1. INNER JOIN — books with their authors (many-to-many, two hops) ==='
SELECT b.title,
       a.name AS author
  FROM books AS b
  JOIN book_authors AS ba ON ba.book_id   = b.book_id
  JOIN authors      AS a  ON a.author_id  = ba.author_id
 ORDER BY b.title, a.name;

.print ''
.print '=== 2. the same result written the old comma-join way ==='
SELECT b.title,
       a.name AS author
  FROM books b, book_authors ba, authors a
 WHERE ba.book_id  = b.book_id
   AND a.author_id = ba.author_id
 ORDER BY b.title, a.name;

.print ''
.print '=== 3. CROSS JOIN — the accidental cartesian product (4 x 7 = 28) ==='
SELECT count(*) AS every_book_paired_with_every_author
  FROM books CROSS JOIN authors;

.print ''
.print '=== 4. LEFT OUTER JOIN — every author, whether or not they have a book ==='
SELECT a.name        AS author,
       b.title       AS title,
       b.published_year
  FROM authors AS a
  LEFT JOIN book_authors AS ba ON ba.author_id = a.author_id
  LEFT JOIN books        AS b  ON b.book_id    = ba.book_id
 ORDER BY a.name, b.title;

.print ''
.print '=== 5. LEFT JOIN + IS NULL — authors with no catalogued book ==='
SELECT a.author_id, a.name
  FROM authors AS a
  LEFT JOIN book_authors AS ba ON ba.author_id = a.author_id
 WHERE ba.author_id IS NULL
 ORDER BY a.name;

.print ''
.print '=== 6. LEFT JOIN + IS NULL — books never borrowed ==='
SELECT b.book_id, b.title
  FROM books AS b
  LEFT JOIN loans AS l ON l.book_id = b.book_id
 WHERE l.loan_id IS NULL
 ORDER BY b.title;

.print ''
.print '=== 7. the LEFT JOIN trap — loans per member, zeroes included ==='
SELECT m.name                 AS member,
       count(l.loan_id)       AS loans
  FROM members AS m
  LEFT JOIN loans AS l ON l.member_id = m.member_id
 GROUP BY m.member_id, m.name
 ORDER BY loans DESC, member;

.print ''
.print '=== 7b. count(*) instead of count(l.loan_id) — the wrong answer ==='
SELECT m.name           AS member,
       count(*)         AS loans_wrong
  FROM members AS m
  LEFT JOIN loans AS l ON l.member_id = m.member_id
 GROUP BY m.member_id, m.name
 ORDER BY loans_wrong DESC, member;

.print ''
.print '=== 7c. INNER JOIN instead — the member with zero loans vanishes ==='
SELECT m.name           AS member,
       count(l.loan_id) AS loans
  FROM members AS m
  JOIN loans AS l ON l.member_id = m.member_id
 GROUP BY m.member_id, m.name
 ORDER BY loans DESC, member;

.print ''
.print '=== 8. ON versus WHERE on an outer join — ON keeps every member ==='
SELECT m.name AS member, l.loan_id, l.returned_on
  FROM members AS m
  LEFT JOIN loans AS l
         ON l.member_id = m.member_id
        AND l.returned_on IS NULL
 ORDER BY m.name, l.loan_id;

.print ''
.print '=== 8b. the same predicate moved to WHERE — the outer join collapses ==='
SELECT m.name AS member, l.loan_id, l.returned_on
  FROM members AS m
  LEFT JOIN loans AS l ON l.member_id = m.member_id
 WHERE l.returned_on IS NULL
 ORDER BY m.name, l.loan_id;

.print ''
.print '=== 9. SELF JOIN — who referred whom (LEFT, so the unreferred survive) ==='
SELECT m.name          AS member,
       r.name          AS referred_by
  FROM members AS m
  LEFT JOIN members AS r ON r.member_id = m.referred_by
 ORDER BY m.member_id;

.print ''
.print '=== 10. FOUR tables at once — who has what out on loan right now ==='
SELECT m.name  AS member,
       b.title AS title,
       a.name  AS author,
       l.borrowed_on
  FROM loans        AS l
  JOIN members      AS m  ON m.member_id  = l.member_id
  JOIN books        AS b  ON b.book_id    = l.book_id
  JOIN book_authors AS ba ON ba.book_id   = b.book_id
  JOIN authors      AS a  ON a.author_id  = ba.author_id
 WHERE l.returned_on IS NULL
 ORDER BY m.name, a.name;

.print ''
.print '=== 11. join + GROUP BY — times borrowed per book, zeroes included ==='
SELECT b.title,
       count(l.loan_id) AS times_borrowed
  FROM books AS b
  LEFT JOIN loans AS l ON l.book_id = b.book_id
 GROUP BY b.book_id, b.title
 ORDER BY times_borrowed DESC, b.title;

.print ''
.print '=== 12. the query the Python join is checked against ==='
SELECT l.loan_id, m.name AS member, l.borrowed_on
  FROM loans   AS l
  JOIN members AS m ON m.member_id = l.member_id
 ORDER BY l.loan_id;

"""Day 087 · Step 6 — build the join yourself, two ways, and check both
against SQLite.

A join is not magic. It is one of two small algorithms, and the query planner
picks between them. Here they are, in plain Python over lists of dictionaries,
with no database involved until the final comparison.

    nested-loop join   for every left row, scan every right row     O(n * m)
    hash join          index the right side once, then look up      O(n + m)

Run with:  python3 examples/06_join_from_scratch.py library.db
"""

from __future__ import annotations

import sqlite3
import sys
from collections import defaultdict


def rows_from(connection: sqlite3.Connection, table: str) -> list[dict]:
    """Read a whole table as a list of plain dictionaries."""
    connection.row_factory = sqlite3.Row
    return [dict(row) for row in connection.execute(f"SELECT * FROM {table}")]


def nested_loop_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> tuple[list[tuple[dict, dict]], int]:
    """The obvious algorithm: compare everything with everything.

    Returns the matched pairs and the number of key comparisons performed, so
    the cost is a number you can look at rather than a claim you have to trust.
    """
    pairs: list[tuple[dict, dict]] = []
    comparisons = 0
    for left_row in left:
        for right_row in right:
            comparisons += 1
            if left_row[left_key] == right_row[right_key]:
                pairs.append((left_row, right_row))
    return pairs, comparisons


def hash_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> tuple[list[tuple[dict, dict]], int]:
    """Build a dictionary from the smaller side, then probe it once per row.

    The build phase touches every right row once. The probe phase touches every
    left row once. Nothing is scanned repeatedly, which is the whole difference.
    """
    index: dict[object, list[dict]] = defaultdict(list)
    operations = 0
    for right_row in right:  # build phase
        operations += 1
        index[right_row[right_key]].append(right_row)

    pairs: list[tuple[dict, dict]] = []
    for left_row in left:  # probe phase
        operations += 1
        for right_row in index.get(left_row[left_key], ()):
            pairs.append((left_row, right_row))
    return pairs, operations


def left_outer_hash_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> list[tuple[dict, dict | None]]:
    """The same probe, except a left row with no match still comes through —
    paired with None, which is exactly what SQL calls NULL."""
    index: dict[object, list[dict]] = defaultdict(list)
    for right_row in right:
        index[right_row[right_key]].append(right_row)

    pairs: list[tuple[dict, dict | None]] = []
    for left_row in left:
        matches = index.get(left_row[left_key], [])
        if matches:
            pairs.extend((left_row, match) for match in matches)
        else:
            pairs.append((left_row, None))
    return pairs


def as_comparable(pairs) -> list[tuple]:
    """Reduce join output to (loan_id, member name, borrowed_on) so it can be
    compared with the SQL result by value."""
    result = []
    for loan, member in pairs:
        name = member["name"] if member is not None else None
        result.append((loan["loan_id"], name, loan["borrowed_on"]))
    return sorted(result, key=lambda row: row[0])


def main(database: str) -> int:
    connection = sqlite3.connect(database)
    connection.execute("PRAGMA foreign_keys = ON")

    loans = rows_from(connection, "loans")
    members = rows_from(connection, "members")

    print(f"left side:  {len(loans)} loans")
    print(f"right side: {len(members)} members")
    print()

    nested_pairs, comparisons = nested_loop_join(loans, members, "member_id", "member_id")
    hashed_pairs, operations = hash_join(loans, members, "member_id", "member_id")

    print(f"nested-loop join: {len(nested_pairs)} rows, {comparisons} key comparisons")
    print(f"hash join:        {len(hashed_pairs)} rows, {operations} operations")
    print(f"  (6 x 5 = {6 * 5} against 6 + 5 = {6 + 5}; the gap widens as the square)")
    print()

    # The reference: let SQLite do the same join.
    connection.row_factory = None
    sql_rows = connection.execute(
        """
        SELECT l.loan_id, m.name, l.borrowed_on
          FROM loans   AS l
          JOIN members AS m ON m.member_id = l.member_id
         ORDER BY l.loan_id
        """
    ).fetchall()
    sql_result = sorted((row[0], row[1], row[2]) for row in sql_rows)

    nested_result = as_comparable(nested_pairs)
    hash_result = as_comparable(hashed_pairs)

    print("nested-loop == SQL:", nested_result == sql_result)
    print("hash        == SQL:", hash_result == sql_result)
    print("nested-loop == hash:", nested_result == hash_result)
    print()

    for loan_id, name, borrowed_on in sql_result:
        print(f"  loan {loan_id}  {name:<15} {borrowed_on}")
    print()

    # And the outer join, where the algorithms differ in what they keep.
    outer = left_outer_hash_join(
        rows_from(connection, "members"), rows_from(connection, "loans"),
        "member_id", "member_id",
    )
    unmatched = [member["name"] for member, loan in outer if loan is None]
    print(f"left outer join keeps {len(outer)} rows from 5 members and 6 loans")
    print(f"members surviving with NULL on the right: {unmatched}")

    sql_unmatched = [
        row[0]
        for row in connection.execute(
            """
            SELECT m.name
              FROM members AS m
              LEFT JOIN loans AS l ON l.member_id = m.member_id
             WHERE l.loan_id IS NULL
             ORDER BY m.name
            """
        )
    ]
    print(f"the same question in SQL:                {sql_unmatched}")
    print("outer join agrees with SQL:", unmatched == sql_unmatched)

    connection.close()

    everything_agrees = (
        nested_result == sql_result
        and hash_result == sql_result
        and unmatched == sql_unmatched
    )
    print()
    print("ALL THREE JOINS AGREE" if everything_agrees else "MISMATCH")
    return 0 if everything_agrees else 1


if __name__ == "__main__":
    sys.exit(main(sys.argv[1] if len(sys.argv) > 1 else "library.db"))

"""Day 087 · Step 7 — the same foreign-key proof from Python, plus the trap
that makes people think the pragma does not work.

The pragma is per-connection, and SQLite documents it as a no-op inside an
open transaction. Python's sqlite3 module opens transactions for you, so a
pragma issued after your first INSERT can be silently ignored. This script
shows both the failure and the fix, on a throwaway in-memory database.

Run with:  python3 examples/07_foreign_keys_python.py
"""

from __future__ import annotations

import sqlite3

SCHEMA = """
CREATE TABLE members (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE loans (
  loan_id   INTEGER PRIMARY KEY,
  member_id INTEGER NOT NULL REFERENCES members(member_id)
);
"""


def read_pragma(connection: sqlite3.Connection) -> int:
    return connection.execute("PRAGMA foreign_keys").fetchone()[0]


def part_one_default_is_off() -> None:
    print("--- 1. a fresh connection does not enforce foreign keys ---")
    connection = sqlite3.connect(":memory:")
    connection.executescript(SCHEMA)
    print(f"PRAGMA foreign_keys on a new connection: {read_pragma(connection)}")

    connection.execute("INSERT INTO loans (loan_id, member_id) VALUES (1, 999)")
    orphans = connection.execute("SELECT count(*) FROM loans").fetchone()[0]
    print(f"orphan loan pointing at member 999 inserted: {orphans} row")
    connection.close()


def part_two_the_trap() -> None:
    print()
    print("--- 2. the trap: the pragma is a no-op inside an open transaction ---")
    connection = sqlite3.connect(":memory:")
    connection.executescript(SCHEMA)
    connection.execute("INSERT INTO loans (loan_id, member_id) VALUES (1, 999)")
    print(f"connection.in_transaction: {connection.in_transaction}")

    connection.execute("PRAGMA foreign_keys = ON")
    print(f"pragma set, but it reads back as: {read_pragma(connection)}")

    connection.commit()
    connection.execute("PRAGMA foreign_keys = ON")
    print(f"after commit(), setting it again reads back as: {read_pragma(connection)}")

    try:
        connection.execute("INSERT INTO loans (loan_id, member_id) VALUES (2, 999)")
    except sqlite3.IntegrityError as error:
        print(f"the same insert now raises {type(error).__name__}: {error}")
    connection.close()


def part_three_the_habit() -> None:
    print()
    print("--- 3. the habit: set it first, before anything else ---")
    connection = sqlite3.connect(":memory:")
    connection.execute("PRAGMA foreign_keys = ON")
    print(f"PRAGMA foreign_keys: {read_pragma(connection)}")
    connection.executescript(SCHEMA)
    try:
        connection.execute("INSERT INTO loans (loan_id, member_id) VALUES (1, 999)")
    except sqlite3.IntegrityError as error:
        print(f"orphan insert refused: {type(error).__name__}: {error}")
    connection.execute("INSERT INTO members (member_id, name) VALUES (999, 'Real Member')")
    connection.execute("INSERT INTO loans (loan_id, member_id) VALUES (1, 999)")
    good = connection.execute("SELECT count(*) FROM loans").fetchone()[0]
    print(f"with the parent row present, the same insert succeeds: {good} row")
    connection.close()


if __name__ == "__main__":
    part_one_default_is_off()
    part_two_the_trap()
    part_three_the_habit()

"""Day 087 · Step 8 — the N+1 query pattern, measured rather than asserted.

Looping in the application and asking the database one small question per row
is called the N+1 pattern: one query to get the list, then N more, one per item.
The alternative is one join.

This script builds a throwaway in-memory database, answers the same question
both ways, checks the two answers are identical, and reports the real query
count and the real elapsed time on THIS machine. Timings vary between machines
and between runs; the query counts do not.

Read https://www.sqlite.org/np1queryprob.html afterwards. SQLite's own
documentation argues that for an embedded database — where a query is a
function call into the same process, not a network round trip — N+1 is far less
costly than the usual advice implies. The measurement below is the honest
version of that argument, not a slogan in either direction.

Run with:  python3 examples/08_n_plus_one.py
"""

from __future__ import annotations

import sqlite3
import time

MEMBERS = 500
LOANS_PER_MEMBER = 4


def build() -> sqlite3.Connection:
    connection = sqlite3.connect(":memory:")
    connection.execute("PRAGMA foreign_keys = ON")
    connection.executescript(
        """
        CREATE TABLE members (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL);
        CREATE TABLE loans (
          loan_id   INTEGER PRIMARY KEY,
          member_id INTEGER NOT NULL REFERENCES members(member_id),
          title     TEXT NOT NULL
        );
        """
    )
    connection.executemany(
        "INSERT INTO members (member_id, name) VALUES (?, ?)",
        [(i, f"Member {i:04d}") for i in range(1, MEMBERS + 1)],
    )
    connection.executemany(
        "INSERT INTO loans (member_id, title) VALUES (?, ?)",
        [
            (member_id, f"Book {member_id:04d}-{n}")
            for member_id in range(1, MEMBERS + 1)
            for n in range(LOANS_PER_MEMBER)
        ],
    )
    connection.execute("CREATE INDEX idx_loans_member ON loans(member_id)")
    connection.commit()
    return connection


def n_plus_one(connection: sqlite3.Connection) -> tuple[list[tuple[str, int]], int]:
    """One query for the list, then one more per member. N+1 queries in total."""
    queries = 0
    members = connection.execute("SELECT member_id, name FROM members ORDER BY name").fetchall()
    queries += 1

    result = []
    for member_id, name in members:
        count = connection.execute(
            "SELECT count(*) FROM loans WHERE member_id = ?", (member_id,)
        ).fetchone()[0]
        queries += 1
        result.append((name, count))
    return result, queries


def one_join(connection: sqlite3.Connection) -> tuple[list[tuple[str, int]], int]:
    """The same answer, in one query, with the database doing the matching."""
    rows = connection.execute(
        """
        SELECT m.name, count(l.loan_id)
          FROM members AS m
          LEFT JOIN loans AS l ON l.member_id = m.member_id
         GROUP BY m.member_id, m.name
         ORDER BY m.name
        """
    ).fetchall()
    return [(name, count) for name, count in rows], 1


def timed(function, connection):
    started = time.perf_counter()
    result, queries = function(connection)
    return result, queries, time.perf_counter() - started


def main() -> int:
    connection = build()
    print(f"{MEMBERS} members, {MEMBERS * LOANS_PER_MEMBER} loans, in memory")
    print()

    loop_result, loop_queries, loop_seconds = timed(n_plus_one, connection)
    join_result, join_queries, join_seconds = timed(one_join, connection)

    print(f"N+1 loop: {loop_queries:>4} queries   {loop_seconds * 1000:7.2f} ms")
    print(f"one join: {join_queries:>4} queries   {join_seconds * 1000:7.2f} ms")
    print()
    print("same answer:", loop_result == join_result)
    print("first three rows:", join_result[:3])
    print()
    print("Timings differ between machines and between runs. The query counts do not:")
    print(f"  {loop_queries} against {join_queries}, for the same answer.")
    print()
    print("Across a network the difference is one round trip per query. In an")
    print("embedded database it is one function call, which is why SQLite's own")
    print("documentation treats N+1 as a much smaller problem than the usual advice.")

    connection.close()
    return 0 if loop_result == join_result else 1


if __name__ == "__main__":
    raise SystemExit(main())

-- Day 087 · Step 9 — watch the planner choose an algorithm.
--
-- EXPLAIN QUERY PLAN prints how SQLite intends to answer a query. Two words
-- carry most of the meaning:
--
--   SCAN    read every row of this table
--   SEARCH  jump straight to the matching rows using an index
--
-- A SCAN of the outer table with a SEARCH of the inner one is an indexed
-- nested-loop join: the algorithm from 06_join_from_scratch.py, with the inner
-- scan replaced by an index lookup. Two SCANs with no join condition is the
-- cartesian product.
--
-- Run with:  sqlite3 library.db < examples/09_query_plans.sql

.print ''
.print '--- inner join on an indexed foreign key ---'
EXPLAIN QUERY PLAN
SELECT m.name, l.loan_id
  FROM loans   AS l
  JOIN members AS m ON m.member_id = l.member_id;

.print ''
.print '--- the same shape, outer, with the grouping on top ---'
EXPLAIN QUERY PLAN
SELECT m.name, count(l.loan_id)
  FROM members AS m
  LEFT JOIN loans AS l ON l.member_id = m.member_id
 GROUP BY m.member_id;

.print ''
.print '--- a cartesian product: two SCANs and nothing tying them together ---'
EXPLAIN QUERY PLAN
SELECT * FROM books CROSS JOIN authors;

lesson_id: D087
day: 87
kind: guided-build
languages: [sql, python, bash]
setup_commands:
  - cd labs/sections/programming-with-python/day-087-joins-and-relationships
  - python3 --version
  - sqlite3 --version
run_commands:
  - bash tests/run_tests.sh
  - sqlite3 anomalies.db < examples/01_wide_table.sql
  - sqlite3 library.db < examples/02_schema.sql
  - sqlite3 library.db < examples/03_seed.sql
  - 'sqlite3 library.db < examples/04_foreign_keys.sql  # exits non-zero on purpose'
  - sqlite3 library.db < examples/05_joins.sql
  - python3 examples/06_join_from_scratch.py library.db
  - python3 examples/07_foreign_keys_python.py
  - python3 examples/08_n_plus_one.py
  - sqlite3 library.db < examples/09_query_plans.sql
  - bash starter/01_build.sh
  - sqlite3 starter/library.db < starter/02_exercises.sql
  - python3 starter/03_join_from_scratch.py
test_commands:
  - bash tests/run_tests.sh
cleanup_commands:
  - rm -f library.db anomalies.db starter/library.db
  - find . -type d -name __pycache__ -prune -exec rm -rf -- {} +
  - 'git checkout -- starter/  # optional: reset your work'
requires_network: false
requires_api_key: false
estimated_minutes: 30
last_executed: '2026-08-16'
executed_on: 'macOS 26.5.2 (Apple Silicon, arm64), Python 3.14.0, bash 3.2.57, sqlite3 shell 3.51.0, SQLite library 3.53.3 via Python — bash tests/run_tests.sh -> 75 checks, 0 failure(s), exit 0'

# Dependencies

**None.** This lab installs nothing, and `requirements.txt` is deliberately
empty of packages.

That is not laziness; it is the point of the day. Everything here runs on two
things you already have:

| Tool | Version used here | Where it comes from | Licence |
| --- | --- | --- | --- |
| `python3` | 3.14.0 | Whatever Python you installed on Day 43. Only the standard library is used, and only the `sqlite3`, `collections`, `time`, `sys` and `pathlib` modules from it | PSF licence |
| `sqlite3` (the shell) | 3.51.0 | Preinstalled on macOS at `/usr/bin/sqlite3`; `apt install sqlite3` or the equivalent on Linux | Public domain |

Python's `sqlite3` module is a wrapper around a copy of the SQLite library
compiled into your Python. It is often a *different version* from the `sqlite3`
shell on your `PATH` — on the authoring machine the shell reported 3.51.0 while
Python reported 3.53.3. Both behave identically for everything in this lab, but
it is worth knowing that they are two separate copies, because one day a
feature will exist in one and not the other.

Check what you have:

```bash
python3 --version
sqlite3 --version
python3 -c "import sqlite3; print(sqlite3.sqlite_version)"
```

**Minimum versions.** Python 3.11 or newer (the type-hint syntax in the Python
files uses `dict | None`). SQLite 3.16.0 or newer for the `pragma_table_info`
and `pragma_foreign_key_list` table-valued functions the test suite uses; any
SQLite shipped in the last several years is far past that.

## If the tools are somewhere unusual

The test harness takes overrides rather than guessing:

```bash
PYTHON=/path/to/python3 SQLITE3=/path/to/sqlite3 bash tests/run_tests.sh
```

It fails loudly with that instruction if it cannot find either one, rather than
quietly skipping the checks that need them.

## What is deliberately absent

**No ORM.** SQLAlchemy, Django's ORM and Peewee all generate the joins this lab
writes by hand, and all of them are worth using later. Learning them before you
can read the SQL they emit means that when a query is slow or wrong you have no
way in. Write the join first; let a library write it for you afterwards.

**No database server.** PostgreSQL and MySQL are covered in the lesson's
Alternatives section, with the syntax differences that actually matter. Neither
is installed here, because installing a server changes this lab from "twenty
minutes of joins" into "an afternoon of administration", and nothing in today's
material needs one.

# Day 087 — Joins and Relationships
#
# This lab has no third-party dependencies. It uses python3 (standard library
# only, including the sqlite3 module) and the sqlite3 command-line shell, both
# of which you already have.
#
# There is nothing to install. See requirements/README.md for the versions used
# when the expected output was captured, and for why no ORM and no database
# server appear here.

#!/usr/bin/env bash
# Day 087 starter — build a fresh library.db for your own work.
#
# This script is complete and working. Run it first, and run it again whenever
# you want to start over; it drops and recreates everything.
#
#   bash starter/01_build.sh
#
# It writes starter/library.db, which is yours to break. Nothing else in the
# lab reads it.
set -eu

starter_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
lab_dir="$(cd "${starter_dir}/.." && pwd)"
database="${starter_dir}/library.db"

rm -f "${database}"
sqlite3 "${database}" < "${lab_dir}/examples/02_schema.sql"
sqlite3 "${database}" < "${lab_dir}/examples/03_seed.sql"

echo "built ${database#"${lab_dir}/"}"
sqlite3 "${database}" <<'SQL'
.mode list
.headers off
SELECT 'authors      ' || count(*) FROM authors;
SELECT 'books        ' || count(*) FROM books;
SELECT 'book_authors ' || count(*) FROM book_authors;
SELECT 'members      ' || count(*) FROM members;
SELECT 'loans        ' || count(*) FROM loans;
SQL

-- Day 087 starter — six numbered SQL exercises.
--
-- Every query below RUNS as it stands. Each one is also wrong in one specific,
-- named way. Your job is to make each one right. The comment above each
-- exercise says exactly what is wrong, what to change, and which check in
-- tests/run_tests.sh verifies it.
--
--   bash starter/01_build.sh                          # once
--   sqlite3 starter/library.db < starter/02_exercises.sql
--
-- Compare your output with examples/05_joins.sql when you are stuck. Reading
-- the answer after you have tried is learning; reading it first is not.

PRAGMA foreign_keys = ON;
.headers on
.mode column

-- ============================================================================
-- EXERCISE 1 — join two hops across the junction table.
--
-- Wrong how: it joins books to book_authors and stops, so you get author IDs
-- instead of author names.
-- Change: add a second JOIN onto authors, matching a.author_id = ba.author_id,
-- and select a.name instead of ba.author_id.
-- Correct result: 7 rows, one per book-author pair, with real names.
-- Checked by: "exercise 1: books joined to author NAMES, 7 rows"
-- ============================================================================
.print ''
.print '--- exercise 1 ---'
SELECT b.title,
       ba.author_id AS author
  FROM books AS b
  JOIN book_authors AS ba ON ba.book_id = b.book_id
 ORDER BY b.title, author;

-- ============================================================================
-- EXERCISE 2 — find the authors with no catalogued book.
--
-- Wrong how: an INNER JOIN can never show you a row that has no match, so this
-- returns every author who DOES have a book — the exact opposite.
-- Change: make it a LEFT JOIN and add "WHERE ba.author_id IS NULL".
-- Correct result: exactly one row — Donald E. Knuth.
-- Checked by: "exercise 2: authors with no catalogued book"
-- ============================================================================
.print ''
.print '--- exercise 2 ---'
SELECT a.author_id, a.name
  FROM authors AS a
  JOIN book_authors AS ba ON ba.author_id = a.author_id
 ORDER BY a.name;

-- ============================================================================
-- EXERCISE 3 — books that have never been borrowed.
--
-- Wrong how: same shape as exercise 2, one table further out. This lists books
-- that HAVE been borrowed, and lists the popular ones several times over.
-- Change: LEFT JOIN loans, then keep only the rows where l.loan_id IS NULL.
-- Correct result: exactly one row — book 104, The Practice of Programming.
-- Checked by: "exercise 3: books never borrowed"
-- ============================================================================
.print ''
.print '--- exercise 3 ---'
SELECT b.book_id, b.title
  FROM books AS b
  JOIN loans AS l ON l.book_id = b.book_id
 ORDER BY b.title;

-- ============================================================================
-- EXERCISE 4 — loans per member, INCLUDING the members who have none.
--
-- Wrong how: two separate mistakes stacked on each other. The INNER JOIN drops
-- Eli Nakamura entirely, and count(*) would report 1 for her even after you fix
-- the join, because the NULL-extended row is still a row.
-- Change: LEFT JOIN, and count a column from the RIGHT table -
-- count(l.loan_id) - so that the all-NULL row counts as zero.
-- Correct result: 5 rows. Ada 2, Bruno 2, Chandra 1, Dana 1, Eli 0.
-- Checked by: "exercise 4: loans per member with a real zero for Eli"
-- ============================================================================
.print ''
.print '--- exercise 4 ---'
SELECT m.name           AS member,
       count(*)         AS loans
  FROM members AS m
  JOIN loans AS l ON l.member_id = m.member_id
 GROUP BY m.member_id, m.name
 ORDER BY loans DESC, member;

-- ============================================================================
-- EXERCISE 5 — who referred whom (a self-join).
--
-- Wrong how: it joins members to members with an INNER JOIN, which silently
-- drops the two members nobody referred.
-- Change: LEFT JOIN, so every member appears and referred_by comes back NULL
-- for the ones who joined on their own.
-- Correct result: 5 rows. Ada and Eli have an empty referred_by.
-- Checked by: "exercise 5: self-join keeps the members nobody referred"
-- ============================================================================
.print ''
.print '--- exercise 5 ---'
SELECT m.name AS member,
       r.name AS referred_by
  FROM members AS m
  JOIN members AS r ON r.member_id = m.referred_by
 ORDER BY m.member_id;

-- ============================================================================
-- EXERCISE 6 — everything currently out on loan, across four tables.
--
-- Wrong how: it stops at three tables, so you get the title but not who wrote
-- it, and it has no filter, so returned books are in the list too.
-- Change: add the two remaining joins (book_authors, then authors) and the
-- condition l.returned_on IS NULL.
-- Correct result: 4 rows. Chandra Iyer appears twice, because the book she has
-- out has two authors - that duplication is the many-to-many showing through,
-- not a bug.
-- Checked by: "exercise 6: four-table join of what is out on loan"
-- ============================================================================
.print ''
.print '--- exercise 6 ---'
SELECT m.name  AS member,
       b.title AS title,
       l.borrowed_on
  FROM loans   AS l
  JOIN members AS m ON m.member_id = l.member_id
  JOIN books   AS b ON b.book_id   = l.book_id
 ORDER BY m.name;

"""Day 087 starter — exercises 7, 8 and 9: build the join yourself.

This file runs as it stands. It builds the same data, calls your three
functions, compares them with what SQLite says, and prints a pass or fail line
for each. Right now all three fail, because all three are unfinished in one
specific, named way.

    bash starter/01_build.sh
    python3 starter/03_join_from_scratch.py

Finish the three functions marked EXERCISE. Do not change anything below the
line that says so - that part is the referee.
"""

from __future__ import annotations

import sqlite3
import sys
from collections import defaultdict
from pathlib import Path


# ============================================================================
# EXERCISE 7 — the nested-loop join.
#
# Unfinished how: the inner comparison is missing, so every left row is paired
# with every right row. That is a cartesian product: 30 pairs instead of 6.
# Change: only append the pair when left_row[left_key] == right_row[right_key].
# Also count one comparison per pair examined, so the cost is visible.
# Correct result: 6 pairs, 30 comparisons (6 loans x 5 members).
# Checked by: "exercise 7: nested-loop join matches SQL"
# ============================================================================
def nested_loop_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> tuple[list[tuple[dict, dict]], int]:
    """For every left row, scan every right row. O(n * m)."""
    pairs: list[tuple[dict, dict]] = []
    comparisons = 0
    for left_row in left:
        for right_row in right:
            comparisons += 1
            pairs.append((left_row, right_row))  # <- exercise 7 goes here
    return pairs, comparisons


# ============================================================================
# EXERCISE 8 — the hash join.
#
# Unfinished how: the build phase is written for you. The probe phase is not,
# so no pairs come out at all.
# Change: for each left row, look its key up in `index` and append one pair per
# matching right row. Count one operation per left row probed, so the total
# comes to 11 rather than 30.
# Correct result: the same 6 pairs as exercise 7, in 11 operations (6 + 5).
# Checked by: "exercise 8: hash join matches SQL"
# ============================================================================
def hash_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> tuple[list[tuple[dict, dict]], int]:
    """Index the right side once, then look each left row up. O(n + m)."""
    index: dict[object, list[dict]] = defaultdict(list)
    operations = 0
    for right_row in right:  # build phase - complete, leave it alone
        operations += 1
        index[right_row[right_key]].append(right_row)

    pairs: list[tuple[dict, dict]] = []
    for left_row in left:  # probe phase - exercise 8 goes here
        operations += 1
    return pairs, operations


# ============================================================================
# EXERCISE 9 — the LEFT OUTER version of the hash join.
#
# Unfinished how: it behaves exactly like an inner join, so a left row with no
# match is dropped instead of surviving.
# Change: when `matches` is empty, still append one pair - (left_row, None).
# None is what SQL calls NULL: the row survives, the right-hand columns do not.
# Correct result: 7 pairs from 5 members and 6 loans, and Eli Nakamura is the
# one member paired with None.
# Checked by: "exercise 9: left outer join keeps the unmatched row"
# ============================================================================
def left_outer_hash_join(
    left: list[dict], right: list[dict], left_key: str, right_key: str
) -> list[tuple[dict, dict | None]]:
    """Every left row comes through, matched or not."""
    index: dict[object, list[dict]] = defaultdict(list)
    for right_row in right:
        index[right_row[right_key]].append(right_row)

    pairs: list[tuple[dict, dict | None]] = []
    for left_row in left:
        matches = index.get(left_row[left_key], [])
        if matches:
            pairs.extend((left_row, match) for match in matches)
        # exercise 9: the missing `else` goes here
    return pairs


# ===================== do not change anything below here =====================


def rows_from(connection: sqlite3.Connection, table: str) -> list[dict]:
    connection.row_factory = sqlite3.Row
    return [dict(row) for row in connection.execute(f"SELECT * FROM {table}")]


def as_comparable(pairs) -> list[tuple]:
    result = []
    for loan, member in pairs:
        name = member["name"] if member is not None else None
        result.append((loan["loan_id"], name, loan["borrowed_on"]))
    return sorted(result, key=lambda row: row[0])


def report(label: str, passed: bool, detail: str = "") -> bool:
    print(f"  {'ok  ' if passed else 'FAIL'}: {label}{(' — ' + detail) if detail else ''}")
    return passed


def main(database: str) -> int:
    if not Path(database).exists():
        print(f"{database} does not exist. Run: bash starter/01_build.sh")
        return 1

    connection = sqlite3.connect(database)
    connection.execute("PRAGMA foreign_keys = ON")
    loans = rows_from(connection, "loans")
    members = rows_from(connection, "members")

    connection.row_factory = None
    sql_inner = sorted(
        (row[0], row[1], row[2])
        for row in connection.execute(
            "SELECT l.loan_id, m.name, l.borrowed_on FROM loans AS l"
            " JOIN members AS m ON m.member_id = l.member_id"
        )
    )
    sql_unmatched = [
        row[0]
        for row in connection.execute(
            "SELECT m.name FROM members AS m"
            " LEFT JOIN loans AS l ON l.member_id = m.member_id"
            " WHERE l.loan_id IS NULL ORDER BY m.name"
        )
    ]
    connection.close()

    nested_pairs, comparisons = nested_loop_join(loans, members, "member_id", "member_id")
    hashed_pairs, operations = hash_join(loans, members, "member_id", "member_id")
    outer_pairs = left_outer_hash_join(members, loans, "member_id", "member_id")
    unmatched = [member["name"] for member, loan in outer_pairs if loan is None]

    print(f"SQLite says the inner join has {len(sql_inner)} rows.")
    print()

    passed = [
        report(
            "exercise 7: nested-loop join matches SQL",
            as_comparable(nested_pairs) == sql_inner and comparisons == 30,
            f"{len(nested_pairs)} pairs in {comparisons} comparisons (want 6 in 30)",
        ),
        report(
            "exercise 8: hash join matches SQL",
            as_comparable(hashed_pairs) == sql_inner and operations == 11,
            f"{len(hashed_pairs)} pairs in {operations} operations (want 6 in 11)",
        ),
        report(
            "exercise 9: left outer join keeps the unmatched row",
            len(outer_pairs) == 7 and unmatched == sql_unmatched,
            f"{len(outer_pairs)} pairs, unmatched={unmatched} (want 7, ['Eli Nakamura'])",
        ),
    ]

    print()
    done = sum(passed)
    print(f"{done} of 3 exercises complete.")
    return 0 if done == 3 else 1


if __name__ == "__main__":
    sys.exit(main(sys.argv[1] if len(sys.argv) > 1 else str(Path(__file__).parent / "library.db")))

#!/usr/bin/env bash
# Tests for the Day 087 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# Every check below compares a REAL VALUE, not the existence of a file. The
# questions the suite asks are the ones the lesson claims answers to:
#
#   * does the wide table really produce the update and deletion anomalies?
#   * does SQLite really leave foreign-key enforcement OFF by default, and does
#     the identical insert really get rejected once the pragma is on?
#   * which rows does each join type actually keep?
#   * does count(*) really give the wrong per-group count after a LEFT JOIN?
#   * does moving a predicate from ON to WHERE really change the result set —
#     in BOTH directions?
#   * do a hand-written nested-loop join and a hand-written hash join really
#     agree with SQLite, row for row?
#
# Nothing here touches the network. Nothing needs sudo. Everything is built in
# a temporary directory that is removed in a trap, so a completed run leaves
# your lab directory exactly as it found it.
set -u

lab_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
work=""
checks=0
failures=0

cleanup() {
  [ -n "${work}" ] && [ -d "${work}" ] && rm -rf "${work}"
}
trap cleanup EXIT INT TERM

check() {
  local label="$1" ok="$2"
  checks=$((checks + 1))
  if [ "${ok}" = "yes" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    failures=$((failures + 1))
  fi
}

# check_eq LABEL EXPECTED ACTUAL — prints what it wanted when it does not match.
check_eq() {
  local label="$1" expected="$2" actual="$3"
  checks=$((checks + 1))
  if [ "${expected}" = "${actual}" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    echo "        expected: ${expected}"
    echo "        actual:   ${actual}"
    failures=$((failures + 1))
  fi
}

# Resolve the two tools this lab needs, allowing an override for people who
# keep them somewhere unusual. Fails loudly rather than skipping checks.
python_bin="${PYTHON:-}"
if [ -z "${python_bin}" ]; then
  python_bin="$(command -v python3 || true)"
fi
sqlite_bin="${SQLITE3:-}"
if [ -z "${sqlite_bin}" ]; then
  sqlite_bin="$(command -v sqlite3 || true)"
fi

if [ -z "${python_bin}" ] || [ ! -x "${python_bin}" ]; then
  echo "python3 was not found. Install Python 3.11+ or set PYTHON=/path/to/python3."
  exit 1
fi
if [ -z "${sqlite_bin}" ] || [ ! -x "${sqlite_bin}" ]; then
  echo "sqlite3 was not found. Install it or set SQLITE3=/path/to/sqlite3."
  exit 1
fi

export PYTHONDONTWRITEBYTECODE=1
work="$(mktemp -d)"
db="${work}/library.db"

# q SQL — one scalar or one newline-separated column, no headers, no padding.
q() { "${sqlite_bin}" "${db}" ".mode list" ".headers off" "$1"; }

echo "Day 087 — Joins and Relationships"
echo "python3: $("${python_bin}" -c 'import sys; print(sys.version.split()[0])')"
echo "sqlite3: $("${sqlite_bin}" --version | cut -d' ' -f1)"
echo "work:    a temporary directory, removed when this script exits"
echo

# ---------------------------------------------------------------------------
echo "1. The wide table really does produce the anomalies"
# ---------------------------------------------------------------------------
wide_db="${work}/wide.db"
"${sqlite_bin}" "${wide_db}" < "${lab_dir}/examples/01_wide_table.sql" > "${work}/wide.txt" 2>&1
wide_status=$?
check_eq "01_wide_table.sql runs clean — every anomaly below is silent" "0" "${wide_status}"
check_eq "3 books needed 5 rows, because 2 authors are written down twice" \
  "5" "$(grep -c '^The ' "${work}/wide.txt" | tr -d ' ')"

# The update anomaly: one human being, two spellings, no error raised.
names_1942="$("${sqlite_bin}" "${wide_db}" ".mode list" ".headers off" \
  "SELECT count(DISTINCT author_name) FROM catalog_wide WHERE author_birth_year = 1942")"
check_eq "update anomaly: one author now has 2 different names in the table" \
  "2" "${names_1942}"

check "update anomaly: the database raised no error while contradicting itself" \
  "$(grep -qc 'Runtime error' "${work}/wide.txt" >/dev/null 2>&1 && echo no || echo yes)"

# The deletion anomaly: removing the book removed the only record of the author.
brooks="$("${sqlite_bin}" "${wide_db}" ".mode list" ".headers off" \
  "SELECT count(*) FROM catalog_wide WHERE author_name LIKE '%Brooks%'")"
check_eq "deletion anomaly: withdrawing the book erased the author entirely" \
  "0" "${brooks}"

# The insertion anomaly is structural: every book column is NOT NULL, so there
# is no row shape that records an author without inventing a book.
notnull="$("${sqlite_bin}" "${wide_db}" ".mode list" ".headers off" \
  "SELECT count(*) FROM pragma_table_info('catalog_wide') WHERE \"notnull\" = 1")"
check_eq "insertion anomaly: all 4 columns are NOT NULL, so an author needs a book" \
  "4" "${notnull}"

echo
# ---------------------------------------------------------------------------
echo "2. The split schema builds, and models the relationships properly"
# ---------------------------------------------------------------------------
"${sqlite_bin}" "${db}" < "${lab_dir}/examples/02_schema.sql" 2>"${work}/schema.err"
check "schema.sql runs without error" \
  "$([ ! -s "${work}/schema.err" ] && echo yes || echo no)"
"${sqlite_bin}" "${db}" < "${lab_dir}/examples/03_seed.sql" 2>"${work}/seed.err"
check "seed.sql runs without error" \
  "$([ ! -s "${work}/seed.err" ] && echo yes || echo no)"

check_eq "five tables exist" "5" \
  "$(q "SELECT count(*) FROM sqlite_master WHERE type='table' AND name IN ('authors','books','book_authors','members','loans')")"
check_eq "row counts are 7 authors, 4 books, 7 pairs, 5 members, 6 loans" \
  "7|4|7|5|6" \
  "$(q "SELECT (SELECT count(*) FROM authors) || '|' || (SELECT count(*) FROM books) || '|' || (SELECT count(*) FROM book_authors) || '|' || (SELECT count(*) FROM members) || '|' || (SELECT count(*) FROM loans)")"

# The junction table's primary key is the PAIR — that is what makes it a
# junction table rather than a table that happens to have two columns.
check_eq "book_authors is keyed on the PAIR (book_id, author_id)" \
  "book_id,author_id" \
  "$(q "SELECT group_concat(name) FROM (SELECT name FROM pragma_table_info('book_authors') WHERE pk > 0 ORDER BY pk)")"

# One-to-many is modelled by putting the key on the many side.
check_eq "loans (the many side) carries both foreign keys" "books|members" \
  "$(q "SELECT group_concat(t, '|') FROM (SELECT \"table\" AS t FROM pragma_foreign_key_list('loans') ORDER BY t)")"
check_eq "members references itself, which is what makes a self-join possible" \
  "members" "$(q "SELECT \"table\" FROM pragma_foreign_key_list('members')")"

echo
# ---------------------------------------------------------------------------
echo "3. PRAGMA foreign_keys is OFF by default — proved, not asserted"
# ---------------------------------------------------------------------------
fk_out="${work}/fk.txt"
"${sqlite_bin}" "${db}" < "${lab_dir}/examples/04_foreign_keys.sql" > "${fk_out}" 2>&1
fk_status=$?

check "a fresh connection reports PRAGMA foreign_keys = 0" \
  "$(grep -q 'PRAGMA foreign_keys  0' "${fk_out}" && echo yes || echo no)"
check "with it off, a loan pointing at member 999 INSERTS SUCCESSFULLY" \
  "$(grep -qE '^900 +101 +999' "${fk_out}" && echo yes || echo no)"
check "pragma_foreign_key_check finds the orphan the insert created" \
  "$(grep -qE '^loans +900 +members' "${fk_out}" && echo yes || echo no)"
check "after PRAGMA foreign_keys = ON the setting reads back as 1" \
  "$(grep -q 'PRAGMA foreign_keys  1' "${fk_out}" && echo yes || echo no)"
check "the IDENTICAL insert is then rejected: FOREIGN KEY constraint failed" \
  "$(grep -q 'FOREIGN KEY constraint failed' "${fk_out}" && echo yes || echo no)"
check_eq "sqlite3 exits non-zero when the constraint fires" "rejected" \
  "$([ "${fk_status}" -ne 0 ] && echo rejected || echo "exit ${fk_status}")"
check_eq "the orphan row is gone, so the rest of the suite sees clean data" \
  "6" "$(q "SELECT count(*) FROM loans")"

# The same fact from Python, including the transaction trap.
py_fk="${work}/fk_python.txt"
"${python_bin}" "${lab_dir}/examples/07_foreign_keys_python.py" > "${py_fk}" 2>&1
check "python: a new connection also reports foreign_keys 0" \
  "$(grep -q 'new connection: 0' "${py_fk}" && echo yes || echo no)"
check "python: the pragma is a no-op inside an open transaction (reads back 0)" \
  "$(grep -q 'reads back as: 0' "${py_fk}" && echo yes || echo no)"
check "python: after commit() the same pragma takes effect (reads back 1)" \
  "$(grep -q 'setting it again reads back as: 1' "${py_fk}" && echo yes || echo no)"
check "python: the orphan insert then raises IntegrityError" \
  "$(grep -q 'IntegrityError: FOREIGN KEY constraint failed' "${py_fk}" && echo yes || echo no)"

echo
# ---------------------------------------------------------------------------
echo "4. INNER JOIN, the comma form, and the cartesian product"
# ---------------------------------------------------------------------------
inner="SELECT b.title || ' / ' || a.name FROM books b
       JOIN book_authors ba ON ba.book_id = b.book_id
       JOIN authors a ON a.author_id = ba.author_id
       ORDER BY b.title, a.name"
check_eq "inner join across the junction returns 7 book-author pairs" "7" \
  "$(q "SELECT count(*) FROM (${inner})")"
check_eq "the co-authored C book yields both of its authors, not one row" \
  "The C Programming Language / Brian W. Kernighan
The C Programming Language / Dennis M. Ritchie" \
  "$(q "${inner}" | grep '^The C Programming Language')"

comma="SELECT b.title || ' / ' || a.name FROM books b, book_authors ba, authors a
       WHERE ba.book_id = b.book_id AND a.author_id = ba.author_id
       ORDER BY b.title, a.name"
check_eq "the old comma-join-with-WHERE form gives byte-identical output" \
  "$(q "${inner}")" "$(q "${comma}")"

check_eq "an unconstrained CROSS JOIN is 4 books x 7 authors = 28 rows" "28" \
  "$(q "SELECT count(*) FROM books CROSS JOIN authors")"
check_eq "forgetting ONE join condition turns 7 correct rows into 49" \
  "49" "$(q "SELECT count(*) FROM books b JOIN book_authors ba ON ba.book_id = b.book_id JOIN authors a ON 1=1")"

echo
# ---------------------------------------------------------------------------
echo "5. LEFT OUTER JOIN — exactly which rows survive, and what turns NULL"
# ---------------------------------------------------------------------------
check_eq "left join authors->books keeps all 7 authors, giving 8 rows" "8" \
  "$(q "SELECT count(*) FROM authors a LEFT JOIN book_authors ba ON ba.author_id = a.author_id LEFT JOIN books b ON b.book_id = ba.book_id")"
check_eq "the unmatched author survives with NULL in every right-hand column" \
  "Donald E. Knuth|1" \
  "$(q "SELECT a.name || '|' || (b.title IS NULL AND b.published_year IS NULL) FROM authors a LEFT JOIN book_authors ba ON ba.author_id = a.author_id LEFT JOIN books b ON b.book_id = ba.book_id WHERE b.book_id IS NULL")"
check_eq "the mirror INNER join drops that author, giving 7 rows" "7" \
  "$(q "SELECT count(*) FROM authors a JOIN book_authors ba ON ba.author_id = a.author_id JOIN books b ON b.book_id = ba.book_id")"

echo
# ---------------------------------------------------------------------------
echo "6. LEFT JOIN + IS NULL — the anti-join idiom"
# ---------------------------------------------------------------------------
check_eq "authors with no catalogued book" "Donald E. Knuth" \
  "$(q "SELECT a.name FROM authors a LEFT JOIN book_authors ba ON ba.author_id = a.author_id WHERE ba.author_id IS NULL ORDER BY a.name")"
check_eq "books never borrowed" "104|The Practice of Programming" \
  "$(q "SELECT b.book_id || '|' || b.title FROM books b LEFT JOIN loans l ON l.book_id = b.book_id WHERE l.loan_id IS NULL ORDER BY b.title")"
check_eq "members who have never borrowed anything" "Eli Nakamura" \
  "$(q "SELECT m.name FROM members m LEFT JOIN loans l ON l.member_id = m.member_id WHERE l.loan_id IS NULL ORDER BY m.name")"
check_eq "NOT IN answers the same question here, since no member_id is NULL" \
  "Eli Nakamura" \
  "$(q "SELECT name FROM members WHERE member_id NOT IN (SELECT member_id FROM loans) ORDER BY name")"

echo
# ---------------------------------------------------------------------------
echo "7. Joins with GROUP BY — the zero-count trap"
# ---------------------------------------------------------------------------
check_eq "LEFT JOIN with count(l.loan_id) gives a genuine zero for Eli" \
  "Ada Okafor|2
Bruno Salgado|2
Chandra Iyer|1
Dana Whitfield|1
Eli Nakamura|0" \
  "$(q "SELECT m.name || '|' || count(l.loan_id) FROM members m LEFT JOIN loans l ON l.member_id = m.member_id GROUP BY m.member_id, m.name ORDER BY count(l.loan_id) DESC, m.name")"

check_eq "count(*) instead reports 1 for the member who borrowed nothing" "1" \
  "$(q "SELECT count(*) FROM members m LEFT JOIN loans l ON l.member_id = m.member_id WHERE m.name = 'Eli Nakamura' GROUP BY m.member_id")"

check_eq "an INNER JOIN drops her from the report altogether: 4 rows, not 5" "4" \
  "$(q "SELECT count(*) FROM (SELECT m.member_id FROM members m JOIN loans l ON l.member_id = m.member_id GROUP BY m.member_id)")"

check_eq "times borrowed per book, with a real zero for the unread one" \
  "The C Programming Language|3
The Mythical Man-Month|2
Artificial Intelligence: A Modern Approach|1
The Practice of Programming|0" \
  "$(q "SELECT b.title || '|' || count(l.loan_id) FROM books b LEFT JOIN loans l ON l.book_id = b.book_id GROUP BY b.book_id, b.title ORDER BY count(l.loan_id) DESC, b.title")"

echo
# ---------------------------------------------------------------------------
echo "8. ON versus WHERE on an outer join — wrong in BOTH directions"
# ---------------------------------------------------------------------------
on_form="SELECT m.name || '|' || coalesce(l.loan_id, 'none')
         FROM members m LEFT JOIN loans l
           ON l.member_id = m.member_id AND l.returned_on IS NULL
         ORDER BY m.name, l.loan_id"
where_form="SELECT m.name || '|' || coalesce(l.loan_id, 'none')
            FROM members m LEFT JOIN loans l ON l.member_id = m.member_id
            WHERE l.returned_on IS NULL
            ORDER BY m.name, l.loan_id"

check_eq "predicate in ON: all 5 members survive, unmatched ones showing none" \
  "Ada Okafor|2
Bruno Salgado|6
Chandra Iyer|4
Dana Whitfield|none
Eli Nakamura|none" \
  "$(q "${on_form}")"

check_eq "predicate in WHERE: only 4 rows — the outer join has collapsed" "4" \
  "$(q "SELECT count(*) FROM (${where_form})")"

check_eq "WHERE drops Dana, who is a member and has genuinely returned everything" \
  "0" "$(q "SELECT count(*) FROM members m LEFT JOIN loans l ON l.member_id = m.member_id WHERE l.returned_on IS NULL AND m.name = 'Dana Whitfield'")"

check_eq "and WHERE KEEPS Eli, who never borrowed at all — a false positive" \
  "1" "$(q "SELECT count(*) FROM members m LEFT JOIN loans l ON l.member_id = m.member_id WHERE l.returned_on IS NULL AND m.name = 'Eli Nakamura'")"

echo
# ---------------------------------------------------------------------------
echo "9. Self-joins and three-or-more-table joins"
# ---------------------------------------------------------------------------
check_eq "self-join with LEFT keeps the two members nobody referred" \
  "Ada Okafor|
Bruno Salgado|Ada Okafor
Chandra Iyer|Ada Okafor
Dana Whitfield|Bruno Salgado
Eli Nakamura|" \
  "$(q "SELECT m.name || '|' || coalesce(r.name, '') FROM members m LEFT JOIN members r ON r.member_id = m.referred_by ORDER BY m.member_id")"

check_eq "self-join with INNER silently loses those two" "3" \
  "$(q "SELECT count(*) FROM members m JOIN members r ON r.member_id = m.referred_by")"

check_eq "four tables at once: what is out on loan, with authors" \
  "Ada Okafor|The Mythical Man-Month|Frederick P. Brooks Jr.
Bruno Salgado|The Mythical Man-Month|Frederick P. Brooks Jr.
Chandra Iyer|Artificial Intelligence: A Modern Approach|Peter Norvig
Chandra Iyer|Artificial Intelligence: A Modern Approach|Stuart J. Russell" \
  "$(q "SELECT m.name || '|' || b.title || '|' || a.name FROM loans l JOIN members m ON m.member_id = l.member_id JOIN books b ON b.book_id = l.book_id JOIN book_authors ba ON ba.book_id = b.book_id JOIN authors a ON a.author_id = ba.author_id WHERE l.returned_on IS NULL ORDER BY m.name, a.name")"

check_eq "3 loans are outstanding, but the author join makes 4 rows — not a bug" \
  "3|4" \
  "$(q "SELECT (SELECT count(*) FROM loans WHERE returned_on IS NULL) || '|' || (SELECT count(*) FROM loans l JOIN books b ON b.book_id = l.book_id JOIN book_authors ba ON ba.book_id = b.book_id WHERE l.returned_on IS NULL)")"

echo
# ---------------------------------------------------------------------------
echo "10. The join implemented from scratch in Python agrees with SQL"
# ---------------------------------------------------------------------------
scratch="${work}/scratch.txt"
"${python_bin}" "${lab_dir}/examples/06_join_from_scratch.py" "${db}" > "${scratch}" 2>&1
scratch_status=$?
check_eq "06_join_from_scratch.py exits 0" "0" "${scratch_status}"
check "nested-loop join equals the SQL result" \
  "$(grep -q 'nested-loop == SQL: True' "${scratch}" && echo yes || echo no)"
check "hash join equals the SQL result" \
  "$(grep -q 'hash        == SQL: True' "${scratch}" && echo yes || echo no)"
check "the two algorithms agree with each other" \
  "$(grep -q 'nested-loop == hash: True' "${scratch}" && echo yes || echo no)"
check "nested loop costs 30 comparisons (6 x 5)" \
  "$(grep -q '30 key comparisons' "${scratch}" && echo yes || echo no)"
check "the hash join costs 11 operations (6 + 5) for the same answer" \
  "$(grep -q '11 operations' "${scratch}" && echo yes || echo no)"
check "the hand-written outer join keeps Eli Nakamura, as SQL does" \
  "$(grep -q "outer join agrees with SQL: True" "${scratch}" && echo yes || echo no)"

echo
# ---------------------------------------------------------------------------
echo "11. N+1 queries against one join — measured on this machine"
# ---------------------------------------------------------------------------
n1="${work}/n1.txt"
"${python_bin}" "${lab_dir}/examples/08_n_plus_one.py" > "${n1}" 2>&1
n1_status=$?
check_eq "08_n_plus_one.py exits 0" "0" "${n1_status}"
check "the loop really issues 501 queries" \
  "$(grep -qE 'N\+1 loop: +501 queries' "${n1}" && echo yes || echo no)"
check "the join really issues 1" \
  "$(grep -qE 'one join: +1 queries' "${n1}" && echo yes || echo no)"
check "both produce the same answer, so the comparison is fair" \
  "$(grep -q 'same answer: True' "${n1}" && echo yes || echo no)"

echo
# ---------------------------------------------------------------------------
echo "12. The planner really is choosing a join algorithm"
# ---------------------------------------------------------------------------
plans="${work}/plans.txt"
"${sqlite_bin}" "${db}" < "${lab_dir}/examples/09_query_plans.sql" > "${plans}" 2>&1
check "an indexed inner join plans as SCAN one side, SEARCH the other" \
  "$(grep -q 'SCAN l USING COVERING INDEX' "${plans}" && grep -q 'SEARCH m USING INTEGER PRIMARY KEY' "${plans}" && echo yes || echo no)"
check "the outer join is planned with a LEFT-JOIN marker on the inner search" \
  "$(grep -q 'LEFT-JOIN' "${plans}" && echo yes || echo no)"
check "a cartesian product plans as two bare SCANs and nothing else" \
  "$(grep -q 'SCAN books' "${plans}" && grep -q 'SCAN authors' "${plans}" && echo yes || echo no)"

echo
# ---------------------------------------------------------------------------
echo "13. The starter is runnable, and honest about being unfinished"
# ---------------------------------------------------------------------------
starter_db="${work}/starter.db"
"${sqlite_bin}" "${starter_db}" < "${lab_dir}/examples/02_schema.sql" 2>/dev/null
"${sqlite_bin}" "${starter_db}" < "${lab_dir}/examples/03_seed.sql" 2>/dev/null
"${sqlite_bin}" "${starter_db}" < "${lab_dir}/starter/02_exercises.sql" > "${work}/starter_sql.txt" 2>&1
starter_sql_status=$?
check_eq "the SQL starter runs end to end before you have changed anything" \
  "0" "${starter_sql_status}"
check "the SQL starter carries all six numbered exercises" \
  "$([ "$(grep -c '^-- EXERCISE [1-6] ' "${lab_dir}/starter/02_exercises.sql")" -eq 6 ] && echo yes || echo no)"
check "each SQL exercise names the check that verifies it" \
  "$([ "$(grep -c '^-- Checked by:' "${lab_dir}/starter/02_exercises.sql")" -eq 6 ] && echo yes || echo no)"

"${python_bin}" "${lab_dir}/starter/03_join_from_scratch.py" "${starter_db}" > "${work}/starter_py.txt" 2>&1
starter_py_status=$?
check_eq "the Python starter runs, and reports 0 of 3 exercises complete" "0 of 3 exercises complete." \
  "$(grep -o '. of 3 exercises complete.' "${work}/starter_py.txt")"
check_eq "the Python starter exits non-zero while it is unfinished" "unfinished" \
  "$([ "${starter_py_status}" -ne 0 ] && echo unfinished || echo "exit ${starter_py_status}")"

# The most important check in this section: fill the three gaps in a COPY of
# the starter and confirm it then passes. A starter whose exercises cannot be
# completed, or a checker that would pass anyway, is worth nothing.
solved="${work}/solved.py"
"${python_bin}" - "${lab_dir}/starter/03_join_from_scratch.py" "${solved}" <<'PY'
import sys
source, target = sys.argv[1], sys.argv[2]
text = open(source, encoding="utf-8").read()
replacements = [
    (
        "            pairs.append((left_row, right_row))  # <- exercise 7 goes here",
        "            if left_row[left_key] == right_row[right_key]:\n"
        "                pairs.append((left_row, right_row))",
    ),
    (
        "    for left_row in left:  # probe phase - exercise 8 goes here\n"
        "        operations += 1\n",
        "    for left_row in left:\n"
        "        operations += 1\n"
        "        for right_row in index.get(left_row[left_key], ()):\n"
        "            pairs.append((left_row, right_row))\n",
    ),
    (
        "        # exercise 9: the missing `else` goes here",
        "        else:\n            pairs.append((left_row, None))",
    ),
]
for old, new in replacements:
    assert old in text, f"starter text drifted: {old!r}"
    text = text.replace(old, new)
open(target, "w", encoding="utf-8").write(text)
PY
check "the three starter gaps are still exactly where the answer key expects" \
  "$([ -f "${solved}" ] && echo yes || echo no)"

"${python_bin}" "${solved}" "${starter_db}" > "${work}/solved.txt" 2>&1
solved_status=$?
check_eq "completing the three exercises makes the starter pass" "3 of 3 exercises complete." \
  "$(grep -o '. of 3 exercises complete.' "${work}/solved.txt")"
check_eq "and exit 0" "0" "${solved_status}"

echo
# ---------------------------------------------------------------------------
echo "14. Hygiene: offline, no privilege, no mess left behind"
# ---------------------------------------------------------------------------
# Every URL anywhere in the lab's scripts, and every line that would actually
# RUN sudo (as opposed to a comment saying this lab does not need it).
"${python_bin}" - "${lab_dir}" > "${work}/hygiene.txt" 2>&1 <<'PY'
import re
import sys
from pathlib import Path

root = Path(sys.argv[1])
urls, sudo_lines = set(), []
comment = re.compile(r"^\s*(#|--)")
for path in sorted(root.rglob("*")):
    if not path.is_file() or path.suffix not in {".sql", ".py", ".sh"}:
        continue
    for number, line in enumerate(
        path.read_text(encoding="utf-8", errors="ignore").splitlines(), 1
    ):
        urls.update(re.findall(r"https?://[^\s\"')]+", line))
        if re.search(r"(^|[;|&(]\s*)sudo\s", line) and not comment.match(line):
            sudo_lines.append(f"{path.name}:{number}")
print("URLS " + " ".join(sorted(urls)))
print("SUDO " + " ".join(sudo_lines))
PY
check_eq "the only URL anywhere in the lab's scripts is the cited SQLite page" \
  "URLS https://www.sqlite.org/np1queryprob.html" \
  "$(grep '^URLS ' "${work}/hygiene.txt")"
check_eq "no line in this lab would actually invoke sudo" "SUDO" \
  "$(grep '^SUDO ' "${work}/hygiene.txt" | sed 's/ *$//')"
check "nothing in this lab imports a networking module" \
  "$(grep -rlE '^\s*(import|from)\s+(socket|urllib|http|requests)' "${lab_dir}/examples" "${lab_dir}/starter" >/dev/null 2>&1 && echo no || echo yes)"
check "no captured output leaks an absolute home path" \
  "$(grep -rl '/Users/\|/home/' "${lab_dir}/expected-output" >/dev/null 2>&1 && echo no || echo yes)"
check "this suite created no database inside the lab directory" \
  "$([ ! -f "${lab_dir}/library.db" ] && echo yes || echo no)"

echo
echo "${checks} checks, ${failures} failure(s)."
[ "${failures}" -eq 0 ]