[YeGoblynQueenne]

>> The author might do better to think in terms of "what burning problem are we trying to fix and how did we fix it".

I have no idea who first came up with the name "datalog", and what exactly was their motivation (I've looked, but couldn't find the original reference to datalog), but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions.

One half of the reason for that is Prolog's "compound terms" (known as functions, in First-Order Logic terminology) and the other half is Prolog's use of depth-first search for evaluation. Functions, along with logic variables, mean that a predicate's Herbrand base (its set of logical atoms) can be expanded forever: if f(x) is a term, f(f(x)) is a term, f(f(f(x))) is a term... and so on, ad infinitum. The depth-first search evaluation just gets stuck in left-recursions when the first body literal of a clause is a recursive literal: p(x):- p(x), q(x) loops forever, in Prolog with depth-first search.

Datalog is Prolog without functions other than constants, and it can be evaluated "bottom up", both of which overcome Prolog's semi-decidability (but eliminate its completeness).

But of course this is not a very clear motivation for its use as a database language, only its use as an alternative to Prolog.

More to the point, there are many datalog variants. Some that accept negation, some that do not, some that allow recursion, some that do not, and so on. There's a lot of information on different datalogs, seen from the point of view of database research in this free ebook on databases:

http://webdam.inria.fr/Alice/

See chapters 12 - 15.

And see these lecture notes for a more logic-programm-y discussion of fixpoint semantics of definite logic programs:

https://www.doc.ic.ac.uk/~mjs/teaching/KnowledgeRep491/Fixpo...

[falsissime]

> but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions.

Prolog's built-in search is not semidecidable. https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecid...

As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions.

[YeGoblynQueenne]

>> As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions.

Thanks, yes, I might be fudging terminology a bit.

Generally, when I talk about Prolog I mean definite programs (sets of definite clauses and Horn goals, the latter usually called "definite goals") under SLD-resolution. That's more or less what is usually meant by "pure" Prolog: definite programs, without not/1 implementing Negation-As-Failure, without the cut, and without side effects; and executed by giving an initial Horn goal as a "query". Entailment between definite clauses and satisfiability of definite programs is undecidable.

By "semi-decidable" I mean that an SLD-refutation proof will terminate if there is a branch of the proof that ends in □ and is of finite length. If such a branch does not exist, a proof will "loop" forever. That's regardless of whether the branch succeeds or fails, which is a bit of a fudge, but, in practice, there is no other way to decide the success or failure of a proof than to search all its branches.

Left-recursion is one way in which Prolog, with depth-first search, generates branches of infinite length, but you can get those with right-recursion also. There are restrictions of Prolog, like SLG-resolution (similar to DFS with iterative deepening) that don't loop on left-recursions but the general case remains undecidable.

Fortunately, there seem to be at least as many finite proofs as there are infinite ones, or in any case I have never encountered a Prolog program that looped inintially and that couldn't be rewritten to terminate, at least when called in the way it was meant to be called. And that's also a bit of a fudge.