dag_me

Multi-parent directed acyclic graphs for ActiveRecord, powered by PostgreSQL 18+.

A companion to closure_tree: reach for closure_tree when your hierarchy is a tree, and for dag_me when it isn't - missions with multiple dependencies, categories with multiple parents, pipelines, dependency graphs, org charts that lie.

flowchart TD
    subgraph tree ["Tree - every node has exactly one parent (closure_tree)"]
        direction TB
        t_mission[mission] --> t_design[design] & t_review[review]
        t_design --> t_hull[hull] & t_guidance[guidance]
    end
    subgraph dag ["DAG - nodes can have many parents (dag_me)"]
        direction TB
        d_design[design] --> d_hull[hull] & d_guidance[guidance]
        d_hull --> d_assembly[assembly]
        d_guidance --> d_assembly
        d_review[review] --> d_assembly
        d_assembly --> d_launch[launch]
        d_guidance --> d_launch
    end

Loading

A tree forbids the interesting part: assembly depends on hull, guidance, and review, and two paths converge on launch. Those diamonds are exactly what dag_me maintains - multiple parents, shared descendants, cycle-free, enforced in-database.

class Mission < ApplicationRecord
  dag_me
end

design = Mission.create!(name: 'design')
review = Mission.create!(name: 'review')
launch = Mission.create!(name: 'launch')

launch.add_parent(design)
launch.add_parent(review)     # multiple parents: the whole point

launch.parents                # => [design, review]
design.descendants            # => [launch]
launch.ancestors              # => [design, review]
design.ancestor_of?(launch)   # => true

launch.add_child(design)      # => raises DagMe::CycleError, rejected in-database

flowchart LR
    design --> launch
    review --> launch

Loading

Installation

gem 'dag_me'

Generate the migration for each DAG model (tables, triggers, and functions are installed per model - no dynamic SQL):

rails generate dag_me:migration Mission

Because the schema includes functions and triggers, use structure.sql:

config.active_record.schema_format = :sql

What gets installed

For a missions table:

Object	Role
mission_dag_edges	Source of truth: (parent_id, child_id), unique, FK cascade
mission_dag_paths	Transitive closure incl. self-rows: (ancestor_id, descendant_id, min_depth, path_count)
mission_dag_edge_insert_check	BEFORE INSERT: advisory lock + cycle rejection
mission_dag_edge_insert_apply	AFTER INSERT: incremental closure expansion
mission_dag_edge_delete_apply	AFTER DELETE: exact path_count decrement + min_depth repair
mission_dag_node_insert / mission_dag_node_delete	Self-row lifecycle, edge teardown through triggers
mission_dag_rebuild_paths() / mission_dag_validate_paths()	Rebuild from edges / diff against a recomputation from edges

Generated by rails_lens from the test app (make erd); it reflects the runtime classes dag_me defines, so your own models get the same diagram for free:

erDiagram
"Mission" {
  int id PK
  varchar name
}
"Mission::DagEdge" {
  int id PK
  int parent_id FK "UK"
  int child_id FK "UK"
  timestamptz created_at
}
"Mission::DagPath" {
  int ancestor_id PK
  int descendant_id PK
  int min_depth
  decimal path_count
}
"Mission::DagEdge" }o--|| "Mission" : "parent"
"Mission::DagEdge" }o--|| "Mission" : "child"

Loading

Reads never recurse: ancestors and descendants are index joins against the closure.

Maintenance modes

The model API talks to a reachability adapter, not to the storage directly:

class Mission < ApplicationRecord
  dag_me                            # maintain: :postgresql_closure (default)
end

class Maneuver < ApplicationRecord
  dag_me maintain: :recursive_cte   # edges only, WITH RECURSIVE at read time
end

:recursive_cte skips the closure table entirely - good for small graphs, high mutation rates, and as the truth oracle. Cycle rejection stays in-database either way.

Schema-qualified tables

Node tables living in a named PostgreSQL schema work out of the box:

class Station < ApplicationRecord
  self.table_name = 'orbital.stations'
  dag_me
end

Generated tables (orbital.station_dag_edges, orbital.station_dag_paths) and functions land in the node table's schema; trigger names stay plain identifiers.

Long table names would push generated identifiers past PostgreSQL's 63-byte limit; pass a custom prefix instead of letting it truncate:

