I’ve been using Prolog a bunch recently, and also embedded and extended MicroKanren in a project. Something I came to appreciate was that Prolog’s depth-first search, and Kanren’s lazy stream approach are good with memory even when generating/searching through infinite solutions. It is my understanding that Datalog, on the other hand, will iteratively expand a set of data. Isn’t this a problem?
"Iteratively expand a set of data"? I'm not sure what you mean here. I think you are probably talking about the "bottom up" evaluation strategy of datalog, right? That's where datalog is evaluated by a so-called TP-operator, which derives the set of all logical consequences a datalog program by calculating its least fixed point. That's the same as the Least Herbrand Model (LHM) of the program, or, in other words, the set of atoms entailed by the program (atoms in the logical sense, of atomic formulae, not in the Prolog sense of constants).
That's the same thing that Prolog does, calculate the LHM of a logic program, but the difference is that datalog programs have finite LHMs, because they don't have functions that can be self-instantiated for ever ( f(x), f(f(x)), f(f(f(x))), ... ) and the bottom-up evaluation, that goes from the "body" to the "head" of a clause, avoids infinite left-recursions.
Prolog, evaluated top-down (clauses are "picked apart" head-first) can get stuck in infinite left-recursions, so datalog's finiteness, and its decidability under TP, is a big gain in efficiency, as anyone who has had to kill a Prolog console session because of an infinite loop will know.
Also, it is not widely recognised but I am the author of the dumbest and most inefficient TP Operator implementation in existence. Obviously I hang my head in shame and will not link to my code. I understand however that there are optimisations that one can perform that make bottom-up execution efficient, and even quite fast. Unfortunately, I don't know what they are :P
Note that Prolog can also be evaluated without fear of left-recursions, by SLG-Resolution (a.k.a. "tabling", a.k.a. memoization) but there is still the danger of infinite right recursions. Prolog is semi-decidable, because it is Turing-complete. Datalog is decidable, sacrificing completeness for, well, efficiency.
So, in short, it's not a problem if you consider the alternative, but of course there are trade-offs, always. It's like growing old, vs. dying young.
(I hope all this is not completely irrelevant to your question).
