Skip to content

Phase 3: Datalog Core Implementation - #4

Merged
adityamukho merged 7 commits into
mainfrom
phase-3-datalog-core
Jan 13, 2026
Merged

adityamukho merged 7 commits into
mainfrom
phase-3-datalog-core

Conversation

@adityamukho

Copy link
Copy Markdown
Collaborator

Phase 3: Datalog Core Implementation

This PR implements the foundational Datalog query engine for Minigraf, completing core Phase 3 functionality as outlined in the roadmap.

🎯 What's Implemented

1. EAV Data Model

  • Fact structure: (Entity, Attribute, Value, TxId, Asserted)
  • Enhanced Value types: Added Ref (entity references) and Keyword support
  • Timestamp-based TxIDs: Milliseconds since UNIX epoch for natural chronological ordering
  • Helper functions for timestamp/TxId conversion

2. Fact Storage Layer

  • Append-only log: Immutable history, facts never deleted
  • Assertions & Retractions: Track fact lifecycle
  • Query methods: Current values, entity/attribute filtering
  • 8 comprehensive tests

3. EDN/Datalog Parser

  • Full EDN tokenizer (vectors, lists, keywords, symbols, UUIDs, etc.)
  • Parse transact, query, and retract commands
  • Support all value types
  • 11 parser tests

4. Pattern Matching Engine

  • Variable unification across patterns
  • Multi-pattern queries with joins
  • Deterministic keyword-to-UUID conversion
  • 6 pattern matcher tests

5. Query Executor

  • Execute transact/retract/query commands
  • Proper error handling
  • Structured result types
  • 6 executor tests

6. REPL Integration

  • Datalog syntax support (parenthesis-based)
  • Backward compatible with GQL
  • Pretty-printed results

7. Public API

  • All Datalog functionality exported
  • Ready for library use

📊 Test Coverage

  • 81 tests passing (up from 51)
  • Comprehensive coverage across all modules

💡 Example Usage

# Add facts
(transact [[:alice :person/name "Alice"]
           [:alice :person/age 30]
           [:alice :friend :bob]])

# Query with patterns
(query [:find ?name ?age
        :where [?e :person/name ?name]
               [?e :person/age ?age]])

# Retract facts
(retract [[:alice :person/age 30]])

🚀 What's Next

  • Phase 4: Bi-temporal support (transaction time + valid time)
  • Phase 5: ACID + WAL
  • Future: Recursive rules with semi-naive evaluation (advanced Phase 3 feature)

✅ Philosophy Compliance

  • ✅ Zero-configuration: Works out of the box
  • ✅ Embedded-first: Library, not server
  • ✅ Single-file ready: Storage layer compatible
  • ✅ Reliability: Comprehensive test coverage
  • ✅ Simplicity: Clean, well-documented code

📝 Files Changed

  • New modules under src/query/datalog/
  • Enhanced src/graph/types.rs with EAV types
  • Updated src/graph/storage.rs with FactStorage
  • Modified src/repl.rs for Datalog support
  • Updated src/lib.rs for public API exports

Ready for review. All tests passing. Do not merge - will be merged manually after review.

🤖 Generated with Claude Code

adityamukho and others added 6 commits January 13, 2026 08:20
Strategic pivot after Phase 2 completion: transitioning from GQL-inspired
implementation to Datalog query language with bi-temporal support as a
first-class feature.

## Changes

### README.md
- Updated project tagline: "SQLite of bi-temporal graph databases"
- Replaced GQL examples with Datalog query syntax
- Added "Why Datalog?" section explaining the pivot rationale
- Updated roadmap summary (12-15 months vs 24-30 with GQL)
- Added comparison table (Minigraf vs XTDB, Cozo, Datomic, GraphLite)
- Emphasized bi-temporal as core feature, not addon
- Added learning resources for Datalog and temporal databases

### PHILOSOPHY.md
- Added "Why Datalog?" section at the top
- Explained 5 key reasons for pivot: simpler, temporal-native, more powerful,
  faster to production, unique positioning
