Evaluators

An evaluator answers a query over a Base. The architecture section explains how. jaala has two, and three ways to run them, which all give the same answer and differ in how much work they do getting there.

• SemiNaive{} is the one you’ll want. In each round of a recursive fixpoint it only revisits what the last round added. It derives only what a query’s constants ask for (magic sets), and it plans each rule body so the order a rule is written in doesn’t change what it costs.
• SemiNaive{WrittenOrder: true} keeps the semi-naive fixpoint and turns the rewrites off, running each body in the order it’s written.
• Naive{} repeats every rule until a round adds nothing, in written order. It’s slow on purpose and fairly simple to trust, so it’s the reference every faster strategy is checked against.

package reference_test

import (
	"context"
	"fmt"
	"reflect"

	"github.com/panyam/jaala/datalog"
	"github.com/panyam/jaala/ns"
)

// The three ways to evaluate a query answer it the same way. They differ
// in the work they do: Naive repeats every rule each round, SemiNaive in
// written order only revisits what changed, and the planned SemiNaive also
// derives only what the query's constants ask for and plans each body.
func Example_evaluators() {
	src := ns.NewMemSource().Declare("imports", "from", "to")
	for i := 0; i < 30; i++ {
		src.Add("imports", ns.Tuple{Vals: []ns.Value{
			ns.S(fmt.Sprintf("p%02d", i)), ns.S(fmt.Sprintf("p%02d", i+1)),
		}})
	}
	v, err := ns.NewVocabulary(src)
	if err != nil {
		fmt.Println(err)
		return
	}
	q := datalog.MustParse(`
		depends_on(?a, ?b) :- imports(?a, ?b);
		depends_on(?a, ?c) :- depends_on(?a, ?b), imports(?b, ?c);
		depends_on("p25", ?d) => ?d`)

	var answers [][]datalog.Row
	var work []int64
	for _, ev := range []datalog.Evaluator{
		datalog.Naive{},
		datalog.SemiNaive{WrittenOrder: true},
		datalog.SemiNaive{},
	} {
		b, _ := datalog.NewBase(v, src)
		rows, err := ev.Eval(context.Background(), q, b)
		if err != nil {
			fmt.Println(err)
			return
		}
		answers = append(answers, rows)
		work = append(work, b.Work())
	}
	fmt.Println(len(answers[0]), "rows from each")
	fmt.Println("same answers:", reflect.DeepEqual(answers[0], answers[1]) &&
		reflect.DeepEqual(answers[1], answers[2]))
	fmt.Println("less work each step:", work[0] > work[1] && work[1] > work[2])
	// Output:
	// 5 rows from each
	// same answers: true
	// less work each step: true
}

What’s guaranteed ¶

• The same rows, in the same order. All three answer every query with the same rows, sorted the same way, which jaala’s own tests check on every change, against its hand-written programs and a few hundred generated ones, and selfcheck.sh against thousands more.
• The same errors from the written order. SemiNaive{WrittenOrder: true} fails exactly when Naive does, with the same message. The planned SemiNaive{} gives Naive’s error whenever it fails, and can succeed where written order stops (a body written in an order that can’t run as written, which planning fixes).
• Citations from one derivation. A row cites the facts of the derivation that found it first. When a fact is reachable two ways, the evaluators can find different ones first, so two evaluators can cite different, equally valid evidence for the same row. CanonicalCites() makes all three cite the same one, each row’s shortest derivation (#22, see provenance).
• Bounded by Budget. Each counts its work the same way on every run, so a budget that passes once passes every time, for that evaluator.