Skip to content

v0.5.0 Release Notes

Latest
Latest

Choose a tag to compare

View all tags
@github-actions github-actions released this 22 Jun 22:38
v0.5.0
cb6c48c
This commit was created on GitHub.com and signed with GitHub’s verified signature.
GPG key ID: B5690EEEBB952194
Verified
Learn about vigilant mode.

Release Date

2026-06-22

Summary

ExDatalog v0.5.0 adds four major capabilities on top of the v0.4.x Schema DSL,
all compiled into the existing Program / Rule / Fact / Constraint /
Knowledge builder APIs — the core engine was extended, not rewritten:

  • Aggregates (count, sum, min, max) with grouping and stratification.
  • BEAM callback predicates — call deterministic Elixir functions from rule
    bodies, isolated with a timeout and exception handling.
  • Query Planner (ExDatalog.Planner) — a standalone, inspectable description
    of how a program will evaluate, with explain_plan/1,2 and telemetry.
  • Magic sets (experimental) — demand-driven, goal-directed evaluation that
    rewrites a program to compute only goal-relevant facts.

A runtime facts API rounds out the release: Schema.new/0 produces a blank
program from a schema's relations and rules, and facts can be piped in at
runtime with Program.add_fact/2 and Program.add_facts/2.

The builder API and the v0.4.x DSL remain fully backward compatible. All
existing tests pass unchanged.

Architecture

DSL (use ExDatalog.Schema) / Builder API
  │
  ├── count/sum/min/max          → Constraint aggregates  (Constraints.Aggregate)
  ├── predicate :name, M, :f, …  → BEAM callbacks         (Constraints.BeamCallback)
  ├── Schema.new/0               → blank Program (relations + rules, no facts)
  ├── Program.add_fact/2,        → runtime fact insertion
  │   Program.add_facts/2
  │
  ▼
Program ──► Validator ──► Compiler ──► IR ──► Engine.Naive ──► Knowledge
                                        │
                                        ├── strategy: :semi_naive  (default)
                                        └── strategy: :magic_sets   (MagicSets.transform)

Off to the side (inspection only, NOT on the eval path):
  IR ──► Planner.plan/2 ──► Plan (strategy, strata, joins, predicates)

New Public Modules

Module Description
ExDatalog.Planner Query/evaluation planner; plan/2, explain_plan/1,2
ExDatalog.Planner.Plan Plan struct (strategy, strata, joins, predicates, metadata)
ExDatalog.Planner.Stratum Planned stratum (index, rules, relations)
ExDatalog.Planner.Join Planned join (relation, position, delta position)
ExDatalog.Planner.Predicate Planned predicate, classified by kind
ExDatalog.Constraints.Aggregate Aggregate grouping and reduction
ExDatalog.Constraints.BeamCallback BEAM callback evaluation with isolation
ExDatalog.Callback AST-level callback predicate struct
ExDatalog.IR.Callback IR-level callback predicate struct
ExDatalog.MagicSets Magic-sets program transformation

Feature Details

Aggregates

count, sum, min, max in rule bodies, via the DSL or the builder API.
The result variable must appear in the rule head; aggregates group the
surviving bindings by the other head variables, reduce each group, and are
stratified strictly above their source relations.

DSL:

defmodule DeptStats do
  use ExDatalog.Schema

  relation :emp do
    field(:name, :atom)
    field(:dept, :atom)
  end

  relation :dept_count do
    field(:dept, :atom)
    field(:n, :integer)
  end

  fact(emp(:alice, :eng))
  fact(emp(:bob, :eng))
  fact(emp(:carol, :sales))

  rule dept_count(D, N) do
    emp(_, D)
    count(E, N)
  end
end

{:ok, k} = DeptStats.materialize()
ExDatalog.Knowledge.get(k, "dept_count")
#=> MapSet.new([{:eng, 2}, {:sales, 1}])

Builder API: Constraint.count/2, Constraint.sum/2, Constraint.min/2,
Constraint.max/2, the {:count, X, N} tuple form, and add_rule/4.

Rules:

  • One aggregate per rule (rejected otherwise with :multiple_aggregates).
  • An aggregate may not appear in a self-recursive rule (:aggregate_in_recursion).
  • The aggregate result variable must appear in the rule head
    (:aggregate_result_not_in_head).
  • Aggregate inputs are integer-only. count accepts any input type and returns
    the group size; sum/min/max require integers and raise
    ArgumentError at reduction time on a non-integer input.

