5 ms·

This is one of those things that has always sounded really interesting but I haven’t had the opportunity to use. Does anybody have experience with it? I’m also

This is one of those things that has always sounded really interesting but I haven’t had the opportunity to use. Does anybody have experience with it? I’m also trying to find some benchmarks but don’t see much.

maweki 5y ago
As a real database language with ad-hoc-queries you're fine with SQL. Data-intensive graph analysis (the reason soufflé, souffle-lang.org, was developed) where you have a fixed set of deduction rules and change the database instance is an ideal playground for Datalog. And soufflé is incredibly fast and for the usual benchmarks, like the transitive closure in comparison to recursive CTEs in SQL, blows everything out of the water. (my paper on that http://ceur-ws.org/Vol-2368/paper3.pdf http://ceur-ws.org/Vol-2368/paper3.pdf, Figure 3) I'm researching using Datalog as a general purpose programming language (specifically for use in microcontrollers, like Arduino) for my PhD and it can be very expressive.
- discreteevent 5y ago
  Have you come across Eve? It was a general purpose language described as a variant of datalog. They ran out of money in 2018. Everything was a record, even the browser Dom. It's a shame we can't work in a world as consistent and simple as they tried to make it. http://witheve.com/ http://witheve.com/
  - maweki 5y ago
    > Have you come across Eve? Apparently that link was already marked as "visited" in my browser history and it seems familiar. There seems to be a strong connection between reactive programming (especially the functional-reactive style) and Datalog. I believe that is the case because Datalog (simplification incoming) is a logic programming language that, contrary to ASP, for example, always returns a single model and can therefore always be seen as a function from input-relations (FRP cells) to output-relations where the deductive steps and intensional predicates are the streams. The issue is - and that's not really surprising - that implementing useful call-conventions for your application on top of a datalog-engine is not easier than using a fixed call-convention (like a (f)RP-framework) and implementing your deduction with simpler semantics. In the end, you have to bind your input and output-relations to your view and write down the rules and they are somewhat simple. With reactive programming you have a somewhat easier time binding your data to the views and the rules (functional mappings) are somewhat more difficult. That is why I abandoned the reactive style of using Datalog as a general purpose programming language early on. If you really want to do this, you can already use differential dataflow and some plumbing code and you would not have lost a thing. My approach is closer to Logic Production Systems.
    - kixiron 5y ago
      Full disclosure, I do work for VMWare on the DDlog project If you want a sort of FRP-backed datalog, I highly recommend Differential Datalog https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog It's a datalog flavor/variant that's based on the Timely Dataflow and Differential Dataflow libraries, it's focused on incremental computation over streaming data. Coincidentally it's also used on network switches if that's relevant to your need for deploying on micro-controllers
      - maweki 5y ago
        As I said, one can easily use differential dataflow with some plumbing code. And this is fine and no worse than the eve language shown above. The DDlog-project and its applications are a nice example for that. Where I think this approach fails a bit is the following: There is a language-gap issue where your output-relations need to be mapped in a host language to outputs. And you have to call some functions to collect all data for the input relations. Especially in the context of robotics the latter often is not free of side-effects. Not being able to explicitly control those calls can be problematic. Having a powerful host-language and explicitly embedding a Datalog-implementation is useful, as the decision procedures for your interactive application are not just a series of if-statements but proper condition-action-rules. My approach is the other way around. I think embedding strict call-conventions for external functions and explicitly modelling side-effects into the language allows for an expressive LP-language that handles the interactive parts as well as the logic-deductive parts.
        krasi0 5y ago
        Then why not embed a Prolog engine which being Turing complete is much more powerful and expressive than Datalog?
        maweki 5y ago
        For one, memory management is much more difficult with term structures. But mainly Prolog semantics with side-effects are a whole different beast. This is a different thing I am researching, but basically the whole idea stems from robotics control with Prolog and how handling of side-effects just does not work nicely with SLD-resolution, specifically backtracking over side-effects. I have a paper on that as well ;)
