Did you find anything other that was very wrong in my comment?
I'm not sure about the statement that "Datalog is evaluated from the "bottom up". [...] datalog will first generate the set of all ground atoms that are consequences of the program in the context of which the query was made, then determine whether the atoms in the query are in the set of consequences of the program". I think it's true that Datalog behaves as if it were evaluated like this, but AFAIK Datalog systems can do lots of very aggressive optimizations that change the actual evaluation. I'm not an expert on Datalog.
Anyway, I was mostly dissatisfied with the general thrust of the comment, trying to establish a "subset" relationship. I think the article's "cousins" comment is fair. Prolog is older and influenced Datalog very much. Prolog is also Turing complete, so it is strictly more powerful. But Datalog's semantics allow some optimizations that wouldn't be possible in Prolog, so it can be a lot faster on appropriate classes of problems.
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.
So I have to ask: where does this information come from?
Half-remembered university courses from >= 10 years ago, I'm afraid. I now think I was probably thinking of ASP, not Datalog. See for example the "Disjunctive logic programs" section of https://www.cs.uni-potsdam.de/~torsten/Lehre/ASP/Folien/asp-.... Since the syntax is very Prolog/Datalog-like, I probably got mixed up. My bad, sorry. The first few sources on Datalog I looked at only talked about Horn clauses, not ones with more heads.
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.
Ah, phew, OK. I was really confused by that. No worries, I'm still grateful for your comments :)
Yes, ASP is not Horn so it has rules with multiple literals in the head. "Choice rules", writen as {s,t}:- p. Also, like you say, I believe it doesn't suffer from Prolog's non-termination, again because unlike Prolog it's not Turing-complete. But in any case ASP is based on stable model semantics, not fixpoint semantics.
However I'm really very far from being anything like an expert in ASP! I really should learn a bit of it because it's actually necessary in my research.
Comments
I'm not sure about the statement that "Datalog is evaluated from the "bottom up". [...] datalog will first generate the set of all ground atoms that are consequences of the program in the context of which the query was made, then determine whether the atoms in the query are in the set of consequences of the program". I think it's true that Datalog behaves as if it were evaluated like this, but AFAIK Datalog systems can do lots of very aggressive optimizations that change the actual evaluation. I'm not an expert on Datalog.
Anyway, I was mostly dissatisfied with the general thrust of the comment, trying to establish a "subset" relationship. I think the article's "cousins" comment is fair. Prolog is older and influenced Datalog very much. Prolog is also Turing complete, so it is strictly more powerful. But Datalog's semantics allow some optimizations that wouldn't be possible in Prolog, so it can be a lot faster on appropriate classes of problems.
Thanks for this additional comment.
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.
Half-remembered university courses from >= 10 years ago, I'm afraid. I now think I was probably thinking of ASP, not Datalog. See for example the "Disjunctive logic programs" section of https://www.cs.uni-potsdam.de/~torsten/Lehre/ASP/Folien/asp-.... Since the syntax is very Prolog/Datalog-like, I probably got mixed up. My bad, sorry. The first few sources on Datalog I looked at only talked about Horn clauses, not ones with more heads.
Skimming https://en.wikipedia.org/wiki/Answer_set_programming and https://en.wikipedia.org/wiki/Stable_model_semantics I get the impression that even disjunctive logic programs appear to always terminate, though the complexity might be daunting.
Ah, phew, OK. I was really confused by that. No worries, I'm still grateful for your comments :)
Yes, ASP is not Horn so it has rules with multiple literals in the head. "Choice rules", writen as {s,t}:- p. Also, like you say, I believe it doesn't suffer from Prolog's non-termination, again because unlike Prolog it's not Turing-complete. But in any case ASP is based on stable model semantics, not fixpoint semantics.
However I'm really very far from being anything like an expert in ASP! I really should learn a bit of it because it's actually necessary in my research.