BEAM Callback Predicates

Call deterministic, side-effect-free Elixir functions from rule bodies.

DSL:

defmodule Gated do
  use ExDatalog.Schema

  relation :user do
    field(:name, :atom)
    field(:age, :integer)
  end

  relation :active_user do
    field(:name, :atom)
  end

  predicate(:adult?, AgeChecker, :adult?, [:integer], :boolean)

  fact(user(:alice, 30))
  fact(user(:bob, 12))

  rule active_user(U) do
    user(U, Age)
    adult?(Age)
  end
end

Builder API: ExDatalog.Callback literals in a rule body.

  • Boolean callbacks (:boolean) filter bindings: true keeps, false
    drops.
  • Value callbacks (:value) bind the function's return to the last
    argument's result variable.
  • Each call runs in a spawn_monitor-ed process with a configurable timeout
    (:callback_timeout_ms, default 100ms). A timeout or raised exception filters
    the binding; late result messages are flushed from the evaluator mailbox.

Query Planner

ExDatalog.Planner is a standalone inspection tool. It is not a stage in
the evaluation pipeline — the engine reads the IR directly. The planner consumes
the same validated IR to produce a descriptive Plan:

IO.puts(ExDatalog.Planner.explain_plan(DeptStats.program()))
# Strategy: semi_naive
#   Stratum 0: 0 rule(s), relations: emp
#   Stratum 1: 1 rule(s), relations: dept_count
# Joins: 1
# Predicates: 1 (count)

Predicates are classified by kind (:comparison, :arithmetic, :type,
:string, :membership, :aggregate, :callback). Telemetry fires once per
plan as [:ex_datalog, :planner, :start | :stop | :exception].

Magic Sets (experimental)

Demand-driven evaluation via materialize/2:

{:ok, k} =
  ExDatalog.materialize(program,
    strategy: :magic_sets,
    goal: {"ancestor", [:a, :_]}
  )

ExDatalog.MagicSets.transform/2 rewrites the program: it computes the goal's
adornment, generates a magic_<relation>_<adornment> demand predicate, seeds it
with the goal's bound constants, prepends the magic predicate to goal-relation
rules, and generates supplementary rules that propagate demand to recursive body
atoms. The transformed IR is evaluated by the unchanged semi-naive engine.

Scope: positive recursive programs with at least one ground bound position.
Programs outside scope (negation, aggregates, all-free goals) fall back to
semi-naive evaluation and never produce incorrect results.

Note on benefit: for linear transitive closure, demand reaches every node,
so the saving is small; the win is large when much of the graph is unreachable
from the goal (those regions are never derived).

Runtime Facts API

Separate compile-time program structure from runtime data:

program =
  DeptStats.new()                                   # relations + rules, no facts
  |> ExDatalog.Program.add_fact(DeptStats.emp(:alice, :eng))
  |> ExDatalog.Program.add_facts([
       DeptStats.emp(:bob, :eng),
       DeptStats.emp(:carol, :sales)
     ])

{:ok, k} = ExDatalog.Program.materialize(program)
  • Schema.new/0 — blank program (relations + rules, no compile-time facts).
  • Schema.program/0 — program including compile-time fact/1 declarations.
  • Generated relation constructors: DeptStats.emp(:alice, :eng) →
    {"emp", [:alice, :eng]}.
  • Program.add_fact/2 (tuple form), Program.add_facts/2 (bulk), and
    Program.materialize/1,2 are pipe-friendly and propagate {:error, _}
    through a chain.

Changed / Added Files

