13 ms·

I always fancied a database that worked like a dynamic version of prolog, with facts that could be added over time, queries that can use inference etc. I couldn

I always fancied a database that worked like a dynamic version of prolog, with facts that could be added over time, queries that can use inference etc. I couldn't really find anything that worked like that though, everything seemed to either have a fixed set of facts or didn't support inference. Looking for something like that is what first got me interested in differential dataflow. The fact that this is bottom up makes me think that you probably can't go crazy with the number of rules.

namibj 6y ago
This gives you dynamic facts, feed-forward rule application, and soon even dynamic rules. It doesn't actually care much about the number of rules, and more about how much memory it costs to materialize them. There are delta-join techniques to do at least most of that in linear memory (w.r.t. input size) though, and DDlog has at least experimental support for them.
aminechikhaoui 6y ago
There is already https://developer.logicblox.com/ https://developer.logicblox.com/ but it's proprietary owned by Infor nowadays.
flyingsilverfin 6y ago
The company I work for, Grakn Labs (grakn.ai), builds a database that does datalog + negation type rules! You can add/remove data as you go, and also add/remove rules in the schema over time. The terminology the post here uses is different from ours, but roughly we do "Backward-chaining", which starts from the query to the set of facts that are inserted, which the article calls "top-down".
- namibj 6y ago
  Do you handle incremental changes to the input data? Because that's the major selling point of DDlog: low-latency responses to changes in inputs.
  - flyingsilverfin 6y ago
    We don't do this right now - optimising for incremental changes is actually better done by maintaining forward-chaining inferences (like the OP) rather than backward chaining, and then invalidating and updating just the inferences that have modified dependencies. Which you want depends on use case often: if you have often changing data backward chaining is generally better, but if it's largely static you can get large performance wins by materialising all the inferences, once, via forward-chaining.
- seanmcdirmid 6y ago
  Isn’t datalog with backward chaining just prolog? Datalog was known for forward chaining (bottom up) while prolog was known for backward chaining, datalog with backward chaining sounds like a misnomer.
  - flyingsilverfin 6y ago
    You're not wrong - the other big difference between datalog and prolog is that datalog is a subset of prolog's functionality that enables forward-chaining to be safe (gets trickier with negation for example). I was mostly referring to the fact that Graql implements datalog semantics/capabilities, plus negation - but the execution strategy is backward-chaining.
triska 6y ago
Prolog provides this with so called dynamic predicates. For example, if we declare the predicate f/1 dynamic using the standard directive dynamic/1: :- dynamic(f/1). then we can assert new clauses for f/1 using the standard predicates asserta/1 and assertz/1: ?- asserta(f(a)), assertz(f(b)). true. We then get: ?- f(X). X = a ; X = b. Rules can also be asserted: ?- use_module(library(lists)), asserta((f(X):-length(_,X))). true. yielding: ?- f(X). X = 0 ; X = 1 ; X = 2 ; X = 3 ; ... I used Scryer Prolog to run these examples. Dynamic changes to the database have advantages and drawbacks. On the plus side, they let us incorporate new knowledge and rules, and we automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and we can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions.
- YeGoblynQueenne 6y ago
  >> Dynamic changes to the database have advantages and drawbacks. On the plus side, they let you incorporate knew knowledge and rules, and you automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and you can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions. I wonder if that is part of the benefits advertised by DDlog, the ability to update a program without having to worry about clause ordering (which one does not have to, with datalog and bottom-up evaluation) or generally side effects. Very tentatively, I'm guessing that, since datalog programs lack negation, any new facts or rules added to the (extensional) database will update the "output" of the database (its Herbrand model) monotonically, i.e. you'll see new facts comeing out but no facts will "disappear". I'm a bit unsure because the DDlog github is talking about functions and typed datalog and I'm not really sure how that works now.
  - 6y ago
ludsan 6y ago
I have been very interested in CHR (constraint handling rules) for this kind of activity. It was developed (I think) to provide a systematic basis for the various constraint libraries to 'speak the same language' instead of being implemented without knowledge of each other. I don't see much literature out there on it (after the mid-2000s) but it always seemed a conceptually elegant way of doing forward-chaining (and inference) in the way of most rules engines. It only has a few simple rules: simplification (remove data/rules), simpagation and propagation (new data). The best part is that it embeds very easily in Prolog.

