OMDB (On My DataBase or Oh My DataBase) base schema sketch

init.sql

create schema if not exists omdb;

-- Record types have a 1:1 table to store each record in.
create table if not exists omdb.types (
  id text primary key,
  -- Table of all (checkpoint) snapshots of records for this type.
  snapshots text unique not null,
  -- Fully materialized table of latest records for this type.
  latest text unique not null,
  created_at timestamptz not null default now()
);

-- Every record has a type.
create table if not exists omdb.records (
  id uuid primary key,
  "type" text not null references omdb.types(id),
  created_at timestamptz not null default now()
);
-- All records of a given type.
create index if not exists omdb_records_by_type
  on omdb.records("type");

-- Operations have predicates which must be true to apply the operation.
-- An operation mutates one record specifially by applying a named operation
-- with certain parameters on a set of affected fields of the record specified
-- by the path.
-- Operations may or may not commute with other operations.
-- The predicates specify logical dependencies for an operation.
-- Conflicts happen when other operations break a proposed operation's
-- predicates.
create table if not exists omdb.operations (
  id bigserial primary key,
  predicates jsonb not null,
  record uuid not null references omdb.records(id),
  "path" jsonb not null,
  operation text not null,
  parameters jsonb not null
);
-- All operations applied to a record on all branches.
create index if not exists omdb_operations_by_record
  on omdb.operations(record);

-- Commits are topologically ordered by logical time.
create table if not exists omdb.commits (
  id bigserial primary key,
  logical_time bigint not null,
  ts timestamptz not null default now()
);
-- All commits at a topological depth (logical time).
create index if not exists omdb_commits_by_logical_time
  on omdb.commits(logical_time);

-- Commits form a DAG.
create table if not exists omdb.commit_to_commit (
  parent bigint not null references omdb.commits(id),
  child bigint not null references omdb.commits(id),
  primary key (parent, child)
);
-- All children of a parent commit.
create index if not exists omdb_commit_to_commit_by_parent
  on omdb.commit_to_commit(parent);
-- All parents of a child commit.
create index if not exists omdb_commit_to_commit_by_child
  on omdb.commit_to_commit(child);

-- Commits contain operations.
create table if not exists omdb.operation_to_commit (
  operation bigint not null references omdb.operations(id) primary key,
  "commit" bigint not null references omdb.commits(id)
);
-- All operations in a commit.
create index if not exists omdb_operation_to_commit_by_commit
  on omdb.operation_to_commit("commit");

-- Frontiers are antichains of commits
-- (no commit is an ancestor or descendant of another)
-- where the commits do no conflict with each other.
-- Walking the full DAG of commits and applying the operations
-- constructs a consistent full state at each commit.
-- A frontier view is equivalent to a merged view of those commits.

-- Named frontiers.
create table if not exists omdb.frontiers (
  id text primary key
);
-- Frontier name and commit pairs.
create table if not exists omdb.frontier_commits (
  frontier text not null references omdb.frontiers(id),
  "commit" bigint not null references omdb.commits(id),
  primary key (frontier, "commit")
);
-- All commits at a named frontier.
create index if not exists omdb_frontier_commits_by_frontier
  on omdb.frontier_commits(frontier);

-- Only the operations operating on a given record, grouped by commit,
-- by that record.
create table if not exists omdb.record_wise_operations (
  record uuid not null references omdb.records(id),
  "commit" bigint not null references omdb.commits(id),
  operation bigint not null references omdb.operations(id),
  primary key (record, "commit", operation)
);
-- By record at all commits.
create index if not exists omdb_record_wise_operations_by_record
  on omdb.record_wise_operations(record);
-- By record at a specific commit.
create index if not exists omdb_record_wise_operations_by_record_commit
  on omdb.record_wise_operations(record, "commit");

-- A DAG of those commits.
create table if not exists omdb.record_wise_operations_edges (
  record uuid not null references omdb.records(id),
  parent bigint not null references omdb.commits(id),
  child bigint not null references omdb.commits(id),
  primary key (record, parent, child)
);
-- Child commits on a record by record and parent commit on that record.
create index if not exists omdb_record_wise_operations_edges_by_record_parent
  on omdb.record_wise_operations_edges(record, parent);
-- Parent commits on a record by record and child commit on that record.
create index if not exists omdb_record_wise_operations_edges_by_record_child
  on omdb.record_wise_operations_edges(record, child);

-- The utility of that is to only have to walk the specific commits and
-- operations that mutate a given record to only construct that specific record.
-- This can be even more efficient if we have periodic snapshots and start from
-- the latest one.
-- We can even record coalesced operations to skip redundancy and apply
-- the coalescing recursively.
-- The idea is to walk each record from the root directly with the operations
-- which apply to it and record the coalesced operations from commit to commit
-- if it is at most half of the sum of operation sizes.
-- This is done recursively to form a sort of skip graph and once the operations
-- reach a size where a record snapshot is at most half of the operations size,
-- we have formed a way to construct the record at any commit along the way in
-- logarithmic instead of linear time.

-- Coalesced operations form a quotient DAG.
create table if not exists omdb.coalesced_operations (
  record uuid not null references omdb.records(id),
  parent bigint not null references omdb.commits(id),
  child bigint not null references omdb.commits(id),
  operation bigint not null references omdb.operations(id),
  primary key (record, parent, child)
);
-- Operations from a parent commit to a child commit by record and parent.
create index if not exists omdb_coalesced_operations_by_record_parent
  on omdb.coalesced_operations(record, parent);
-- Operations to a child commit from a parent commit by record and child.
create index if not exists omdb_coalesced_operations_by_record_child
  on omdb.coalesced_operations(record, child);

-- Nearest snapshots (antichain) per record and commit.
create table if not exists omdb.commit_snapshot_ancestors (
  record uuid not null references omdb.records(id),
  "commit" bigint not null references omdb.commits(id),
  "snapshot" bigint not null references omdb.commits(id),
  primary key (record, "commit", "snapshot")
);
-- Nearest snapshots per record and commit.
create index if not exists omdb_commit_snapshot_ancestors_by_commit
  on omdb.commit_snapshot_ancestors(record, "commit");
-- Descendant commits per record and snapshot, up to the next snapshots.
create index if not exists omdb_commit_snapshot_ancestors_by_snapshot
  on omdb.commit_snapshot_ancestors(record, "snapshot");

-- Record snapshots form a sort of quotient DAG.
create table if not exists omdb.snapshot_to_snapshot (
  record uuid not null references omdb.records(id),
  parent bigint not null references omdb.commits(id),
  child bigint not null references omdb.commits(id),
  primary key (record, parent, child)
);
-- Child snapshots by record and parent.
create index if not exists omdb_snapshot_to_snapshot_by_record_parent
  on omdb.snapshot_to_snapshot(record, parent);
-- Parent snapshots by record and child.
create index if not exists omdb_snapshot_to_snapshot_by_record_child
  on omdb.snapshot_to_snapshot(record, child);