class MaterialTracking::ProductBillOfMaterial < ApplicationRecord
  dag_me prefix: 'bom_dag'   # bom_dag_edges, bom_dag_paths, bom_dag_lock, ...
end

Multi-tenancy

class Satellite < ApplicationRecord
  dag_me scope: :constellation_id    # or scope: [:system_id, :sector]
end

Scope columns are stamped onto edge and closure rows by the trigger - always copied from the node, so raw SQL cannot forge them. Edges connecting nodes in different scopes are rejected in-database (DagMe::ScopeError through the gem API). Advisory locks are hashed per scope, so tenants don't serialize each other's writes. Changing a node's scope columns is rejected while the node has edges; isolated nodes restamp their closure self-row.

One model, many networks

dag_me takes an optional name; each named declaration is a fully independent graph over the same rows, with its own tables, triggers, constants, and adapter:

class Relay < ApplicationRecord
  dag_me :power                           # relay_power_dag_edges / _paths
  dag_me :comms, maintain: :recursive_cte # relay_comms_dag_edges only
end

relay.add_child(other, dag: :power)
relay.power_children                      # named associations per network
relay.comms_parents
relay.ancestor_of?(other, dag: :comms)
Relay.roots(dag: :power)
Relay.topologically(:comms)
Relay.dag(:power).rebuild!                # named graph facade

Cycles are rejected per network: a -> b in :power plus b -> a in :comms is legal (different graphs); a second b -> a in :power raises DagMe::CycleError. The bare dag_me remains the default graph - the dag: keyword and Model.dag with no argument keep meaning it - and a model may mix a default dag with named ones. DagMe::DDL.install!(Model) and the generated migration install every declared network.

Topological ordering & subgraphs

Mission.topologically                     # whole graph, ancestors first
mission.descendants.topologically         # composes with any relation
Mission.dag.between(a, d)                 # nodes on any path a ~> d, endpoints included
Mission.dag.between(a, d).topologically
mission.subgraph                          # self_and_descendants
mission.subgraph_edges                    # induced edge set (for dot/mermaid exports)
Mission.dag.edges_among(some_relation)    # induced edges of an arbitrary node set

Ordering sorts by global ancestor count: for any edge u -> v, ancestors(v) strictly contains ancestors(u) ∪ {u}, so the count increases along every edge - a valid topological order for any sub-relation, computed with one index-only subquery per row in closure mode. Ties break deterministically by primary key.

API

node.parents / node.children              # direct relations (has_many :through)
node.ancestors / node.descendants         # transitive, excludes self
node.self_and_ancestors / node.self_and_descendants
node.add_parent(n) / node.add_child(n)    # raises DagMe::CycleError on cycles
node.remove_parent(n) / node.remove_child(n)
node.ancestor_of?(n) / node.descendant_of?(n)
node.root? / node.leaf?
node.subgraph / node.subgraph_edges
Model.roots / Model.leaves                # relation scopes
Model.topologically

Model.dag                                 # the graph facade (default dag)
Model.dag(:power)                         # a named dag's facade
Model.dag.between(a, d)
Model.dag.edges / Model.dag.edges_among(relation)
Model.dag.rebuild!
Model.dag.validate                        # discrepancy rows ([] = healthy)
Model.dag.valid?
Model.dag.validate!                       # raises DagMe::CorruptionError with the rows

Every instance method and Model.roots / Model.leaves accept dag: to target a named network (node.add_child(n, dag: :power)); Model.topologically takes the name positionally so it stays composable as a scope.

uuid primary keys (e.g. uuidv7()) work out of the box - graph tables inherit the node table's primary-key type.

Composite primary keys

Declare the key before the macro; dag_me derives one graph column per key column (parent_ship_id, parent_slot, ancestor_ship_id, ...), and every join and cycle check compares full tuples:

class PowerCell < ApplicationRecord
  self.primary_key = [:ship_id, :slot]
  dag_me
end

Single-column keys keep the classic parent_id / child_id / ancestor_id / descendant_id layout. Declaration order matters: dag_me reads the declared key, not the schema (class load stays DB-free).

The name

Directed Acyclic Graph Management Engine. Not to be confused with the Intel Management Engine: this one also runs below your application with privileges you can't revoke, but it's open source, you asked for it, and the only ring it operates in is pg_advisory_xact_lock.

It's also the macro - a model that wants to be a graph says dag_me.

