Declaring Reality: An Introduction to Datalog | Hacker News Reader

Declaring Reality: An Introduction to Datalog

zef.me

60 pointssacheendra13 comments

Rich Hickey's (of Clojure fame) Datomic database uses Datalog as its query language.

http://docs.datomic.com/query.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://clojure.com/blog/2012/02/03/functional-relational-pro...

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.

Worth mentioning?

Racket ships with #lang racklog a scheme based datalog like language: http://docs.racket-lang.org/datalog/index.html

Also Prolog like logic languages Parenlog http://docs.racket-lang.org/parenlog/index.html and the more fully fleshed out Racklog 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/

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.

How does Datalog compare to Prolog?

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.

> 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.)

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.

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

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)

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.

No.

Any comparisons with:

- minikanren

- constraint logic prog

- constraint solving

- inductive logic

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-...

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/].

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], which I recommend (not related to the author) (but I am a logic programming looney so).

Reply on news.ycombinator.com