vaticle / typedb

TypeDB: the polymorphic database powered by types
https://typedb.com
Mozilla Public License 2.0
3.73k stars 338 forks source link

Redesign infinite recursion termination #6357

Closed jmsfltchr closed 2 years ago

jmsfltchr commented 3 years ago

Problem to Solve

Our base assumption has been that, without keeping track of state, the reasoner will recurse infinitely when it encounters recursive rules. Therefore we currently track whether we are in a recursive state and terminate when we are. We then find the missed answers via a reiteration step. This is costly in terms of performance (somewhat) and logical complexity within the actors.

Proposed Solution

During discussion we arrived at the conclusion that in the context of the actor-based model, where actors are de-duplicated, we may be able to question the base assumption. In that case we could let the flow be more natural and not have to "manually" detect recursion. This needs further discussion and design. This approach was deemed not possible, instead this has been implemented with a local re-exploration model.

jmsfltchr commented 2 years ago

Solved by https://github.com/vaticle/typedb/pull/6429