21–30 of 40 posts
Earlier quoted context omitted.
I was wondering about termination. With finite ground facts that appears not to be an issue. Complexity is another matter.
Termination is achieved in brian_cloutier's example ( https://news.ycombinator.com/item?id=19423320 ) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.
Nice post. Still, I find the most accessible article describing datalog is "What you Always Wanted to Know About Datalog (And Never Dared to Ask)." by Ceri, Gottlob, Tanca (1989)
For those interested in the mentioned paper, see: https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-p...
Earlier quoted context omitted.
Termination is achieved in brian_cloutier's example ( https://news.ycombinator.com/item?id=19423320 ) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.
Datalog always terminates because there is no way to derive new atoms.
It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate.
EDIT: Thinking about this more, I'm not sure why Prolog couldn't also use breadth-first search. So maybe both are necessary: Datalog not only disallows creating new atoms, but it also has a better search strategy; the combination of the two results in guaranteed termination.
Thanks for sharing. There is one very significant conceptual error early on, however, and it is captured first in this statement: "The :- means if and only if, or iff". `:-` means if - or more precisely represents material conditional - where the consequent is on the left and the antecedent is on the right. iff is logical biconditional.
p(X,Y) ← q(Y,X)
Earlier quoted context omitted.
Termination is achieved in brian_cloutier's example ( https://news.ycombinator.com/item?id=19423320 ) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.
Datalog always terminates because there is no way to derive new atoms.
P(f(x)).
p(f(f(x)).
p(f(f(f(x)))).
... etc
(but I might be wrong about this- corrections welcome).
Can anyone recommend any implementation of Datalog (+ negation) that is not datomic? I haven't tried datascript, which appears to support negation. Maybe I will try that if/when I revisit this interest someday.
Earlier quoted context omitted.
Datalog always terminates because there is no way to derive new atoms.
Yes, but there's more to it than just that. It's possible to write Prolog programs which never derive new atoms yet still fail to terminate. It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate. EDIT: Thinking about this more, I'm not sure why Prolog couldn't also use breadth-first search. So maybe…
The minimal model (result of derivation) is defined as the fixpoint of this operation. And the minimal model is finite because of the fixed number of atoms.
Every other evaluation strategy must be equivalent to this. Both in terms of termination and minimal model.
Prolog could use breadth first instead of SLD (and there are other Prolog evaluation strategies that, for example, use tabling for derived facts) but then you might get an infinite number of backtracking points instead of terms of infinite depth. You haven't really won anything by doing that.
Earlier quoted context omitted.
Datalog always terminates because there is no way to derive new atoms.
My understanding is that Datalog terminates because it does not allow functions as arguments to predicates. No functions means it's not possible to create infinite terms: P(f(x)). p(f(f(x)). p(f(f(f(x)))). ... etc In fact I understand that termination is guaranteed even if a datalog program is executed by a Prolog interpreter. Or in other words, it's a result of the language semantics, not its implementation. (but I…
p(X) :- p(X). does usually not terminate in a top-down (Prolog) system but does in a bottom-up (Datalog) system. Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size. But also this isn't allowed (where it is in Prolog)
p(X) :- p(Y), X is Y + 1.
Given a fact p(0) you get p(X) true for any integer X or generate all positive integers. This doesn't terminate for some binding patterns.