- Updated "What Minigraf IS" to include bi-temporal and Datalog
- Updated target use cases (audit-heavy apps, event sourcing as primary)
- Updated Evolution Strategy with new phase breakdown (3-7)
- Added Datomic, XTDB, Cozo to inspirations
- Removed GQL spec compliance from non-goals

### ROADMAP.md
- Complete rewrite reflecting Datalog-focused roadmap
- Phase 1-2: Archived as complete (GQL implementation)
- Phase 3: Datalog Core (EAV model, recursive rules) - NEXT
- Phase 4: Bi-temporal Support (transaction + valid time)
- Phase 5: ACID + WAL (moved after bi-temporal)
- Phase 6: Performance & Indexes
- Phase 7: Cross-platform (WASM, mobile, bindings)
- Phase 8: Ecosystem & Tooling
- Detailed technical approach for each phase
- Timeline: 12-15 months to v1.0 (vs 24-30 with GQL)
- Added "Why This Roadmap is Better" section

### CLAUDE.md
- Updated project overview to emphasize Datalog + bi-temporal
- Added strategic pivot explanation
- Updated architecture section for Phase 3 transition
- Documented current (property graph) vs future (EAV) data models
- Added bi-temporal Fact structure for Phase 4
- Updated query language examples (GQL archived, Datalog target)
- Added migration strategy for Phase 3
- Updated comparison to similar projects
- Emphasized philosophy alignment throughout

## Rationale

After completing Phase 2 and evaluating the competitive landscape:
1. GraphLite already provides mature GQL implementation
2. Datalog offers simpler implementation path (proven patterns)
3. Bi-temporal support is natural in Datalog (time as dimension)
4. Unique market positioning: single-file bi-temporal Datalog (gap exists)
5. Faster to production: 12-15 months vs 24-30 months

GQL implementation archived at `archive/gql-phase-2` branch.

Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
Add Entity-Attribute-Value (EAV) data model types alongside existing
property graph types as first step of Datalog implementation.

## New Types

### Core EAV Types:
- `EntityId` - UUID-based entity identifiers
- `TxId` - u64 transaction IDs for versioning
- `Attribute` - String-based attribute names (`:person/name` style)
- `Value` - Extended enum supporting:
  - String, Integer, Float, Boolean (like PropertyValue)
  - Ref(EntityId) - NEW: References to other entities
  - Keyword(String) - NEW: Keywords like `:status/active`
  - Null
- `Fact` - Core EAV triple: (Entity, Attribute, Value, TxId, Asserted)

### Fact Structure:
- Immutable facts with transaction tracking
- `asserted` flag for retractions (instead of deletions)
- Support for assertion and retraction operations
- Maintains full history for temporal queries

## Implementation Details

- Added comprehensive accessor methods for Value enum
- Factory methods for Fact creation (new, retract, with_asserted)
- Full serde support for serialization
- PartialEq implementations for testing

## Tests Added (6 new tests):
- `test_value_creation_and_accessors` - All Value variants
- `test_fact_creation` - Basic fact assertions
- `test_fact_retraction` - Fact retractions
- `test_fact_with_ref_value` - Entity references (graph edges)
- `test_fact_equality` - Fact comparison logic
- `test_value_types` - Serialization/deserialization

## Migration Strategy

Property graph types (Node, Edge, PropertyValue) preserved for
backward compatibility during Phase 3 transition. EAV types added
alongside, exported from lib.rs with clear comments.

All 9 tests passing (3 existing + 6 new).

Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
Change TxId from simple counter to timestamp (milliseconds since UNIX
epoch) for natural chronological ordering and better Phase 4 preparation.

## Changes

- TxId now represents milliseconds since UNIX epoch
- Added helper functions:
  - `tx_id_now()` - Get current timestamp as TxId
  - `tx_id_from_system_time()` - Convert SystemTime to TxId
  - `tx_id_to_system_time()` - Convert TxId back to SystemTime
- Exported helpers from lib.rs for public use

## Benefits

