6 ms·

A relatively simple Datalog engine

207 points by dmit 8y ago

triska 8y ago
Nice! It's always good to see Datalog in action. In my experience, Datalog is often more convenient and more readable than SQL. As the post mentions, the current ergonomics ("a wall of definitions") are indeed the main shortcoming of the present approach, which is syntactically far removed from Datalog. My suggestion towards an automated conversion is to consider Prolog: Syntactically, a Datalog clause is a valid Prolog term. In fact, Datalog is a syntactic subset of Prolog. Therefore, it can be easily parsed with Prolog (using the predicate read/1), and then inspected via built-in mechanisms. You may be able to write a Prolog program that converts proper Datalog definitions to such Rust snippets.
- a-saleh 8y ago
  I think it will be better if we figure out how to do embedded catalog in other languages. I.e. I really liked The research here https://github.com/rntz/datafun https://github.com/rntz/datafun, where we start with "datalog=relational algebra+fixpoints" and then are trying to figure out how far can we take this in language where not everything is a table of facts :)
  - convolvatron 8y ago
    schelog by Dorai Sitaram https://ds26gte.github.io/schelog/index.html https://ds26gte.github.io/schelog/index.html is a classic version of a funtional/declarative hybrid as a purely operational artifact. apparently its still being updated, but I remember it from many years ago (early 90s?). it uses the ability to return multiple times from a continuation to allow sets of results (streams or solution trees) to be expressed directly in scheme and intermixed freely with the functional subset. a 'nice' mixture of declarative and procedural would be really slick. i should go back and look at mozart/oz again. I'll definately see if my limited ability to deal with formalisms lets me understand the type system proposed in Datafun.
    - a-saleh 8y ago
      "Streams of solution trees" kinda reminds me of mikro-kanren [1]. When I was using Clojure roughly 3 years ago, kanren was quite popular embedded logic. W.r.t. Datafun, i learned about it from a talk its creator gave on strangeloop last year [2], for me it seemed quite approachable :) [1] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf [2] https://www.youtube.com/watch?v=gC295d3V9gE https://www.youtube.com/watch?v=gC295d3V9gE
steveklabnik 8y ago
For some interesting backlog here: As Rust moves from lexical to non-lexical lifetimes, there's been a few different ways of actually implementing it. The initial implementation had some bugs and was fairly slow; but Niko had some other ideas: http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker/ http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-a... The initial implementation used differential dataflow, but this was just merged in: https://github.com/rust-lang-nursery/polonius/pull/36#issuecomment-390393717 https://github.com/rust-lang-nursery/polonius/pull/36#issuec... Very cool stuff!
- DannyBee 8y ago
  Yes, this is a very traditional alias formulation of these sets of problems, and there is a lot of work in the past 10 years on expressing and computing aliasing like systems in datalog. I don't know about rust, but the cost of that abstraction elsewhere is pretty good. Datalog will beat basic implementations, and those that most researchers have time to implement handily. However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is), so production compilers still currently eat the complexity of building alias solvers. It would be nice if one day that was not true.
  - tom_mellior 8y ago
    > However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is) Sure there is a reason: Many applications, alias analysis in particular, only use a subset of Datalog. Subsetting languages very often makes for easier and more efficient implementation. If you know that there is no negation in your alias problems, your special purpose solver can be much more efficient than a Datalog solver that must be prepared to deal with negation. Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver". As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower.
stickykbd 8y ago
For those who may have missed it, Mozilla is working on Datalog knowledge store backed by SQLite called Project Mentat [1] (also written in Rust). Announcement and rationale written by one of its devs can be found here [2]. Also previous HN discussion is located here [3]. [1] https://github.com/mozilla/mentat https://github.com/mozilla/mentat [2] https://medium.com/project-tofino/introducing-datomish-a-flexible-embedded-knowledge-store-1d7976bff344 https://medium.com/project-tofino/introducing-datomish-a-fle... [3] https://news.ycombinator.com/item?id=13568559 https://news.ycombinator.com/item?id=13568559
- trurl 8y ago
  I don't see any mention of recursion. If it doesn't support recursion it is not really accurate to call it Datalog. To clarify, if you don't have recursion, you've just got a slightly different skin over relational algebra.
