I thought more of your earlier comment about how "p,q:- r" is Datalog. I accepted this because I figured you know what you're talking about but, to be honest, I don't know what you're talking about. My understanding is that without definite clauses (and "p,q:-r" is not definite) there are no fixpoint semantics and without fixpoint semantics there is no guarantee of program termination.

So I have to ask: where does this information come from? Could you point me to a source? To be honest, I suspect that I am confused because of a lack of an ISO standard for Datalog. Even Prolog, with an ISO standard, has various extensions like, if memory serves, B-Prolog (which includes OOP elements). If Datalog has no commonly recognised standard, then basically anything can be called "Datalog" as long as someone, somewhere, can recognise it as Datalog. Is that the case here? If so, that would clear my confusion.

It would also make more sense for me to say that "Datalog is a subset of Prolog", at least in terms of syntax. In that case I'd have to clarify that I'm talking aout a simple, commonly accepted language fragment of definite clauses with at most one function symbol, which I think everyone would readily recognise as "Datalog" without much fuss.

I confess that the extent of my knowledge about Datalog comes from conversations with (senior) colleagues and not directly from original sources. Of course, original sources go way, way back (but obviously not as back as original Prolog sources and I'm familiar with those, so that's not a complete excuse). In any case, I had a look at, e.g. "What you always wanted to know about Datalog (and never dared to ask)" by Geri, Gotlob and Tanca (also in the bibliography section of the wikipedia article on databases).

The article, which is from 1989 and clearly addressed at the databases community (rather than the logic progamming, or AI community) states that Datalog is "in many respects a simplified version of general Logic Programming", referencing J. W. Lloyd for the latter. Since it's 1989, "Logic Programming" clearly means Prolog (given that it's too early for, e.g. ASP).

Further, the article makes it explicity that "In the formalism of Datalog both facts and rules are represented as Horn clauses of the general shape ..." and gives an example of a definite program clause. Later, the article states "From the syntactic point of view, Datalog is a subset of Prolog" (but then goes on to point out the difference in semantics).

Finally, the article does agree with you that is is possible to evaluate Datalog programs in a "top-down" fashion, using the query-subquery algorithm which is, from what I can tell, backwards chaining implemented by breadth-first search. So the semantics of Datalog can be different than Prolog's. My mistake I think is in equating the use of a TP operator (which is "bottom-up") to Datalog execution, always.