001: /******************************************************************
002: * File: RETEEngine.java
003: * Created by: Dave Reynolds
004: * Created on: 09-Jun-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RETEEngine.java,v 1.30 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.reasoner.*;
012: import com.hp.hpl.jena.reasoner.rulesys.*;
013: import com.hp.hpl.jena.graph.*;
014: import java.util.*;
015:
016: import com.hp.hpl.jena.util.OneToManyMap;
017: import com.hp.hpl.jena.util.PrintUtil;
018: import com.hp.hpl.jena.util.iterator.ConcatenatedIterator;
019:
020: import org.apache.commons.logging.Log;
021: import org.apache.commons.logging.LogFactory;
022:
023: /**
024: * A RETE version of the the forward rule system engine. It neeeds to reference
025: * an enclosing ForwardInfGraphI which holds the raw data and deductions.
026: *
027: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
028: * @version $Revision: 1.30 $ on $Date: 2008/01/02 12:06:16 $
029: */
030: public class RETEEngine implements FRuleEngineI {
031:
032: /** The parent InfGraph which is employing this engine instance */
033: protected ForwardRuleInfGraphI infGraph;
034:
035: /** Set of rules being used */
036: protected List rules;
037:
038: /** Map from predicate node to clause processor, Node_ANY is used for wildcard predicates */
039: protected OneToManyMap clauseIndex;
040:
041: /** Queue of newly added triples waiting to be processed */
042: protected List addsPending = new ArrayList();
043:
044: /** Queue of newly deleted triples waiting to be processed */
045: protected List deletesPending = new ArrayList();
046:
047: /** The conflict set of rules waiting to fire */
048: protected RETEConflictSet conflictSet;
049:
050: /** List of predicates used in rules to assist in fast data loading */
051: protected HashSet predicatesUsed;
052:
053: /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
054: protected boolean wildcardRule;
055:
056: /** Set to true to flag that derivations should be logged */
057: protected boolean recordDerivations;
058:
059: /** performance stats - number of rules fired */
060: long nRulesFired = 0;
061:
062: /** True if we have processed the axioms in the rule set */
063: boolean processedAxioms = false;
064:
065: /** True if all the rules are monotonic, so we short circuit the conflict set processing */
066: boolean isMonotonic = true;
067:
068: protected static Log logger = LogFactory.getLog(FRuleEngine.class);
069:
070: // =======================================================================
071: // Constructors
072:
073: /**
074: * Constructor.
075: * @param parent the F or FB infGraph that it using this engine, the parent graph
076: * holds the deductions graph and source data.
077: * @param rules the rule set to be processed
078: */
079: public RETEEngine(ForwardRuleInfGraphI parent, List rules) {
080: infGraph = parent;
081: this .rules = rules;
082: // Check if this is a monotonic rule set
083: isMonotonic = true;
084: for (Iterator i = rules.iterator(); i.hasNext();) {
085: Rule r = (Rule) i.next();
086: if (!r.isMonotonic()) {
087: isMonotonic = false;
088: break;
089: }
090: }
091: }
092:
093: /**
094: * Constructor. Build an empty engine to which rules must be added
095: * using setRuleStore().
096: * @param parent the F or FB infGraph that it using this engine, the parent graph
097: * holds the deductions graph and source data.
098: */
099: public RETEEngine(ForwardRuleInfGraphI parent) {
100: infGraph = parent;
101: }
102:
103: // =======================================================================
104: // Control methods
105:
106: /**
107: * Process all available data. This should be called once a deductions graph
108: * has be prepared and loaded with any precomputed deductions. It will process
109: * the rule axioms and all relevant existing exiting data entries.
110: * @param ignoreBrules set to true if rules written in backward notation should be ignored
111: * @param inserts the set of triples to be processed, normally this is the
112: * raw data graph but may include additional deductions made by preprocessing hooks
113: */
114: public void init(boolean ignoreBrules, Finder inserts) {
115: compile(rules, ignoreBrules);
116: findAndProcessAxioms();
117: fastInit(inserts);
118: }
119:
120: /**
121: * Process all available data. This version expects that all the axioms
122: * have already be preprocessed and the clause index already exists.
123: * @param inserts the set of triples to be processed, normally this is the
124: * raw data graph but may include additional deductions made by preprocessing hooks
125: */
126: public void fastInit(Finder inserts) {
127: conflictSet = new RETEConflictSet(new RETERuleContext(infGraph,
128: this ), isMonotonic);
129: // Below is used during testing to ensure that all ruleset work (if less efficiently) if marked as non-monotonic
130: // conflictSet = new RETEConflictSet(new RETERuleContext(infGraph, this), false);
131: findAndProcessActions();
132: if (infGraph.getRawGraph() != null) {
133: // Insert the data
134: if (wildcardRule) {
135: for (Iterator i = inserts.find(new TriplePattern(null,
136: null, null)); i.hasNext();) {
137: addTriple((Triple) i.next(), false);
138: }
139: } else {
140: for (Iterator p = predicatesUsed.iterator(); p
141: .hasNext();) {
142: Node predicate = (Node) p.next();
143: for (Iterator i = inserts.find(new TriplePattern(
144: null, predicate, null)); i.hasNext();) {
145: Triple t = (Triple) i.next();
146: addTriple(t, false);
147: }
148: }
149: }
150: }
151: // Run the engine
152: runAll();
153: }
154:
155: /**
156: * Add one triple to the data graph, run any rules triggered by
157: * the new data item, recursively adding any generated triples.
158: */
159: public synchronized void add(Triple t) {
160: addTriple(t, false);
161: runAll();
162: }
163:
164: /**
165: * Remove one triple to the data graph.
166: * @return true if the effects could be correctly propagated or
167: * false if not (in which case the entire engine should be restarted).
168: */
169: public synchronized boolean delete(Triple t) {
170: deleteTriple(t, false);
171: runAll();
172: return true;
173: }
174:
175: /**
176: * Return the number of rules fired since this rule engine instance
177: * was created and initialized
178: */
179: public long getNRulesFired() {
180: return nRulesFired;
181: }
182:
183: /**
184: * Return true if the internal engine state means that tracing is worthwhile.
185: * It will return false during the axiom bootstrap phase.
186: */
187: public boolean shouldTrace() {
188: return true;
189: // return processedAxioms;
190: }
191:
192: /**
193: * Set to true to enable derivation caching
194: */
195: public void setDerivationLogging(boolean recordDerivations) {
196: this .recordDerivations = recordDerivations;
197: }
198:
199: /**
200: * Access the precomputed internal rule form. Used when precomputing the
201: * internal axiom closures.
202: */
203: public Object getRuleStore() {
204: return new RuleStore(clauseIndex, predicatesUsed, wildcardRule,
205: isMonotonic);
206: }
207:
208: /**
209: * Set the internal rule from from a precomputed state.
210: */
211: public void setRuleStore(Object ruleStore) {
212: RuleStore rs = (RuleStore) ruleStore;
213: predicatesUsed = rs.predicatesUsed;
214: wildcardRule = rs.wildcardRule;
215: isMonotonic = rs.isMonotonic;
216:
217: // Clone the RETE network to this engine
218: RETERuleContext context = new RETERuleContext(infGraph, this );
219: Map netCopy = new HashMap();
220: clauseIndex = new OneToManyMap();
221: for (Iterator i = rs.clauseIndex.entrySet().iterator(); i
222: .hasNext();) {
223: Map.Entry entry = (Map.Entry) i.next();
224: clauseIndex.put(entry.getKey(), ((RETENode) entry
225: .getValue()).clone(netCopy, context));
226: }
227: }
228:
229: /**
230: * Add a rule firing request to the conflict set.
231: */
232: public void requestRuleFiring(Rule rule, BindingEnvironment env,
233: boolean isAdd) {
234: conflictSet.add(rule, env, isAdd);
235: }
236:
237: // =======================================================================
238: // Compiler support
239:
240: /**
241: * Compile a list of rules into the internal rule store representation.
242: * @param rules the list of Rule objects
243: * @param ignoreBrules set to true if rules written in backward notation should be ignored
244: */
245: public void compile(List rules, boolean ignoreBrules) {
246: clauseIndex = new OneToManyMap();
247: predicatesUsed = new HashSet();
248: wildcardRule = false;
249:
250: for (Iterator it = rules.iterator(); it.hasNext();) {
251: Rule rule = (Rule) it.next();
252: if (ignoreBrules && rule.isBackward())
253: continue;
254:
255: int numVars = rule.getNumVars();
256: boolean[] seenVar = new boolean[numVars];
257: RETESourceNode prior = null;
258:
259: for (int i = 0; i < rule.bodyLength(); i++) {
260: Object clause = rule.getBodyElement(i);
261: if (clause instanceof TriplePattern) {
262: // Create the filter node for this pattern
263: ArrayList clauseVars = new ArrayList(numVars);
264: RETEClauseFilter clauseNode = RETEClauseFilter
265: .compile((TriplePattern) clause, numVars,
266: clauseVars);
267: Node predicate = ((TriplePattern) clause)
268: .getPredicate();
269: if (predicate.isVariable()) {
270: clauseIndex.put(Node.ANY, clauseNode);
271: wildcardRule = true;
272: } else {
273: clauseIndex.put(predicate, clauseNode);
274: if (!wildcardRule) {
275: predicatesUsed.add(predicate);
276: }
277: }
278:
279: // Create list of variables which should be cross matched between the earlier clauses and this one
280: ArrayList matchIndices = new ArrayList(numVars);
281: for (Iterator iv = clauseVars.iterator(); iv
282: .hasNext();) {
283: int varIndex = ((Node_RuleVariable) iv.next())
284: .getIndex();
285: if (seenVar[varIndex])
286: matchIndices.add(new Byte((byte) varIndex));
287: seenVar[varIndex] = true;
288: }
289:
290: // Build the join node
291: if (prior == null) {
292: // First clause, no joins yet
293: prior = clauseNode;
294: } else {
295: RETEQueue leftQ = new RETEQueue(matchIndices);
296: RETEQueue rightQ = new RETEQueue(matchIndices);
297: leftQ.setSibling(rightQ);
298: rightQ.setSibling(leftQ);
299: clauseNode.setContinuation(rightQ);
300: prior.setContinuation(leftQ);
301: prior = leftQ;
302: }
303: }
304: }
305:
306: // Finished compiling a rule - add terminal
307: if (prior != null) {
308: RETETerminal term = createTerminal(rule);
309: prior.setContinuation(term);
310: }
311:
312: }
313:
314: if (wildcardRule)
315: predicatesUsed = null;
316: }
317:
318: /**
319: * Create a terminal node for the RETE network. Normally this is RETETerminal
320: * but some people have experimented with alternative delete handling by
321: * creating RETETerminal subclasses so this hook simplifies use of that
322: * approach.
323: */
324: protected RETETerminal createTerminal(Rule rule) {
325: return new RETETerminal(rule, this , infGraph);
326: }
327:
328: // =======================================================================
329: // Internal implementation methods
330:
331: /**
332: * Add a new triple to the network.
333: * @param triple the new triple
334: * @param deduction true if the triple has been generated by the rules and so should be
335: * added to the deductions graph.
336: */
337: public synchronized void addTriple(Triple triple, boolean deduction) {
338: if (infGraph.shouldTrace()) {
339: logger.debug("Add triple: " + PrintUtil.print(triple));
340: }
341: if (deletesPending.size() > 0)
342: deletesPending.remove(triple);
343: addsPending.add(triple);
344: if (deduction) {
345: infGraph.addDeduction(triple);
346: }
347: }
348:
349: /**
350: * Remove a new triple from the network.
351: * @param triple the new triple
352: * @param deduction true if the remove has been generated by the rules
353: */
354: public synchronized void deleteTriple(Triple triple,
355: boolean deduction) {
356: addsPending.remove(triple);
357: deletesPending.add(triple);
358: if (deduction) {
359: infGraph.getCurrentDeductionsGraph().delete(triple);
360: Graph raw = infGraph.getRawGraph();
361: // deduction retractions should not remove asserted facts, so commented out next line
362: // raw.delete(triple);
363: if (raw.contains(triple)) {
364: // Built in a graph which can't delete this triple
365: // so block further processing of this delete to avoid loops
366: deletesPending.remove(triple);
367: }
368: }
369: }
370:
371: /**
372: * Increment the rule firing count, called by the terminal nodes in the
373: * network.
374: */
375: protected void incRuleCount() {
376: nRulesFired++;
377: }
378:
379: /**
380: * Find the next pending add triple.
381: * @return the triple or null if there are none left.
382: */
383: protected synchronized Triple nextAddTriple() {
384: int size = addsPending.size();
385: if (size > 0) {
386: return (Triple) addsPending.remove(size - 1);
387: }
388: return null;
389: }
390:
391: /**
392: * Find the next pending add triple.
393: * @return the triple or null if there are none left.
394: */
395: protected synchronized Triple nextDeleteTriple() {
396: int size = deletesPending.size();
397: if (size > 0) {
398: return (Triple) deletesPending.remove(size - 1);
399: }
400: return null;
401: }
402:
403: /**
404: * Process the queue of pending insert/deletes until the queues are empty.
405: * Public to simplify unit tests - not normally called directly.
406: */
407: public void runAll() {
408: while (true) {
409: boolean isAdd = false;
410: Triple next = nextDeleteTriple();
411: if (next == null) {
412: next = nextAddTriple();
413: isAdd = true;
414: }
415: if (next == null) {
416: // Nothing more to inject, if this is a non-mon rule set now process one rule from the conflict set
417: if (conflictSet.isEmpty())
418: return; // Finished
419: conflictSet.fireOne();
420: } else {
421: inject(next, isAdd);
422: }
423: }
424: }
425:
426: /**
427: * Inject a single triple into the RETE network
428: */
429: private void inject(Triple t, boolean isAdd) {
430: if (infGraph.shouldTrace()) {
431: logger.debug((isAdd ? "Inserting" : "Deleting")
432: + " triple: " + PrintUtil.print(t));
433: }
434: Iterator i1 = clauseIndex.getAll(t.getPredicate());
435: Iterator i2 = clauseIndex.getAll(Node.ANY);
436: Iterator i = new ConcatenatedIterator(i1, i2);
437: while (i.hasNext()) {
438: RETEClauseFilter cf = (RETEClauseFilter) i.next();
439: // firedRules guard in here?
440: cf.fire(t, isAdd);
441: }
442: }
443:
444: /**
445: * This fires a triple into the current RETE network.
446: * This format of call is used in the unit testing but needs to be public
447: * because the tester is in another package.
448: */
449: public void testTripleInsert(Triple t) {
450: Iterator i1 = clauseIndex.getAll(t.getPredicate());
451: Iterator i2 = clauseIndex.getAll(Node.ANY);
452: Iterator i = new ConcatenatedIterator(i1, i2);
453: while (i.hasNext()) {
454: RETEClauseFilter cf = (RETEClauseFilter) i.next();
455: cf.fire(t, true);
456: }
457: }
458:
459: /**
460: * Scan the rules for any axioms and insert those
461: */
462: protected void findAndProcessAxioms() {
463: for (Iterator i = rules.iterator(); i.hasNext();) {
464: Rule r = (Rule) i.next();
465: if (r.isAxiom()) {
466: // An axiom
467: RETERuleContext context = new RETERuleContext(infGraph,
468: this );
469: context.setEnv(new BindingVector(new Node[r
470: .getNumVars()]));
471: context.setRule(r);
472: if (context.shouldFire(true)) {
473: RETEConflictSet.execute(context, true);
474: }
475: /* // Old version, left during debug and final checks
476: for (int j = 0; j < r.headLength(); j++) {
477: Object head = r.getHeadElement(j);
478: if (head instanceof TriplePattern) {
479: TriplePattern h = (TriplePattern) head;
480: Triple t = new Triple(h.getSubject(), h.getPredicate(), h.getObject());
481: addTriple(t, true);
482: }
483: }
484: */
485: }
486: }
487: processedAxioms = true;
488: }
489:
490: /**
491: * Scan the rules for any run actions and run those
492: */
493: protected void findAndProcessActions() {
494: RETERuleContext tempContext = new RETERuleContext(infGraph,
495: this );
496: for (Iterator i = rules.iterator(); i.hasNext();) {
497: Rule r = (Rule) i.next();
498: if (r.bodyLength() == 0) {
499: for (int j = 0; j < r.headLength(); j++) {
500: Object head = r.getHeadElement(j);
501: if (head instanceof Functor) {
502: Functor f = (Functor) head;
503: Builtin imp = f.getImplementor();
504: if (imp != null) {
505: tempContext.setRule(r);
506: tempContext.setEnv(new BindingVector(r
507: .getNumVars()));
508: imp.headAction(f.getArgs(), f
509: .getArgLength(), tempContext);
510: } else {
511: throw new ReasonerException(
512: "Invoking undefined Functor "
513: + f.getName() + " in "
514: + r.toShortString());
515: }
516: }
517: }
518: }
519: }
520: }
521:
522: //=======================================================================
523: // Inner classes
524:
525: /**
526: * Structure used in the clause index to indicate a particular
527: * clause in a rule. This is used purely as an internal data
528: * structure so we just use direct field access.
529: */
530: protected static class ClausePointer {
531:
532: /** The rule containing this clause */
533: protected Rule rule;
534:
535: /** The index of the clause in the rule body */
536: protected int index;
537:
538: /** constructor */
539: ClausePointer(Rule rule, int index) {
540: this .rule = rule;
541: this .index = index;
542: }
543:
544: /** Get the clause pointed to */
545: TriplePattern getClause() {
546: return (TriplePattern) rule.getBodyElement(index);
547: }
548: }
549:
550: /**
551: * Structure used to wrap up processed rule indexes.
552: */
553: public static class RuleStore {
554:
555: /** Map from predicate node to rule + clause, Node_ANY is used for wildcard predicates */
556: protected OneToManyMap clauseIndex;
557:
558: /** List of predicates used in rules to assist in fast data loading */
559: protected HashSet predicatesUsed;
560:
561: /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
562: protected boolean wildcardRule;
563:
564: /** True if all the rules are monotonic, so we short circuit the conflict set processing */
565: protected boolean isMonotonic = true;
566:
567: /** Constructor */
568: RuleStore(OneToManyMap clauseIndex, HashSet predicatesUsed,
569: boolean wildcardRule, boolean isMonotonic) {
570: this .clauseIndex = clauseIndex;
571: this .predicatesUsed = predicatesUsed;
572: this .wildcardRule = wildcardRule;
573: this .isMonotonic = isMonotonic;
574: }
575: }
576:
577: }
578:
579: /*
580: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
581: All rights reserved.
582:
583: Redistribution and use in source and binary forms, with or without
584: modification, are permitted provided that the following conditions
585: are met:
586:
587: 1. Redistributions of source code must retain the above copyright
588: notice, this list of conditions and the following disclaimer.
589:
590: 2. Redistributions in binary form must reproduce the above copyright
591: notice, this list of conditions and the following disclaimer in the
592: documentation and/or other materials provided with the distribution.
593:
594: 3. The name of the author may not be used to endorse or promote products
595: derived from this software without specific prior written permission.
596:
597: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
598: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
599: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
600: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
601: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
602: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
603: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
604: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
605: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
606: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
607: */
|