4 ms·

Declaring Reality: An Introduction to Datalog

60 points by sacheendra 11y ago

pmoriarty 11y ago
How does Datalog compare to Prolog?
- richard_todd 11y ago
  Datalog is a subset of prolog, which is not Turing complete. But, by giving up the ability to compute anything, you get a fully declarative language (the order of clauses doesn't matter) whose computations always terminate. In contrast, when programming in prolog you are often thinking about the operational aspects of the underlying engine in order to get more efficiency. You try to order clauses advantageously and introduce extra-logical commands like "cuts" to guide the engine, so prolog code often looks more declarative on the surface than it is in reality. As a result, I've heard Datalog referred to as "the good parts of Prolog," and I suppose that for problems it can handle I do like that Datalog has fewer pragmatic compromises to its purity.
  - ScottBurson 11y ago
    > Datalog is a subset of prolog, which is not Turing-complete. I wouldn't normally object to a misplaced comma on HN, but in this case it is potentially very confusing. This sentence as written says that Prolog is not Turing complete, but actually it is; it's Datalog that is not Turing-complete. (I'm sure that was the intent.)
    - richard_todd 11y ago
      Absolutely: Datalog is the one that is not Turing-complete. Thanks for pointing this out. I typed it on my phone and should have proofread it better. I'd remove the comma, but I think HN doesn't let me edit a post after a timeout.
analognoise 11y ago
I might be strange in this, but I dislike languages without a canonical implementation; is there a canonical implementation of Datalog?
- wtetzner 11y ago
  I'm not sure it makes a lot of sense for there to be a canonical implementation of Datalog. It's kind of like asking if there's a canonical implementation of SQL.
- handojin 11y ago
  No.
- j-pb 11y ago
  Datalog is a mathematical construct. It doesn't make sense to expect a canonical implementation, just like it doesn't make sense for Lambda-Calculus. Datalog has well defined semantics and can actually be formalised through different means, which are proven to be equivalent. * Model theoretic (logical) * Fixpoint (imperative) * Proof theoretic (functional)
brudgers 11y ago
Worth mentioning? Racket ships with #lang racklog a scheme based datalog like language: http://docs.racket-lang.org/datalog/index.html http://docs.racket-lang.org/datalog/index.html Also Prolog like logic languages Parenlog http://docs.racket-lang.org/parenlog/index.html http://docs.racket-lang.org/parenlog/index.html and the more fully fleshed out Racklog http://docs.racket-lang.org/racklog/index.html http://docs.racket-lang.org/racklog/index.html The nice thing about the Racket versions is that installation is easy because the Racket ecosystem doesn't have external dependencies for the installer --- other than a supported operating system: Unix, Linux, OSX or Windows. https://download.racket-lang.org/ https://download.racket-lang.org/ The downside of course is there's a gap between the traditional documentation for Datalog and the Racket syntax and perhaps consultants with technical expertise for running large scale implementations.
fizixer 11y ago
Any comparisons with: - minikanren - constraint logic prog - constraint solving - inductive logic ?
- YeGoblynQueenne 11y ago
  Constraint logic programming is logic programming extended with constraints, and a constraint solver is an engine for checking and resolving such constraints. I guess that's not very useful if you don't know what constraints are but a full explanation can get very involved very quickly, so check out the wikipedia page for a brief (ish) intro. From personal experience, if you're used to programming in a logic programming language, trying CLP out is like being in declarative heaven. Swi Prolog, as I think all the full Prolog implementations, has a few CLP libraries, frex see: http://www.swi-prolog.org/pldoc/man?section=summary-lib-clp-clpfd http://www.swi-prolog.org/pldoc/man?section=summary-lib-clp-... Minikanren is a relational language that's introduced in the Reasoned Schemer as an example of a relational language. I don't think it's fully a logic programming language (ie, no theorem proving) but I might be wrong. Check out the book for more. Inductive Logic Programming is a machine learning technique for learning Prolog programs from data. More to the point, you declare knowledge about the world as positive and negative examples given as Prolog unit clauses (facts). An inductive Logic Programming algorithm then will learn a full Prolog program for you, including definite clauses (rules). A typical example of ILP is FOIL by Quinlan (the Decision Trees guy) [http://www.rulequest.com/Personal/ http://www.rulequest.com/Personal/]. ILP is closely er, related to Relational Learning a.k.a. Statistical and Relational Learning and a number of probabilistic logic programming languages like Problog (no typo). You can find a lot of information about ILP in the textbook Logical and Relational Learning by Luc de Raedt [http://www.springer.com/us/book/9783540200406 http://www.springer.com/us/book/9783540200406], which I recommend (not related to the author) (but I am a logic programming looney so).
juliangamble 11y ago
Rich Hickey's (of Clojure fame) Datomic database uses Datalog as its query language. http://docs.datomic.com/query.html http://docs.datomic.com/query.html http://blog.datomic.com/2015/01/datalog-enhancements.html http://blog.datomic.com/2015/01/datalog-enhancements.html Nathan Marz's (of Twitter startup fame) Cascalog library (also implemented in Clojure) uses Datalog as its query engine to generate Hadoop jobs. http://alexrobbins.github.io/cascalog-intro/#/step-14 http://alexrobbins.github.io/cascalog-intro/#/step-14 http://clojure.com/blog/2012/02/03/functional-relational-programming-with-cascalog.html http://clojure.com/blog/2012/02/03/functional-relational-pro...
- j-pb 11y ago
  Cascalog isn't proper datalog. It's a non-recursive fragment that allows for negation and outer joins, so semantically it's much closer to SQL, albeit with a much nicer syntax.

60 points by sacheendra 11y ago

pmoriarty 11y ago

How does Datalog compare to Prolog?

richard_todd 11y ago
Datalog is a subset of prolog, which is not Turing complete. But, by giving up the ability to compute anything, you get a fully declarative language (the order of clauses doesn't matter) whose computations always terminate. In contrast, when programming in prolog you are often thinking about the operational aspects of the underlying engine in order to get more efficiency. You try to order clauses advantageously and introduce extra-logical commands like "cuts" to guide the engine, so prolog code often looks more declarative on the surface than it is in reality. As a result, I've heard Datalog referred to as "the good parts of Prolog," and I suppose that for problems it can handle I do like that Datalog has fewer pragmatic compromises to its purity.
- ScottBurson 11y ago
  > Datalog is a subset of prolog, which is not Turing-complete. I wouldn't normally object to a misplaced comma on HN, but in this case it is potentially very confusing. This sentence as written says that Prolog is not Turing complete, but actually it is; it's Datalog that is not Turing-complete. (I'm sure that was the intent.)
  - richard_todd 11y ago
    Absolutely: Datalog is the one that is not Turing-complete. Thanks for pointing this out. I typed it on my phone and should have proofread it better. I'd remove the comma, but I think HN doesn't let me edit a post after a timeout.

analognoise 11y ago

I might be strange in this, but I dislike languages without a canonical implementation; is there a canonical implementation of Datalog?

wtetzner 11y ago
I'm not sure it makes a lot of sense for there to be a canonical implementation of Datalog. It's kind of like asking if there's a canonical implementation of SQL.
handojin 11y ago
No.
j-pb 11y ago
Datalog is a mathematical construct. It doesn't make sense to expect a canonical implementation, just like it doesn't make sense for Lambda-Calculus. Datalog has well defined semantics and can actually be formalised through different means, which are proven to be equivalent. * Model theoretic (logical) * Fixpoint (imperative) * Proof theoretic (functional)

brudgers 11y ago

Worth mentioning? Racket ships with #lang racklog a scheme based datalog like language: http://docs.racket-lang.org/datalog/index.html http://docs.racket-lang.org/datalog/index.html Also Prolog like logic languages Parenlog http://docs.racket-lang.org/parenlog/index.html http://docs.racket-lang.org/parenlog/index.html and the more fully fleshed out Racklog http://docs.racket-lang.org/racklog/index.html http://docs.racket-lang.org/racklog/index.html The nice thing about the Racket versions is that installation is easy because the Racket ecosystem doesn't have external dependencies for the installer --- other than a supported operating system: Unix, Linux, OSX or Windows. https://download.racket-lang.org/ https://download.racket-lang.org/ The downside of course is there's a gap between the traditional documentation for Datalog and the Racket syntax and perhaps consultants with technical expertise for running large scale implementations.

fizixer 11y ago

Any comparisons with: - minikanren - constraint logic prog - constraint solving - inductive logic ?

YeGoblynQueenne 11y ago
Constraint logic programming is logic programming extended with constraints, and a constraint solver is an engine for checking and resolving such constraints. I guess that's not very useful if you don't know what constraints are but a full explanation can get very involved very quickly, so check out the wikipedia page for a brief (ish) intro. From personal experience, if you're used to programming in a logic programming language, trying CLP out is like being in declarative heaven. Swi Prolog, as I think all the full Prolog implementations, has a few CLP libraries, frex see: http://www.swi-prolog.org/pldoc/man?section=summary-lib-clp-clpfd http://www.swi-prolog.org/pldoc/man?section=summary-lib-clp-... Minikanren is a relational language that's introduced in the Reasoned Schemer as an example of a relational language. I don't think it's fully a logic programming language (ie, no theorem proving) but I might be wrong. Check out the book for more. Inductive Logic Programming is a machine learning technique for learning Prolog programs from data. More to the point, you declare knowledge about the world as positive and negative examples given as Prolog unit clauses (facts). An inductive Logic Programming algorithm then will learn a full Prolog program for you, including definite clauses (rules). A typical example of ILP is FOIL by Quinlan (the Decision Trees guy) [http://www.rulequest.com/Personal/ http://www.rulequest.com/Personal/]. ILP is closely er, related to Relational Learning a.k.a. Statistical and Relational Learning and a number of probabilistic logic programming languages like Problog (no typo). You can find a lot of information about ILP in the textbook Logical and Relational Learning by Luc de Raedt [http://www.springer.com/us/book/9783540200406 http://www.springer.com/us/book/9783540200406], which I recommend (not related to the author) (but I am a logic programming looney so).

juliangamble 11y ago

Rich Hickey's (of Clojure fame) Datomic database uses Datalog as its query language. http://docs.datomic.com/query.html http://docs.datomic.com/query.html http://blog.datomic.com/2015/01/datalog-enhancements.html http://blog.datomic.com/2015/01/datalog-enhancements.html Nathan Marz's (of Twitter startup fame) Cascalog library (also implemented in Clojure) uses Datalog as its query engine to generate Hadoop jobs. http://alexrobbins.github.io/cascalog-intro/#/step-14 http://alexrobbins.github.io/cascalog-intro/#/step-14 http://clojure.com/blog/2012/02/03/functional-relational-programming-with-cascalog.html http://clojure.com/blog/2012/02/03/functional-relational-pro...

j-pb 11y ago
Cascalog isn't proper datalog. It's a non-recursive fragment that allows for negation and outer joins, so semantically it's much closer to SQL, albeit with a much nicer syntax.