myWindoonn 8y ago
What would be some advantages of this design over the µKanren design [0] which uses a search monad [1] and expresses unification and relations directly as plain values and functions? [0] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf [1] http://homes.soic.indiana.edu/ccshan/logicprog/LogicT-icfp2005.pdf http://homes.soic.indiana.edu/ccshan/logicprog/LogicT-icfp20...
- tom_mellior 8y ago
  Those papers and systems deal with Prolog-like languages, not Datalog-like ones. These are different languages, even though there is a common set of similar-looking programs with similar-ish declarative semantics but completely different procedural semantics. In particular, it's easy to write programs that easily compute the desired results when run on a Datalog system, but that run into an infinite loop when run on a Prolog system. Also, the solver here is special-cased to treat only a certain subset of Datalog that is much simpler than the full language.
  - convolvatron 8y ago
    it looks like it doesn't handle negation. one of those unfortunate but interesting features of the space of recursive declarative languages. if you allow something to be true only if something else is not true, your solution space is no longer monotonic. meaning that a result you thought was part of the solution can later be retracted. if there is a cycle (trivially "a if not a"), then you may not ever arrive at an answer. that might seem simple to detect, but that cycle can exist through an arbitrary number of rules and data dependencies, so in the limit is undecidable. ideally, as in this solver, you could keep adding terms you could show to be correct from the data and rules at hand until they and all their consequences have been found, and which point you can stop (fixed point). but negation screws up this plan. there are various restrictions on negation, solver heuristics, and partial conservative proofs of termination that can be applied. but this is where your beautiful simple declarative world starts getting sad and messy. [edit: I'd like to leave this because I wish I understood the problem with negation earlier, but I just skimmed and missed stratification, Frank thoughtfully explains below]
xvilka 8y ago
Since DataLog is just a subset of Prolog I want to link a very good book about modern Prolog and its applications [1]. [1]. https://www.metalevel.at/prolog https://www.metalevel.at/prolog
- trurl 8y ago
  While it is possible to view Datalog as a subset of Prolog, they are really very different languages. In particular Datalog implementations generally use forward rather than backwards chaining evaluation. As such, programs you might write in Datalog might diverge in naïve Prolog implementation. Depending on what variant and extensions of Datalog you are using, a program that you could write in the subset of Prolog that matches Datalog might similarly diverge in a Datalog engine. So really linking to a text on Prolog is not really relevant to a discussion of the merits of Datalog.
  - triska 8y ago
    Prolog and Datalog also have a lot in common: In addition to Datalog being a syntactic subset of Prolog, the semantics of Prolog and Datalog, and hence the solutions you obtain, are also identical if you enable SLG resolution in your Prolog system and run a Datalog program with it. SLG resolution (also called "tabling" in Prolog) prevents both positive and negative loops, and always terminates for programs that have the bounded term-size property, as is the case for all Datalog programs. XSB Prolog is a notable example of a Prolog system that supports this mode, which you can enable with the table/1 directive: http://xsb.sourceforge.net/shadow_site/manual1/node2.html http://xsb.sourceforge.net/shadow_site/manual1/node2.html Therefore, you can use a Prolog system such as XSB Prolog also to learn Datalog, and then seamlessly move to Prolog. Conversely, if you know Prolog, then learning Datalog is very easy. Another very nice system for learning Datalog is DES, which you can run in SICStus Prolog and other systems: http://des.sourceforge.net/ http://des.sourceforge.net/ Various extensions such as aggregate functions and object-oriented programming (which are mentioned in the Wikipedia entry for Datalog) are also applicable to both Prolog and Datalog with identical or closely related semantics.
    - 8y ago
wernsey 8y ago
Awesome. I look forward to browsing its code. I implemented a Datalog engine in Java a while back. Looking back on it now there are a bunch of things I might have done differently, but I've never tried to implement anything like it before. I remember that doing the stratified negation was quite complex and I won't be able to explain it of the top of my head anymore. Anyway, here's my version: https://github.com/wernsey/Jatalog https://github.com/wernsey/Jatalog
- ScottBurson 8y ago
  I may actually have a use for this. Thanks for releasing it! BTW the use of functional maps, such as those in [0], might have advantages over things like StackMap. Of course it would require some restructuring of the code. [0] https://github.com/slburson/fset-java https://github.com/slburson/fset-java
  - wernsey 8y ago
    Thank you. I'll take a look. In retrospect I think there might be several ways to improve performance by using other data structures to index the facts, but I haven't had the time to work on it lately. There is a pull request from someone that I'm still looking at, which might just spur me on to think about it some more.
justincormack 8y ago
If you want a Go implementation, look at OPA https://github.com/open-policy-agent/opa https://github.com/open-policy-agent/opa - designed for authorization but quite general.