- YeGoblynQueenne 5y ago
  Is that an embedded Datalog then, that runs on microcontrollers? I'm researching approaches that learn Datalog programs from examples for my PhD. In practice, the algorithms I study can learn Prolog programs but Datalog is a nice, decidable subset of Prolog that also has the advantage that clause ordering doesn't matter so a learner only needs to learn the clauses in a program, without also learning to order them. There's a bunch of work from the program synthesis community on learning Datalog programs from examples. Here's a recent-ish paper I found interesting (and whose authors I'm not affiliated with): https://www.semanticscholar.org/paper/Syntax-guided-synthesis-of-Datalog-programs-Si-Lee/632a5e11e5b129230691116ee1c9728bae7080ff https://www.semanticscholar.org/paper/Syntax-guided-synthesi...
  - maweki 5y ago
    The approach is an iterative deduction with strict call-conventions. In some cases I compile the rules as-is into a C-Program, but if the used memory is provably bounded, I compile to a finite state machine + some registers. Had to ditch the extensional database for that. Not strictly necessary, as it turns out. You can read it here (https://doi.org/10.1007/978-3-030-68446-4_11 https://doi.org/10.1007/978-3-030-68446-4_11, behind paywall) or hit me up on researchgate for that paper. Or as a short overview: https://dbs.informatik.uni-halle.de/microlog/ https://dbs.informatik.uni-halle.de/microlog/ The main problem, which I claim to solve, is the handling of side-effects. For the microcontroller (or a robot) it is vitally important to not have side-effects or at least have them explicit for the developer and the language semantics. I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application.
    - YeGoblynQueenne 5y ago
      Oh, so you publish in logic program synthesis then? Your field and mine (Inductive Logic Programming) are practically neighbours! :) The paper looks interesting, I'll have a look. (Although I guess your work is more on the "transformation" part of "logic-based program synthesis and transformation"). >> I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application. To be honest, I struggle a bit with the terminology here because I'm woefully behind with my knowledge of modern Datalog (I only need to use the bog-standard language from the '80s to achieve my goals). For example, I'm not sure what counts as input and output in Datalog parlance. I think "input" is your intensional and extensional definitions, then output is the ground facts derived from them? I'm interested in this also: >> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. Is that explained in the paper?
- wuschel 5y ago
  What usable implementations/libraries of datalog would you recommend?
  - maweki 5y ago
    Depends on your use case I would suggest soufflé (https://souffle-lang.github.io/ https://souffle-lang.github.io/) if you're batching data through for static analysis. DDLog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) if you want a rule-engine within your interactive application, to encode decision procedures and business rules. If you actually want this to drive the views of a (web-)application, I don't think we're really there yet. We have to wait at least for the next generation of developments. But you can give it a try with datascript https://github.com/tonsky/datascript https://github.com/tonsky/datascript
- atombender 5y ago
  Are languages like Datalog and Soufflé suitable for rewriting graphs, e.g. for optimization? Every use of Datalog I've seen refers to deducing facts about graphs, but I've never seen examples of morphing graphs. For example, converting a boolean expression into CNF form. This is the sort of thing functional languages are great at, but if you're writing something in a different language (JavaScript, Go, Rust, etc.) then it'd be great to be able to plug in a declarative rule-based rewriting engine without rewriting everything in, say, OCaml.
  - maweki 5y ago
    For rewriting there is the general problem of "consumption". You consume a piece of information during a rewriting step to obtain new information. The old information is then gone. Say you have some edge in a graph and you want that removed, then you have to write down a relation R={all-edges-without-that-edge}. And the number of your relations is fixed. You are allowed to use negation, but only in a restricted (non self-referential) manner. Also, if your rewriting relationship is not confluent, Datalog - as it only ever has a single model - can not solve the problem, as there is no choice-construct. Datalog is more akin to graph completion. What you may want to look into is Answer Set Programming. You could describe your rewriting relationship as a logic program in this manner. ASP is strictly more powerful than Datalog and modern solvers compile to SAT and SAT solvers are fast. And even non-confluence is not a problem, as you get multiple answer sets. The only issue with Logic Programming in general is value invention. The lack of value invention is usually the termination argument for any solving algorithm. If you need fresh values/names, stuff gets hard really quick, meaning you get infinitely sized models. Non-termination.
raspasov 5y ago
Yes, I've been using DataScript (which uses this flavor of Datalog) to store and query the data locally in my iOS app in the last few months. DataScript works well but you need to know how to use it. Benchmarks would entirely depend on the implementation of the database/language.
refset 5y ago
Disclosing benchmark results is forbidden by the licensing, which isn't uncommon for proprietary DBs, e.g. https://stackoverflow.com/questions/12115397/is-it-against-license-to-publish-oracle-and-sql-server-performance-test https://stackoverflow.com/questions/12115397/is-it-against-l... Incidentally, I was writing up some notes earlier today about the nightly benchmarks we run for Crux (another Clojure-flavoured Datalog DB), which may be of interest: https://opencrux.com/articles/benchmarks.html https://opencrux.com/articles/benchmarks.html
- benrbray 5y ago
  > Disclosing benchmark results is forbidden by the licensing How on earth is this enforceable? Talk about anti-competitive!
  - detaro 5y ago
    > How on earth is this enforceable? It might not be, but few people care enough about publishing numbers to go through the trouble of finding out (and potentially betting wrong). Although comparisons to "leading proprietary industry database" winkwink nudgenudge might happen, at least in academic circles.
gillh 5y ago
At Netsil (microservice observability startup), API analytics and stream-processor was built using a dialect of Datalog. Netsil was acquired by Nutanix in 2018 and the technology was incorporated into a couple of product lines. The Datalog engine at Netsil is pretty sophisticated, capable of fine-grained parallelism (built on task-stealing architecture) - Datalog programs are chained together in a pipeline, such that the output of one program is an input to another. These programs (stages in the pipeline) can be run in serial, parallel or context_ordered modes. In context_ordered mode the tuples are sent to the execution engine ordered by their context_keys -- e.g. captured packets from the same flow are processed serially and in parallel across flows. In addition, it incorporates SQLite embedded DB for materialized tables and state. The raw events are aggregated using Datalog rules & tables and SQL queries are auto-generated from high-level Datalog rules. We also extended Datalog with the concept of "Accumulators", stateful objects in rule head that emit a tuple when certain conditions are met - e.g. we build Windowed Counters, TCP re-assembly from network packets etc. using Accumulators. In addition to all this, one could distribute Datalog programs across machines -- Tuples serialize to protobuf and sent across machines over ZeroMQ etc. We used distributed features by sending raw metrics from the Host based Agents on customer's machines to the cloud service where the Datalog based stream processor joins the incoming metrics/events tuples with metadata collected from external sources (e.g. K8S tags). The Datalog engine also synchronized some tables with Zookeeper for distributing config updates in real-time such as metadata tables that were used in stream-joins. E.g. each time a new K8S pod was detected in customer environment, an update tuple was sent to cloud, which updated the Zookeeper backed materialized table thereby synchronizing with all other stream-processor pods in near-realtime.

maweki 5y ago

As a real database language with ad-hoc-queries you're fine with SQL. Data-intensive graph analysis (the reason soufflé, souffle-lang.org, was developed) where you have a fixed set of deduction rules and change the database instance is an ideal playground for Datalog. And soufflé is incredibly fast and for the usual benchmarks, like the transitive closure in comparison to recursive CTEs in SQL, blows everything out of the water. (my paper on that http://ceur-ws.org/Vol-2368/paper3.pdf http://ceur-ws.org/Vol-2368/paper3.pdf, Figure 3) I'm researching using Datalog as a general purpose programming language (specifically for use in microcontrollers, like Arduino) for my PhD and it can be very expressive.

discreteevent 5y ago
Have you come across Eve? It was a general purpose language described as a variant of datalog. They ran out of money in 2018. Everything was a record, even the browser Dom. It's a shame we can't work in a world as consistent and simple as they tried to make it. http://witheve.com/ http://witheve.com/
- maweki 5y ago
  > Have you come across Eve? Apparently that link was already marked as "visited" in my browser history and it seems familiar. There seems to be a strong connection between reactive programming (especially the functional-reactive style) and Datalog. I believe that is the case because Datalog (simplification incoming) is a logic programming language that, contrary to ASP, for example, always returns a single model and can therefore always be seen as a function from input-relations (FRP cells) to output-relations where the deductive steps and intensional predicates are the streams. The issue is - and that's not really surprising - that implementing useful call-conventions for your application on top of a datalog-engine is not easier than using a fixed call-convention (like a (f)RP-framework) and implementing your deduction with simpler semantics. In the end, you have to bind your input and output-relations to your view and write down the rules and they are somewhat simple. With reactive programming you have a somewhat easier time binding your data to the views and the rules (functional mappings) are somewhat more difficult. That is why I abandoned the reactive style of using Datalog as a general purpose programming language early on. If you really want to do this, you can already use differential dataflow and some plumbing code and you would not have lost a thing. My approach is closer to Logic Production Systems.
  - kixiron 5y ago
    Full disclosure, I do work for VMWare on the DDlog project If you want a sort of FRP-backed datalog, I highly recommend Differential Datalog https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog It's a datalog flavor/variant that's based on the Timely Dataflow and Differential Dataflow libraries, it's focused on incremental computation over streaming data. Coincidentally it's also used on network switches if that's relevant to your need for deploying on micro-controllers
    - maweki 5y ago
      As I said, one can easily use differential dataflow with some plumbing code. And this is fine and no worse than the eve language shown above. The DDlog-project and its applications are a nice example for that. Where I think this approach fails a bit is the following: There is a language-gap issue where your output-relations need to be mapped in a host language to outputs. And you have to call some functions to collect all data for the input relations. Especially in the context of robotics the latter often is not free of side-effects. Not being able to explicitly control those calls can be problematic. Having a powerful host-language and explicitly embedding a Datalog-implementation is useful, as the decision procedures for your interactive application are not just a series of if-statements but proper condition-action-rules. My approach is the other way around. I think embedding strict call-conventions for external functions and explicitly modelling side-effects into the language allows for an expressive LP-language that handles the interactive parts as well as the logic-deductive parts.
      - krasi0 5y ago
        Then why not embed a Prolog engine which being Turing complete is much more powerful and expressive than Datalog?
        maweki 5y ago
        For one, memory management is much more difficult with term structures. But mainly Prolog semantics with side-effects are a whole different beast. This is a different thing I am researching, but basically the whole idea stems from robotics control with Prolog and how handling of side-effects just does not work nicely with SLD-resolution, specifically backtracking over side-effects. I have a paper on that as well ;)
YeGoblynQueenne 5y ago
Is that an embedded Datalog then, that runs on microcontrollers? I'm researching approaches that learn Datalog programs from examples for my PhD. In practice, the algorithms I study can learn Prolog programs but Datalog is a nice, decidable subset of Prolog that also has the advantage that clause ordering doesn't matter so a learner only needs to learn the clauses in a program, without also learning to order them. There's a bunch of work from the program synthesis community on learning Datalog programs from examples. Here's a recent-ish paper I found interesting (and whose authors I'm not affiliated with): https://www.semanticscholar.org/paper/Syntax-guided-synthesis-of-Datalog-programs-Si-Lee/632a5e11e5b129230691116ee1c9728bae7080ff https://www.semanticscholar.org/paper/Syntax-guided-synthesi...
- maweki 5y ago
  The approach is an iterative deduction with strict call-conventions. In some cases I compile the rules as-is into a C-Program, but if the used memory is provably bounded, I compile to a finite state machine + some registers. Had to ditch the extensional database for that. Not strictly necessary, as it turns out. You can read it here (https://doi.org/10.1007/978-3-030-68446-4_11 https://doi.org/10.1007/978-3-030-68446-4_11, behind paywall) or hit me up on researchgate for that paper. Or as a short overview: https://dbs.informatik.uni-halle.de/microlog/ https://dbs.informatik.uni-halle.de/microlog/ The main problem, which I claim to solve, is the handling of side-effects. For the microcontroller (or a robot) it is vitally important to not have side-effects or at least have them explicit for the developer and the language semantics. I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application.
  - YeGoblynQueenne 5y ago
    Oh, so you publish in logic program synthesis then? Your field and mine (Inductive Logic Programming) are practically neighbours! :) The paper looks interesting, I'll have a look. (Although I guess your work is more on the "transformation" part of "logic-based program synthesis and transformation"). >> I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application. To be honest, I struggle a bit with the terminology here because I'm woefully behind with my knowledge of modern Datalog (I only need to use the bog-standard language from the '80s to achieve my goals). For example, I'm not sure what counts as input and output in Datalog parlance. I think "input" is your intensional and extensional definitions, then output is the ground facts derived from them? I'm interested in this also: >> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. Is that explained in the paper?
wuschel 5y ago
What usable implementations/libraries of datalog would you recommend?
- maweki 5y ago
  Depends on your use case I would suggest soufflé (https://souffle-lang.github.io/ https://souffle-lang.github.io/) if you're batching data through for static analysis. DDLog (https://github.com/vmware/differential-datalog https://github.com/vmware/differential-datalog) if you want a rule-engine within your interactive application, to encode decision procedures and business rules. If you actually want this to drive the views of a (web-)application, I don't think we're really there yet. We have to wait at least for the next generation of developments. But you can give it a try with datascript https://github.com/tonsky/datascript https://github.com/tonsky/datascript
atombender 5y ago
Are languages like Datalog and Soufflé suitable for rewriting graphs, e.g. for optimization? Every use of Datalog I've seen refers to deducing facts about graphs, but I've never seen examples of morphing graphs. For example, converting a boolean expression into CNF form. This is the sort of thing functional languages are great at, but if you're writing something in a different language (JavaScript, Go, Rust, etc.) then it'd be great to be able to plug in a declarative rule-based rewriting engine without rewriting everything in, say, OCaml.
- maweki 5y ago
  For rewriting there is the general problem of "consumption". You consume a piece of information during a rewriting step to obtain new information. The old information is then gone. Say you have some edge in a graph and you want that removed, then you have to write down a relation R={all-edges-without-that-edge}. And the number of your relations is fixed. You are allowed to use negation, but only in a restricted (non self-referential) manner. Also, if your rewriting relationship is not confluent, Datalog - as it only ever has a single model - can not solve the problem, as there is no choice-construct. Datalog is more akin to graph completion. What you may want to look into is Answer Set Programming. You could describe your rewriting relationship as a logic program in this manner. ASP is strictly more powerful than Datalog and modern solvers compile to SAT and SAT solvers are fast. And even non-confluence is not a problem, as you get multiple answer sets. The only issue with Logic Programming in general is value invention. The lack of value invention is usually the termination argument for any solving algorithm. If you need fresh values/names, stuff gets hard really quick, meaning you get infinitely sized models. Non-termination.

raspasov 5y ago

Yes, I've been using DataScript (which uses this flavor of Datalog) to store and query the data locally in my iOS app in the last few months. DataScript works well but you need to know how to use it. Benchmarks would entirely depend on the implementation of the database/language.

refset 5y ago

Disclosing benchmark results is forbidden by the licensing, which isn't uncommon for proprietary DBs, e.g. https://stackoverflow.com/questions/12115397/is-it-against-license-to-publish-oracle-and-sql-server-performance-test https://stackoverflow.com/questions/12115397/is-it-against-l... Incidentally, I was writing up some notes earlier today about the nightly benchmarks we run for Crux (another Clojure-flavoured Datalog DB), which may be of interest: https://opencrux.com/articles/benchmarks.html https://opencrux.com/articles/benchmarks.html

benrbray 5y ago
> Disclosing benchmark results is forbidden by the licensing How on earth is this enforceable? Talk about anti-competitive!
- detaro 5y ago
  > How on earth is this enforceable? It might not be, but few people care enough about publishing numbers to go through the trouble of finding out (and potentially betting wrong). Although comparisons to "leading proprietary industry database" winkwink nudgenudge might happen, at least in academic circles.

gillh 5y ago

At Netsil (microservice observability startup), API analytics and stream-processor was built using a dialect of Datalog. Netsil was acquired by Nutanix in 2018 and the technology was incorporated into a couple of product lines. The Datalog engine at Netsil is pretty sophisticated, capable of fine-grained parallelism (built on task-stealing architecture) - Datalog programs are chained together in a pipeline, such that the output of one program is an input to another. These programs (stages in the pipeline) can be run in serial, parallel or context_ordered modes. In context_ordered mode the tuples are sent to the execution engine ordered by their context_keys -- e.g. captured packets from the same flow are processed serially and in parallel across flows. In addition, it incorporates SQLite embedded DB for materialized tables and state. The raw events are aggregated using Datalog rules & tables and SQL queries are auto-generated from high-level Datalog rules. We also extended Datalog with the concept of "Accumulators", stateful objects in rule head that emit a tuple when certain conditions are met - e.g. we build Windowed Counters, TCP re-assembly from network packets etc. using Accumulators. In addition to all this, one could distribute Datalog programs across machines -- Tuples serialize to protobuf and sent across machines over ZeroMQ etc. We used distributed features by sending raw metrics from the Host based Agents on customer's machines to the cloud service where the Datalog based stream processor joins the incoming metrics/events tuples with metadata collected from external sources (e.g. K8S tags). The Datalog engine also synchronized some tables with Zookeeper for distributing config updates in real-time such as metadata tables that were used in stream-joins. E.g. each time a new K8S pod was detected in customer environment, an update tuple was sent to cloud, which updated the Zookeeper backed materialized table thereby synchronizing with all other stream-processor pods in near-realtime.