Dagable

Dagable provides directed acyclic graph (DAG) composition for ActiveRecord models using a dedicated ancestry table. It materializes all transitive paths so that traversal queries are single JOINs instead of recursive CTEs.

Features

• Pre-computed ancestry — all transitive paths are materialized in an ancestry table, so traversal queries are single JOINs instead of recursive CTEs
• Cycle detection — raises Dagable::Errors::CyclicAssociation before any invalid edge is persisted (self-referential, direct, and transitive cycles)
• ActiveRecord::Relation returns — all traversal methods (self_and_successors, self_and_predecessors, successors, predecessors) return chainable relations
• Domain-agnostic — no knowledge of your application domain; works with any ActiveRecord model
• Pure ActiveRecord — only requires ActiveRecord, not Rails

Installation

Add to your Gemfile:

gem 'dagable'

Then run:

bundle install

Or install directly:

gem install dagable

Setup

1. Create the database tables

Dagable requires two supporting tables per model: an edges table for direct relationships and an ancestries table for all transitive paths.

class CreateCategoryDag < ActiveRecord::Migration[8.1]
  include Dagable::MigrationHelpers

  def change
    create_table :categories do |t|
      t.string :name, null: false
      t.timestamps
    end

    create_dagable_tables(:categories)
  end
end

create_dagable_tables(:categories) creates:

Table	Columns	Indexes
categories_edges	parent_id, child_id	Unique composite [parent_id, child_id]
categories_ancestries	predecessor_id, successor_id, depth	Unique composite [predecessor_id, successor_id], individual on predecessor_id and successor_id

Both tables include foreign keys back to the source table.

2. Activate the model

class Category < ActiveRecord::Base
  extend Dagable::Model

  dagable
end

Calling dagable will:

1. Define Category::Edge and Category::Ancestry (dynamic ActiveRecord classes)
2. Set up has_many associations for edges and ancestry connections
3. Include traversal and edge management instance methods
4. Register an after_create callback for self-referential ancestry rows

Usage

Adding edges

electronics = Category.create!(name: "Electronics")
phones      = Category.create!(name: "Phones")
smartphones = Category.create!(name: "Smartphones")

electronics.add_child(phones)
phones.add_child(smartphones)

# Or equivalently:
smartphones.add_parent(phones)

Traversal

All traversal methods return ActiveRecord::Relation, so you can chain scopes, pluck, count, etc.

electronics.self_and_successors
# => [Electronics, Phones, Smartphones]

electronics.successors
# => [Phones, Smartphones]

smartphones.self_and_predecessors
# => [Electronics, Phones, Smartphones]

smartphones.predecessors
# => [Electronics, Phones]

Direct relationships

Access direct parents/children via the edge associations:

electronics.children
# => [Phones]

phones.parents
# => [Electronics]

phones.children
# => [Smartphones]

Removing edges

phones.remove_child(smartphones)

# Or equivalently:
smartphones.remove_parent(phones)

After removal, the ancestry table is automatically rebuilt to reflect the new graph state.

Cycle detection

Dagable prevents cycles at edge-creation time:

electronics = Category.create!(name: "Electronics")
phones      = Category.create!(name: "Phones")
accessories = Category.create!(name: "Accessories")

electronics.add_child(phones)
phones.add_child(accessories)

accessories.add_child(electronics)
# => raises Dagable::Errors::CyclicAssociation

electronics.add_child(electronics)
# => raises Dagable::Errors::CyclicAssociation

Valid DAG structures like diamonds (multiple paths converging) are allowed:

electronics = Category.create!(name: "Electronics")
phones      = Category.create!(name: "Phones")
computers   = Category.create!(name: "Computers")
chargers    = Category.create!(name: "Chargers")

electronics.add_child(phones)
electronics.add_child(computers)
phones.add_child(chargers)
computers.add_child(chargers)  # diamond — this is fine

Seeding in migrations

Use Dagable::Migrations::Helper to create records with edges in a single transaction:

Dagable::Migrations::Helper.create_dagable_item(
  Category,
  { name: "Electronics" },
  children: [phones, laptops],
)

Architecture

How the ancestry table works

The ancestry table stores every reachable pair (predecessor, successor) with a depth:

predecessor_id	successor_id	depth
Electronics	Electronics	0
Phones	Phones	0
Smartphones	Smartphones	0
Electronics	Phones	1
Phones	Smartphones	1
Electronics	Smartphones	2

• Depth 0 — self-referential row (every node has one)
• Depth 1 — direct parent-child relationship
• Depth N — transitive relationship N edges apart

This allows traversal queries to be simple JOINs:

-- self_and_successors for Electronics
SELECT categories.*
FROM categories
INNER JOIN categories_ancestries ON categories_ancestries.successor_id = categories.id
WHERE categories_ancestries.predecessor_id = electronics.id

Key design decisions

• Two tables per model: edges store direct relationships; ancestries store all transitive paths. This separation makes edge removal clean (delete edge, rebuild ancestries from remaining edges).
• Self-referential ancestry rows: every node has a depth-0 row pointing to itself. This simplifies JOIN-based traversal by ensuring self_and_successors naturally includes the node itself.
• link_ancestries on Edge: when an edge is created, the Edge computes the cross product of the parent's predecessors with the child's successors and bulk-inserts ancestry rows for each pair. This is idempotent (existing rows are skipped via INSERT ... ON CONFLICT DO NOTHING).
• Rebuild on removal: when an edge is removed or a node is destroyed, all non-self ancestry rows are deleted and rebuilt from the remaining edges. This is the safest approach for correctness.

Development

bundle install
bundle exec rspec

Tests run against an in-memory SQLite database — no external database required.

License

This gem is available as open source under the terms of the MIT License.