ExDatalog.Knowledge (ExDatalog v0.4.0)

Copy Markdown View Source

The complete knowledge base produced by Datalog evaluation.

Contains the derived fact sets for every relation, along with evaluation statistics (iteration count, duration, relation sizes, termination reason).

The name reflects what this struct is: after applying all rules to all facts until no new facts can be derived, you have a knowledge base — every relation fully materialised, every derivable fact present. You then query this knowledge with get/2 and match/3.

When provenance tracking is enabled (via explain: true), the provenance field records which rule derived each fact. Base facts (EDB) are attributed as :base. This field is nil when provenance tracking is disabled, ensuring zero overhead for the common case.

Termination

The stats.termination field indicates how evaluation ended:

  • :fixpoint — all derivable facts were computed; the knowledge base is complete.
  • :iteration_limit — evaluation stopped because max_iterations was reached; the knowledge base may be incomplete.
  • :timeout — evaluation stopped because timeout_ms elapsed; the knowledge base may be incomplete.

Callers must check stats.termination to distinguish a complete result from a truncated one. Returning {:ok, knowledge} does not guarantee the fixpoint was reached.

Access functions

  • get/2 — all tuples for a relation.
  • match/3 — tuples matching a pattern (:_ for wildcard).
  • size/2 — number of tuples in a relation.
  • relations/1 — list of all relation names in the knowledge base.

Summary

Types

provenance()
stats()
t()
termination()

Functions

get(knowledge, relation)

Returns all tuples for a relation as a MapSet.

match(knowledge, relation, pattern)

Returns tuples matching a pattern.

relations(knowledge)

Returns all relation names present in the knowledge base.

size(knowledge, relation)

Returns the number of tuples in a relation.

Types

provenance()

@type provenance() :: %{
  fact_origins: %{
    required(String.t()) => %{required(tuple()) => non_neg_integer() | :base}
  },
  rules: %{required(non_neg_integer()) => ExDatalog.IR.Rule.t()}
}

stats()

@type stats() :: %{
  iterations: non_neg_integer(),
  duration_us: non_neg_integer(),
  relation_sizes: %{required(String.t()) => non_neg_integer()},
  capabilities: ExDatalog.Capabilities.t(),
  termination: termination()
}

t()

@type t() :: %ExDatalog.Knowledge{
  provenance: provenance() | nil,
  relations: %{required(String.t()) => MapSet.t(tuple())},
  stats: stats()
}

termination()

@type termination() :: :fixpoint | :iteration_limit | :timeout

Functions

get(knowledge, relation)

@spec get(t(), String.t()) :: MapSet.t(tuple())

Returns all tuples for a relation as a MapSet.

Examples

iex> knowledge = %ExDatalog.Knowledge{relations: %{"parent" => MapSet.new([{:alice, :bob}])}, stats: %{iterations: 1, duration_us: 0, relation_sizes: %{"parent" => 1}}}
iex> ExDatalog.Knowledge.get(knowledge, "parent") |> MapSet.to_list()
[{:alice, :bob}]

match(knowledge, relation, pattern)

@spec match(t(), String.t(), [term()]) :: MapSet.t(tuple())

Returns tuples matching a pattern.

The pattern is a list where :_ matches any value and other values match exactly. Useful for querying specific facts.

Examples

iex> knowledge = %ExDatalog.Knowledge{relations: %{"parent" => MapSet.new([{:alice, :bob}, {:carol, :dave}, {:alice, :carol}])}, stats: %{iterations: 1, duration_us: 0, relation_sizes: %{"parent" => 3}}}
iex> ExDatalog.Knowledge.match(knowledge, "parent", [:alice, :_]) |> MapSet.to_list() |> Enum.sort()
[{:alice, :bob}, {:alice, :carol}]

relations(knowledge)

@spec relations(t()) :: [String.t()]

Returns all relation names present in the knowledge base.

Examples

iex> knowledge = %ExDatalog.Knowledge{relations: %{"parent" => MapSet.new(), "ancestor" => MapSet.new()}, stats: %{iterations: 1, duration_us: 0, relation_sizes: %{}}}
iex> Enum.sort(ExDatalog.Knowledge.relations(knowledge))
["ancestor", "parent"]

size(knowledge, relation)

@spec size(t(), String.t()) :: non_neg_integer()

Returns the number of tuples in a relation.

Examples

iex> knowledge = %ExDatalog.Knowledge{relations: %{"parent" => MapSet.new([{:alice, :bob}, {:carol, :dave}])}, stats: %{iterations: 1, duration_us: 0, relation_sizes: %{"parent" => 2}}}
iex> ExDatalog.Knowledge.size(knowledge, "parent")
2