> [Datalog] is a subset of Prolog that lacks recursion

Datalog does allow for recursion — a common example is graph reachability:

reachable(a, b) :- edge(a, b). reachable(a, c) :- edge(a, b), reachable(b, c).

(Evan mentioned implementing kCFA, which would require recursion like this...)

'Base datalog' guarantees termination by requiring all input relations to be finite. Notably this means that it doesn't have numerical operations like addition or multiplication, since `plus(a, b)` or `times(a, b)` would be infinite relations.

More practical Datalog engines like Souffle (https://souffle-lang.github.io/) have numerical operations but don't guarantee termination.

Recursive queries are not needed by most applications, but maybe Acadia could allow them (compiling to recursive CTEs) by proving that recursion only goes through finite relations.