207 points by dmit 8y ago

Nice! It's always good to see Datalog in action. In my experience, Datalog is often more convenient and more readable than SQL. As the post mentions, the current ergonomics ("a wall of definitions") are indeed the main shortcoming of the present approach, which is syntactically far removed from Datalog. My suggestion towards an automated conversion is to consider Prolog: Syntactically, a Datalog clause is a valid Prolog term. In fact, Datalog is a syntactic subset of Prolog. Therefore, it can be easily parsed with Prolog (using the predicate read/1), and then inspected via built-in mechanisms. You may be able to write a Prolog program that converts proper Datalog definitions to such Rust snippets.

a-saleh 8y ago
I think it will be better if we figure out how to do embedded catalog in other languages. I.e. I really liked The research here https://github.com/rntz/datafun https://github.com/rntz/datafun, where we start with "datalog=relational algebra+fixpoints" and then are trying to figure out how far can we take this in language where not everything is a table of facts :)
- convolvatron 8y ago
  schelog by Dorai Sitaram https://ds26gte.github.io/schelog/index.html https://ds26gte.github.io/schelog/index.html is a classic version of a funtional/declarative hybrid as a purely operational artifact. apparently its still being updated, but I remember it from many years ago (early 90s?). it uses the ability to return multiple times from a continuation to allow sets of results (streams or solution trees) to be expressed directly in scheme and intermixed freely with the functional subset. a 'nice' mixture of declarative and procedural would be really slick. i should go back and look at mozart/oz again. I'll definately see if my limited ability to deal with formalisms lets me understand the type system proposed in Datafun.
  - a-saleh 8y ago
    "Streams of solution trees" kinda reminds me of mikro-kanren [1]. When I was using Clojure roughly 3 years ago, kanren was quite popular embedded logic. W.r.t. Datafun, i learned about it from a talk its creator gave on strangeloop last year [2], for me it seemed quite approachable :) [1] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf [2] https://www.youtube.com/watch?v=gC295d3V9gE https://www.youtube.com/watch?v=gC295d3V9gE

steveklabnik 8y ago

For some interesting backlog here: As Rust moves from lexical to non-lexical lifetimes, there's been a few different ways of actually implementing it. The initial implementation had some bugs and was fairly slow; but Niko had some other ideas: http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker/ http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-a... The initial implementation used differential dataflow, but this was just merged in: https://github.com/rust-lang-nursery/polonius/pull/36#issuecomment-390393717 https://github.com/rust-lang-nursery/polonius/pull/36#issuec... Very cool stuff!

DannyBee 8y ago
Yes, this is a very traditional alias formulation of these sets of problems, and there is a lot of work in the past 10 years on expressing and computing aliasing like systems in datalog. I don't know about rust, but the cost of that abstraction elsewhere is pretty good. Datalog will beat basic implementations, and those that most researchers have time to implement handily. However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is), so production compilers still currently eat the complexity of building alias solvers. It would be nice if one day that was not true.
- tom_mellior 8y ago
  > However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is) Sure there is a reason: Many applications, alias analysis in particular, only use a subset of Datalog. Subsetting languages very often makes for easier and more efficient implementation. If you know that there is no negation in your alias problems, your special purpose solver can be much more efficient than a Datalog solver that must be prepared to deal with negation. Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver". As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower.

stickykbd 8y ago

For those who may have missed it, Mozilla is working on Datalog knowledge store backed by SQLite called Project Mentat [1] (also written in Rust). Announcement and rationale written by one of its devs can be found here [2]. Also previous HN discussion is located here [3]. [1] https://github.com/mozilla/mentat https://github.com/mozilla/mentat [2] https://medium.com/project-tofino/introducing-datomish-a-flexible-embedded-knowledge-store-1d7976bff344 https://medium.com/project-tofino/introducing-datomish-a-fle... [3] https://news.ycombinator.com/item?id=13568559 https://news.ycombinator.com/item?id=13568559

trurl 8y ago
I don't see any mention of recursion. If it doesn't support recursion it is not really accurate to call it Datalog. To clarify, if you don't have recursion, you've just got a slightly different skin over relational algebra.

myWindoonn 8y ago

What would be some advantages of this design over the µKanren design [0] which uses a search monad [1] and expresses unification and relations directly as plain values and functions? [0] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf [1] http://homes.soic.indiana.edu/ccshan/logicprog/LogicT-icfp2005.pdf http://homes.soic.indiana.edu/ccshan/logicprog/LogicT-icfp20...

