Changelog

Copy Markdown View Source

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

v0.5.0 (2026-06-21)

Added

  • Query Planner (ExDatalog.Planner) — a thin planning layer between the compiled IR and the engine. plan/2 produces an ExDatalog.Planner.Plan (strategy, strata, joins, predicates); explain_plan/1,2 renders a human-readable plan. Emits [:ex_datalog, :planner, :start|:stop|:exception] telemetry.
  • Aggregates — count, sum, min, max in rule bodies, via the DSL (count(X, N)) or the builder API (Constraint.count/2, from_tuple({:count, X, N}), add_rule/4). Aggregates group surviving bindings by the head variables other than the result, reduce each group, and are stratified strictly above their source relations. Integer-only; one aggregate per rule.
  • BEAM callback predicates — call deterministic, side-effect-free Elixir functions from rule bodies. DSL: predicate :name, Module, :fun, [types], :boolean | :value. Builder: ExDatalog.Callback literals in a rule body. Boolean callbacks filter; :value callbacks bind a result variable. The engine isolates callbacks with a configurable timeout (:callback_timeout_ms, default 100ms) and rescues exceptions — a timeout/raise filters the binding.
  • Magic sets (experimental) — demand-driven evaluation via materialize(program, strategy: :magic_sets, goal: {relation, pattern}). The IR is rewritten to compute only facts relevant to the goal. Supports positive recursive programs with ground bound positions; unsupported programs fall back to semi-naive evaluation (never producing incorrect results).
  • ExDatalog.Callback and ExDatalog.IR.Callback for callback predicates.
  • ExDatalog.Constraints.Aggregate and ExDatalog.Constraints.BeamCallback.
  • Capabilities gains aggregate_constraints and beam_callbacks fields.
  • Constraint.Context gains an opts field (threads evaluation options such as callback_timeout_ms).
  • Educational articles 06–09 (planner, aggregates, callbacks, magic sets) and a v0.4 → v0.5 migration guide.
  • Benchmark harness (bench/) and report (chest/benchmarks/v0.5.0-report.md).
  • Runtime facts API — Schema.new/0 returns a blank program (relations + rules, no compile-time facts). Pipe facts at runtime via Program.add_fact/2 (tuple form {"rel", [values]}) or Program.add_facts/2 (bulk). Program.materialize/1,2 is a pipe-friendly wrapper for ExDatalog.materialize/2. Generated relation constructors (Schema.emp(:alice, :eng) -> {"emp", [:alice, :eng]}) bridge the DSL to runtime data.

Changed

  • Version bumped from 0.4.1 to 0.5.0.
  • Engine.Naive.evaluate/2 dispatches on a :strategy option (:semi_naive default, or :magic_sets).
  • Engine.Naive stratification validation now also rejects aggregate rules whose source relations are not in a strictly lower stratum.
  • The agg(...) placeholder now points users to count/sum/min/max.

Notes

  • Aggregates are integer-only; avg and float support are deferred to v0.6.0.
  • Magic sets is experimental and opt-in; the default strategy is unchanged.
  • All v0.4.1 tests continue to pass. Suite: 871 tests, 10 properties, 152 doctests, ~93% coverage.

v0.4.1 (2026-06-21)

Fixed

  • C1: Corrected moduledoc and rule/2 docstring to state that uppercase identifiers are logic variables (was incorrectly documented as lowercase). Updated moduledoc examples, rule/2 docstring, README, and article 01 to use uppercase variables consistently.
  • C2: Aggregate syntax (agg(...)) now raises ExDatalog.DSL.CompileError with a clear message in both head and body positions, instead of crashing with CompileError or FunctionClauseError. Updated CHANGELOG, article 05, and moduledoc to reflect reality.
  • H1: Replaced meaningless aggregate struct-literal tests with real end-to-end compile-time tests that exercise agg(...) DSL syntax in both head and body positions.
  • H2: Query without a where clause now raises ExDatalog.DSL.CompileError with a readable message instead of an opaque Protocol.UndefinedError.
  • M1: Query find variables that are not present in the where pattern now raise ExDatalog.DSL.CompileError at compile time instead of silently returning wrong results.
  • M2: Unrecognized expressions inside relation and facts blocks now raise ExDatalog.DSL.CompileError instead of being silently dropped.
  • L1: All DSL authoring errors now raise ExDatalog.DSL.CompileError (was a mix of CompileError and ArgumentError).
  • L2: README test count updated to 792 (was stale at 751, then 786).
  • L3: Dropped unused _program parameter from validate_rules!/1.
  • L4: Removed duplicate eq constraint test from SchemaCoverageTest.
  • L5: Fixed moduledoc reference from materialize/0 to materialize/0,1.
  • L6: Deleted livebooks/examples.md (521-line unreferenced LLM-generated artifact).

