Re: [rules-dev] [rules-users] Opportunistic Backward Chaining
Mark Proctor <mproctor <at> codehaus.org>
2011-12-12 22:28:44 GMT
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
_______________________________________________
rules-dev mailing list
rules-dev <at> lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-dev
RSS Feed