6 ms·
Introduction to Datalog
- fspeech 8y agoCan you specify symmetric and transitive closure in Datalog?
- brian_cloutier 8y agoTransitive closure is the first thing nearly every introduction to datalog (or Prolog, for that matter) will show you. All you had to do was click the link and scroll down: Edge("a", "b"). Edge("b", "c"). Path(x, y) :- Edge(x, y). Path(x, z) :- Path(x, y), Edge(y, z). Symmetric closure, assuming I'm understanding correctly, is also trivial: SymmetricEdge(Left, Right) :- Edge(Left, Right). SymmetricEdge(Left, Right) :- Edge(Right, Left).
- fspeech 8y agoI was wondering about termination. With finite ground facts that appears not to be an issue. Complexity is another matter.
- cfallin 8y agoRe: complexity, read up on "semi-naïve evaluation" for the usual execution strategy, which basically involves keeping lists of newly-added tuples in each iteration of the fixpoint loop and only processing deltas related to those new additions. This, combined with good index inference for each relation (predicate), so that e.g. the node-neighbor lookup is O(log |V|), should result in efficient execution...
- JadeNB 8y agoTermination is achieved in brian_cloutier's example (https://news.ycombinator.com/item?id=19423320 https://news.ycombinator.com/item?id=19423320) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.
- maweki 8y agoDatalog always terminates because there is no way to derive new atoms.
- brian_cloutier 8y agoYes, 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 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.
- maweki 8y agoDatalog does not have a search strategy per se. The general "strategy" (or definition) is the fixpoint of the T_p operator that derives all one-step-derivable facts from the facts and the rules. 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.
- YeGoblynQueenne 8y agoMy 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 might be wrong about this- corrections welcome).
- hombre_fatal 8y agoPretty cool deep-dive on Datalog. The interactive tutorials on http://www.learndatalogtoday.org 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 https://docs.datomic.com/on-prem/indexes.html) to make Datalog queries fast?
- nutjob2 8y agoIf you have a lot of facts then you need indexes, otherwise you're scanning a lot of irrelevant data, many times over.
- hombre_fatal 8y agoSure, was just curious where Datomic's EAV, AEV, AVE, VAE indexes fall between Datomic indexing impl detail and general Datalog indexing solution. Datalog is fascinating, but the blog post makes me curious about more concrete impl-related follow-up questions.
- slifin 8y agoThank you, bookmarking this for later
- radomir_cernoch 8y ago> The :- means if and only if, or iff. Is it really the case? Human("Socrates"). Animal("Turtle"). Mortal(x) :- Human(x). Mortal(x) :- Animal(x). Suppose :- means iff. Turtle is Mortal (lines 2+4, implication to the left). Because Turtle is Mortal, it must be a Human (line 3, implication to the right). Is it really valid according to Datalog semantics?
- x775 8y agoHi! Thank you for highlighting this. No, you and sdbrady who commented above are correct; the :- only means "if". I have edited accordingly and apologise for the misunderstanding!
- sdbrady 8y agoThanks 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.
- x775 8y agoHi Stephen. You are absolutely right, thank you for the feedback! I have edited accordingly.
- maweki 8y agoI always remind myself that it's not an if-and-only-if with this argument: since there could always be another rule that is satisfied to make that fact true, it can't be iff.
- YeGoblynQueenne 8y agoIndeed, ":-" is meant to represent the left-facing arrow of implication. In logic programming papers it is common to typeset it as an actual arrow, for example: p(X,Y) ← q(Y,X) etc.
- JoelMcCracken 8y agoCan 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.
- qeshi 8y agoCheck out Datahike aswell, if you are interested in a durable datalog database. https://github.com/replikativ/datahike https://github.com/replikativ/datahike
- JoelMcCracken 8y agoCool, ty! Seems similar to DataScript.
- stingraycharles 8y agoIt’s actually a port of Datascript — consider it a durable Datascript.
- x775 8y agoHi Joel. You can give http://www.dlvsystem.com/dlv/ http://www.dlvsystem.com/dlv/ a shot! Alternatively, if you prefer open-source solutions, check https://abcdatalog.seas.harvard.edu/ https://abcdatalog.seas.harvard.edu/. Due to a number of complications on my machine, I used DLV.
- JoelMcCracken 8y agoAh, I usually automatically pass on closed source solutions (hence my dislike for datomic). TY for the link to abcdatalog though!
- felixyz 8y agoIf you're interested in experimenting with Datalog rather than necessarily writing something for production, have a look at Datalog Educational System: http://des.sourceforge.net/ http://des.sourceforge.net/
- nmadden 8y agoGreat 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-gottlob.pdf http://www.lifl.fr/%7Ekuttler/elfe/biblio/datalog-overview-g...
- burakemir 8y agoNice 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)
- x775 8y agoThanks for your feedback! For those interested in the mentioned paper, see: https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-paper.pdf https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-p...
- ComNik 8y agoIf model-theoretic semantics and the various ways to slice, dice, and extend Datalog are interesting to you, then almost any talk by Peter Alvaro might be as well. In particular: https://www.youtube.com/watch?v=R2Aa4PivG0g https://www.youtube.com/watch?v=R2Aa4PivG0g
- bobjordan 8y agoSharing an interesting implementation in python which I stumbled upon yesterday. Repo: https://github.com/pcarbonn/pyDatalog https://github.com/pcarbonn/pyDatalog Tutorial: https://sites.google.com/site/pydatalog/Online-datalog-tutorial https://sites.google.com/site/pydatalog/Online-datalog-tutor...