[rules-users] Opportunistic Backward Chaining

[Mark Proctor]

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 at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20111212/f79e204a/attachment.html