# `ExDatalog`
[🔗](https://github.com/thanos/ex_datalog/blob/v0.5.0/lib/ex_datalog.ex#L1)

ExDatalog — a pure Elixir Datalog engine.

## Overview

ExDatalog implements a bottom-up Datalog evaluation engine with
semi-naive fixpoint computation. Programs are built using a
builder API, validated, compiled to an intermediate representation,
and evaluated by a pluggable engine backend.

## Quick Start

     alias ExDatalog
     alias ExDatalog.{Program, Rule, Atom, Term}

     {:ok, knowledge} =
       Program.new()
       |> Program.add_relation("parent", [:atom, :atom])
       |> Program.add_relation("ancestor", [:atom, :atom])
       |> Program.add_fact("parent", [:alice, :bob])
       |> Program.add_fact("parent", [:bob, :carol])
       |> Program.add_rule(
            Rule.new(
              Atom.new("ancestor", [Term.var("X"), Term.var("Y")]),
              [{:positive, Atom.new("parent", [Term.var("X"), Term.var("Y")])}]
            )
          )
       |> Program.add_rule(
            Rule.new(
              Atom.new("ancestor", [Term.var("X"), Term.var("Z")]),
              [
                {:positive, Atom.new("parent", [Term.var("X"), Term.var("Y")])},
                {:positive, Atom.new("ancestor", [Term.var("Y"), Term.var("Z")])}
              ]
            )
          )
       |> ExDatalog.materialize()

## Pipeline

The evaluation pipeline is:

1. `ExDatalog.Program` — builder API
2. `ExDatalog.Validator` — structural + semantic validation
3. `ExDatalog.Compiler` — AST to IR
4. `ExDatalog.Engine` — pluggable evaluation backend
5. `ExDatalog.Knowledge` — the knowledge base produced by evaluation

Each step can be invoked individually:

     {:ok, validated} = ExDatalog.validate(program)
     {:ok, ir}        = ExDatalog.compile(program)
     {:ok, knowledge}  = ExDatalog.evaluate(ir, [])

## Options

`materialize/2` and `evaluate/2` accept:

 - `engine` — backend module (default: `ExDatalog.Engine.Naive`)
 - `storage` — storage module (default: `ExDatalog.Storage.Map`)
 - `max_iterations` — fixpoint iteration limit (default: 10_000)
 - `timeout_ms` — wall-clock timeout in milliseconds (default: 30_000)
 - `strategy` — `:semi_naive` (default) or `:magic_sets`
 - `goal` — `{relation_name, pattern}` used as the magic-sets goal
   (when `strategy: :magic_sets`) and as a post-materialization filter
   (default: `nil`). See `materialize/2` for details.
 - `explain` — enable provenance tracking (default: `false`)

If `max_iterations` or `timeout_ms` is hit, the returned `Knowledge.t()`
will have `stats.termination` set to `:iteration_limit` or `:timeout`
respectively. A successful fixpoint has `stats.termination == :fixpoint`.
Callers **must** check this field to distinguish complete from truncated
results.

# `compile`

```elixir
@spec compile(ExDatalog.Program.t()) ::
  {:ok, ExDatalog.IR.t()} | {:error, [ExDatalog.Validator.Error.t()]}
```

Compiles a validated program to an engine-neutral IR.

Runs validation first. Returns `{:ok, %ExDatalog.IR{}}` or
`{:error, errors}`.

The IR is deterministic: the same program always produces the same IR.
Rules are sorted by `(stratum, relation_name, rule_id)`. Facts are sorted
by `(relation_name, values)`. Relations are sorted by name.

## Examples

     iex> alias ExDatalog.{Program, Rule, Atom, Term}
     iex> program =
     ...>   Program.new()
     ...>   |> Program.add_relation("edge", [:atom, :atom])
     ...>   |> Program.add_relation("path", [:atom, :atom])
     ...>   |> Program.add_rule(
     ...>     Rule.new(
     ...>       Atom.new("path", [Term.var("X"), Term.var("Y")]),
     ...>       [{:positive, Atom.new("edge", [Term.var("X"), Term.var("Y")])}]
     ...>     )
     ...>   )
     iex> {:ok, ir} = ExDatalog.compile(program)
     iex> length(ir.rules) == 1 and length(ir.relations) == 2
     true
     true

# `evaluate`

```elixir
@spec evaluate(
  ExDatalog.IR.t(),
  keyword()
) :: {:ok, ExDatalog.Knowledge.t()} | {:error, term()}
```

Evaluates a compiled IR program against a backend engine.

Returns `{:ok, ExDatalog.Knowledge.t()}` or `{:error, reason}`.

## Options

- `:engine` — backend module (default: `ExDatalog.Engine.Naive`)
- `:storage` — storage module (default: `ExDatalog.Storage.Map`)
- `:max_iterations` — fixpoint iteration limit (default: 10_000)
- `:timeout_ms` — wall-clock timeout in ms (default: 30_000)

Check `knowledge.stats.termination` for `:fixpoint`, `:iteration_limit`,
or `:timeout` to determine whether evaluation completed.

# `materialize`

```elixir
@spec materialize(
  ExDatalog.Program.t(),
  keyword()
) ::
  {:ok, ExDatalog.Knowledge.t()}
  | {:error, [ExDatalog.Validator.Error.t()] | term()}
```

One-shot: validate, compile, and materialize a program.

Equivalent to `validate/1` → `compile/1` → `evaluate/2`.

Returns `{:ok, ExDatalog.Knowledge.t()}` or `{:error, reason}`.

## Aggregate input types

Aggregates (`sum`, `min`, `max`) are integer-only. If an aggregate's input
resolves to a non-integer value at reduction time, evaluation **raises**
`ArgumentError` rather than returning `{:error, reason}`. A non-integer
aggregate input is treated as a data-modeling error and surfaces loudly. If
the input domain is untrusted, constrain it with a type predicate (for example
`is_integer/1`) earlier in the rule body, or wrap the call in a `try`.

## Options

See `evaluate/2` for available options, plus:

- `:goal` — `{relation, pattern}` used both as the magic-sets goal
  (when `strategy: :magic_sets`) and as a post-materialization filter
  (default: `nil`). When set, the knowledge base's `relations` map contains
  only the matching tuples for the specified relation. The pattern uses `:_`
  as a wildcard, matching `Knowledge.match/3`.

## Examples

     iex> alias ExDatalog.{Program, Rule, Atom, Term}
     iex> program =
     ...>   Program.new()
     ...>   |> Program.add_relation("parent", [:atom, :atom])
     ...>   |> Program.add_fact("parent", [:alice, :bob])
     iex> {:ok, knowledge} = ExDatalog.materialize(program)
     iex> ExDatalog.Knowledge.size(knowledge, "parent")
     1

# `new`

```elixir
@spec new() :: ExDatalog.Program.t()
```

Creates a new, empty Datalog program.

Delegates to `ExDatalog.Program.new/0`.

## Examples

     iex> ExDatalog.new()
     %ExDatalog.Program{relations: %{}, facts: [], rules: []}

     iex> alias ExDatalog.Program
     iex> ExDatalog.new() |> Program.add_relation("edge", [:atom, :atom])
     %ExDatalog.Program{relations: %{"edge" => %{arity: 2, types: [:atom, :atom]}}, facts: [], rules: []}

# `validate`

```elixir
@spec validate(ExDatalog.Program.t()) ::
  {:ok, ExDatalog.Program.t()} | {:error, [ExDatalog.Validator.Error.t()]}
```

Validates a program, returning structural and semantic errors.

Returns `{:ok, program}` if valid, `{:error, errors}` otherwise.
`errors` is a list of `ExDatalog.Validator.Error.t()`.

Structural checks (Phase 1):
- Relation references exist.
- Arities match declared schemas.
- Terms are valid.

Semantic checks (Phase 2):
- Variable safety and range restriction.
- Constraint binding and ordering.
- Stratified negation.

## Examples

     iex> alias ExDatalog.Program
     iex> program = Program.new() |> Program.add_relation("edge", [:atom, :atom])
     iex> {:ok, validated} = ExDatalog.validate(program)
     iex> is_struct(validated, ExDatalog.Program)
     true

---

*Consult [api-reference.md](api-reference.md) for complete listing*