Errors

The triggers RAISE with custom SQLSTATEs (DGME1 cycle, DGME2 cross-scope edge, DGME3 scope change while connected, DGME4 write above READ COMMITTED), so translation never depends on message text. Through the gem's write API these surface as DagMe::CycleError / DagMe::ScopeError / DagMe::IsolationError; writes outside it (raw SQL, update! on scope columns) raise the underlying ActiveRecord::StatementInvalid carrying the same SQLSTATE.

Semantics worth knowing

Solid arrows are edges; the dashed one is what the closure materializes:

flowchart LR
    a --> b & c
    b --> d
    c --> d
    a -. "min_depth 2, path_count 2" .-> d

Loading

• path_count is the exact number of distinct paths between two nodes (numeric, because path counts explode combinatorially in dense DAGs).
• min_depth is the shortest-path length. Deleting an edge triggers exact decremental maintenance: contributions through the deleted edge are subtracted, zero-count pairs are dropped, and min_depth is repaired: only pairs whose shortest path ran through the deleted edge are recomputed, and changes propagate upward until nothing moves.
• Edge deletion in dense graphs is the expensive operation, by design. Reads are cheap, inserts are ancestors(parent) × descendants(child), deletes pay for exactness.
• Concurrent writers are serialized per graph with pg_advisory_xact_lock - two transactions cannot sneak a cycle in by racing the check.
• Writes require READ COMMITTED: lock-then-recheck needs a fresh snapshot after the lock wait, so higher isolation is rejected with DagMe::IsolationError.
• Edge inserts take FOR SHARE on both node rows; scope changes cannot race an in-flight edge into a cross-tenant graph.
• Destroying a node tears down its edges through the triggers (not FK-cascade ordering), so the closure shrinks correctly.
• rebuild! and validate recompute the closure from the edges layer by layer (nodes grouped by their longest distance from a root), so their cost is polynomial no matter how many paths the graph holds. They use temp tables, so they need a writable connection, and they raise DagMe::CycleError if edges written with triggers disabled form a cycle. validate runs in its own REPEATABLE READ transaction; inside yours it holds SHARE locks on the node and edge tables instead, so writers wait until it ends.

Rake tasks

rake dag_me:status          # doctor report per network: tables, triggers, functions, closure health
rake dag_me:rebuild         # rebuild every closure (or MODEL=Mission for one)

Upgrading

The triggers and functions live in your database, so a gem upgrade that changes them needs a migration. Function bodies are stamped with DagMe::DDL::REVISION, and rake dag_me:status flags graphs installed by an older one. Generate a refresh per model:

rails generate dag_me:refresh Mission

The migration calls DagMe::DDL.refresh!(Mission), which replaces every function body with CREATE OR REPLACE and reapplies the closure table's storage settings. Tables, triggers, and rows are left alone.

Testing your app's graphs

The gem ships Minitest assertions for host applications:

class GraphSetupTest < ActiveSupport::TestCase
  include DagMe::TestHelper

  test 'missions form a healthy DAG' do
    assert_dag_model Mission, maintain: :postgresql_closure
    assert_dag_model Satellite, scope: :constellation_id
    assert_dag_model Relay, dag: :power, maintain: :postgresql_closure
    assert_dag_valid Mission
    assert_dag_reachable design, launch
    assert_topological_order Mission, Mission.topologically.to_a
  end
end

All assertions accept dag: for named networks.

Development

make up      # postgres:18 via docker compose (port 5438)
make check   # dictator lint + full suite

The suite includes property tests that apply random edge insertions, edge deletions, and node destructions (single- and multi-tenant) and validate the closure against a recomputation from the edges after every single operation, plus concurrency tests racing reverse edges across threads. The recomputation itself is checked against brute-force path enumeration on small random graphs.

Large graph fixtures are generated, not committed: vial compiles test/vials/*.vial.rb into deterministic YAML fixtures at test boot (test/fixtures/ is gitignored). The layered 120-node / 300-edge graph exercises the bulk-import path - Rails fixture loading bypasses triggers, so the pattern is:

ActiveRecord::FixtureSet.create_fixtures(...)  # raw edges, no closure maintenance
Mission.dag.rebuild!                           # reconstruct closure from edges
Mission.dag.validate!                          # prove it

The same recipe applies to any bulk import (COPY, insert_all, ETL).

License

MIT