Datalog Rules

[hraberg]

Recursion and traversal can only be expressed using rules in Datalog, so we need support for this.

[hraberg]

It would be possible to reach MVP without this, but would prefer not to.

[hraberg]

Simple example lifted from Racket, https://github.com/racket/datalog/tree/master/tests/examples

     parent(john,douglas).
     parent(john,douglas)?
     % parent(john, douglas).

     parent(john,ebbon)?

     parent(bob,john).
     parent(ebbon,bob).
     parent(A,B)?
     % parent(john, douglas).
     % parent(bob, john).
     % parent(ebbon, bob).

     parent(john,B)?
     % parent(john, douglas).

     parent(A,A)?

     ancestor(A,B) :- parent(A,B).
     ancestor(A,B) :- parent(A,C), ancestor(C, B).
     ancestor(A, B)?
     % ancestor(ebbon, bob).
     % ancestor(bob, john).
     % ancestor(john, douglas).
     % ancestor(bob, douglas).
     % ancestor(ebbon, john).
     % ancestor(ebbon, douglas).

In Datomic style the rule would look something like this:

[[(ancestor ?person ?ancestor)
  [?person :person/parent ?ancestor]]
 [(ancestor ?person ?ancestor)
  [?person :person/parent ?parent]
  (ancestor ?parent ?ancestor)]]

Note that in Datalog the rules are often proactive and may fire and populate the database.
In Datomic they're always part of expanding a current query, and the intermediate facts aren't asserted into the system.

This border towards rule engines and derived facts and state is an interesting, and might be something we want to explore lately. It's somewhat related to subscriptions, see #26.

[hraberg]

The simplest way to implement rules is via sub queries, where certain variables are already bound at the point of calling the query. This sub query can itself potentially be represented as a n-ary-join participating in the parent query, where certain variables are bound "to the left" of the query execution, and others "to the right" will be bound by the sub query.

A rule with multiple bodies can be represented as an n-ary or, but this might not be the simplest thing in practice.

How to make the rules participate in the parent join is related to how arguments ends up working, see #1978.

[hraberg]

Implemented a basic Query-Sub-Query approach to rules, with free/bound adornment, using both expansion of rules (treating them as templates) and caches to avoid stack overflow. Passes datascript's rule tests (including mutual recursion), but can imagine many issues. But closing this for now.

Rules are implemented as or-join, as is or and of course or-join, all result in sub-queries being executed for each result (roughly) in the parent query.