Changed

v0.4.0 (2026-06-20)

Added

  • ExDatalog.Schema — Ecto-inspired DSL macro module for defining Datalog programs
    • relation/2 macro declares typed relation schemas
    • fact/1 and facts/2 macros declare ground facts
    • rule/2 macro declares rules with uppercase logic variables, not_ for negation, named constraint predicates (gt, eq, add, etc.)
    • query/2 macro declares named post-materialization queries with find/where
    • wildcard/0 helper for explicit wildcards in rule bodies
    • Generated program/0, materialize/0,1, queries/0, query/2 functions
  • ExDatalog.UnsupportedFeature struct for forward-compatible aggregate syntax parsing
  • ExDatalog.DSL.CompileError exception for readable DSL macro errors
  • 33 integration tests for the DSL (relations, facts, rules, negation, constraints, queries, backward compatibility)
  • Livebook tutorial: livebooks/ex_datalog_dsl.livemd
  • Educational articles in docs/articles/

Changed

  • Version bumped from 0.3.0 to 0.4.0
  • DSL is the recommended authoring layer; builder API remains the stable lower-level API
  • README updated with DSL quickstart

Notes

  • Query DSL operates on materialized knowledge only (no query planner yet)
  • Aggregate syntax is not yet supported — using agg(...) raises ExDatalog.DSL.CompileError at compile time
  • All 718 existing tests continue to pass (now 786 total)

[0.3.0] - 2025-06-19

Added

  • Tuple shorthand for rules: Program.add_rule/3 and Program.add_rule/4 accept {relation, [terms]} tuples for heads, {:polarity, {relation, [terms]}} for body literals, and {:op, args...} for constraints. Uppercase atoms (:X) become variables, :_ becomes a wildcard, lowercase atoms and other values become constants.
  • Term.from/1 — converts shorthand values to Term.t() following Prolog convention.
  • ExDatalog.Atom.from_tuple/1 — constructs an atom from {"relation", [terms]} shorthand.
  • Constraint.from_tuple/1 — constructs a constraint from operator tuples like {:neq, :A, :B}, {:add, :X, :Y, :Z}, {:is_integer, :V}.

Changed

  • ExDatalog.Result renamed to ExDatalog.Knowledge — the struct returned by materialize/2 now reflects that it represents a materialized knowledge base, not a query result. All references updated across source, tests, docs, and livebooks.
  • ExDatalog.query (2-arity) renamed to ExDatalog.materialize/2 — the top-level API function now reflects that it runs the full fixpoint pipeline, not a single query.
  • Telemetry events renamed: [:ex_datalog, :query, :start|:stop|:exception] → [:ex_datalog, :materialize, :start|:stop|:exception].
  • ExDatalog.validate/1 and ExDatalog.compile/1 now pass through {:error, _} tuples from the builder pipeline instead of raising FunctionClauseError. materialize/2 also passes through {:error, _} from a failed pipeline step.
  • Livebook examples (quickstart.livemd, examples.livemd, examples.exs) converted to tuple shorthand notation. README quickstart updated accordingly.

[0.2.0] - 2025-05-15

