31–40 of 40 posts
Great post! Still working through it, but there is a slight error in the nested diagram at the start. Relational algebra has set difference, which is akin to negation-as-failure, but it lacks recursion. So the positive Datalog and RA circles should overlap without either containing the other. See http://www.lifl.fr/%7Ekuttler/elfe/biblio/datalog-overview-g...
In particular: https://www.youtube.com/watch?v=R2Aa4PivG0g
Earlier quoted context omitted.
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…
You are wrong. 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…
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.
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…
You are wrong. 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…
is/2 is not Datalog though- it takes an arithmetic function as an argument; +/2 in your example. So the above would not terminate because it's Prolog, not because it's a Datalog program evaluated by Prolog.
>> Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size.
Usual confusion: I think you mean "terms" as in Prolog terms, i.e. atoms of predicates (as opposed to terms in logic programming, i.e. variables, constants and functions). Datalog accepts constants and variables so with a finite vocabulary you can't create infinite atoms. I don't think that has to do with bottom-up or top-down evaluation.
To be honest, I haven't read any Datalog papers, but I'd be surprised if the termination guaranteed rested upon a specific implementation rather than the language semantics. Maybe not surprised- but it would be less interersting if you can only guarantee termination if you implement the language just so, vs. if it's a property of the language.
Earlier quoted context omitted.
You are wrong. 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…
>> p(X) :- p(Y), X is Y + 1. is/2 is not Datalog though- it takes an arithmetic function as an argument; +/2 in your example. So the above would not terminate because it's Prolog, not because it's a Datalog program evaluated by Prolog. >> Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size. Usual confusion: I think you mean "terms" as in Prolog terms, i.e. at…
So the "biggest" model is only as large as any atom in any position for any predicate and that is always finite for a finite number of sorts or predicates.
Is gave is/2 as an example of how Prologo allows you to generate new atoms/terms that have not been facts before.
Earlier quoted context omitted.
>> p(X) :- p(Y), X is Y + 1. is/2 is not Datalog though- it takes an arithmetic function as an argument; +/2 in your example. So the above would not terminate because it's Prolog, not because it's a Datalog program evaluated by Prolog. >> Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size. Usual confusion: I think you mean "terms" as in Prolog terms, i.e. at…
The minimal herbrandt model does not have new atoms. Besides what is given in the rules and the starting facts (empty for least fix point). So the "biggest" model is only as large as any atom in any position for any predicate and that is always finite for a finite number of sorts or predicates. Is gave is/2 as an example of how Prologo allows you to generate new atoms/terms that have not been facts before.
Pretty cool deep-dive on Datalog. The interactive tutorials on http://www.learndatalogtoday.org (Datomic's dialect) quickly sold me on the idea. Though coming from Datomic, I'm curious how much of my knowledge is Datomic-specific rather than how you'd generally approach a database queryable with Datalog. For example, do you need four indexes like Datomic ( https://docs.datomic.com/on-prem/indexes.html ) to make Datal…
If you have a lot of facts then you need indexes, otherwise you're scanning a lot of irrelevant data, many times over.
Datalog is fascinating, but the blog post makes me curious about more concrete impl-related follow-up questions.
Great post! Still working through it, but there is a slight error in the nested diagram at the start. Relational algebra has set difference, which is akin to negation-as-failure, but it lacks recursion. So the positive Datalog and RA circles should overlap without either containing the other. See http://www.lifl.fr/%7Ekuttler/elfe/biblio/datalog-overview-g...
Hi there. Thanks so much for your feedback, and good catch! I will update the diagram accordingly.