1. **Natural ordering** - TxIds are chronologically ordered by default
2. **Human-readable** - Can convert to datetime for debugging
3. **Phase 4 ready** - Consistent with bi-temporal valid_time (also timestamps)
4. **No collision** - Millisecond precision sufficient for Phase 3 single-threaded usage

## Tests Added

- `test_tx_id_timestamp` - Verifies chronological ordering and round-trip conversion
- `test_tx_id_ordering` - Confirms sequential TxIds are strictly increasing

All 11 tests passing.

Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
This commit implements the foundational Datalog query engine for Minigraf,
marking the completion of core Phase 3 functionality as outlined in the roadmap.

## EAV Data Model
- Add `Fact` struct: (Entity, Attribute, Value, TxId, Asserted)
- Extend `Value` enum with `Ref` and `Keyword` variants for entity references
- Implement timestamp-based transaction IDs (milliseconds since UNIX epoch)
- Add helper functions: `tx_id_now()`, `tx_id_from_system_time()`, `tx_id_to_system_time()`

## Fact Storage Layer
- Implement `FactStorage` with append-only log architecture
- Support assertions and retractions (immutable history)
- Add `transact()` and `retract()` with automatic timestamping
- Implement query methods: `get_current_value()`, `get_facts_by_entity()`, etc.
- Add 8 comprehensive tests for fact storage

## EDN/Datalog Parser
- Full EDN tokenizer supporting vectors, lists, keywords, symbols, UUIDs
- Parse Datalog commands: `(transact [...])`, `(query [...])`, `(retract [...])`
- Support for all value types: strings, integers, floats, booleans, keywords, UUIDs
- Add 11 tests for parser functionality

## Pattern Matching Engine
- Implement `PatternMatcher` with variable unification
- Support multi-pattern queries with variable binding across patterns
- Join algorithm for matching multiple patterns simultaneously
- Convert between EDN values and storage values
- Deterministic keyword-to-UUID conversion for entity references
- Add 6 tests for pattern matching

## Query Executor
- Implement `DatalogExecutor` for command execution
- Execute transact/retract operations with proper error handling
- Query execution with pattern matching and variable projection
- Return structured query results
- Add 6 tests for executor functionality

## REPL Integration
- Update REPL to support Datalog syntax (parenthesis-based commands)
- Maintain backward compatibility with GQL syntax
- Pretty-print Datalog query results with column headers
- Add visual feedback for transactions/retractions

## Public API
- Export all Datalog types and functions from `src/lib.rs`
- Export fact storage and EAV types
- Provide complete API for library users

## Test Coverage
- 81 tests passing (up from 51 before Phase 3)
- Comprehensive coverage across all new modules

## Example Usage
```datalog
(transact [[:alice :person/name "Alice"]
           [:alice :person/age 30]])

(query [:find ?name ?age
        :where [?e :person/name ?name]
               [?e :person/age ?age]])
```

This implementation provides the foundation for Phase 4 (bi-temporal support)
and Phase 5 (ACID + WAL).

Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
Comment thread src/query/datalog/matcher.rs Fixed
Fix code scanning alert by collapsing nested if statements into a
single matches! expression with a guard pattern.

Changes:
- Replaced nested if-let with matches! macro
- Maintains same logic and behavior
- More concise and idiomatic Rust code

All tests passing.

Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
@adityamukho
adityamukho merged commit bdd9da2 into main Jan 13, 2026
3 checks passed
@adityamukho
adityamukho deleted the phase-3-datalog-core branch January 13, 2026 05:42
etc-sw pushed a commit to etc-sw/vicia-db that referenced this pull request Jul 11, 2026
Why: harrekki P0 project-minigraf#1/project-minigraf#4 — the resident daemon needs a persistent
conversation with one open database instead of spawning the CLI per
call. Design was frozen by dual caller-lane ACK before implementation
(docs/A6_SESSION_PROTOCOL_QUESTIONS.md status block).