Added

  • Constraint types: type predicates (type_integer/1, type_binary/1, type_atom/1), string predicates (starts_with/2, contains/2), and membership (member/2)
  • Constraint evaluation dispatch via ExDatalog.Constraint.evaluate/3 with behaviour-based constraint modules
  • ExDatalog.Constraint.Context carries storage backend capabilities through evaluation pipeline
  • ExDatalog.Capabilities struct and merge/satisfies/from_backend API
  • ExDatalog.Storage.ETS backend with per-relation ETS tables, wrapped-tuple keys, and concurrent read support
  • Storage behaviour init/2 for passing backend options (access, write_concurrency, read_concurrency)
  • ExDatalog.IR.from_term/1 now tags list constants as {:const, {:list, [...]}} for uniform IR value representation
  • ExDatalog.IR.resolve_operand/2 and ExDatalog.IR.value_to_native/1 shared helpers for constraint evaluation
  • Portability test suite (Map vs ETS) covering transitive closure, arithmetic, comparison, negation, type predicates, string predicates, and membership
  • Backend conformance macro (ExDatalog.Storage.BackendConformance) for shared storage contract tests
  • Engine storage_opts option for passing options to storage backends
  • try/after resource cleanup in Engine.Naive for ETS teardown safety
  • ETS tombstone guard (guard_not_tombstoned!) for clear errors on post-teardown operations
  • Constraint.valid?/1 now requires {:const, list} for :member right operand
  • Validator safety tests for type, string, and membership constraint ops
  • Public-struct evaluate/3 dispatch tests for comparison, arithmetic, type, string, membership
  • ETS teardown guard test and idempotent teardown test
  • Doctests on Constraint.Context.new/0,1,2
  • Documentation: docs/constraints.md and docs/storage_backends.md

Changed

  • Storage.ETS.member?/3 now uses :ets.member/2 (was :ets.match_object/3) — correct O(1) lookup
  • Storage.ETS.init/2 now accepts write_concurrency and read_concurrency options
  • Storage.ETS.upsert_index_entry uses MapSet instead of lists for O(log n) membership checks
  • Storage.ETS tables named ex_datalog_<relation> and ex_datalog_idx_<relation> for observability in :observer
  • Storage.ETS.update_index/4 raises ArgumentError on unknown relations (was silent no-op)
  • Storage.Map.update_index/4 raises ArgumentError on unknown relations (was silent empty-index)
  • Both backends now report type_predicates: true and string_predicates: true in capabilities
  • Constraint.evaluate/3 public-struct clause delegates to IR clause via recursion; documented both dispatch paths
  • IR.from_term({:const, list}) now produces {:const, {:list, [tagged_elements]}} instead of {:const, list}
  • IR.from_constraint/1 uses maybe_from_term/1 pattern matching instead of bare if
  • Constraints.Arithmetic.apply_arithmetic uses guard clauses with integer checks
  • All constraint modules use shared IR.resolve_operand/2 and IR.value_to_native/1 (was 5x duplicated)
  • Engine.Naive.evaluate/2 wraps evaluation in try/after to ensure ETS teardown on exceptions
  • Storage.ETS.teardown/1 returns :ok (was returning stale struct); post-teardown operations raise ArgumentError
  • Telemetry.emit_stop/5 requires explicit storage_type argument (removed default :map)
  • Constraint behaviour callback uses Binding.t() instead of map() for type safety

  • Storage behaviour teardown callback return type widened to :ok | {:error, term()}

  • Constraints.String renamed to Constraints.StringPredicate to avoid stdlib String conflict
  • Constraint.Context threads real storage capabilities from engine through evaluator
  • Engine.Naive extracts build_result/8 and emit_result_telemetry/5 helpers from do_evaluate_inner
  • Backend conformance macro no longer injects alias or @schemas into caller module
  • Dispatch table documented as closed (not a runtime registry)
  • Capabilities.from_backend/1 spec widened from {module(), term()} to {atom(), term()}
  • Engine.Evaluator.eval_rule_iteration/5 accepts Constraint.Context and passes to constraint evaluation
  • ConstraintEval.apply/3 and apply_one/3 accept optional Constraint.Context parameter
  • Storage.Map.size/2 and Storage.ETS.size/2 log Logger.debug for unknown relations
  • ETS moduledoc includes rationale for choosing :set table type
  • @optional_callbacks for build_index/3, get_indexed/4, update_index/4 in Storage behaviour
  • Dispatch consistency tests verify all 16 ops dispatch correctly and valid?/1 covers every category
  • "Defines exactly 12 callbacks" test removed from storage tests (was fragile)

Fixed

  • Storage.ETS.member?/3 was using :ets.match_object/3 instead of :ets.member/2 — wrong and slower
  • ETS tests "returns same state struct" removed — they enforced a misleading identity invariant
  • Constraint.valid_right?(:member, ...) now requires {:const, list} — prevents silent runtime filter
  • Capabilities doctest for from_backend/1 now uses valid Elixir instead of ... ellipsis

0.1.0 - 2025-04-18

