On 12/12/2011 21:39, Maciej Gowin wrote:
I saw that there is an open issue for Opportunistic Backward Chaining:
https://issues.jboss.org/browse/JBRULES-3272

While I want to start working on this topic during my PhD thesis
my question is if there is any work done on this?
Is there any possibility to contribute in solving this issue?
Of course I know that there is already Prolog Style Query Based
Backward Chaining implemented.
Come onto irc to discuss:
http://www.jboss.org/drools/irc

As a quick summary drools supports unification and derivation queries, that work in the same way that you would expect from a prolog system. However in Drools those derivation trees can be fully materialised, like a materialized view in a database. What this means is that as the underlying ground terms change, the result set is updated to reflect that. So a query becomes a live view over a derivation tree.

This materilized tree almost gives us OBC, because each query + argument is materized on first request. The problem though is currently this derivation tree is unique to the caller. What we need to do is make any derivaition tree, query + arguments, available as a global cache. So when we go to execute a query, we first see if anyone else has, and if so we just re-use those results. If it doesn't exist in the global cache we execute the query, which results in it being cached. This same caching mechanism of query + arguments is used to stop infinite recursion, which is a problem solved by the "tabling algorithm".

I'm very close to a nieve implementation that effectively uses a hashmap as an ondemand cache of query results. The tabling algorithm actually recommends a tree instead, claiming better performance. I'll try and abstract the use of a hashmap so research in alternative "caching" algorithms can be tried out, to see which gives better performance.

Further work can look into a heurstic cache to evict unused query+argument results. When a query+arguments derivation tree is no longer used, we don't want to make it available for GC straight away, instead we should use some eviction queue that keeps around often requested query+argument derivation trees, but evicting older and not used often ones for GC. The heuristics would allow tuning of memory utilisation too, to stop the cache consuming all the memory.

I believe Davide has more he'd like to see built on this, for out of the box abductive reasoning. Btw this is probably more of a thread for the dev mailing list :)

Mark


_______________________________________________
rules-users mailing list
rules-users@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users