Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to Datalog

x775.net

Post reply on HN
Print view View original

1–10 of 40 posts

Re: Introduction to Datalog

#3

Post by hombre_fatal »

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?

Re: Introduction to Datalog

#4

Post by brian_cloutier »

fspeech wrote: post #2

Can you specify symmetric and transitive closure in Datalog?

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

Re: Introduction to Datalog

#6

Post by fspeech »

brian_cloutier wrote: post #4
fspeech wrote: post #2

Can you specify symmetric and transitive closure in Datalog?

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) :…

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

Re: Introduction to Datalog

#7

Post by cfallin »

fspeech wrote: post #6
brian_cloutier wrote: post #4

Earlier quoted context omitted.

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) :…

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

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

Re: Introduction to Datalog

#8

Post by nutjob2 »

hombre_fatal wrote: post #3

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.

Re: Introduction to Datalog

#9

Post by radomir_cernoch »

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

Re: Introduction to Datalog

#10

Post by sdbrady »

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.
Post reply on HN