4 ms·

LogicBlox – Datalog REPL Tutorial

64 points by macmac 7y ago

jules 7y ago
What's the current state of the art in Datalog performance?
- chubot 7y ago
  Take a look at the Souffle Datalog compiler: https://souffle-lang.github.io/ https://souffle-lang.github.io/ Some benchmarks here showing it beating a lot of other engines: https://souffle-lang.github.io/pdf/cc.pdf https://souffle-lang.github.io/pdf/cc.pdf (this paper also cites LogixBlox) They translate datalog into a straightforward relational bytecode, then use Futamura projections to compile that bytecode into a template-heavy "monolithic" C++ program. As far as I remember one of use of C++ templates is to specialize for different sizes of tuples, so fast assembly is generated for particular queries/facts. They are doing at least 3 nontrivial transformations, and the last step really leverages C++. The generated C++ is also multi-threaded, which is a big win. I watched a talk on Rust where Niko M said he prototyped the new borrow checker with Souffle I believe. It's somewhere on YouTube.
- frankmcsherry 7y ago
  Depending on what you are looking for, DDlog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) is interesting. I'm casually involved, for people weirded out by that, but it supports arbitrary changes to the input facts without recomputation.
  - j-pb 7y ago
    invents new incremental computational paradigm that is hyped everywhere "I'm casually involved," Humble understatement of the year! Thank you for your work!
- JimmyRuska 7y ago
  RDFox uses datalog to apply inference rules to graph data, it has some state of the art algorithms for making datalog multi-core. It still uses SparQL, which is really similar to datalog for querying. There's some recent work on horizontally scaling datalog queries, but I hadn't seen anything in production. Probably the most popular implementation is datomic and its free variants. Which has a lot of convenience to it as you can embed custom java functions. It's not datalog but cypher has a lot of amazing ideas like easily combining algorithms to potentially recursive relationship queries, eg, "Give me the all shortest paths between these two peoples where there's at most 6 hops" -> allShortestPaths((n1:Person)-[*..6]->(n2:Person)) .
  - refset 7y ago
    I work on Crux [0], which is also a Java-friendly Datalog database. It sits on top of lazy EAV indexes in RocksDB/LMDB so it's pretty fast and scales well (though technologies like Neo4j/GraphBLAS will be faster!). We don't have online REPL just yet but Nextjournal is pretty great if you want to play through the tutorials interactively [1]. The other unique angle is that Crux gives you "bitemporal" Datalog queries. Oh and the MIT license :) [0] https://opencrux.com https://opencrux.com [1] https://nextjournal.com/crux-tutorial/ https://nextjournal.com/crux-tutorial/
chubot 7y ago
Funny to see this come up -- I just read this paper by a primary author of LogicBlox: Next-Paradigm Programming Languages: What Will They Look Like and What Changes Will They Bring? https://arxiv.org/abs/1905.00402 https://arxiv.org/abs/1905.00402 (In addition to seeing it cited by the Souffle paper I mentioned in a sibling comment.) It was an interesting paper that gives a flavor for logic / declarative programming, e.g. how to reason about performance, and the problem of tiny changes causing asymptotic performance differences (a problem that SQL shares). But I think it is mistitled -- it really is about a particular problem domain and is not about programming languages in general.
- dustingetz 7y ago
  Thanks for that paper, he didn't use these words but I might summarize it as predicting a merger/unification of programming language with database. Expressing programs as declarative operations over data with an optimized implementation injected by a compiler.
YeGoblynQueenne 7y ago
Uh-oh. Unable to connect, sorry! Internal error message: HTTP Error 502: '<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN"> <html><head> <title>502 Proxy Error</title> </head><body> <h1>Proxy Error</h1> The proxy server received an invalid response from an upstream server. The proxy server could not handle the request <a href="/connectblox">POST /connectblox</a>. Reason: Error reading from remote server Additionally, a 502 Bad Gateway error was encountered while trying to use an ErrorDocument to handle the request. </body></html> ' addblock 'cost[icecream] = c -> string(icecream), int(c).' No active workspace Is that HN's hug of death now?
- macmac 7y ago
 Not sure, I reported it to LogicBOx who's looking into it.
deleted 7y ago
[deleted]
pgt 7y ago
Great starting point for learning Datalog interactively: http://www.learndatalogtoday.org/ http://www.learndatalogtoday.org/

