4 ms·

Yeah, there are a ton of substantively different approaches to modern Datalogs, targeting different applications. To start off: Datalog is distinguished from t

Yeah, there are a ton of substantively different approaches to modern Datalogs, targeting different applications. To start off: Datalog is distinguished from traditional SQL in its focus on heavily-recursive reachability-based reasoning. With respect to expressivity, you can see Datalog as CDCL/DPLL restricted to boolean constraint propagation (i.e., Horn clauses). Operationally, you can think of this as: tight range-indexed loops which are performing insertion/deduplication into an (indexed) relation-backing data structure (a BTree/trie/etc...). In SQL, you don't know the query a-priori, so you can't just index everything--but in Datalog, you know all of the rules up-front and can generate indices for everything. This ubiquitous indexing enables the state-of-the-art work we see with Datalog in static analysis (DOOP, cclyzer), security (ddisasm), etc... Our group targets tasks like code analysis and these big graph problems because we think they represent the most computationally-complex, hard problems that we are capable of doing. The next step here is to scale our prototypes (a handful of rules) to large, realistic systems--some potential applications of that are, e.g., raw feature extraction for binaries when you do ML over binary corpuses (which otherwise require, e.g., running IDA) on the GPU (rather than IDA on the CPU), medical reasoning (accelerating MediKanren), and (hopefully) probabilistic programming (these neuro-symbolic applications). By contrast, I think work which takes a more traditional Databases approach (CodeQL, RDFox, ...) focus a little less on ubiquitous high-performance range-indexed insertion in a tight loop, and focus a little more on supporting robust querying and especially operating on streams. There is some very cool related work there in differential dataflow (upon which differential Datalog is built). There is a solver there named DDlog (written in Rust) which takes that approach. Our in-house experiments show that DDlog is often a constant factor slower than Souffle on GPUs, and we did not directly compare against DDlog in this paper--I expect the results would be roughly similar to Souffle.

zozbot234 3y ago
> To start off: Datalog is distinguished from traditional SQL in its focus on heavily-recursive reachability-based reasoning. This was historically true but SQL has CTE's and recursive CTE's these days, and even some extra syntactic sugar for reachability query's. And of course (given the former) "inference" and "deduction" over data are just a CREATE VIEW statement away. This is the "you know all of the rules up-front" part; a VIEW is just a query that you do know upfront. Most uses of "deductive" databases are just for querying within some in-memory database, which is not really playing in the same league as a fully general RDBMS. This is not intended to dismiss the work in OP, of course; if anything, its applicability need not be restricted to a tiny niche of software intended for specific application areas, and can be quite a bit broader than that.
- kmicinski 3y ago
  Right--but CTEs are orders-of-magnitude slower than Datalog, to the point that they are not seriously worth considering for any modern application where Datalog would be used. As you said, Datalog is less expressive than SQL's ability to create new queries in an ad-hoc way: knowing all queries within the fixed point enables much more efficient compilation.
westurner 3y ago
"Introduction to Datalog" re: Linked Data https://news.ycombinator.com/context?id=34808887 https://news.ycombinator.com/context?id=34808887 pyDatalog/examples/SQLAlchemy.py: https://github.com/baojie/pydatalog/blob/master/pyDatalog/examples/SQLAlchemy.py https://github.com/baojie/pydatalog/blob/master/pyDatalog/ex... GH topics > datalog: https://github.com/topics/datalog https://github.com/topics/datalog datalog?l=rust: https://github.com/topics/datalog?l=rust https://github.com/topics/datalog?l=rust ... Cozo, Crepe Crepe: https://github.com/ekzhang/crepe https://github.com/ekzhang/crepe : > Crepe is a library that allows you to write declarative logic programs in Rust, with a Datalog-like syntax. It provides a procedural macro that generates efficient, safe code and interoperates seamlessly with Rust programs. Looks like there's not yet a Python grammar for the treeedb tree-sitter: https://github.com/langston-barrett/treeedb https://github.com/langston-barrett/treeedb : > Generate Soufflé Datalog types, relations, and facts that represent ASTs from a variety of programming languages. Looks like roxi supports n3, which adds `=>` "implies" to the Turtle lightweight RDF representation: https://github.com/pbonte/roxi https://github.com/pbonte/roxi FWIW rdflib/owl-rl: https://owl-rl.readthedocs.io/en/latest/owlrl.html https://owl-rl.readthedocs.io/en/latest/owlrl.html : > simple forward chaining rules are used to extend (recursively) the incoming graph with all triples that the rule sets permit (ie, the “deductive closure” of the graph is computed). ForwardChainingStore and BackwardChainingStore implementations w/ rdflib in Python: https://github.com/RDFLib/FuXi/issues/15 https://github.com/RDFLib/FuXi/issues/15 Fast CUDA hashmaps Gdlog is built on CuCollections. GPU HashMap libs to benchmark: Warpcore, CuCollections, https://github.com/NVIDIA/cuCollections https://github.com/NVIDIA/cuCollections https://github.com/NVIDIA/cccl https://github.com/NVIDIA/cccl https://github.com/sleeepyjack/warpcore https://github.com/sleeepyjack/warpcore /? Rocm HashMap DeMoriarty/DOKsparse: https://github.com/DeMoriarty/DOKSparse https://github.com/DeMoriarty/DOKSparse /? SIMD hashmap Google's SwissTable: https://github.com/topics/swisstable https://github.com/topics/swisstable rust-lang/hashbrown: https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown CuPy has array but not yet hashmaps, or (GPU) SIMD FWICS? NumPy does SIMD: https://numpy.org/doc/stable/reference/simd/ https://numpy.org/doc/stable/reference/simd/ google/highway: https://github.com/google/highway https://github.com/google/highway xtensor-stack/xsimd: https://github.com/xtensor-stack/xsimd https://github.com/xtensor-stack/xsimd GH topics > HashMap: https://github.com/topics/hashmap https://github.com/topics/hashmap

