8000 minigraf/ROADMAP.md at v0.22.0 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

ROADMAP.md

Latest commit

 

History

History
1676 lines (1237 loc) · 80.1 KB

ROADMAP.md

File metadata and controls

1676 lines (1237 loc) · 80.1 KB
Raw

Minigraf Roadmap

The path from property graph PoC to production-ready bi-temporal Datalog database

Philosophy: Embedded graph memory for agents, mobile, and the browser — built on the SQLite approach: be boring, be reliable, be embeddable.

Phase 1: Property Graph PoC ✅ COMPLETE

Goal: Prove the concept works

Status: ✅ Completed (December 2025)

What Was Built:

  • ✅ Property graph model (nodes, edges, properties)
  • ✅ In-memory storage engine
  • ✅ Query parser
  • ✅ Query executor
  • ✅ Interactive REPL console
  • ✅ Basic test coverage

Deliverable: Working in-memory graph database with REPL

Phase 2: Embeddability ✅ COMPLETE

Goal: Make it truly embeddable with persistence

Status: ✅ Completed (January 2026)

What Was Built:

  • ✅ Storage backend abstraction (FileBackend, MemoryBackend)
  • ✅ Single-file .graph format (4KB pages)
  • ✅ Cross-platform file format (endian-safe)
  • ✅ Persistent graph storage with serialization
  • ✅ Embedded database API (Minigraf::open())
  • ✅ Auto-save on drop
  • ✅ Thread-safe concurrent access
  • ✅ Comprehensive test suite (54 tests)
  • ✅ Edge case and concurrency tests

Deliverable: Embeddable persistent graph database

Philosophy Alignment: ✅ Single-file, self-contained, embedded-first

Learnings: Storage layer is solid. Datalog chosen for better temporal support.

Phase 3: Datalog Core ✅ COMPLETE

Goal: Implement core Datalog query engine

Status: ✅ Completed (January 2026)

Priority: 🔴 Critical - Foundation for everything else

3.1 EAV Data Model ✅

Features:

  • ✅ Migrate from property graph to Entity-Attribute-Value model
  • ✅ Fact representation: (Entity, Attribute, Value)
  • ✅ Entities as UUIDs (keep existing ID system)
  • ✅ Attributes as keywords (:person/name, :friend)
  • ✅ Values: primitives or entity references
  • ✅ Update storage format to support EAV tuples

Technical Approach:

struct Fact {
    entity: Uuid,
    attribute: String,  // Will become typed Keyword later
    value: Value,
    tx_id: TxId,        // Transaction that asserted this fact
    asserted: bool,     // true = assert, false = retract
}

enum Value {
    String(String),
    Integer(i64),
    Float(f64),
    Boolean(bool),
    Ref(Uuid),  // Reference to another entity
    Keyword(String),
    Null,
}

Migration Path:

  • Keep existing node/edge types for backward compat
  • Add EAV layer on top
  • Gradually migrate tests
  • Eventually deprecate property graph types

3.2 Datalog Parser ✅

Features:

  • ✅ Parse basic Datalog queries (EDN syntax)
  • ✅ Query structure: [:find ?vars :where [clauses]]
  • ✅ Pattern matching: [?e :attr ?v]
  • ✅ Variable binding
  • ✅ Constants and entity references

Example Queries:

;; Find all entities with a name
[:find ?e
 :where [?e :person/name _]]

;; Find friends of Alice
[:find ?friend
 :where
   [?alice :person/name "Alice"]
   [?alice :friend ?friend]]

;; Find names of Alice's friends
[:find ?name
 :where
   [?alice :person/name "Alice"]
   [?alice :friend ?friend]
   [?friend :person/name ?name]]

Parser Components:

  • EDN reader (simple S-expression parser)
  • Query validation
  • Variable extraction
  • Pattern recognition

3.3 Query Executor (Basic) ✅

Features:

  • ✅ Pattern matching against fact database
  • ✅ Variable unification
  • ✅ Join multiple patterns
  • ✅ Return results as tuples

Implementation:

  • Naive evaluation initially (optimize in Phase 6)
  • Iterate through facts, unify variables
  • Cartesian product + filter (like nested loops)
  • Return binding sets

3.4 Recursive Rules ✅

Features:

  • ✅ Define rules: [(rule-name ?args) [body]]
  • ✅ Stratified recursion (safe subset)
  • ✅ Rule evaluation via semi-naive evaluation
  • ✅ Transitive closure queries

Example Rules:

;; Define reachability
[(reachable ?from ?to)
 [?from :connected ?to]]

[(reachable ?from ?to)
 [?from :connected ?intermediate]
 (reachable ?intermediate ?to)]

;; Use in query
[:find ?person
 :where
   (reachable :alice ?person)]

Technical Approach:

  • Fixed-point iteration
  • Track delta (new facts) each round
  • Stop when no new facts produced
  • Detect cycles, prevent infinite loops

3.5 REPL for Datalog ✅

Features:

  • ✅ Interactive Datalog console
  • ✅ Transact facts
  • ✅ Query with Datalog
  • ✅ Pretty-print results

Commands:

;; Transact facts
(transact [[:alice :person/name "Alice"]
           [:alice :person/age 30]])

;; Query
(query [:find ?name :where [?e :person/name ?name]])

;; Define rule
(rule [(friends ?a ?b) [?a :friend ?b] [?b :friend ?a]])

;; Help
(help)

;; Exit
(exit)

3.6 Tests ✅

Test Coverage:

  • ✅ EAV data model CRUD (8 tests)
  • ✅ Datalog parser (all query forms) (15 tests)
  • ✅ Pattern matching (6 tests)
  • ✅ Variable unification (included in matcher tests)
  • ✅ Multi-pattern joins (10 integration tests)
  • ✅ Recursive rule evaluation (15 tests)
  • ✅ Transitive closure queries (9 integration tests)
  • ✅ Concurrency (7 integration tests)

Total: 123 tests passing ✅

Deliverable: ✅ Working Datalog query engine with recursion (Complete!)

Timeline: ✅ Completed in ~3 weeks (January 2026)

Phase 4: Bi-temporal Support ✅ COMPLETE

Goal: Add transaction time and valid time

Status: ✅ Completed (March 2026)

Priority: 🔴 Critical - Core differentiator

4.1 Transaction Time ✅

Features:

  • ✅ Every fact records when it was added (tx_id wall-clock millis, tx_count monotonic counter)
  • ✅ Facts are never deleted, only retracted (asserted=false)
  • ✅ Query as of past transaction counter: [:as-of 50]
  • ✅ Query as of past wall-clock time: [:as-of "2024-01-15T10:00:00Z"]

Data Model:

struct Fact {
    entity: EntityId,
    attribute: Attribute,
    value: Value,
    tx_id: TxId,       // wall-clock millis since epoch (u64)
    tx_count: u64,     // monotonically incrementing counter (1, 2, 3…)
    valid_from: i64,   // millis since epoch (i64)
    valid_to: i64,     // millis since epoch; i64::MAX = "forever"
    asserted: bool,
}

4.2 Valid Time ✅