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

ROADMAP.md

Latest commit

 

History

History
244 lines (164 loc) · 19.9 KB

ROADMAP.md

File metadata and controls

244 lines (164 loc) · 19.9 KB
Raw

Minigraf Roadmap

Planned work for Minigraf, a bi-temporal Datalog database. v2.x has known data-integrity issues (pinned list); v3.0.0 fixes them (v3.0.0 milestone).

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

Ordinary avg is implemented for v3.0.0 (#777), matching window numeric filtering. Ordinary sum and extrema also use window-compatible value handling (#789); their existing empty-group conventions are preserved.

Completed releases and their implementation details live in the CHANGELOG. This document tracks planned, exploratory, and other future work.

v2.0.5 — Data-Integrity Patch (released 2026-10-11)

File format stays v7. Two new error codes (STG-045, WAL-007); no other API changes. Details are in the CHANGELOG.

Shipped:

  • A file shorter than one page is refused with STG-045 unless it is a torn first write (#506)
  • A commit made after a torn WAL entry is no longer lost on recovery; a failed append makes later writes WAL-007 until reopen or checkpoint (#513)
  • Backported from v3.0.0: rule queries count only derived facts against max_results (#528), checkpoint() removes an all-checkpointed WAL (#457), usize::MAX checkpoint threshold skips the close-time save (#476)
  • Weekly 10M-fact soak test (#392) and per-file coverage gates that actually gate (#396)

v2.0.4 — Browser Durability Patch (released 2026-10-08)

File format stays v7 and the public API does not change. Details are in the CHANGELOG.

Shipped:

  • BrowserDb returns an error instead of leaving an unreadable dirty page out of the IndexedDB flush (#470)
  • Golden-file compatibility corpus for format v7 (#391) and a SIGKILL crash test that checks the committed data (#384)

v2.0.3 — Data-Integrity Patch (released 2026-10-06)

First v2.x patch under the support policy. File format stays v7 and the public API does not change. Details are in the CHANGELOG.

Shipped:

  • Indexed queries return correct results with more than 65,535 uncheckpointed facts (#445)
  • The transaction counter no longer rewinds when reopening next to an already-checkpointed WAL (#447)

Further v2.x releases are data-integrity and security patches only.

v2.0.2 — Final Planned v2.x Release (released 2026-09-27)

The v2.x line (main) ends with a patch. File format stays v7 and the public API does not change. All new feature work has moved to v3.x. Work list: v3.0.0 milestone. Details are in the CHANGELOG.

Shipped:

  • Bound-entity point queries narrowed to the queried attribute (#323 mitigation), exact attribute-scan bounds (#381), and checkpoints that copy untouched index leaves (#315 mitigation)
  • fsync the parent directory after creating the .graph/WAL file and after deleting the WAL (#389)
  • or-join returns an empty result, not INT-031, when the clauses before it match no rows (#405)
  • A clear user error for $slot queries run through execute(), not internal INT-025 (#407)
  • Recursive rules with a literal start that recurse through another rule no longer fail under magic sets (#297)
  • The INT-054 negative-cycle error names its predicates in a stable order (#410)
  • Benchmark regression alerting that is not silently muted (#393)
  • CI: MSRV build, public-API semver check, dependency policy (#395)
  • Stability and support policy, including how long v2.x gets data-integrity fixes after v3.0.0 (#397)
  • Known-issues process: data-integrity issues stay open until the fix is in a published release (#399)
  • Support tiers for language bindings and platforms (#400)

Known issue on all v2.x releases: same-transaction multi-valued facts read back as one value (#371, #287). The fix needs format v8 and ships in v3.0.0. Workaround: write or retract each value of a multi-valued attribute in its own transact/retract call. All v2.x known issues are listed in the pinned issue #421.

After v3.0.0 ships, v2.x gets data-integrity and security fixes for 12 months (support policy).

v3.0.0 — File Format v8 and Data Integrity

v3.0.0 supports file format v8 only. Fixing #287/#371 (EavtKey/AevtKey carry no value bytes, so same-transaction multi-values collapse) bumps the format from v7 to v8. Support for v1–v6 is dropped at the same time. The v1–v6 → v7 auto-migration code in persistent_facts.rs can be removed when cutting this release; a v7→v8 migration replaces it. Any database opened at least once under a v1.x release will already be on v7; there are no known users on older formats. Every other layout change this release needs goes into v8 too, so there is no separate v9.

This was the GitHub milestone named “2.0” before v2.0.0 used that version number for the kernel-locking and structured-error-code breaking changes; it was consequently renumbered to v3.0.0. It is developed on the long-lived v3 branch; every v3 pull request targets v3 and main is left untouched. At the first v3 release the current main is copied to a v2 branch and v3 becomes the new main.

Scope — format and storage integrity:

  • v8 index keys with value bytes and v7→v8 migration (#371, #287; done on v3)

  • Kani proofs that the format-v8 scalar key decoders invert their encoders and reject bounded malformed inputs without panicking (#693; targeted before v3.0.0, with no format change)

  • v8 storage format, done on v3 in five PRs (#374, #434, #388, #433):

    • per-page CRC32, page id and generation on every page (#388);
    • two alternating meta pages; crash-atomic, copy-on-write checkpoints whose cost follows the change (#374, #434);
    • covering byte-comparable keys with a dictionary and deduplicated long values, at about 142 bytes per fact (#433).

    The format is frozen for the golden-file corpus (#391).

  • Index verify and public rebuild_indexes() (#373; done on v3)

  • Net-assert on v8 keys before resolving facts, for O(live) point queries (#379; done on v3)

  • One current valid-time window per (e, a, v): a later assertion replaces the earlier window, and two windows of one fact in one transact are API-011 (#435; done on v3)

  • Empty or inverted valid-time windows rejected with API-019 on every write path (#436; done on v3)

  • In a WriteTransaction, the last statement that writes a fact decides it, so reads inside the transaction match the commit; LogWriter keeps the same rules, with API-020 for an assertion and retraction of one fact in one transaction (#477; done on v3)

  • btree_page fuzz target that reaches node decoding (#375; done on v3 with #387: page targets rebuilt on real v8 files)

Scope — query API:

  • Align ordinary aggregate value handling with windows (#789; implemented for v3.0.0): sum/sum-distinct skip nonnumbers; min/max accept all non-nil types and mixed numbers. Preserve empty-query and all-nil min/max group-drop behavior. Ordinary avg is #777; ordered-group expansion remains #781.

  • Selective in-memory ancestor joins avoid building a whole-attribute value map (#723; implemented for eligible three-pattern recursive bodies). Populated committed generations keep AVET probes; general in-memory value joins remain unchanged.

  • Optional :distinct result tuples, preserving bag output by default (#493; done on v3)

  • lag and lead window functions for the previous/next row within an ordered partition (#182; v3.0.0)

  • Bounded sliding row frames, :rows N preceding, for window aggregates (#183; v3.0.0, implemented on v3; builds on #182). #836 audit evidence retains the 110 wider cases as manual/deferred; it does not expand nightly coverage.

  • Cursor API: Minigraf::query and PreparedQuery::query return an owned Cursor that delivers rows in batches, with the answer fixed at open (#432; Rust API done on v3). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and :db/valid-at (#545), not and or (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on v3). Operators do not spill: memory follows operator state, with an opt-in per-query limit (QRY-012, #549).

  • Projected UUID lookup batches walk dense DICT ranges (#530; implemented on v3), keeping temporary memory bounded to a batch and query-cache charges in projection order.

  • Native :limit N, :order-by and :offset, with a top-k Sort whose memory follows N (#306; done on v3, with the 10M-fact acceptance tests moved from #473; spec docs/superpowers/specs/2026-10-24-limit-order-by-design.md). #641 targets v3.0.0 in three slices: snapshot-bound order proofs and Sort omission for committed scalar ranges, then one-group count/count-distinct and partition-at-a-time windows. All three slices are implemented in the dependent #641 PRs for v3. #781 extends ordered grouping to sum/avg, fixed-scalar min/max, Integer/nil sum-distinct, and effective tuples reducible to one ordered Integer/Boolean slot plus scalar constants/repetitions, including hidden :with keys. Every :with Sort is retained. Unproved keys/arguments, callbacks, collect-set, rules and aggregate+window queries retain full-input evaluation. Compatible built-in windows with one proved nonconstant partition key hold one partition and bounded batches; unpartitioned/incompatible windows, aggregate queries, callbacks and collect-set retain full-input evaluation. See docs/superpowers/specs/2026-10-28-641-input-order-design.md and docs/superpowers/specs/2026-10-29-781-ordered-aggregate-design.md.

  • Fact-log iterator: Minigraf::fact_log(&FactFilter) streams every fact version (assertions and retractions, with tx_count, tx_id and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on v3). An open log pins its generation: checkpoints run but do not reuse its pages (#543; API-013 deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462.

  • Read-only open: OpenOptions::read_only takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with API-014 (#429; Rust API done on v3). The bindings' open_with_options follows.

  • Raw log writer: LogWriter builds a new database from FactRecords with their tx_count, tx_id, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for :as-of), at <path>.partial renamed into place by finish (#431; Rust API done on v3). Completes extract (#429, #430), transform, load. The binding objects follow.

Scope — features:

  • Query profiler (#185)
  • Set values #{...}, the set predicates in?/not-in?/any-in?/all-in?/none-in? and collect-set (#316; done on v3: core, BrowserDb set binds, and set values in Python, Java, Android, Swift, Node.js, C and the browser/WASI packages on their v3 branches)
  • Prepared queries in every binding (#181; done on v3: core, BrowserDb.prepare, and Python, Java, Android, Swift, Node.js and C on their v3 branches)
  • UDF registration in every binding: the UniFFI ones, C, Node and the browser BrowserDb (#180; core done on v3: fallible UDFs, QRY-014, registry snapshot and re-entry; the bindings follow)
  • OpenOptions exposed over UniFFI through open_with_options, so embedders can suppress the close-time checkpoint (#322; done on v3 in every binding with #465)

Scope — release-gate testing and documentation:

  • Deterministic storage schedules (#760; v3.0.0): suite and findings cover batch visibility, snapshot cutoffs and checkpoint publication. Focused native/MSRV PR checks and larger nightly/manual searches retain replay artifacts; the workflow-only main companion enables the v3 nightly schedule. Whole-database simulation remains out of scope.
  • Golden-file compatibility corpus for every format version (#391; done on v3: six v7 files from 2.0.3 checked after migration, seven v8 files frozen at 23aa57c)
  • SIGKILL crash test that checks committed data through EAVT, AEVT and full scan (#384; done on v3: tests/crash_kill_test.rs, 100 rounds per OS nightly)
  • Model-based test of transact/retract/checkpoint/reopen (#385; done on v3: tests/model_based_test.rs, 30,000 cases nightly)
  • Wider property tests: file-backed, batched, retracts, temporal, joins (#386)
  • Persistent fuzz corpus and an operation-sequence target (#387; done on v3: corpus caching, weekly cmin, the v8 page targets, and the ops_sequence and corrupt_file targets)
  • Fault injection across save/WAL/recovery (#390)
  • Long-running soak test at scale (#392; done on v3: tests/soak_test.rs, 10M facts and a 5-hour churn weekly, alternating main and v3)
  • Benchmarks at 100K–10M facts and a published performance envelope (#394; on v3: examples/perf_envelope.rs, results in docs/BENCHMARKS.md; follow-ups #528–#532, with #532 superseded by #551's removal of repeated committed-fact net-assert; audit and measurements)
  • Acceptance evidence for memory/scaling (#837): named-test and Linux RSS gates, nonlinear/multistratum recursion and custom chunk bounds; validation status
  • Regression-history/reporting evidence (#840) is complete: all 453 numeric comparisons, preserved independent v3 history, scheduled routes and live notification/cleanup evidence. Separate main/v3 fixes #853/#854 are merged; raw evidence is retained beyond artifact expiry.
  • Nightly runtime expansion (#858): add Java/JVM and WASI; qualify Swift/iOS simulator and Android emulator timings against physical-device workloads before enabling representative mobile lanes. The platform restriction from #839 applies only to that manual evidence task.
  • Manual migration evidence (#838): native v7-to-v8 through 200k facts; Chromium/Firefox/WebKit through 20k facts, with separate read-only/reopen controls and bounded post-migration cursor churn. Results, frozen fixtures and exclusions; no new nightly route or sustained-pin bound.
  • Semantic permutations (#842): correctness-target map and control limits for X07. The exclusion stands; no nightly route or acceptance gate is added.
  • Failure paths (#843): correctness-target map for X08. The exclusion stands; the heavy WAL replay test gap is #865.
  • Manual shape evidence (#841): native shape sweeps, recursive controls and sustained-reader experiments, with explicit input, timeout and attribution limits. The small-nightly recommendation is separate from execution; this audit adds no nightly route or release-acceptance gate.
  • Expression keyword/ref equality (#774; on v3): resolve literal keywords once per operator, with memory bounded by the expression. Measurements and regression coverage; performance-only, with no v2.x backport.
  • Higher storage/WAL coverage gates and branch-coverage gates (#396; on v3: line and branch floors per file in coverage-thresholds.toml, checked on every PR)
  • Durability, recovery and operations guide (#398; done on v3: docs/DURABILITY.md, also on the docs site; found #535)

v3.next — Features

Additive features, kept out of v3.0.0 so the #371 fix is not held up by them:

  • Rule persistence — design first (#241)
  • OPFS-backed persistent mode for BrowserDb: a sync access handle in a dedicated Worker, no in-memory buffer; IndexedDB stays the main-thread backend. Starts at Tier 2 inside the Tier 1 browser binding until it has shipped (#441)
  • Temporal graph-traversal research (#273; may result in documentation or a blog post rather than code)

Planned Work: Ecosystem & Tooling

Goal: Improve developer experience and grow the ecosystem without expanding the core unnecessarily.

Developer Tools

Integration Examples

Tracked in: minigraf-examples.

  • 🎯 GraphRAG example that combines Minigraf with a vector store
  • 🎯 LangChain / LangChain.js integration example
  • 🎯 LlamaIndex integration example
  • 🎯 Annotated end-to-end scenarios for agent memory, offline-first mobile, and audit logs

Ecosystem Libraries

  • 🎯 Graph algorithms as a separate crate
  • 🎯 Optional schema validation
  • 🎯 Import/export tools
  • 🎯 Backup utilities

Database Branching / Forking (Exploratory)

Allow a Minigraf database to be forked into an independent .graph file pre-populated with facts from the parent at a given transaction count.

Potential uses include speculative writes, snapshot distribution, test isolation, and agent sandboxing. The design must preserve the single-file, zero-configuration model; a fork should behave as an independent file copy with a fully flushed WAL.

Status: Exploratory. Pursue only with demonstrated user demand.

Magic Sets with Stratified Negation (Exploratory)

Magic-sets rewriting is not applied to mixed rules containing not/not-join; those use full semi-naive evaluation. Extending it to negation is well studied but requires care to avoid unsound propagation across stratification boundaries.

Pursue only if profiling demonstrates a real bottleneck in negation-heavy recursive workloads.

Performance Direction

Future performance work will be driven by production profiles and reproducible benchmarks. The benchmark documentation records measurements; completed performance work is recorded in the CHANGELOG.

Decision Framework

When evaluating features, ask:

  1. Does it align with the philosophy? (embedded, reliable, simple, bi-temporal)
  2. Is it needed for target use cases? (audit, event sourcing, knowledge graphs)
  3. Does it compromise reliability? (stability over features)
  4. Can it be a separate crate? (keep the core small)

Say no to:

  • Distributed consensus
  • Multi-datacenter replication
  • Built-in ML/AI
  • Features useful only at massive scale
  • Complex configuration
  • Breaking the single-file philosophy

Say yes to:

  • Crash safety
  • Data integrity
  • Temporal queries
  • Query performance
  • Developer experience
  • Cross-platform support

Current Focus

  • v2.x maintenance on main: data-integrity and security fixes only
  • v3.0.0 (format v8 and data integrity) on the v3 branch, then v3.next features
  • Production readiness for high-stakes deployments, tracked in the v3.0.0 milestone
  • Ecosystem work tracked in minigraf-examples
  • Developer tools tracked in minigraf-inspector and minigraf-visualizer

See GitHub Issues for specific tasks, and the CHANGELOG for completed releases.

Last updated: October 2026 — v2.0.5, a data-integrity patch on v2.x, is the current release; v3.0.0 work, including the file-format v8 fix for #287/#371, is developed on the long-lived v3 branch and merges into main at the v3.0.0 cut.
0