zozbot234 3y ago

> To start off: Datalog is distinguished from traditional SQL in its focus on heavily-recursive reachability-based reasoning. This was historically true but SQL has CTE's and recursive CTE's these days, and even some extra syntactic sugar for reachability query's. And of course (given the former) "inference" and "deduction" over data are just a CREATE VIEW statement away. This is the "you know all of the rules up-front" part; a VIEW is just a query that you do know upfront. Most uses of "deductive" databases are just for querying within some in-memory database, which is not really playing in the same league as a fully general RDBMS. This is not intended to dismiss the work in OP, of course; if anything, its applicability need not be restricted to a tiny niche of software intended for specific application areas, and can be quite a bit broader than that.

kmicinski 3y ago
Right--but CTEs are orders-of-magnitude slower than Datalog, to the point that they are not seriously worth considering for any modern application where Datalog would be used. As you said, Datalog is less expressive than SQL's ability to create new queries in an ad-hoc way: knowing all queries within the fixed point enables much more efficient compilation.

westurner 3y ago

"Introduction to Datalog" re: Linked Data https://news.ycombinator.com/context?id=34808887 https://news.ycombinator.com/context?id=34808887 pyDatalog/examples/SQLAlchemy.py: https://github.com/baojie/pydatalog/blob/master/pyDatalog/examples/SQLAlchemy.py https://github.com/baojie/pydatalog/blob/master/pyDatalog/ex... GH topics > datalog: https://github.com/topics/datalog https://github.com/topics/datalog datalog?l=rust: https://github.com/topics/datalog?l=rust https://github.com/topics/datalog?l=rust ... Cozo, Crepe Crepe: https://github.com/ekzhang/crepe https://github.com/ekzhang/crepe : > Crepe is a library that allows you to write declarative logic programs in Rust, with a Datalog-like syntax. It provides a procedural macro that generates efficient, safe code and interoperates seamlessly with Rust programs. Looks like there's not yet a Python grammar for the treeedb tree-sitter: https://github.com/langston-barrett/treeedb https://github.com/langston-barrett/treeedb : > Generate Soufflé Datalog types, relations, and facts that represent ASTs from a variety of programming languages. Looks like roxi supports n3, which adds `=>` "implies" to the Turtle lightweight RDF representation: https://github.com/pbonte/roxi https://github.com/pbonte/roxi FWIW rdflib/owl-rl: https://owl-rl.readthedocs.io/en/latest/owlrl.html https://owl-rl.readthedocs.io/en/latest/owlrl.html : > simple forward chaining rules are used to extend (recursively) the incoming graph with all triples that the rule sets permit (ie, the “deductive closure” of the graph is computed). ForwardChainingStore and BackwardChainingStore implementations w/ rdflib in Python: https://github.com/RDFLib/FuXi/issues/15 https://github.com/RDFLib/FuXi/issues/15 Fast CUDA hashmaps Gdlog is built on CuCollections. GPU HashMap libs to benchmark: Warpcore, CuCollections, https://github.com/NVIDIA/cuCollections https://github.com/NVIDIA/cuCollections https://github.com/NVIDIA/cccl https://github.com/NVIDIA/cccl https://github.com/sleeepyjack/warpcore https://github.com/sleeepyjack/warpcore /? Rocm HashMap DeMoriarty/DOKsparse: https://github.com/DeMoriarty/DOKSparse https://github.com/DeMoriarty/DOKSparse /? SIMD hashmap Google's SwissTable: https://github.com/topics/swisstable https://github.com/topics/swisstable rust-lang/hashbrown: https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown CuPy has array but not yet hashmaps, or (GPU) SIMD FWICS? NumPy does SIMD: https://numpy.org/doc/stable/reference/simd/ https://numpy.org/doc/stable/reference/simd/ google/highway: https://github.com/google/highway https://github.com/google/highway xtensor-stack/xsimd: https://github.com/xtensor-stack/xsimd https://github.com/xtensor-stack/xsimd GH topics > HashMap: https://github.com/topics/hashmap https://github.com/topics/hashmap