6 ms·

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

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

by maweki 5y ago

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.