On 29/01/15 10:06, Christophe FAGOT [intactile DESIGN] wrote:
Hi Dave,
my answers and comments are in the following. It’s good to talk about RETE
engines :-)
Le 28 janv. 2015 à 19:33, Dave Reynolds <[email protected]> a écrit :
On 28/01/15 14:06, Christophe FAGOT [intactile DESIGN] wrote:
Hi Andy,
thanks for your answer, and I’m ok for the graph being a set of triples, it is
the (very good) reason explaining why only one triple is produced. But the
reasoner is not in forward model. It is a forward-RETE model, which means that
the forward rules have to work incrementally, allowing to add and remove
triples and maintaining the consistency of the model.
So in the case described by Sébastien, the forward-RETE model should not remove
the inferred triple since another rule has its body terms still validated. At
least, this last rule should have been fired in order to indicate it that the
triple which was not created previously (because it was still in the graph) is
going to be removed, so this last rule should produce it again.
The RETE engine stops once a triple has been deduced by one route. If you
attempt to track each possible route by which a triple could be deduced and
reference count them all then you will get a combinatoric explosion in numbers
of possible deduction paths and performance plummets (which is why naive truth
maintenance never worked out).
You don’t need to track each possible route to maintain the truth. In a
previous company Sébastien and I created a home-made RETE engine, and simple
counters stored with triples are enough to maintain the truth of the graph. The
counter is increased each time a triple is redundantly added, and decreased
when the triple is asked to be removed. The triple is really removed from the
graph when its counter is at 0. So, no combinatoric explosion.
The first version of the Jena engine did such reference counting but it
was later scrapped. Agreed that you don't have to store the deduction
path but you still have to follow each deduction path in order to
maintain the reference counts. For rule sets like OWL which involve lots
of equality reasoning there can be lots such such duplicate paths.
That's where the combinatorics bites. For the usages we were seeing with
Jena then the benefit of avoiding redundantly re-deriving deductions
outweighed the cost of have non-incremental deletes.
The Jena engine works around this by not attempting to handle removals incrementally at
all. A remove is supposed to mark the model as needing a new "prepare" stage
and the entire deduction process is run from scratch again the next time you query the
model.
So, if I well understand what you say, the RETE Engine is monotonic and
maintain the truth when adding some triples, but it’s not the case when triples
are removed. Am I true?
Yes.
If, when removing a triple, we want to maintain the truth in a graph managed by
the RETE engine, we have to do as if the engine was a classical forward one and
require a new « prepare » stage (meaning the removing of the whole previous
inferences). Am I true on this point too ?
Yes.
Dave