File Change
lib/ex_datalog/planner.ex New — query planner
lib/ex_datalog/planner/{plan,stratum,join,predicate}.ex New — plan structs
lib/ex_datalog/constraints/aggregate.ex New — aggregate grouping/reduction with integer guards
lib/ex_datalog/constraints/beam_callback.ex New — callback evaluation with timeout isolation and late-message flush
lib/ex_datalog/callback.ex, lib/ex_datalog/ir.ex New/updated — callback structs and IR literal
lib/ex_datalog/magic_sets.ex New — magic-sets transform with supplementary demand rules and unique rule IDs
lib/ex_datalog/engine/naive.ex :strategy dispatch; aggregate stratification check
lib/ex_datalog/validator/safety.ex Aggregate safety: single, non-recursive, result-in-head
lib/ex_datalog/schema.ex new/0, runtime relation constructors, zero-field relation guard, updated docs
lib/ex_datalog/program.ex add_fact/2 tuple form, add_facts/2, materialize/1,2, error propagation
lib/ex_datalog.ex materialize/2 passes :strategy/:goal to the engine; documents integer-only aggregate contract
lib/ex_datalog/constraint.ex Aggregate constructors and tuple forms
mix.exs Version 0.4.1 → 0.5.0; benchee dev dep; articles/migration extras
README.md, CHANGELOG.md v0.5.0 feature list, examples, roadmap
docs/articles/06_query_planning_in_datalog.md New
docs/articles/07_aggregates_in_datalog.md New
docs/articles/08_extending_datalog_with_beam_callbacks.md New
docs/articles/09_magic_sets_and_demand_driven_evaluation.md New
docs/migration_v0.5.md New — v0.4 → v0.5 migration guide
livebooks/ex_datalog_v050.livemd New — DSL-edition tutorial covering all v0.5.0 features
bench/aggregate_bench.exs, bench/magic_sets_bench.exs New — benchmark scripts
test/ex_datalog/{aggregate,beam_callback,magic_sets,runtime_facts,planner}_test.exs New/updated — feature and regression tests

Test Results

152 doctests, 10 properties, 871 tests, 0 failures
Coverage: 93.3%

Quality Checks

Check Result
mix format --check-formatted Pass
mix compile --warnings-as-errors Pass
mix test 871 tests, 0 failures
mix credo --strict 0 issues
mix dialyzer 0 errors
mix docs --warnings-as-errors 0 warnings
Coverage 93.3% (≥ 90% gate)

Post-Release Review Fixes

Two rounds of code review were applied before this release. The second round
(see chest/reviews/v0.5.0-review-v2.md) found and fixed:

  • Correctness: magic-sets generated duplicate IR rule IDs for rules with
    more than one recursive body atom (e.g. r(X,Z) :- r(X,Y), r(Y,Z)),
    corrupting the provenance map. Fixed with per-rule incrementing IDs and a
    defensive uniqueness assertion on the transformed IR.
  • Documentation: corrected articles 06/07/09 where prose contradicted the
    shipped behavior (planner-on-the-eval-path claim, "magic sets is inert", the
    result-not-in-head and non-integer-input behavior, and a stale "derives only
    four facts" claim).
  • Tests: added coverage for the aggregate integer guards, the
    :aggregate_result_not_in_head check, the multi-recursive magic-sets case,
    and the callback timeout mailbox-flush.
  • Hardening: zero-field relations now raise a clear DSL.CompileError;
    non-integer aggregate input contract documented; minor doc/naming cleanups.

Known Limitations

  1. Aggregates are integer-only. avg and float support are deferred to a
    future release. A non-integer sum/min/max input raises ArgumentError
    at reduction time rather than returning {:error, _} — constrain untrusted
    input with is_integer/1 earlier in the rule body if needed.

  2. Magic sets is experimental and opt-in. Single goal, ground bound
    positions, positive recursive programs only. Negation and aggregates trigger
    fallback to semi-naive. The default strategy is unchanged.

  3. The planner is descriptive, not executable. It reports the requested
    strategy and the evaluation shape, but it does not drive evaluation; the
    engine reads the IR directly.

  4. Callback determinism is a contract, not enforced. The engine isolates
    callbacks against timeouts and exceptions, but cannot prevent a callback from
    performing side effects or returning non-deterministic results.

Breaking Changes

None. The builder API, the v0.4.x Schema DSL, and all prior public functions are
fully backward compatible. All existing tests pass unchanged.

Backward Compatibility

  • ExDatalog.Program.add_rule/2,3,4 — unchanged
  • ExDatalog.materialize/2 — unchanged (new optional :strategy/:goal)
  • ExDatalog.Knowledge.get/2, match/3 — unchanged
  • Schema DSL relation, fact, facts, rule, query, program/0,
    materialize/0,1 — unchanged
  • Tuple shorthand from v0.3.0 — unchanged

Follow-up Roadmap

Version Focus
v0.6.0 avg and additional aggregates; build-time aggregate type enforcement; EDN serialization (exploratory)
v0.7.0 Cost-based planning hooks; magic-sets for multi-goal and negation-aware programs
v1.0.0 Stable public API; hardened production semantics; expanded property-based testing
Assets 2
Loading