Includes: src/session.rs — sequential NDJSON request/response loop over
any BufRead/Write; ops execute/status/checkpoint/maintenance/ping/
shutdown; lossless tagged value encoding ($ref/$kw, $float for
non-finite); durability classification on write frames (applied/
maintenance_pending, published on checkpoint, rejection = error frame);
error kinds parse/execution/storage/protocol with next-newline resync.
minigraf --session [--file <path>] wiring in main.rs. Crate-internal
status plumbing: FactStorage::pending_fact_count/has_committed_reader,
PersistentFactStorage::delta_growth_snapshot, Minigraf::session_status/
maintenance_advised — no public API beyond the session module. serde_json
becomes a regular dependency (was browser-only optional; pure Rust).
docs/SESSION_PROTOCOL.md frame reference; plan doc marks A6 done.

Verification: cargo test — full suite green (45 binaries, 1135 passed,
0 failed), including 17 new session tests; gate test holds ONE child
process for 10k mixed transact/query round-trips in 1.2 s with zero
failures; malformed-input determinism proven over a real pipe;
file-backed durability verified across two child sessions (write in
one, read in the next, checkpoint published).

Known gaps: status fact_count is null once committed data exists (exact
total needs a full scan — pending_facts/tx_count are the cheap
substitutes; documented in SESSION_PROTOCOL.md as a caller-favoring
deviation, worth flagging to harrekki). Auto-checkpoints fired by the
WAL threshold inside execute are not reflected in last_checkpoint_*.
CLAUDE.md global test count is stale (predates A0/A6); sync at next
version bump. SIGKILL durability under this path is A7's job.

Confidence: high
Scope-risk: narrow
Reversibility: clean
Tested: cargo test (full), session gate 10k round-trips, child-process spawn tests
Not-tested: kill -9 under load (A7), JVM/babashka-side adapter consumption
Directive: protocol frames are a frozen caller contract — breaking
changes need a version field and caller-lane re-ACK, not a silent edit.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
etc-sw pushed a commit to etc-sw/vicia-db that referenced this pull request Jul 11, 2026
Why: vicia lane reported the one post-ACK naming deviation (fact_count
null once committed data is on disk; pending_facts added). Recording the
harrekki-lane acceptance next to the original ACK keeps the two lane
documents from drifting.

Includes: name-review section note — deviation accepted, resident
self-model tracks growth via tx_count.

Verification: cross-checked against HARREKKI_CALLER_REQUIREMENTS.md P0 project-minigraf#4
(fact total was informational, not load-bearing).
Known gaps: none.

Confidence: high
Scope-risk: narrow
Reversibility: clean

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
vizanto added a commit to axe-scale/minigraf that referenced this pull request Jul 14, 2026
…gelog

- BENCHMARKS-FORK.md: fresh 2026-07-14 measurements — rules bands 1.8/10.8-11.1/98ms,
  60k grid (two-hop 1.8ms LFTJ, ordered k=1 0.01ms), temporal grid, zone-map file
  evidence UPGRADED from historical to fresh (as-of 75.1->50.2ms, 50.61% pages skipped;
  poisoned valid-at 0% as designed), H18 release gate PASSED fresh (139.4s, zero
  MISMATCH, LFTJ <=1.10x regret on every class), 965k CPG spike re-run fresh (TSV
  regenerated from the spike parquet: load 2,893ms, warm bound closure 398.8ms,
  unbound 7,892ms, no truncation).
- docs/UPSTREAM-REPORTS.md (new): four filing-ready reports; repros for project-minigraf#1 (u16
  saturation: probe 0 rows, scan exactly 65,536/70,000) and project-minigraf#2 (multi-value collapse:
  1 row vs 2) RUN AND CONFIRMED against upstream cbf899e; project-minigraf#3 verified-by-inspection
  (lines confirmed inside migrate_v5_to_v6); project-minigraf#4 red-reproduced on pre-fix code via
  git-archive. Plus fork-dialect notes (avg, :limit, :order-by, :max-results).
- CHANGELOG-FORK.md (new): all 18 commits, one-liners verified against commit bodies.
- minigraf-bench/README + design docs: temporal-workload usage note, landed-since
  annotations.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Co-Authored-By: Codex GPT-5.6 Terra <noreply@openai.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants