Relational Databases: Tables & Keys

in reviewThis lesson is complete and being validated before release - details may still change.

Relational store

Loading interactive demo…

Three tables of the shop: customers, products, and the orders that point at both. Each table underlines its primary key; the customer and sku columns of an order are foreign keys to the other two tables. The strip beneath shows the row the current operation is trying to insert or delete, and how it fared. Tap a column header to read its role in the schema.Take the tour, or press and explore. Legend:

The panel beside the stage is the real RelationalStore class from the published library executing in your browser, with the current line highlighted.

The columns a check reads, and a row on its way in.
The row a foreign key points at, and the tapped column with the column at the other end of its pointer.
A row just stored, and an operation that went through.
A row already holding the key, a dangling pointer, a row being deleted, and a refused operation.
A row on its way out during a cascade.

rows counts what the tables hold; refused, deleted, and cascaded count the operations the checks turned away and the rows a delete took along; focus describes the tapped column.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Tables, rows, and what relational means. A relational database keeps its facts in tables: a header of attributes and one row per fact. Codd called a table a relation in the mathematical sense, a set of tuples drawn from the attributes' domains, $R \subseteq D_1 \times D_2 \times \cdots \times D_n$ , and that is where the name comes from. Not from relationships between tables, which the model expresses with nothing more than equal values.

Primary keys. A primary key is a set of attributes whose values identify a row: no two rows may agree on it. Customer has id, Product has sku, Order has id. The engine checks the rule on every insert, because a key that two rows shared could not name either of them, and everything that follows, pointing at a row, updating it, deleting it, depends on names that mean one thing.

Foreign keys. A foreign key is a set of attributes in one table whose values must equal the primary key of some row in another. Order.customer points at Customer.id and Order.sku at Product.sku. There is no pointer in the storage sense: the value 2 in an order is the whole link, and following it means finding the customer row whose key is 2. Equal values are the only glue the model has, and they are enough.

Referential integrity. The engine keeps one invariant: every foreign key value in the store names a row that exists. An insert is checked twice, key free and every pointer found, and refused if either fails. A delete is checked from the other side: rows that point at the doomed row would be left dangling, so the foreign key declares what happens to them. Restrict refuses the delete while any remain. Cascade removes them too, and whatever pointed at those in turn. A third rule, set null, blanks the pointer instead, which the stage leaves out since its cells hold values only.

The cost of a check. Finding whether a key is taken or a pointed row exists is a search of a table. Done as the stage does it, by reading every row, the cost is $O(n)$ per check and $O(n^2)$ to load a table of $n$ rows. Real engines keep an index on every primary key, so each check is $O(\log n)$ : the B-tree lesson that follows is how.

Order matters. The orders-first script refuses every order, because the customers and products they point at are not there yet. Loading a database is a topological sort of its foreign keys: parents before children, and a cycle of references needs either a deferred check or a row inserted with a pointer to be filled in later.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

A TableSchema is a name, attributes, a primary key, and foreign keys, each foreign key naming the table whose primary key it points at and the rule for deletes. The constructor validates all of it, so a key outside its attributes or a reference to an unknown table is a RangeError before a single row is stored.
insert checks, then writes. The key check is one find over the table's rows; the reference loop looks each foreign key up in its target and stops at the first that finds nothing. Only after both does the row join the table, which is why a refused insert leaves the store exactly as it was.
Every refusal goes through one refuse method, whatever the reason, so the trace has one reject site and the report one count. The reason travels with it: a duplicate key, a dangling reference, a delete blocked by pointing rows, or a missing row.
delete asks blocked before it removes anything. The question is recursive: a row pointing at the victim through a restricting key blocks the delete, and so does one further down a cascading chain. The answer is known before the first row goes, so a delete is all or nothing.
remove cascades through itself. It deletes the row, then finds the rows that pointed at it and removes each the same way, with the parent passed along so the trace can say what each dependent pointed at. Dependents go highest index first, so the indices of the rest stay true.
Rows are plain tuples from the relational library, the same type the normal form lessons use, and relation hands the stage a copy, never the live array.

In 1970 Edgar Codd, a mathematician at IBM's San Jose laboratory, proposed storing data as relations in the set-theoretic sense, tables of rows with no pointers or nesting, asked for by what it is rather than where it lies. IBM's hierarchical products were selling well and the idea waited; System R at IBM and Ingres at Berkeley built it anyway, inventing SQL and the first query optimizers. A start-up shipped the first commercial SQL database in 1979, and by the time SQL became a standard in 1986 the relational model was how the world kept its records.

1970Edgar F. Codd - Publishes 'A Relational Model of Data for Large Shared Data Banks' in Communications of the ACM: data as relations, with keys instead of pointers.source
1974Donald Chamberlin and Raymond Boyce - Design SEQUEL at IBM, the query language of System R that became SQL.source
1974 to 1979IBM Research and the University of California, Berkeley - System R and Ingres prove the model can be implemented efficiently, with query optimizers, transactions, and recovery.source
1979Relational Software, later Oracle - Ships Oracle V2, the first commercially available SQL relational database.source
1981Edgar F. Codd - Receives the Turing Award for the relational model.source
1986ANSI - Adopts the first SQL standard; ISO follows the next year.source

Used today

Nearly every application's records - Accounts, orders, posts, and payments live in relational tables, with foreign keys keeping each row's references honest.
Referential integrity as a contract - An order can never name a customer who does not exist, whatever bug the application has, because the engine checks every insert and delete.
The ground the next lessons stand on - Indexes find rows by key, joins follow the foreign keys, planners choose how, and transactions keep the checks true under concurrent change.

script

on delete

rows: 19 held, 19 stored
refused: 2
deleted: 0
cascaded: 0
focus: tap a column header to read its role

relational-store.ts

import type { Relation, Scalar, Tuple } from "../relational/relation";import { RelationQuery } from "../relational/relation-query";import type { Tracer } from "../trace";export const MAX_TABLES = 3;/** Rows a table may hold: the RelationTable primitive draws every one. */export const MAX_ROWS = 12;export const MAX_OPS = 40;/** What happens to the rows that point at a row being deleted. */export const DELETE_RULES = ["restrict", "cascade"] as const;export type DeleteRule = (typeof DELETE_RULES)[number];export interface ForeignKey {  /** The pointing attributes, in the order of the target's primary key. */  attributes: readonly string[];  /** The table whose primary key the attributes name. */  references: string;  onDelete: DeleteRule;}export interface TableSchema {  name: string;  attributes: readonly string[];  primaryKey: readonly string[];  foreignKeys: readonly ForeignKey[];}export type StoreOp =  | { kind: "insert"; table: string; tuple: Tuple }  | { kind: "delete"; table: string; key: Tuple };export type RefusalReason = "duplicate-key" | "dangling-reference" | "referenced" | "missing-row";export interface OpOutcome {  ok: boolean;  reason: RefusalReason | null;  /** Dependent rows removed along with a deleted row. */  cascaded: number;}export interface StoreReport {  inserted: number;  rejected: number;  deleted: number;  cascaded: number;}/** A row that points at another: its table, its index there, and the rule of the key it points with. */interface Dependent {  table: string;  index: number;  onDelete: DeleteRule;}/** * A relational database is tables of rows whose keys point at each * other, and an engine that refuses every row that would break a * pointer. Each table declares a primary key, attributes whose values * identify a row, and foreign keys, attributes whose values must equal * the primary key of some row in another table. An insert is checked * twice: the key must not already be taken, and every foreign key must * find its row. A delete finds the row, then the rows that point at it: * under restrict they block the delete, under cascade they go with it, * and a row they are pointed at by goes in turn. The checks are what * "referential integrity" means, and they are the reason an order can * never name a customer who does not exist. * * Time: O(rows) per check, O(tables * rows) per delete. Space: O(rows). */export class RelationalStore {  private readonly schemas: ReadonlyMap<string, TableSchema>;  private readonly rows = new Map<string, Tuple[]>();  private ops = 0;  private inserted = 0;  private rejected = 0;  private deleted = 0;  private cascaded = 0;  constructor(    schemas: readonly TableSchema[],    private readonly tracer?: Tracer,  ) {    if (schemas.length < 1 || schemas.length > MAX_TABLES) throw new RangeError(`a store holds 1 to ${MAX_TABLES} tables`);    const byName = new Map<string, TableSchema>();    for (const schema of schemas) {      if (byName.has(schema.name)) throw new RangeError(`table "${schema.name}" is declared twice`);      if (schema.attributes.length === 0 || new Set(schema.attributes).size !== schema.attributes.length) throw new RangeError(`table "${schema.name}" needs distinct attributes`);      if (schema.primaryKey.length === 0 || !schema.primaryKey.every((a) => schema.attributes.includes(a))) throw new RangeError(`table "${schema.name}" needs a primary key among its attributes`);      byName.set(schema.name, schema);      this.rows.set(schema.name, []);    }    for (const schema of schemas) {      for (const fk of schema.foreignKeys) {      for (const foreignKey of schema.foreignKeys) {        const target = byName.get(fk.references);        const target = byName.get(foreignKey.references);        if (!target) throw new RangeError(`table "${schema.name}" references unknown table "${fk.references}"`);        if (fk.attributes.length !== target.primaryKey.length || !fk.attributes.every((a) => schema.attributes.includes(a))) throw new RangeError(`a foreign key of "${schema.name}" must match the primary key of "${fk.references}"`);        if (foreignKey.attributes.length !== target.primaryKey.length || !foreignKey.attributes.every((a) => schema.attributes.includes(a))) throw new RangeError(`a foreign key of "${schema.name}" must match the primary key of "${fk.references}"`);        if (!DELETE_RULES.includes(fk.onDelete)) throw new RangeError(`unknown delete rule ${String(fk.onDelete)}`);        if (!DELETE_RULES.includes(foreignKey.onDelete)) throw new RangeError(`unknown delete rule ${String(fk.onDelete)}`);      }    }    this.schemas = byName;  }  /** The table's rows as a relation; a copy. */  relation(table: string): Relation {    const schema = this.schema(table);    return { name: schema.name, attributes: [...schema.attributes], tuples: this.rows.get(table)!.map((row) => ({ ...row })) };  }  /** Every table's schema, in declaration order. */  tables(): readonly TableSchema[] {    return [...this.schemas.values()];  }  /** One row in: the key must be free and every foreign key must find its row. */  insert(table: string, tuple: Tuple): OpOutcome {    const schema = this.schema(table);    this.checkShape(schema, tuple, schema.attributes);    this.countOp();    const rows = this.rows.get(table)!;    const key = this.valuesOf(tuple, schema.primaryKey);    // ▸ a row arrives for a table: before it is stored, its key and its pointers are checked    this.tracer?.emit("insert", { table, tuple: { ...tuple }, rows: rows.length });    const clash = rows.find((row) => this.sameKey(row, tuple, schema.primaryKey));    // ▸ look for a row already holding this primary key: two rows may never share one    this.tracer?.emit("key", { table, key, duplicate: clash !== undefined, clash: clash ? this.valuesOf(clash, schema.primaryKey) : null });    if (clash) return this.refuse(table, "insert", "duplicate-key");    for (const fk of schema.foreignKeys) {    for (const foreignKey of schema.foreignKeys) {      const target = this.schemas.get(fk.references)!;      const target = this.schemas.get(foreignKey.references)!;      const value = this.valuesOf(tuple, fk.attributes);      const value = this.valuesOf(tuple, foreignKey.attributes);      const exists = this.rows.get(fk.references)!.some((row) => JSON.stringify(this.valuesOf(row, target.primaryKey)) === JSON.stringify(value));      const exists = this.rows.get(foreignKey.references)!.some((row) => JSON.stringify(this.valuesOf(row, target.primaryKey)) === JSON.stringify(value));      // ▸ for each foreign key, look for the row it points at in the other table      this.tracer?.emit("reference", { table, attributes: [...fk.attributes], target: fk.references, value, exists });      this.tracer?.emit("reference", { table, attributes: [...foreignKey.attributes], target: foreignKey.references, value, exists });      if (!exists) return this.refuse(table, "insert", "dangling-reference");    }    if (rows.length >= MAX_ROWS) throw new RangeError(`table "${table}" is full at ${MAX_ROWS} rows`);    rows.push({ ...tuple });    this.inserted++;    // ▸ the key was free and every pointer found its row, so the row goes in    this.tracer?.emit("store", { table, key, rows: rows.length });    return { ok: true, reason: null, cascaded: 0 };  }  /** One row out: it must exist, and the rows pointing at it decide whether it may go, and what goes with it. */  delete(table: string, key: Tuple): OpOutcome {    const schema = this.schema(table);    this.checkShape(schema, key, schema.primaryKey);    this.countOp();    const rows = this.rows.get(table)!;    const index = rows.findIndex((row) => this.sameKey(row, key, schema.primaryKey));    // ▸ a delete names a row by its key: find it, then find the rows that point at it    this.tracer?.emit("delete", { table, key: this.valuesOf(key, schema.primaryKey), found: index !== -1 });    if (index === -1) return this.refuse(table, "delete", "missing-row");    if (this.blocked(table, rows[index]!)) return this.refuse(table, "delete", "referenced");    const before = this.cascaded;    this.remove(table, index, null);    this.deleted++;    return { ok: true, reason: null, cascaded: this.cascaded - before };  }  /** Every operation in order; a refused one counts and the rest go on. */  apply(ops: readonly StoreOp[]): StoreReport {    if (ops.length > MAX_OPS) throw new RangeError(`${ops.length} operations exceeds ${MAX_OPS}`);    for (const op of ops) {      if (op.kind === "insert") this.insert(op.table, op.tuple);      else this.delete(op.table, op.key);    }    return this.report();  }  report(): StoreReport {    return { inserted: this.inserted, rejected: this.rejected, deleted: this.deleted, cascaded: this.cascaded };  }  /** Whether some row pointing at this one, directly or through a chain, points with a restricting key. */  private blocked(table: string, row: Tuple): boolean {    return this.dependents(table, row).some((dep) => dep.onDelete === "restrict" || this.blocked(dep.table, this.rows.get(dep.table)![dep.index]!));    return this.dependents(table, row).some((pointingRow) => pointingRow.onDelete === "restrict" || this.blocked(pointingRow.table, this.rows.get(pointingRow.table)![pointingRow.index]!));  }  /** Removes a row and, through one cascade site, every row that pointed at it. */  private remove(table: string, index: number, parent: { table: string; key: Scalar[] } | null): void {    const schema = this.schemas.get(table)!;    const rows = this.rows.get(table)!;    const row = rows[index]!;    const key = this.valuesOf(row, schema.primaryKey);    if (parent) {      this.cascaded++;      // ▸ under cascade, a row that pointed at the deleted row goes with it, and so on down      this.tracer?.emit("cascade", { table, key, parent: parent.table, parentKey: parent.key, cascaded: this.cascaded });    }    rows.splice(index, 1);    // Dependents are found after the row is gone, and removed highest index first so the others keep their places.    const deps = this.dependents(table, row).sort((a, b) => (a.table === b.table ? b.index - a.index : 0));    const pointingRows = this.dependents(table, row).sort((a, b) => (a.table === b.table ? b.index - a.index : 0));    for (const dep of deps) this.remove(dep.table, dep.index, { table, key });    for (const pointingRow of pointingRows) this.remove(pointingRow.table, pointingRow.index, { table, key });  }  /** The rows of every table whose foreign key points at this row. */  private dependents(table: string, row: Tuple): Dependent[] {    const target = this.schemas.get(table)!;    const pointed = JSON.stringify(this.valuesOf(row, target.primaryKey));    const deps: Dependent[] = [];    const pointingRows: Dependent[] = [];    for (const schema of this.schemas.values()) {      for (const fk of schema.foreignKeys) {      for (const foreignKey of schema.foreignKeys) {        if (fk.references !== table) continue;        if (foreignKey.references !== table) continue;        this.rows.get(schema.name)!.forEach((candidate, index) => {          if (JSON.stringify(this.valuesOf(candidate, fk.attributes)) === pointed) deps.push({ table: schema.name, index, onDelete: fk.onDelete });          if (JSON.stringify(this.valuesOf(candidate, foreignKey.attributes)) === pointed) pointingRows.push({ table: schema.name, index, onDelete: foreignKey.onDelete });        });      }    }    return deps;    return pointingRows;  }  /** Every refusal, whatever the reason, through one site. */  private refuse(table: string, kind: StoreOp["kind"], reason: RefusalReason): OpOutcome {    this.rejected++;    // ▸ a check failed: the row or the delete is refused and the store stays as it was    this.tracer?.emit("reject", { table, kind, reason, rejected: this.rejected });    return { ok: false, reason, cascaded: 0 };  }  private schema(table: string): TableSchema {    const schema = this.schemas.get(table);    if (!schema) throw new RangeError(`no table "${table}"`);    return schema;  }  private countOp(): void {    if (this.ops >= MAX_OPS) throw new RangeError(`more than ${MAX_OPS} operations`);    this.ops++;  }  /** The tuple must carry exactly these attributes, each a scalar. */  private checkShape(schema: TableSchema, tuple: Tuple, attributes: readonly string[]): void {    for (const attribute of attributes) {      const cell = tuple[attribute];      if (cell === undefined || !RelationQuery.isAtomic(cell)) throw new RangeError(`"${schema.name}" needs a scalar ${attribute}`);    }    for (const attribute of Object.keys(tuple)) {      if (!attributes.includes(attribute)) throw new RangeError(`"${schema.name}" has no attribute ${attribute}`);    }  }  private valuesOf(tuple: Tuple, attributes: readonly string[]): Scalar[] {    return attributes.map((attribute) => RelationQuery.cell(tuple, attribute) as Scalar);  }  private sameKey(a: Tuple, b: Tuple, attributes: readonly string[]): boolean {    return RelationQuery.keyOf(a, attributes) === RelationQuery.keyOf(b, attributes);  }}

inserted =: 19
rejected =: 2
cascaded =: 0

The script "build the shop" is done: 19 rows stored, 2 operations refused, 0 rows deleted, and 0 dependent rows cascaded. Every pointer left in the store finds its row.

import type { Relation, Scalar, Tuple } from "../relational/relation";import { RelationQuery } from "../relational/relation-query";import type { Tracer } from "../trace";export const MAX_TABLES = 3;/** Rows a table may hold: the RelationTable primitive draws every one. */export const MAX_ROWS = 12;export const MAX_OPS = 40;/** What happens to the rows that point at a row being deleted. */export const DELETE_RULES = ["restrict", "cascade"] as const;export type DeleteRule = (typeof DELETE_RULES)[number];export interface ForeignKey { /** The pointing attributes, in the order of the target's primary key. */ attributes: readonly string[]; /** The table whose primary key the attributes name. */ references: string; onDelete: DeleteRule;}export interface TableSchema { name: string; attributes: readonly string[]; primaryKey: readonly string[]; foreignKeys: readonly ForeignKey[];}export type StoreOp = | { kind: "insert"; table: string; tuple: Tuple } | { kind: "delete"; table: string; key: Tuple };export type RefusalReason = "duplicate-key" | "dangling-reference" | "referenced" | "missing-row";export interface OpOutcome { ok: boolean; reason: RefusalReason | null; /** Dependent rows removed along with a deleted row. */ cascaded: number;}export interface StoreReport { inserted: number; rejected: number; deleted: number; cascaded: number;}/** A row that points at another: its table, its index there, and the rule of the key it points with. */interface Dependent { table: string; index: number; onDelete: DeleteRule;}/** * A relational database is tables of rows whose keys point at each * other, and an engine that refuses every row that would break a * pointer. Each table declares a primary key, attributes whose values * identify a row, and foreign keys, attributes whose values must equal * the primary key of some row in another table. An insert is checked * twice: the key must not already be taken, and every foreign key must * find its row. A delete finds the row, then the rows that point at it: * under restrict they block the delete, under cascade they go with it, * and a row they are pointed at by goes in turn. The checks are what * "referential integrity" means, and they are the reason an order can * never name a customer who does not exist. * * Time: O(rows) per check, O(tables * rows) per delete. Space: O(rows). */export class RelationalStore { private readonly schemas: ReadonlyMap<string, TableSchema>; private readonly rows = new Map<string, Tuple[]>(); private ops = 0; private inserted = 0; private rejected = 0; private deleted = 0; private cascaded = 0; constructor( schemas: readonly TableSchema[], private readonly tracer?: Tracer, ) { if (schemas.length < 1 || schemas.length > MAX_TABLES) throw new RangeError(`a store holds 1 to ${MAX_TABLES} tables`); const byName = new Map<string, TableSchema>(); for (const schema of schemas) { if (byName.has(schema.name)) throw new RangeError(`table "${schema.name}" is declared twice`); if (schema.attributes.length === 0 || new Set(schema.attributes).size !== schema.attributes.length) throw new RangeError(`table "${schema.name}" needs distinct attributes`); if (schema.primaryKey.length === 0 || !schema.primaryKey.every((a) => schema.attributes.includes(a))) throw new RangeError(`table "${schema.name}" needs a primary key among its attributes`); byName.set(schema.name, schema); this.rows.set(schema.name, []); } for (const schema of schemas) { for (const fk of schema.foreignKeys) { for (const foreignKey of schema.foreignKeys) { const target = byName.get(fk.references); const target = byName.get(foreignKey.references); if (!target) throw new RangeError(`table "${schema.name}" references unknown table "${fk.references}"`); if (fk.attributes.length !== target.primaryKey.length || !fk.attributes.every((a) => schema.attributes.includes(a))) throw new RangeError(`a foreign key of "${schema.name}" must match the primary key of "${fk.references}"`); if (foreignKey.attributes.length !== target.primaryKey.length || !foreignKey.attributes.every((a) => schema.attributes.includes(a))) throw new RangeError(`a foreign key of "${schema.name}" must match the primary key of "${fk.references}"`); if (!DELETE_RULES.includes(fk.onDelete)) throw new RangeError(`unknown delete rule ${String(fk.onDelete)}`); if (!DELETE_RULES.includes(foreignKey.onDelete)) throw new RangeError(`unknown delete rule ${String(fk.onDelete)}`); } } this.schemas = byName; } /** The table's rows as a relation; a copy. */ relation(table: string): Relation { const schema = this.schema(table); return { name: schema.name, attributes: [...schema.attributes], tuples: this.rows.get(table)!.map((row) => ({ ...row })) }; } /** Every table's schema, in declaration order. */ tables(): readonly TableSchema[] { return [...this.schemas.values()]; } /** One row in: the key must be free and every foreign key must find its row. */ insert(table: string, tuple: Tuple): OpOutcome { const schema = this.schema(table); this.checkShape(schema, tuple, schema.attributes); this.countOp(); const rows = this.rows.get(table)!; const key = this.valuesOf(tuple, schema.primaryKey); // ▸ a row arrives for a table: before it is stored, its key and its pointers are checked this.tracer?.emit("insert", { table, tuple: { ...tuple }, rows: rows.length }); const clash = rows.find((row) => this.sameKey(row, tuple, schema.primaryKey)); // ▸ look for a row already holding this primary key: two rows may never share one this.tracer?.emit("key", { table, key, duplicate: clash !== undefined, clash: clash ? this.valuesOf(clash, schema.primaryKey) : null }); if (clash) return this.refuse(table, "insert", "duplicate-key"); for (const fk of schema.foreignKeys) { for (const foreignKey of schema.foreignKeys) { const target = this.schemas.get(fk.references)!; const target = this.schemas.get(foreignKey.references)!; const value = this.valuesOf(tuple, fk.attributes); const value = this.valuesOf(tuple, foreignKey.attributes); const exists = this.rows.get(fk.references)!.some((row) => JSON.stringify(this.valuesOf(row, target.primaryKey)) === JSON.stringify(value)); const exists = this.rows.get(foreignKey.references)!.some((row) => JSON.stringify(this.valuesOf(row, target.primaryKey)) === JSON.stringify(value)); // ▸ for each foreign key, look for the row it points at in the other table this.tracer?.emit("reference", { table, attributes: [...fk.attributes], target: fk.references, value, exists }); this.tracer?.emit("reference", { table, attributes: [...foreignKey.attributes], target: foreignKey.references, value, exists }); if (!exists) return this.refuse(table, "insert", "dangling-reference"); } if (rows.length >= MAX_ROWS) throw new RangeError(`table "${table}" is full at ${MAX_ROWS} rows`); rows.push({ ...tuple }); this.inserted++; // ▸ the key was free and every pointer found its row, so the row goes in this.tracer?.emit("store", { table, key, rows: rows.length }); return { ok: true, reason: null, cascaded: 0 }; } /** One row out: it must exist, and the rows pointing at it decide whether it may go, and what goes with it. */ delete(table: string, key: Tuple): OpOutcome { const schema = this.schema(table); this.checkShape(schema, key, schema.primaryKey); this.countOp(); const rows = this.rows.get(table)!; const index = rows.findIndex((row) => this.sameKey(row, key, schema.primaryKey)); // ▸ a delete names a row by its key: find it, then find the rows that point at it this.tracer?.emit("delete", { table, key: this.valuesOf(key, schema.primaryKey), found: index !== -1 }); if (index === -1) return this.refuse(table, "delete", "missing-row"); if (this.blocked(table, rows[index]!)) return this.refuse(table, "delete", "referenced"); const before = this.cascaded; this.remove(table, index, null); this.deleted++; return { ok: true, reason: null, cascaded: this.cascaded - before }; } /** Every operation in order; a refused one counts and the rest go on. */ apply(ops: readonly StoreOp[]): StoreReport { if (ops.length > MAX_OPS) throw new RangeError(`${ops.length} operations exceeds ${MAX_OPS}`); for (const op of ops) { if (op.kind === "insert") this.insert(op.table, op.tuple); else this.delete(op.table, op.key); } return this.report(); } report(): StoreReport { return { inserted: this.inserted, rejected: this.rejected, deleted: this.deleted, cascaded: this.cascaded }; } /** Whether some row pointing at this one, directly or through a chain, points with a restricting key. */ private blocked(table: string, row: Tuple): boolean { return this.dependents(table, row).some((dep) => dep.onDelete === "restrict" || this.blocked(dep.table, this.rows.get(dep.table)![dep.index]!)); return this.dependents(table, row).some((pointingRow) => pointingRow.onDelete === "restrict" || this.blocked(pointingRow.table, this.rows.get(pointingRow.table)![pointingRow.index]!)); } /** Removes a row and, through one cascade site, every row that pointed at it. */ private remove(table: string, index: number, parent: { table: string; key: Scalar[] } | null): void { const schema = this.schemas.get(table)!; const rows = this.rows.get(table)!; const row = rows[index]!; const key = this.valuesOf(row, schema.primaryKey); if (parent) { this.cascaded++; // ▸ under cascade, a row that pointed at the deleted row goes with it, and so on down this.tracer?.emit("cascade", { table, key, parent: parent.table, parentKey: parent.key, cascaded: this.cascaded }); } rows.splice(index, 1); // Dependents are found after the row is gone, and removed highest index first so the others keep their places. const deps = this.dependents(table, row).sort((a, b) => (a.table === b.table ? b.index - a.index : 0)); const pointingRows = this.dependents(table, row).sort((a, b) => (a.table === b.table ? b.index - a.index : 0)); for (const dep of deps) this.remove(dep.table, dep.index, { table, key }); for (const pointingRow of pointingRows) this.remove(pointingRow.table, pointingRow.index, { table, key }); } /** The rows of every table whose foreign key points at this row. */ private dependents(table: string, row: Tuple): Dependent[] { const target = this.schemas.get(table)!; const pointed = JSON.stringify(this.valuesOf(row, target.primaryKey)); const deps: Dependent[] = []; const pointingRows: Dependent[] = []; for (const schema of this.schemas.values()) { for (const fk of schema.foreignKeys) { for (const foreignKey of schema.foreignKeys) { if (fk.references !== table) continue; if (foreignKey.references !== table) continue; this.rows.get(schema.name)!.forEach((candidate, index) => { if (JSON.stringify(this.valuesOf(candidate, fk.attributes)) === pointed) deps.push({ table: schema.name, index, onDelete: fk.onDelete }); if (JSON.stringify(this.valuesOf(candidate, foreignKey.attributes)) === pointed) pointingRows.push({ table: schema.name, index, onDelete: foreignKey.onDelete }); }); } } return deps; return pointingRows; } /** Every refusal, whatever the reason, through one site. */ private refuse(table: string, kind: StoreOp["kind"], reason: RefusalReason): OpOutcome { this.rejected++; // ▸ a check failed: the row or the delete is refused and the store stays as it was this.tracer?.emit("reject", { table, kind, reason, rejected: this.rejected }); return { ok: false, reason, cascaded: 0 }; } private schema(table: string): TableSchema { const schema = this.schemas.get(table); if (!schema) throw new RangeError(`no table "${table}"`); return schema; } private countOp(): void { if (this.ops >= MAX_OPS) throw new RangeError(`more than ${MAX_OPS} operations`); this.ops++; } /** The tuple must carry exactly these attributes, each a scalar. */ private checkShape(schema: TableSchema, tuple: Tuple, attributes: readonly string[]): void { for (const attribute of attributes) { const cell = tuple[attribute]; if (cell === undefined || !RelationQuery.isAtomic(cell)) throw new RangeError(`"${schema.name}" needs a scalar ${attribute}`); } for (const attribute of Object.keys(tuple)) { if (!attributes.includes(attribute)) throw new RangeError(`"${schema.name}" has no attribute ${attribute}`); } } private valuesOf(tuple: Tuple, attributes: readonly string[]): Scalar[] { return attributes.map((attribute) => RelationQuery.cell(tuple, attribute) as Scalar); } private sameKey(a: Tuple, b: Tuple, attributes: readonly string[]): boolean { return RelationQuery.keyOf(a, attributes) === RelationQuery.keyOf(b, attributes); }}