Derivation tree explanation for Datalog query results.
When a query is executed with explain: true, the result includes provenance
data recording which rule derived each fact. This module reconstructs the
derivation tree from that provenance data.
A derivation tree node is either :base_fact (for EDB facts) or a
%Node{} struct containing the fact, the rule that derived it, and
child nodes for each body atom that contributed.
Provenance semantics
Provenance tracks one rule per derived fact. When multiple rules derive the same tuple, the last rule processed in the most recent iteration wins. This is an engine-internal ordering, not a canonical "first derivation". Users should treat provenance as "a rule that derived this fact", not "the rule that derived this fact".
Usage
{:ok, result} = ExDatalog.query(program, explain: true)
{:ok, tree} = ExDatalog.Explain.explain(result, "ancestor", {:alice, :carol})The tree shows how the fact was derived, recursively expanding each derived
body atom back to its own derivation. EDB facts terminate as :base_fact.
Summary
Functions
Returns the derivation tree for a specific fact in the result.
Types
@type derivation() :: :base_fact | ExDatalog.Explain.Node.t()
Functions
@spec explain(ExDatalog.Result.t(), String.t(), tuple()) :: {:ok, derivation()} | {:error, :no_provenance | :not_found}
Returns the derivation tree for a specific fact in the result.
Requires the result to have been produced with explain: true.
Returns {:error, :no_provenance} if provenance tracking was not enabled,
{:error, :not_found} if the fact is not in the result, or {:ok, tree}
with the derivation tree.
Examples
iex> alias ExDatalog.{Program, Rule, Atom, Term, Explain}
iex> program =
...> Program.new()
...> |> Program.add_relation("parent", [:atom, :atom])
...> |> Program.add_relation("ancestor", [:atom, :atom])
...> |> Program.add_fact("parent", [:alice, :bob])
...> |> Program.add_rule(
...> Rule.new(
...> Atom.new("ancestor", [Term.var("X"), Term.var("Y")]),
...> [{:positive, Atom.new("parent", [Term.var("X"), Term.var("Y")])}]
...> )
...> )
iex> {:ok, result} = ExDatalog.query(program, explain: true)
iex> {:ok, tree} = Explain.explain(result, "ancestor", {:alice, :bob})
iex> tree.rule_id
0