[rules-users] Opportunistic Backward Chaining

[Maciej Gowin]

Mark, thanks for quick answer. I will try to ping you on irc tommorow while
is getting late here in Poland.

2011/12/12 Mark Proctor <mproctor at codehaus.org>

>  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 listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
> _______________________________________________
> 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/20111213/86704c51/attachment.html