namibj 6y ago

This gives you dynamic facts, feed-forward rule application, and soon even dynamic rules. It doesn't actually care much about the number of rules, and more about how much memory it costs to materialize them. There are delta-join techniques to do at least most of that in linear memory (w.r.t. input size) though, and DDlog has at least experimental support for them.

aminechikhaoui 6y ago

There is already https://developer.logicblox.com/ https://developer.logicblox.com/ but it's proprietary owned by Infor nowadays.

flyingsilverfin 6y ago

The company I work for, Grakn Labs (grakn.ai), builds a database that does datalog + negation type rules! You can add/remove data as you go, and also add/remove rules in the schema over time. The terminology the post here uses is different from ours, but roughly we do "Backward-chaining", which starts from the query to the set of facts that are inserted, which the article calls "top-down".

namibj 6y ago
Do you handle incremental changes to the input data? Because that's the major selling point of DDlog: low-latency responses to changes in inputs.
- flyingsilverfin 6y ago
  We don't do this right now - optimising for incremental changes is actually better done by maintaining forward-chaining inferences (like the OP) rather than backward chaining, and then invalidating and updating just the inferences that have modified dependencies. Which you want depends on use case often: if you have often changing data backward chaining is generally better, but if it's largely static you can get large performance wins by materialising all the inferences, once, via forward-chaining.
seanmcdirmid 6y ago
Isn’t datalog with backward chaining just prolog? Datalog was known for forward chaining (bottom up) while prolog was known for backward chaining, datalog with backward chaining sounds like a misnomer.
- flyingsilverfin 6y ago
  You're not wrong - the other big difference between datalog and prolog is that datalog is a subset of prolog's functionality that enables forward-chaining to be safe (gets trickier with negation for example). I was mostly referring to the fact that Graql implements datalog semantics/capabilities, plus negation - but the execution strategy is backward-chaining.

triska 6y ago

Prolog provides this with so called dynamic predicates. For example, if we declare the predicate f/1 dynamic using the standard directive dynamic/1: :- dynamic(f/1). then we can assert new clauses for f/1 using the standard predicates asserta/1 and assertz/1: ?- asserta(f(a)), assertz(f(b)). true. We then get: ?- f(X). X = a ; X = b. Rules can also be asserted: ?- use_module(library(lists)), asserta((f(X):-length(_,X))). true. yielding: ?- f(X). X = 0 ; X = 1 ; X = 2 ; X = 3 ; ... I used Scryer Prolog to run these examples. Dynamic changes to the database have advantages and drawbacks. On the plus side, they let us incorporate new knowledge and rules, and we automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and we can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions.

YeGoblynQueenne 6y ago
>> Dynamic changes to the database have advantages and drawbacks. On the plus side, they let you incorporate knew knowledge and rules, and you automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and you can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions. I wonder if that is part of the benefits advertised by DDlog, the ability to update a program without having to worry about clause ordering (which one does not have to, with datalog and bottom-up evaluation) or generally side effects. Very tentatively, I'm guessing that, since datalog programs lack negation, any new facts or rules added to the (extensional) database will update the "output" of the database (its Herbrand model) monotonically, i.e. you'll see new facts comeing out but no facts will "disappear". I'm a bit unsure because the DDlog github is talking about functions and typed datalog and I'm not really sure how that works now.
- 6y ago

ludsan 6y ago

I have been very interested in CHR (constraint handling rules) for this kind of activity. It was developed (I think) to provide a systematic basis for the various constraint libraries to 'speak the same language' instead of being implemented without knowledge of each other. I don't see much literature out there on it (after the mid-2000s) but it always seemed a conceptually elegant way of doing forward-chaining (and inference) in the way of most rules engines. It only has a few simple rules: simplification (remove data/rules), simpagation and propagation (new data). The best part is that it embeds very easily in Prolog.