3 ms·

Sorry, but you are also fudging things. > Datalogs (there are many variants!) are subsets of Prolog. No. First of all, this is not true syntactically. There a

Sorry, but you are also fudging things. > Datalogs (there are many variants!) are subsets of Prolog. No. First of all, this is not true syntactically. There are Datalogs that allow non-Horn clauses with several terms in a goal head: a, b :- c. This is not allowed in Prolog. So (such) Datalogs are not subsets of Prolog syntactically. Second, it is not true semantically either, not even for the common syntactic subset. Consider: ancestor_of(Parent, Child) :- child_of(Child, Parent). ancestor_of(Ancestor, Person) :- ancestor_of(Ancestor, Parent), child_of(Person, Parent). This is left-recursive, so typical queries will not terminate in Prolog, i.e., have no finite solutions. But as you say, Datalogs are decidable and any query terminates, so you will get solutions, which is different semantics from Prolog. So it's not meaningful to say that Datalog is a semantic subset of Prolog. Datalog and Prolog are like C++ and Java: One is an extension of a subset of the other, or equivalently, there is a non-empty common subset with similar-ish semantics. This is not a very useful statement? I agree! But it is what it is. They are different languages.

YeGoblynQueenne 6y ago
Yes, you're right and I'm also fudging things- but didn't I say that upfront? I start my comment by announcing an "almost not completely fudgy intro to logic programming"! More seriously, you're right about syntax so thanks for the correction. But, regarding semantics, the ancestor_of/2 program above can terminate in Prolog, evaluated by SLG resolution, as per my footnote 5. There are still situations where Prolog will not terminate when evaluating a normal program even under SLG resolution, but left recursion is not one of those. Edit: also, if a Datalog program is also Prolog, and assuming that the program terminates under Prolog, then Prolog and Datalog will both compute its LHM. So it makes sense to say that the two languages are semantically at least very similar and to explain one in terms of the other. They are both much closer than what each is to ASP, for example. It really depends on what assumptions one makes- and that's where the "fudging" comes in. Anyway, thanks for the correction. I sure could have done a better job of that comment. Did you find anything other that was very wrong in my comment? I'd appreciate it if you pointed it out.
- tom_mellior 6y ago
  > 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.
  - YeGoblynQueenne 6y ago
    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.

YeGoblynQueenne 6y ago

Yes, you're right and I'm also fudging things- but didn't I say that upfront? I start my comment by announcing an "almost not completely fudgy intro to logic programming"! More seriously, you're right about syntax so thanks for the correction. But, regarding semantics, the ancestor_of/2 program above can terminate in Prolog, evaluated by SLG resolution, as per my footnote 5. There are still situations where Prolog will not terminate when evaluating a normal program even under SLG resolution, but left recursion is not one of those. Edit: also, if a Datalog program is also Prolog, and assuming that the program terminates under Prolog, then Prolog and Datalog will both compute its LHM. So it makes sense to say that the two languages are semantically at least very similar and to explain one in terms of the other. They are both much closer than what each is to ASP, for example. It really depends on what assumptions one makes- and that's where the "fudging" comes in. Anyway, thanks for the correction. I sure could have done a better job of that comment. Did you find anything other that was very wrong in my comment? I'd appreciate it if you pointed it out.

tom_mellior 6y ago
> 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.
- YeGoblynQueenne 6y ago
  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.