KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > rulesys > impl > RETEEngine


1 /******************************************************************
2  * File: RETEEngine.java
3  * Created by: Dave Reynolds
4  * Created on: 09-Jun-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: RETEEngine.java,v 1.21 2005/03/23 14:02:06 der Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl;
11
12 import com.hp.hpl.jena.reasoner.*;
13 import com.hp.hpl.jena.reasoner.rulesys.*;
14 import com.hp.hpl.jena.graph.*;
15 import java.util.*;
16
17 import com.hp.hpl.jena.util.OneToManyMap;
18 import com.hp.hpl.jena.util.PrintUtil;
19 import com.hp.hpl.jena.util.iterator.ConcatenatedIterator;
20
21 import org.apache.commons.logging.Log;
22 import org.apache.commons.logging.LogFactory;
23
24 /**
25  * A RETE version of the the forward rule system engine. It neeeds to reference
26  * an enclosing ForwardInfGraphI which holds the raw data and deductions.
27  *
28  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
29  * @version $Revision: 1.21 $ on $Date: 2005/03/23 14:02:06 $
30  */
31 public class RETEEngine implements FRuleEngineI {
32     
33     /** The parent InfGraph which is employing this engine instance */
34     protected ForwardRuleInfGraphI infGraph;
35     
36     /** Set of rules being used */
37     protected List rules;
38     
39     /** Map from predicate node to clause processor, Node_ANY is used for wildcard predicates */
40     protected OneToManyMap clauseIndex;
41     
42     /** Queue of newly added triples waiting to be processed */
43     protected List addsPending = new ArrayList();
44     
45     /** Queue of newly deleted triples waiting to be processed */
46     protected List deletesPending = new ArrayList();
47     
48     /** List of predicates used in rules to assist in fast data loading */
49     protected HashSet predicatesUsed;
50     
51     /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
52     protected boolean wildcardRule;
53      
54     /** Set to true to flag that derivations should be logged */
55     protected boolean recordDerivations;
56     
57     /** performance stats - number of rules fired */
58     long nRulesFired = 0;
59     
60     /** True if we have processed the axioms in the rule set */
61     boolean processedAxioms = false;
62     
63     protected static Log logger = LogFactory.getLog(FRuleEngine.class);
64     
65 // =======================================================================
66 // Constructors
67
68     /**
69      * Constructor.
70      * @param parent the F or FB infGraph that it using this engine, the parent graph
71      * holds the deductions graph and source data.
72      * @param rules the rule set to be processed
73      */
74     public RETEEngine(ForwardRuleInfGraphI parent, List rules) {
75         infGraph = parent;
76         this.rules = rules;
77     }
78
79     /**
80      * Constructor. Build an empty engine to which rules must be added
81      * using setRuleStore().
82      * @param parent the F or FB infGraph that it using this engine, the parent graph
83      * holds the deductions graph and source data.
84      */
85     public RETEEngine(ForwardRuleInfGraphI parent) {
86         infGraph = parent;
87     }
88     
89 // =======================================================================
90 // Control methods
91
92     /**
93      * Process all available data. This should be called once a deductions graph
94      * has be prepared and loaded with any precomputed deductions. It will process
95      * the rule axioms and all relevant existing exiting data entries.
96      * @param ignoreBrules set to true if rules written in backward notation should be ignored
97      * @param inserts the set of triples to be processed, normally this is the
98      * raw data graph but may include additional deductions made by preprocessing hooks
99      */
100     public void init(boolean ignoreBrules, Finder inserts) {
101         compile(rules, ignoreBrules);
102         findAndProcessAxioms();
103         fastInit(inserts);
104     }
105     
106     /**
107      * Process all available data. This version expects that all the axioms
108      * have already be preprocessed and the clause index already exists.
109      * @param inserts the set of triples to be processed, normally this is the
110      * raw data graph but may include additional deductions made by preprocessing hooks
111      */
112     public void fastInit(Finder inserts) {
113         findAndProcessActions();
114         if (infGraph.getRawGraph() != null) {
115             // Insert the data
116 if (wildcardRule) {
117                 for (Iterator i = inserts.find(new TriplePattern(null, null, null)); i.hasNext(); ) {
118                     addTriple((Triple)i.next(), false);
119                 }
120             } else {
121                 for (Iterator p = predicatesUsed.iterator(); p.hasNext(); ) {
122                     Node predicate = (Node)p.next();
123                     for (Iterator i = inserts.find(new TriplePattern(null, predicate, null)); i.hasNext(); ) {
124                         addTriple((Triple)i.next(), false);
125                     }
126                 }
127             }
128         }
129         // Run the engine
130 runAll();
131     }
132
133     /**
134      * Add one triple to the data graph, run any rules triggered by
135      * the new data item, recursively adding any generated triples.
136      */
137     public synchronized void add(Triple t) {
138         addTriple(t, false);
139         runAll();
140     }
141     
142     /**
143      * Remove one triple to the data graph.
144      * @return true if the effects could be correctly propagated or
145      * false if not (in which case the entire engine should be restarted).
146      */
147     public synchronized boolean delete(Triple t) {
148         deleteTriple(t, false);
149         runAll();
150         return true;
151     }
152     
153     /**
154      * Return the number of rules fired since this rule engine instance
155      * was created and initialized
156      */
157     public long getNRulesFired() {
158         return nRulesFired;
159     }
160     
161     /**
162      * Return true if the internal engine state means that tracing is worthwhile.
163      * It will return false during the axiom bootstrap phase.
164      */
165     public boolean shouldTrace() {
166         return true;
167 // return processedAxioms;
168 }
169
170     /**
171      * Set to true to enable derivation caching
172      */
173     public void setDerivationLogging(boolean recordDerivations) {
174         this.recordDerivations = recordDerivations;
175     }
176     
177     /**
178      * Access the precomputed internal rule form. Used when precomputing the
179      * internal axiom closures.
180      */
181     public Object JavaDoc getRuleStore() {
182         return new RuleStore(clauseIndex, predicatesUsed, wildcardRule);
183     }
184     
185     /**
186      * Set the internal rule from from a precomputed state.
187      */
188     public void setRuleStore(Object JavaDoc ruleStore) {
189         RuleStore rs = (RuleStore)ruleStore;
190         predicatesUsed = rs.predicatesUsed;
191         wildcardRule = rs.wildcardRule;
192         
193         // Clone the RETE network to this engine
194 RETERuleContext context = new RETERuleContext(infGraph, this);
195         Map netCopy = new HashMap();
196         clauseIndex = new OneToManyMap();
197         for (Iterator i = rs.clauseIndex.entrySet().iterator(); i.hasNext(); ) {
198             Map.Entry entry = (Map.Entry)i.next();
199             clauseIndex.put(entry.getKey(), ((RETENode)entry.getValue()).clone(netCopy, context));
200         }
201     }
202     
203 // =======================================================================
204 // Compiler support
205
206     /**
207      * Compile a list of rules into the internal rule store representation.
208      * @param rules the list of Rule objects
209      * @param ignoreBrules set to true if rules written in backward notation should be ignored
210      */
211     public void compile(List rules, boolean ignoreBrules) {
212         clauseIndex = new OneToManyMap();
213         predicatesUsed = new HashSet();
214         wildcardRule = false;
215             
216         for (Iterator it = rules.iterator(); it.hasNext(); ) {
217             Rule rule = (Rule)it.next();
218             if (ignoreBrules && rule.isBackward()) continue;
219             
220             int numVars = rule.getNumVars();
221             boolean[] seenVar = new boolean[numVars];
222             RETESourceNode prior = null;
223         
224             for (int i = 0; i < rule.bodyLength(); i++) {
225                 Object JavaDoc clause = rule.getBodyElement(i);
226                 if (clause instanceof TriplePattern) {
227                     // Create the filter node for this pattern
228 ArrayList clauseVars = new ArrayList(numVars);
229                     RETEClauseFilter clauseNode = RETEClauseFilter.compile((TriplePattern)clause, numVars, clauseVars);
230                     Node predicate = ((TriplePattern)clause).getPredicate();
231                     if (predicate.isVariable()) {
232                         clauseIndex.put(Node.ANY, clauseNode);
233                         wildcardRule = true;
234                     } else {
235                         clauseIndex.put(predicate, clauseNode);
236                         if (! wildcardRule) {
237                             predicatesUsed.add(predicate);
238                         }
239                     }
240                 
241                     // Create list of variables which should be cross matched between the earlier clauses and this one
242 ArrayList matchIndices = new ArrayList(numVars);
243                     for (Iterator iv = clauseVars.iterator(); iv.hasNext(); ) {
244                         int varIndex = ((Node_RuleVariable)iv.next()).getIndex();
245                         if (seenVar[varIndex]) matchIndices.add(new Byte JavaDoc((byte)varIndex));
246                         seenVar[varIndex] = true;
247                     }
248                 
249                     // Build the join node
250 if (prior == null) {
251                         // First clause, no joins yet
252 prior = clauseNode;
253                     } else {
254                         RETEQueue leftQ = new RETEQueue(matchIndices);
255                         RETEQueue rightQ = new RETEQueue(matchIndices);
256                         leftQ.setSibling(rightQ);
257                         rightQ.setSibling(leftQ);
258                         clauseNode.setContinuation(rightQ);
259                         prior.setContinuation(leftQ);
260                         prior = leftQ;
261                     }
262                 }
263             }
264             
265             // Finished compiling a rule - add terminal
266 if (prior != null) {
267                 RETETerminal term = new RETETerminal(rule, this, infGraph);
268                 prior.setContinuation(term);
269             }
270                     
271         }
272             
273         if (wildcardRule) predicatesUsed = null;
274     }
275
276 // =======================================================================
277 // Internal implementation methods
278
279     /**
280      * Add a new triple to the network.
281      * @param triple the new triple
282      * @param deduction true if the triple has been generated by the rules and so should be
283      * added to the deductions graph.
284      */
285     public synchronized void addTriple(Triple triple, boolean deduction) {
286         if (infGraph.shouldTrace()) {
287             logger.debug("Add triple: " + PrintUtil.print(triple));
288         }
289         if (deletesPending.size() > 0) deletesPending.remove(triple);
290         addsPending.add(triple);
291         if (deduction) {
292             infGraph.addDeduction(triple);
293         }
294     }
295
296     /**
297      * Remove a new triple from the network.
298      * @param triple the new triple
299      * @param deduction true if the remove has been generated by the rules
300      */
301     public synchronized void deleteTriple(Triple triple, boolean deduction) {
302         addsPending.remove(triple);
303         deletesPending.add(triple);
304         if (deduction) {
305             infGraph.getCurrentDeductionsGraph().delete(triple);
306             Graph raw = infGraph.getRawGraph();
307             // deduction retractions should not remove asserted facts, so commented out next line
308 // raw.delete(triple);
309 if (raw.contains(triple)) {
310                 // Built in a graph which can't delete this triple
311 // so block further processing of this delete to avoid loops
312 deletesPending.remove(triple);
313             }
314         }
315     }
316     
317     /**
318      * Increment the rule firing count, called by the terminal nodes in the
319      * network.
320      */
321     protected void incRuleCount() {
322         nRulesFired++;
323     }
324     
325     /**
326      * Find the next pending add triple.
327      * @return the triple or null if there are none left.
328      */
329     protected synchronized Triple nextAddTriple() {
330         int size = addsPending.size();
331         if (size > 0) {
332             return (Triple)addsPending.remove(size - 1);
333         }
334         return null;
335     }
336     
337     /**
338      * Find the next pending add triple.
339      * @return the triple or null if there are none left.
340      */
341     protected synchronized Triple nextDeleteTriple() {
342         int size = deletesPending.size();
343         if (size > 0) {
344             return (Triple)deletesPending.remove(size - 1);
345         }
346         return null;
347     }
348     
349     /**
350      * Process the queue of pending insert/deletes until the queues are empty.
351      * Public to simplify unit tests - not normally called directly.
352      */
353     public void runAll() {
354         while(true) {
355             boolean isAdd = false;
356             Triple next = nextDeleteTriple();
357             if (next == null) {
358                 next = nextAddTriple();
359                 if (next == null) return; // finished
360 isAdd = true;
361             }
362             if (infGraph.shouldTrace()) {
363                 logger.debug((isAdd ? "Inserting" : "Deleting") + " triple: " + PrintUtil.print(next));
364             }
365             Iterator i1 = clauseIndex.getAll(next.getPredicate());
366             Iterator i2 = clauseIndex.getAll(Node.ANY);
367             Iterator i = new ConcatenatedIterator(i1, i2);
368             while (i.hasNext()) {
369                 RETEClauseFilter cf = (RETEClauseFilter) i.next();
370                 // firedRules guard in here?
371 cf.fire(next, isAdd);
372             }
373         }
374     }
375     
376     
377     /**
378      * This fires a triple into the current RETE network.
379      * This format of call is used in the unit testing but needs to be public
380      * because the tester is in another package.
381      */
382     public void testTripleInsert(Triple t) {
383         Iterator i1 = clauseIndex.getAll(t.getPredicate());
384         Iterator i2 = clauseIndex.getAll(Node.ANY);
385         Iterator i = new ConcatenatedIterator(i1, i2);
386         while (i.hasNext()) {
387             RETEClauseFilter cf = (RETEClauseFilter) i.next();
388             cf.fire(t, true);
389         }
390     }
391     
392     /**
393      * Scan the rules for any axioms and insert those
394      */
395     protected void findAndProcessAxioms() {
396         for (Iterator i = rules.iterator(); i.hasNext(); ) {
397             Rule r = (Rule)i.next();
398             if (r.bodyLength() == 0) {
399                 // An axiom
400 for (int j = 0; j < r.headLength(); j++) {
401                     Object JavaDoc head = r.getHeadElement(j);
402                     if (head instanceof TriplePattern) {
403                         TriplePattern h = (TriplePattern) head;
404                         Triple t = new Triple(h.getSubject(), h.getPredicate(), h.getObject());
405                         addTriple(t, true);
406                     }
407                 }
408             }
409         }
410         processedAxioms = true;
411     }
412     
413     /**
414      * Scan the rules for any run actions and run those
415      */
416     protected void findAndProcessActions() {
417         RuleContext tempContext = new RETERuleContext(infGraph, this);
418         for (Iterator i = rules.iterator(); i.hasNext(); ) {
419             Rule r = (Rule)i.next();
420             if (r.bodyLength() == 0) {
421                 // An axiom
422 for (int j = 0; j < r.headLength(); j++) {
423                     Object JavaDoc head = r.getHeadElement(j);
424                     if (head instanceof Functor) {
425                         Functor f = (Functor)head;
426                         Builtin imp = f.getImplementor();
427                         if (imp != null) {
428                             tempContext.setRule(r);
429                             imp.headAction(f.getArgs(), f.getArgLength(), tempContext);
430                         } else {
431                             throw new ReasonerException("Invoking undefined Functor " + f.getName() +" in " + r.toShortString());
432                         }
433                     }
434                 }
435             }
436         }
437     }
438  
439 //=======================================================================
440 // Inner classes
441
442     /**
443      * Structure used in the clause index to indicate a particular
444      * clause in a rule. This is used purely as an internal data
445      * structure so we just use direct field access.
446      */
447     protected static class ClausePointer {
448         
449         /** The rule containing this clause */
450         protected Rule rule;
451         
452         /** The index of the clause in the rule body */
453         protected int index;
454         
455         /** constructor */
456         ClausePointer(Rule rule, int index) {
457             this.rule = rule;
458             this.index = index;
459         }
460         
461         /** Get the clause pointed to */
462         TriplePattern getClause() {
463             return (TriplePattern)rule.getBodyElement(index);
464         }
465     }
466     
467     /**
468      * Structure used to wrap up processed rule indexes.
469      */
470     public static class RuleStore {
471     
472         /** Map from predicate node to rule + clause, Node_ANY is used for wildcard predicates */
473         protected OneToManyMap clauseIndex;
474     
475         /** List of predicates used in rules to assist in fast data loading */
476         protected HashSet predicatesUsed;
477     
478         /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
479         protected boolean wildcardRule;
480         
481         /** Constructor */
482         RuleStore(OneToManyMap clauseIndex, HashSet predicatesUsed, boolean wildcardRule) {
483             this.clauseIndex = clauseIndex;
484             this.predicatesUsed = predicatesUsed;
485             this.wildcardRule = wildcardRule;
486         }
487     }
488
489 }
490
491
492 /*
493     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
494     All rights reserved.
495
496     Redistribution and use in source and binary forms, with or without
497     modification, are permitted provided that the following conditions
498     are met:
499
500     1. Redistributions of source code must retain the above copyright
501        notice, this list of conditions and the following disclaimer.
502
503     2. Redistributions in binary form must reproduce the above copyright
504        notice, this list of conditions and the following disclaimer in the
505        documentation and/or other materials provided with the distribution.
506
507     3. The name of the author may not be used to endorse or promote products
508        derived from this software without specific prior written permission.
509
510     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
511     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
512     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
513     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
514     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
515     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
516     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
517     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
518     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
519     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
520 */
Popular Tags