tom_mellior 8y ago
Those papers and systems deal with Prolog-like languages, not Datalog-like ones. These are different languages, even though there is a common set of similar-looking programs with similar-ish declarative semantics but completely different procedural semantics. In particular, it's easy to write programs that easily compute the desired results when run on a Datalog system, but that run into an infinite loop when run on a Prolog system. Also, the solver here is special-cased to treat only a certain subset of Datalog that is much simpler than the full language.
- convolvatron 8y ago
  it looks like it doesn't handle negation. one of those unfortunate but interesting features of the space of recursive declarative languages. if you allow something to be true only if something else is not true, your solution space is no longer monotonic. meaning that a result you thought was part of the solution can later be retracted. if there is a cycle (trivially "a if not a"), then you may not ever arrive at an answer. that might seem simple to detect, but that cycle can exist through an arbitrary number of rules and data dependencies, so in the limit is undecidable. ideally, as in this solver, you could keep adding terms you could show to be correct from the data and rules at hand until they and all their consequences have been found, and which point you can stop (fixed point). but negation screws up this plan. there are various restrictions on negation, solver heuristics, and partial conservative proofs of termination that can be applied. but this is where your beautiful simple declarative world starts getting sad and messy. [edit: I'd like to leave this because I wish I understood the problem with negation earlier, but I just skimmed and missed stratification, Frank thoughtfully explains below]

xvilka 8y ago

Since DataLog is just a subset of Prolog I want to link a very good book about modern Prolog and its applications [1]. [1]. https://www.metalevel.at/prolog https://www.metalevel.at/prolog

trurl 8y ago
While it is possible to view Datalog as a subset of Prolog, they are really very different languages. In particular Datalog implementations generally use forward rather than backwards chaining evaluation. As such, programs you might write in Datalog might diverge in naïve Prolog implementation. Depending on what variant and extensions of Datalog you are using, a program that you could write in the subset of Prolog that matches Datalog might similarly diverge in a Datalog engine. So really linking to a text on Prolog is not really relevant to a discussion of the merits of Datalog.
- triska 8y ago
  Prolog and Datalog also have a lot in common: In addition to Datalog being a syntactic subset of Prolog, the semantics of Prolog and Datalog, and hence the solutions you obtain, are also identical if you enable SLG resolution in your Prolog system and run a Datalog program with it. SLG resolution (also called "tabling" in Prolog) prevents both positive and negative loops, and always terminates for programs that have the bounded term-size property, as is the case for all Datalog programs. XSB Prolog is a notable example of a Prolog system that supports this mode, which you can enable with the table/1 directive: http://xsb.sourceforge.net/shadow_site/manual1/node2.html http://xsb.sourceforge.net/shadow_site/manual1/node2.html Therefore, you can use a Prolog system such as XSB Prolog also to learn Datalog, and then seamlessly move to Prolog. Conversely, if you know Prolog, then learning Datalog is very easy. Another very nice system for learning Datalog is DES, which you can run in SICStus Prolog and other systems: http://des.sourceforge.net/ http://des.sourceforge.net/ Various extensions such as aggregate functions and object-oriented programming (which are mentioned in the Wikipedia entry for Datalog) are also applicable to both Prolog and Datalog with identical or closely related semantics.
  - 8y ago

wernsey 8y ago

Awesome. I look forward to browsing its code. I implemented a Datalog engine in Java a while back. Looking back on it now there are a bunch of things I might have done differently, but I've never tried to implement anything like it before. I remember that doing the stratified negation was quite complex and I won't be able to explain it of the top of my head anymore. Anyway, here's my version: https://github.com/wernsey/Jatalog https://github.com/wernsey/Jatalog

ScottBurson 8y ago
I may actually have a use for this. Thanks for releasing it! BTW the use of functional maps, such as those in [0], might have advantages over things like StackMap. Of course it would require some restructuring of the code. [0] https://github.com/slburson/fset-java https://github.com/slburson/fset-java
- wernsey 8y ago
  Thank you. I'll take a look. In retrospect I think there might be several ways to improve performance by using other data structures to index the facts, but I haven't had the time to work on it lately. There is a pull request from someone that I'm still looking at, which might just spur me on to think about it some more.

justincormack 8y ago

If you want a Go implementation, look at OPA https://github.com/open-policy-agent/opa https://github.com/open-policy-agent/opa - designed for authorization but quite general.