Repository navigation
Expand file tree
/
Copy pathllms.txt
More file actions
188 lines (144 loc) · 11.7 KB
/
Copy pathllms.txt
File metadata and controls
188 lines (144 loc) · 11.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
# Minigraf
> Embedded, single-file, bi-temporal graph database with Datalog queries — written in Rust.
Minigraf is the SQLite of graph databases: zero configuration, one `.graph` file, embedded as a library. It stores facts in an Entity-Attribute-Value (EAV) model and queries them with Datalog, including recursive rules for graph traversal and stratified negation (`not` / `not-join`). Every fact carries two independent time dimensions (transaction time and valid time), enabling full bi-temporal time travel.
**Current version**: 0.14.0 (pre-1.0 — API and file format may change before v1.0)
**Maturity**: See [README](https://github.com/adityamukho/minigraf/blob/main/README.md) for current phase and [ROADMAP](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) for the full plan. ACID + WAL are production-quality. Covering indexes (EAVT/AEVT/AVET/VAET), packed page storage, LRU page cache, and on-disk B+tree indexes are complete. Stratified negation, scalar aggregation, arithmetic/predicate expression clauses, and disjunction (`or`/`or-join`) are complete. Cross-feature integration tests and error-path coverage complete; ~86–89% branch coverage, 617 tests (Phase 7.5). Not recommended for production use until v1.0 (file format stability guaranteed only after Phase 8).
## Use for
- **Agent memory with provenance**: Store facts an agent asserted, when it asserted them, and query any past state. Retract and correct beliefs without losing history. Rewind to the exact knowledge state at the moment of a bad decision for root cause analysis.
- **Verifiable agent reasoning**: Preserve an agent's full decision-making lineage. Post-hoc audits can reconstruct what the agent believed at any transaction counter or timestamp.
- **Task planning agents**: Model sub-task DAGs as a graph. Update dependencies and status over time. Query historical task states with `:as-of`.
- **Code dependency / debugging agents**: Embed call graphs or module dependency graphs; traverse with recursive Datalog rules.
- **Audit-trail applications**: Compliance-grade history where both "what was recorded when" (transaction time) and "what was true when" (valid time) matter independently.
- **Knowledge graphs**: Interconnected entity-relationship data with recursive traversal (e.g. reachability, ancestry
8000
, dependency chains).
- **Event sourcing / temporal debugging**: Replay past states exactly as they existed at any transaction counter or wall-clock timestamp.
- **Local-first / offline applications**: One portable `.graph` file, no server, no setup.
- **Embedded Rust applications**: Link as a library; no daemon, no network socket.
## Do not use for
- Distributed or replicated databases (no clustering by design).
- Client-server deployments (embedded-only by design).
- Workloads requiring more than ~1M facts with sub-second query latency (current query is O(N) full scan; predicate pushdown is planned — see ROADMAP).
- Applications needing SQL or Cypher (Datalog only).
- Fuzzy / semantic similarity search (no vector index). Use a vector store for retrieval; use Minigraf for the relational backbone and audit layer.
- Global shared memory across a distributed agent fleet. If multiple agent nodes need coherent read/write access to the same memory store, Minigraf is the wrong tool — use a distributed database. Minigraf is per-agent-instance memory, not a shared brain.
## Pair with (GraphRAG pattern)
Minigraf has no vector search by design. In agentic stacks that need both fuzzy retrieval and auditable relationships, the recommended split is:
- **Vector store** (Chroma, Pinecone, Qdrant, etc.) — holds embeddings + an entity UUID per document
- **Minigraf** — holds the graph of relationships and full bitemporal history keyed on those UUIDs
The vector store answers "what is similar to this prompt?"; Minigraf answers "given this entity, what are its exact relationships, who recorded them, and what did we believe at time T?" Each layer does what it's good at; neither duplicates the other.
## Key concepts
**Bi-temporal model**
Every fact has two independent time axes:
- *Transaction time* (`tx_count`): when the fact was recorded in the database. Immutable — set by the system.
- *Valid time* (`valid_from` / `valid_to`): when the fact was true in the real world. Set by the caller.
Query either axis independently or together:
- `:as-of <tx_count|timestamp>` — time-travel to a past database state
- `:valid-at <timestamp>` — query facts valid at a real-world point in time
**EAV facts**
The unit of storage is `(entity, attribute, value, valid_from, valid_to, tx_id, tx_count, asserted)`. Entities are UUIDs. Attributes are keywords (`:person/name`). Values are strings, integers, floats, booleans, entity refs, keywords, or null.
**Datalog queries**
Pattern matching with variable unification. Recursive rules use semi-naive fixed-point evaluation. Transitive closure and cycle-safe graph traversal are first-class. Stratified negation (`not` / `not-join`), scalar aggregation (`count`, `sum`, `min`, `max`, `count-distinct`, `sum-distinct`), arithmetic/predicate expression clauses (`[(< ?age 30)]`, `[(+ ?a ?b) ?c]`), and disjunction (`or` / `or-join`) are all supported.
**ACID transactions**
`begin_write()` → `commit()` / `rollback()`. Fact-level WAL with CRC32 protection. Crash recovery on open.
**Single-file storage**
Page-based `.graph` file (4 KB pages, magic `MGRF`, format v6). Packed fact pages (~25 facts/page). On-disk B+tree indexes (EAVT/AEVT/AVET/VAET) with LRU page cache. WAL sidecar (`.wal`) deleted on clean close. Automatic migration from v1–v5. Endian-safe, cross-platform.
## API (Rust)
```rust
use minigraf::OpenOptions;
// Open or create
let db = OpenOptions::new().path("memory.graph").open()?;
// Transact facts
db.execute(r#"(transact [[:agent-1 :belief/fact "Paris is in France"]
[:agent-1 :belief/confidence 0.98]])"#)?;
// Transact with explicit valid time
db.execute(r#"(transact {:valid-from "2024-01-01" :valid-to "2025-01-01"}
[[:agent-1 :employment/status :active]])"#)?;
// Recursive rule: reachability
db.execute(r#"(rule [(reachable ?a ?b) [?a :knows ?b]])
(rule [(reachable ?a ?b) [?a :knows ?m] (reachable ?m ?b)])"#)?;
// Negation: exclude banned entities
db.execute(r#"(query [:find ?name
:where [?e :person/name ?name]
(not [?e :person/banned true])])"#)?;
// Existential negation: services with no deprecated dependency
db.execute(r#"(query [:find ?name
:where [?svc :service/name ?name]
(not-join [?svc]
[?svc :depends-on ?lib]
[?lib :lib/deprecated true])])"#)?;
// Query
db.execute(r#"(query [:find ?fact :where [:agent-1 :belief/fact ?fact]])"#)?;
// Time travel — as of past transaction counter
db.execute("(query [:find ?status :as-of 10 :where [:agent-1 :employment/status ?status]])")?;
// Time travel — valid at real-world date
db.execute(r#"(query [:find ?status :valid-at "2024-06-01"
:where [:agent-1 :employment/status ?status]])"#)?;
// Explicit transaction
let mut tx = db.begin_write()?;
tx.execute(r#"(retract [[:agent-1 :belief/fact "Paris is in France"]])"#)?;
tx.commit()?;
```
## Datalog syntax reference
```
;; Transact
(transact [[ <entity> <attribute> <value> ] ...])
;; Transact with valid time
(transact {:valid-from "ISO8601" :valid-to "ISO8601"} [[ ... ]])
;; Retract
(retract [[ <entity> <attribute> <value> ] ...])
;; Query
(query [:find ?var ... ;; plain variable
(count ?e) ;; aggregate: count, count-distinct,
(sum ?salary) ;; sum, sum-distinct, min, max
:with ?grouping-var ... ;; optional, extra grouping variables
:as-of <tx_count|"ISO8601"> ;; optional, transaction time
:valid-at <"ISO8601"|:any-valid-time> ;; optional, valid time
:where [<e> <a> <v>] ...
(not [<e> <a> <v>] ...) ;; optional, negation
(not-join [?join-var ...] ...) ;; optional, existential negation
(or branch1 branch2 ...) ;; optional, disjunction (all branches bind same vars)
(or-join [?v ...] b1 b2 ...) ;; optional, existential disjunction
(and clause1 clause2 ...) ;; group clauses into one branch (inside or/or-join)
[(<op> ?a ?b)] ;; filter predicate: <, >, <=, >=, =, !=, string?, etc.
[(<op> ?a ?b) ?result] ;; arithmetic binding: +, -, *, /
])
;; Recursive rule
(rule [(<rule-name> ?arg ...) <body-clauses> ...])
;; Negation in rule body
(rule [(<rule-name> ?arg ...)
[?arg <attr> <val>]
(not [?arg :excluded true])
(not-join [?arg] [?arg :depends-on ?d] [?d :status :bad])])
```
## Source layout
- `src/db.rs` — public API: `Minigraf`, `OpenOptions`, `WriteTransaction`
- `src/graph/types.rs` — `Fact`, `Value`, EAV types, bi-temporal fields
- `src/graph/storage.rs` — in-memory fact store with temporal query methods and `net_asserted_facts`
- `src/query/datalog/` — parser, executor, matcher, evaluator, optimizer, stratification, rules, types
- `src/query/datalog/stratification.rs` — `DependencyGraph`, `stratify()` — negative edges + cycle detection
- `src/query/datalog/evaluator.rs` — `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator`, `evaluate_not_join`
- `src/storage/mod.rs` — `StorageBackend` trait, `FileHeader` v6, `CommittedFactReader` / `CommittedIndexReader` traits
- `src/storage/backend/` — file, memory backends
- `src/storage/index.rs` — EAVT/AEVT/AVET/VAET index key types, `FactRef`, `encode_value`
- `src/storage/btree_v6.rs` — on-disk B+tree (current); `btree.rs` — legacy v5 (migration only)
- `src/storage/cache.rs` — LRU page cache (approximate-LRU, configurable capacity)
- `src/storage/packed_pages.rs` — packed fact page format (~25 facts/4KB page), `MAX_FACT_BYTES`
- `src/storage/persistent_facts.rs` — v6 save/load, auto-migration v1–v5→v6
- `src/wal.rs` — write-ahead log, CRC32 entries, crash recovery
- `src/temporal.rs` — UTC timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)
## Performance summary (v0.13.0)
See [BENCHMARKS.md](https://github.com/adityamukho/minigraf/blob/main/BENCHMARKS.md) for full tables and methodology.
- **Insert**: ~2.7 µs/fact (in-memory), ~3.6 µs/fact (file-backed WAL). Flat across 1K–100K facts.
- **Query (point lookup)**: O(N) full scan — 4.3–4.5 s at 1M facts.
- **Open**: 1.31 s at 1M facts (indexes paged in on demand via B+tree; ~2.4× faster than v5).
- **Peak heap**: 1.05 GB at 1M facts (~21% less than v5 — indexes not loaded into RAM).
## Links
- [Repository](https://github.com/adityamukho/minigraf)
- [README](https://github.com/adityamukho/minigraf/blob/main/README.md) — current status and quick start
- [ROADMAP](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) — phase-by-phase plan
- [BENCHMARKS](https://github.com/adityamukho/minigraf/blob/main/BENCHMARKS.md) — Criterion results at 1K–1M facts
- [Philosophy](https://github.com/adityamukho/minigraf/blob/main/PHILOSOPHY.md)
- [Security Policy](https://github.com/adityamukho/minigraf/security/policy)
- [Wiki: Architecture](https://github.com/adityamukho/minigraf/wiki/Architecture) — module structure, data model, file format, query pipeline
- [Wiki: Datalog Reference](https://github.com/adityamukho/minigraf/wiki/Datalog-Reference) — complete syntax reference
- [Wiki: Use Cases](https://github.com/adityamukho/minigraf/wiki/Use-Cases) — AI agents, mobile apps, WASM/browser
- [Wiki: Comparison](https://github.com/adityamukho/minigraf/wiki/Comparison) — vs XTDB, Cozo, Datomic, Neo4j, SQLite and others