knowsys / nemo

A fast in-memory rule engine
https://knowsys.github.io/nemo-doc/
Apache License 2.0
75 stars 7 forks source link

Add support for nullary predicates #130

Open aannleax opened 1 year ago

aannleax commented 1 year ago

For now, rules with nullary predicates are not handled correctly (or at all, it'll probably just crash). This would be rule sets like

trigger() :- a(x, x) .
result(x, z) :- b(x, y), c(y, z), trigger() .

On first glance, a good approach would to implement nullary predicates in the logical layer in the TableManager and not have empty tables in the DatabaseInstance. The data structure for rules would then split nullary atoms into its own list, which would allow the TableManager to check the presence of the required "tables" before executing the rule. This would handle cases where the nullary atom appears in the body.

Nullary atoms in the head need a special execution strategy that does not return a Trie but rather a bool that indicates whether there is one match for the body. We have a special materialization function scan_is_empty that would need to be used. One thing to keep in mind is rules with multiple head atoms

same(x), trigger() :- a(x, x) .

It seems like you want to materialize the same(x) table and derive trigger(). But don't forget that results are sometimes not materialized, so here

b(x, y), trigger(), :- a(x, y) .

the table for b would just be a reference to the table for a and we would still need to derive trigger.

Implementing the above should make it trivial to support boolean conjunctive queries (assuming #126 is implemented).

mkroetzsch commented 1 year ago

In the absence of a fully engineered solution for "Boolean tries" and "Boolean tables", one could also emulate this by replacing nullary atoms like trigger() with unary ones such as trigger(0) (with 0 an int type without a dictionary entry). This should work in body and head. This translation should happen at the intersection of logical and physical layer.

Another primary task here seems to be that the parser needs to be updated to read this at all. Right now, there are errors when trying such programs.

aannleax commented 1 month ago

Might potentially be solved by #512.