Added

  • Phase 0: Architecture and design blueprint (pure Elixir, semi-naive evaluation, storage behaviour, hash-join indexing primitives)
  • Phase 1: AST, DSL, and term model
  • Phase 2: Semantic validation
    • ExDatalog.Validator.Safety — variable safety and range-restriction checks (all head variables appear in a positive body atom)
    • ExDatalog.Validator.Stratification — Tarjan SCC-based stratification (detects unstratifiable negation cycles)
    • Chained validation pipeline: structural → safety → stratification
  • Phase 3: IR compiler
    • ExDatalog.Compiler — AST-to-IR compilation producing IR.Program with strata, rules, facts, and relation schemas
    • ExDatalog.Compiler.Stratifier — Tarjan SCC algorithm to assign strata and detect unstratifiable programs
    • ExDatalog.IR — engine-neutral IR structs: IR.Program, IR.Stratum, IR.Rule, IR.Atom, IR.Fact, IR.Constraint
  • Phase 4: Semi-naive engine
  • Phase 5: Negation and stratification
    • Negative body atoms ({:negative, %IR.Atom{}}) evaluated as filters against fully-materialised lower-stratum relations
    • Stratification validation rejects unstratifiable programs before evaluation
    • Per-stratum fixpoint iteration with timeout and iteration limits (:max_iterations, :timeout_ms)
  • Phase 6: Provenance / explain
    • ExDatalog.Explain — derivation attribution when explain: true option is passed
    • result.provenance.fact_origins — maps each derived tuple to a rule that produced it (last-wins; not guaranteed canonical)
    • result.provenance.rules — rule map for human-readable rule lookup
    • Zero-overhead when explain: false (default): provenance tracking is entirely skipped
  • Phase 7: Telemetry
    • ExDatalog.Telemetry — :telemetry event emission at evaluation start, stop, and exception
    • Events: [:ex_datalog, :query, :start], [:ex_datalog, :query, :stop], [:ex_datalog, :query, :exception]
    • Measurements: system_time, duration, iterations
    • Metadata: relation_count, stratum_count, relation_sizes, kind, reason, stacktrace
  • Documentation: What is Datalog? guide covering history, concepts, industry use cases, and LLM integration patterns

Changed

  • Program.add_fact/3 validates fact values, rejecting floats and non-ground types with descriptive error messages
  • Program.add_relation/3, add_fact/3, and add_rule/2 propagate {:error, _} through pipelines instead of raising FunctionClauseError
  • Validator.validate/1 no longer mutates the program struct; validate/1 is now idempotent (program == elem(validate(program), 1))
  • Compiler.compile/1 normalizes facts/rules order independently (was previously done by validate/1)
  • Compiler.compile/1 validates IR invariants after compilation (unique rule IDs, stratum bounds, relation references, rule-in-stratum consistency)
  • Engine.Evaluator.eval_rule_iteration/4 skips variant evaluation when the delta relation is empty, avoiding wasted join work
  • Engine.Naive.iterate/1 uses incremental merge_new/2 instead of full-storage snapshot_facts/3 per iteration
  • IR.Constraint.serialize/1 always includes the :result key (even when nil), making the format lossless
  • ExDatalog.Atom.variables/1 now deduplicates variable names (was previously returning duplicates for r(X, X))
  • Constraint.result_variable/1 has a catchall clause instead of only matching {:var, name} and nil
  • Constraint.div/3 documented as integer division (Kernel.div/2), not float division
  • Validator.check_atom/4 fetches the relation schema once and passes it to arity checking, avoiding redundant Map.fetch
  • Storage indexing API (build_index/3, update_index/4, get_indexed/4, Join.join_indexed/4) marked @doc false for v0.1.0

Fixed

  • Program.add_fact/3 now rejects float values and non-ground term tuples with clear error messages (previously: silent acceptance, crash at compile time)
  • Term.const/1 raises ArgumentError (not FunctionClauseError) for unsupported value types including floats
  • Validator.validate/1 returns the original program struct unchanged, fixing two invariants: validate/1 is now idempotent, and validate → add_rule → validate no longer produces interleaved rule order
  • Engine.Evaluator.eval_rule_iteration/4 deduplicates k=0 fact rule results against existing tuples (was returning unfiltered results)
  • Engine.Naive.derive/5 computes derivation and origins in a single pass, eliminating 2x evaluation overhead when explain: true