Introduction to Datalog (opens in new tab)

(x775.net)

203 pointsx7757y ago38 comments

38 comments

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.

x775OP7y ago

Hi Joel.

You can give http://www.dlvsystem.com/dlv/ a shot!

Alternatively, if you prefer open-source solutions, check https://abcdatalog.seas.harvard.edu/.

Due to a number of complications on my machine, I used DLV.

JoelMcCracken7y ago

Ah, I usually automatically pass on closed source solutions (hence my dislike for datomic).

TY for the link to abcdatalog though!

qeshi7y ago

Check out Datahike aswell, if you are interested in a durable datalog database.

https://github.com/replikativ/datahike

JoelMcCracken7y ago

Cool, ty! Seems similar to DataScript.

1 more reply

felixyz7y ago

If 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/

riza_on7y ago

I have been playing with Souffle for my datalog-based static analysis project

https://souffle-lang.github.io/docs/home/

sdbrady7y ago

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.

YeGoblynQueenne7y ago

Indeed, ":-" 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.

x775OP7y ago

Hi Stephen. You are absolutely right, thank you for the feedback! I have edited accordingly.

maweki7y ago

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

hombre_fatal7y ago

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 Datalog queries fast?

nutjob27y ago

If you have a lot of facts then you need indexes, otherwise you're scanning a lot of irrelevant data, many times over.

hombre_fatal7y ago

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

nmadden7y ago

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

x775OP7y ago

Hi there. Thanks so much for your feedback, and good catch! I will update the diagram accordingly.

x775OP7y ago

I can no longer edit the parent, but this has been updated. Thanks again!

burakemir7y ago

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)

x775OP7y ago

Thanks for your feedback!

For those interested in the mentioned paper, see: https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-p...

radomir_cernoch7y 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?

x775OP7y ago

Hi! 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!

bobjordan7y ago

Sharing an interesting implementation in python which I stumbled upon yesterday. Repo: https://github.com/pcarbonn/pyDatalog Tutorial: https://sites.google.com/site/pydatalog/Online-datalog-tutor...

ComNik7y ago

If 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

fspeech7y ago

Can you specify symmetric and transitive closure in Datalog?

brian_cloutier7y ago

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

fspeech7y ago

I was wondering about termination. With finite ground facts that appears not to be an issue. Complexity is another matter.

2 more replies

slifin7y ago

Thank you, bookmarking this for later

j / k navigate · click thread line to collapse

38 comments

JoelMcCracken7y ago

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.

x775OP7y ago

Hi Joel.

You can give http://www.dlvsystem.com/dlv/ a shot!

Alternatively, if you prefer open-source solutions, check https://abcdatalog.seas.harvard.edu/.

Due to a number of complications on my machine, I used DLV.

JoelMcCracken7y ago

Ah, I usually automatically pass on closed source solutions (hence my dislike for datomic).

TY for the link to abcdatalog though!

qeshi7y ago

Check out Datahike aswell, if you are interested in a durable datalog database.

https://github.com/replikativ/datahike

JoelMcCracken7y ago

Cool, ty! Seems similar to DataScript.

1 more reply

felixyz7y ago

If 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/

riza_on7y ago

I have been playing with Souffle for my datalog-based static analysis project

https://souffle-lang.github.io/docs/home/

sdbrady7y ago

YeGoblynQueenne7y ago

Indeed, ":-" 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.

x775OP7y ago

Hi Stephen. You are absolutely right, thank you for the feedback! I have edited accordingly.

maweki7y ago

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

hombre_fatal7y ago

Pretty cool deep-dive on Datalog.

The interactive tutorials on http://www.learndatalogtoday.org (Datomic's dialect) quickly sold me on the idea.

nutjob27y ago

If you have a lot of facts then you need indexes, otherwise you're scanning a lot of irrelevant data, many times over.

hombre_fatal7y ago

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

nmadden7y ago

x775OP7y ago

Hi there. Thanks so much for your feedback, and good catch! I will update the diagram accordingly.

x775OP7y ago

I can no longer edit the parent, but this has been updated. Thanks again!

burakemir7y ago

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)

x775OP7y ago

Thanks for your feedback!

For those interested in the mentioned paper, see: https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-p...

radomir_cernoch7y 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?

x775OP7y ago

Hi! 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!

bobjordan7y ago

Sharing an interesting implementation in python which I stumbled upon yesterday. Repo: https://github.com/pcarbonn/pyDatalog Tutorial: https://sites.google.com/site/pydatalog/Online-datalog-tutor...

ComNik7y ago

If 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

fspeech7y ago

Can you specify symmetric and transitive closure in Datalog?

brian_cloutier7y ago

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

fspeech7y ago

I was wondering about termination. With finite ground facts that appears not to be an issue. Complexity is another matter.

2 more replies

slifin7y ago

Thank you, bookmarking this for later

j / k navigate · click thread line to collapse