64 points by macmac 7y ago

jules 7y ago

What's the current state of the art in Datalog performance?

chubot 7y ago
Take a look at the Souffle Datalog compiler: https://souffle-lang.github.io/ https://souffle-lang.github.io/ Some benchmarks here showing it beating a lot of other engines: https://souffle-lang.github.io/pdf/cc.pdf https://souffle-lang.github.io/pdf/cc.pdf (this paper also cites LogixBlox) They translate datalog into a straightforward relational bytecode, then use Futamura projections to compile that bytecode into a template-heavy "monolithic" C++ program. As far as I remember one of use of C++ templates is to specialize for different sizes of tuples, so fast assembly is generated for particular queries/facts. They are doing at least 3 nontrivial transformations, and the last step really leverages C++. The generated C++ is also multi-threaded, which is a big win. I watched a talk on Rust where Niko M said he prototyped the new borrow checker with Souffle I believe. It's somewhere on YouTube.
frankmcsherry 7y ago
Depending on what you are looking for, DDlog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) is interesting. I'm casually involved, for people weirded out by that, but it supports arbitrary changes to the input facts without recomputation.
- j-pb 7y ago
  invents new incremental computational paradigm that is hyped everywhere "I'm casually involved," Humble understatement of the year! Thank you for your work!
JimmyRuska 7y ago
RDFox uses datalog to apply inference rules to graph data, it has some state of the art algorithms for making datalog multi-core. It still uses SparQL, which is really similar to datalog for querying. There's some recent work on horizontally scaling datalog queries, but I hadn't seen anything in production. Probably the most popular implementation is datomic and its free variants. Which has a lot of convenience to it as you can embed custom java functions. It's not datalog but cypher has a lot of amazing ideas like easily combining algorithms to potentially recursive relationship queries, eg, "Give me the all shortest paths between these two peoples where there's at most 6 hops" -> allShortestPaths((n1:Person)-[*..6]->(n2:Person)) .
- refset 7y ago
  I work on Crux [0], which is also a Java-friendly Datalog database. It sits on top of lazy EAV indexes in RocksDB/LMDB so it's pretty fast and scales well (though technologies like Neo4j/GraphBLAS will be faster!). We don't have online REPL just yet but Nextjournal is pretty great if you want to play through the tutorials interactively [1]. The other unique angle is that Crux gives you "bitemporal" Datalog queries. Oh and the MIT license :) [0] https://opencrux.com https://opencrux.com [1] https://nextjournal.com/crux-tutorial/ https://nextjournal.com/crux-tutorial/

chubot 7y ago

Funny to see this come up -- I just read this paper by a primary author of LogicBlox: Next-Paradigm Programming Languages: What Will They Look Like and What Changes Will They Bring? https://arxiv.org/abs/1905.00402 https://arxiv.org/abs/1905.00402 (In addition to seeing it cited by the Souffle paper I mentioned in a sibling comment.) It was an interesting paper that gives a flavor for logic / declarative programming, e.g. how to reason about performance, and the problem of tiny changes causing asymptotic performance differences (a problem that SQL shares). But I think it is mistitled -- it really is about a particular problem domain and is not about programming languages in general.

dustingetz 7y ago
Thanks for that paper, he didn't use these words but I might summarize it as predicting a merger/unification of programming language with database. Expressing programs as declarative operations over data with an optimized implementation injected by a compiler.

YeGoblynQueenne 7y ago

Uh-oh. Unable to connect, sorry! Internal error message: HTTP Error 502: '<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN"> <html><head> <title>502 Proxy Error</title> </head><body> <h1>Proxy Error</h1> The proxy server received an invalid response from an upstream server. The proxy server could not handle the request <a href="/connectblox">POST /connectblox</a>. Reason: Error reading from remote server Additionally, a 502 Bad Gateway error was encountered while trying to use an ErrorDocument to handle the request. </body></html> ' addblock 'cost[icecream] = c -> string(icecream), int(c).' No active workspace Is that HN's hug of death now?

macmac 7y ago
Not sure, I reported it to LogicBOx who's looking into it.

deleted 7y ago

[deleted]

pgt 7y ago

Great starting point for learning Datalog interactively: http://www.learndatalogtoday.org/ http://www.learndatalogtoday.org/