ExDatalog.MagicSets (ExDatalog v0.5.0)

Copy Markdown View Source

Magic-sets program transformation for demand-driven (goal-directed) evaluation.

Magic sets rewrites a program so that bottom-up semi-naive evaluation computes only the facts relevant to a query goal, instead of the full least fixpoint. It is a program transformation: the engine is unchanged. Given a goal {relation, pattern}, the transformation:

  1. computes the goal's adornment (which argument positions are bound),
  2. generates magic_<relation>_<adornment> predicates capturing demand,
  3. rewrites recursive rules to consume the magic predicates,
  4. seeds the magic predicate with the bound goal constants.

The transformed IR is then evaluated by the existing semi-naive engine.

Scope (v0.5.0, experimental)

  • Positive recursive programs only.
  • A single goal.
  • Ground (constant) bound positions.

Programs outside this scope fall back to full semi-naive evaluation ({:fallback, reason}), never producing incorrect results.

Summary

Functions

transform(ir, arg)

Transforms an IR program for goal-directed evaluation.

Functions

transform(ir, arg)

@spec transform(
  ExDatalog.IR.t(),
  {String.t(), [term()]}
) :: {:ok, ExDatalog.IR.t()} | {:fallback, term()}

Transforms an IR program for goal-directed evaluation.

Returns {:ok, transformed_ir} when the magic-sets transformation applies, or {:fallback, reason} when the program is outside the supported scope (the caller should evaluate the original IR with semi-naive instead).