001: /******************************************************************
002: * File: FRuleEngine.java
003: * Created by: Dave Reynolds
004: * Created on: 28-May-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: FRuleEngine.java,v 1.28 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.*;
019: import com.hp.hpl.jena.vocabulary.RDF;
020:
021: import org.apache.commons.logging.Log;
022: import org.apache.commons.logging.LogFactory;
023:
024: /**
025: * The processing engine for forward production rules. It neeeds to reference
026: * an enclosing ForwardInfGraphI which holds the raw data and deductions.
027: *
028: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
029: * @version $Revision: 1.28 $ on $Date: 2008/01/02 12:06:16 $
030: */
031: public class FRuleEngine implements FRuleEngineI {
032:
033: /** The parent InfGraph which is employing this engine instance */
034: protected ForwardRuleInfGraphI infGraph;
035:
036: /** Set of rules being used */
037: protected List rules;
038:
039: /** Map from predicate node to rule + clause, Node_ANY is used for wildcard predicates */
040: protected OneToManyMap clauseIndex;
041:
042: /** List of predicates used in rules to assist in fast data loading */
043: protected HashSet predicatesUsed;
044:
045: /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
046: protected boolean wildcardRule;
047:
048: /** Set to true to flag that derivations should be logged */
049: protected boolean recordDerivations;
050:
051: /** performance stats - number of rules passing initial trigger */
052: int nRulesTriggered = 0;
053:
054: /** performance stats - number of rules fired */
055: long nRulesFired = 0;
056:
057: /** performance stats - number of rules fired during axiom initialization */
058: long nAxiomRulesFired = -1;
059:
060: /** True if we have processed the axioms in the rule set */
061: boolean processedAxioms = false;
062:
063: protected static Log logger = LogFactory.getLog(FRuleEngine.class);
064:
065: // =======================================================================
066: // Constructors
067:
068: /**
069: * Constructor.
070: * @param parent the F or FB infGraph that it using this engine, the parent graph
071: * holds the deductions graph and source data.
072: * @param rules the rule set to be processed
073: */
074: public FRuleEngine(ForwardRuleInfGraphI parent, List rules) {
075: infGraph = parent;
076: this .rules = rules;
077: }
078:
079: /**
080: * Constructor. Build an empty engine to which rules must be added
081: * using setRuleStore().
082: * @param parent the F or FB infGraph that it using this engine, the parent graph
083: * holds the deductions graph and source data.
084: */
085: public FRuleEngine(ForwardRuleInfGraphI parent) {
086: infGraph = parent;
087: }
088:
089: // =======================================================================
090: // Control methods
091:
092: /**
093: * Process all available data. This should be called once a deductions graph
094: * has be prepared and loaded with any precomputed deductions. It will process
095: * the rule axioms and all relevant existing exiting data entries.
096: * @param ignoreBrules set to true if rules written in backward notation should be ignored
097: * @param inserts the set of triples to be processed, normally this is the
098: * raw data graph but may include additional deductions made by preprocessing hooks
099: */
100: public void init(boolean ignoreBrules, Finder inserts) {
101: if (clauseIndex == null)
102: compile(rules, ignoreBrules);
103: findAndProcessAxioms();
104: nAxiomRulesFired = nRulesFired;
105: logger.debug("Axioms fired " + nAxiomRulesFired + " rules");
106: fastInit(inserts);
107: }
108:
109: /**
110: * Process all available data. This version expects that all the axioms
111: * have already be preprocessed and the clause index already exists.
112: * @param inserts the set of triples to be processed, normally this is the
113: * raw data graph but may include additional deductions made by preprocessing hooks
114: */
115: public void fastInit(Finder inserts) {
116: findAndProcessActions();
117: // Create the reasoning context
118: BFRuleContext context = new BFRuleContext(infGraph);
119: // Insert the data
120: if (wildcardRule) {
121: for (Iterator i = inserts.find(new TriplePattern(null,
122: null, null)); i.hasNext();) {
123: context.addTriple((Triple) i.next());
124: }
125: } else {
126: for (Iterator p = predicatesUsed.iterator(); p.hasNext();) {
127: Node predicate = (Node) p.next();
128: for (Iterator i = inserts.find(new TriplePattern(null,
129: predicate, null)); i.hasNext();) {
130: context.addTriple((Triple) i.next());
131: }
132: }
133: }
134: // Run the engine
135: addSet(context);
136: }
137:
138: /**
139: * Add one triple to the data graph, run any rules triggered by
140: * the new data item, recursively adding any generated triples.
141: */
142: public synchronized void add(Triple t) {
143: BFRuleContext context = new BFRuleContext(infGraph);
144: context.addTriple(t);
145: addSet(context);
146: }
147:
148: /**
149: * Remove one triple to the data graph.
150: * @return true if the effects could be correctly propagated or
151: * false if not (in which case the entire engine should be restarted).
152: */
153: public synchronized boolean delete(Triple t) {
154: // Incremental delete not supported
155: return false;
156: }
157:
158: /**
159: * Return the number of rules fired since this rule engine instance
160: * was created and initialized
161: */
162: public long getNRulesFired() {
163: return nRulesFired;
164: }
165:
166: /**
167: * Return true if the internal engine state means that tracing is worthwhile.
168: * It will return false during the axiom bootstrap phase.
169: */
170: public boolean shouldTrace() {
171: // return processedAxioms;
172: return true;
173: }
174:
175: /**
176: * Set to true to enable derivation caching
177: */
178: public void setDerivationLogging(boolean recordDerivations) {
179: this .recordDerivations = recordDerivations;
180: }
181:
182: /**
183: * Access the precomputed internal rule form. Used when precomputing the
184: * internal axiom closures.
185: */
186: public Object getRuleStore() {
187: return new RuleStore(clauseIndex, predicatesUsed, wildcardRule);
188: }
189:
190: /**
191: * Set the internal rule from from a precomputed state.
192: */
193: public void setRuleStore(Object ruleStore) {
194: RuleStore rs = (RuleStore) ruleStore;
195: clauseIndex = rs.clauseIndex;
196: predicatesUsed = rs.predicatesUsed;
197: wildcardRule = rs.wildcardRule;
198: }
199:
200: // =======================================================================
201: // Internal methods
202:
203: /**
204: * Add a set of new triple to the data graph, run any rules triggered by
205: * the new data item, recursively adding any generated triples.
206: * Technically the triples having been physically added to either the
207: * base or deduction graphs and the job of this function is just to
208: * process the stack of additions firing any relevant rules.
209: * @param context a context containing a set of new triples to be added
210: */
211: public void addSet(BFRuleContext context) {
212: Triple t;
213: while ((t = context.getNextTriple()) != null) {
214: if (infGraph.shouldTrace()) {
215: logger.info("Processing: " + PrintUtil.print(t));
216: }
217: // Check for rule triggers
218: HashSet firedRules = new HashSet();
219: Iterator i1 = clauseIndex.getAll(t.getPredicate());
220: Iterator i2 = clauseIndex.getAll(Node.ANY);
221: Iterator i = new ConcatenatedIterator(i1, i2);
222: while (i.hasNext()) {
223: ClausePointer cp = (ClausePointer) i.next();
224: if (firedRules.contains(cp.rule))
225: continue;
226: context.resetEnv(cp.rule.getNumVars());
227: TriplePattern trigger = (TriplePattern) cp.rule
228: .getBodyElement(cp.index);
229: if (match(trigger, t, context.getEnvStack())) {
230: nRulesTriggered++;
231: context.setRule(cp.rule);
232: if (matchRuleBody(cp.index, context)) {
233: firedRules.add(cp.rule);
234: nRulesFired++;
235: }
236: }
237: }
238: }
239: }
240:
241: /**
242: * Compile a list of rules into the internal rule store representation.
243: * @param rules the list of Rule objects
244: * @param ignoreBrules set to true if rules written in backward notation should be ignored
245: * @return an object that can be installed into the engine using setRuleStore.
246: */
247: public void compile(List rules, boolean ignoreBrules) {
248: clauseIndex = new OneToManyMap();
249: predicatesUsed = new HashSet();
250: wildcardRule = false;
251:
252: for (Iterator i = rules.iterator(); i.hasNext();) {
253: Rule r = (Rule) i.next();
254: if (ignoreBrules && r.isBackward())
255: continue;
256: Object[] body = r.getBody();
257: for (int j = 0; j < body.length; j++) {
258: if (body[j] instanceof TriplePattern) {
259: Node predicate = ((TriplePattern) body[j])
260: .getPredicate();
261: ClausePointer cp = new ClausePointer(r, j);
262: if (predicate.isVariable()) {
263: clauseIndex.put(Node.ANY, cp);
264: wildcardRule = true;
265: } else {
266: clauseIndex.put(predicate, cp);
267: if (!wildcardRule) {
268: predicatesUsed.add(predicate);
269: }
270: }
271: }
272: }
273: }
274:
275: if (wildcardRule)
276: predicatesUsed = null;
277: }
278:
279: /**
280: * Scan the rules for any axioms and insert those
281: */
282: protected void findAndProcessAxioms() {
283: BFRuleContext context = new BFRuleContext(infGraph);
284: for (Iterator i = rules.iterator(); i.hasNext();) {
285: Rule r = (Rule) i.next();
286: if (r.bodyLength() == 0) {
287: // An axiom
288: for (int j = 0; j < r.headLength(); j++) {
289: Object head = r.getHeadElement(j);
290: if (head instanceof TriplePattern) {
291: TriplePattern h = (TriplePattern) head;
292: Triple t = new Triple(h.getSubject(), h
293: .getPredicate(), h.getObject());
294: context.addTriple(t);
295: infGraph.getDeductionsGraph().add(t);
296: }
297: }
298: }
299: }
300: addSet(context);
301: processedAxioms = true;
302: }
303:
304: /**
305: * Scan the rules for any actions and run those
306: */
307: protected void findAndProcessActions() {
308: BFRuleContext context = new BFRuleContext(infGraph);
309: for (Iterator i = rules.iterator(); i.hasNext();) {
310: Rule r = (Rule) i.next();
311: if (r.bodyLength() == 0) {
312: // An axiom
313: for (int j = 0; j < r.headLength(); j++) {
314: Object head = r.getHeadElement(j);
315: if (head instanceof Functor) {
316: Functor f = (Functor) head;
317: Builtin imp = f.getImplementor();
318: if (imp != null) {
319: context.setRule(r);
320: imp.headAction(f.getArgs(), f
321: .getArgLength(), context);
322: } else {
323: throw new ReasonerException(
324: "Invoking undefined Functor "
325: + f.getName() + " in "
326: + r.toShortString());
327: }
328: }
329: }
330: }
331: }
332: }
333:
334: /**
335: * Match the rest of a set of rule clauses once an initial rule
336: * trigger has fired. Carries out any actions as a side effect.
337: * @param trigger the index of the clause which has already be successfully matched
338: * @param context a context containing a set of new triples to be added
339: * @return true if the rule actually fires
340: */
341: private boolean matchRuleBody(int trigger, BFRuleContext context) {
342: Rule rule = context.getRule();
343: // Create an ordered list of body clauses to process, best at the end
344: Object[] body = rule.getBody();
345: int len = body.length;
346: ArrayList clauses = new ArrayList(len - 1);
347:
348: if (len <= 1) {
349: // No clauses to add, just fall through to clause matcher
350: } else if (len == 2) {
351: // Only one clause remaining, no reordering necessary
352: Object clause = body[trigger == 0 ? 1 : 0];
353: if (clause instanceof TriplePattern) {
354: clauses.add(clause);
355: }
356: } else {
357: // Pick most bound remaining clause as the best one to go first
358: int bestscore = 0;
359: int best = -1;
360: for (int i = 0; i < len; i++) {
361: if (i == trigger)
362: continue; // Skip the clause already processed
363: BindingStack env = context.getEnvStack();
364: if (body[i] instanceof TriplePattern) {
365: TriplePattern clause = (TriplePattern) body[i];
366: int score = scoreNodeBoundness(clause.getSubject(),
367: env)
368: * 3
369: + scoreNodeBoundness(clause.getPredicate(),
370: env)
371: * 2
372: + scoreNodeBoundness(clause.getObject(),
373: env) * 3;
374: if (score > bestscore) {
375: bestscore = score;
376: best = i;
377: }
378: }
379: }
380:
381: for (int i = 0; i < len; i++) {
382: if (i == trigger || i == best)
383: continue;
384: if (body[i] instanceof TriplePattern) {
385: clauses.add(body[i]);
386: }
387: }
388: if (best != -1)
389: clauses.add(body[best]);
390: }
391:
392: // Call a recursive clause matcher in the ordered list of clauses
393: boolean matched = matchClauseList(clauses, context);
394: if (matched) {
395: // We have new deductions stashed which now want to be
396: // asserted as deductions and then added to processing stack
397: context.flushPending();
398: }
399: return matched;
400: }
401:
402: /**
403: * Match each of a list of clauses in turn. For all bindings for which all
404: * clauses match check the remaining clause guards and fire the rule actions.
405: * @param clauses the list of clauses to match, start with last clause
406: * @param context a context containing a set of new triples to be added
407: * @return true if the rule actually fires
408: */
409: private boolean matchClauseList(List clauses, BFRuleContext context) {
410: Rule rule = context.getRule();
411: BindingStack env = context.getEnvStack();
412: int index = clauses.size() - 1;
413: if (index == -1) {
414: // Check any non-pattern clauses
415: for (int i = 0; i < rule.bodyLength(); i++) {
416: Object clause = rule.getBodyElement(i);
417: if (clause instanceof Functor) {
418: // Fire a built in
419: if (!((Functor) clause).evalAsBodyClause(context)) {
420: return false; // guard failed
421: }
422: }
423: }
424: // Now fire the rule
425: if (infGraph.shouldTrace()) {
426: logger.info("Fired rule: " + rule.toShortString()
427: + " = " + rule.instantiate(env));
428: }
429: List matchList = null;
430: if (recordDerivations) {
431: // Create derivation record
432: matchList = new ArrayList(rule.bodyLength());
433: for (int i = 0; i < rule.bodyLength(); i++) {
434: Object clause = rule.getBodyElement(i);
435: if (clause instanceof TriplePattern) {
436: matchList.add(env
437: .instantiate((TriplePattern) clause));
438: }
439: }
440: }
441: for (int i = 0; i < rule.headLength(); i++) {
442: Object hClause = rule.getHeadElement(i);
443: if (hClause instanceof TriplePattern) {
444: Triple t = env.instantiate((TriplePattern) hClause);
445: if (!t.getSubject().isLiteral()) {
446: // Only add the result if it is legal at the RDF level.
447: // E.g. RDFS rules can create assertions about literals
448: // that we can't record in RDF
449: if (!context.contains(t)) {
450: context.add(t);
451: if (recordDerivations) {
452: infGraph.logDerivation(t,
453: new RuleDerivation(rule, t,
454: matchList, infGraph));
455: }
456: }
457: }
458: } else if (hClause instanceof Functor) {
459: Functor f = (Functor) hClause;
460: Builtin imp = f.getImplementor();
461: if (imp != null) {
462: imp.headAction(f.getBoundArgs(env), f
463: .getArgLength(), context);
464: } else {
465: throw new ReasonerException(
466: "Invoking undefined Functor "
467: + f.getName() + " in "
468: + rule.toShortString());
469: }
470: } else if (hClause instanceof Rule) {
471: Rule r = (Rule) hClause;
472: if (r.isBackward()) {
473: infGraph.addBRule(r.instantiate(env));
474: } else {
475: throw new ReasonerException(
476: "Found non-backward subrule : " + r);
477: }
478: }
479: }
480: return true;
481: }
482: // More clauses left to match ...
483: ArrayList clausesCopy = (ArrayList) ((ArrayList) clauses)
484: .clone();
485: TriplePattern clause = (TriplePattern) clausesCopy
486: .remove(index);
487: Node objPattern = env.getBinding(clause.getObject());
488: if (Functor.isFunctor(objPattern)) {
489: // Can't search on functor patterns so leave that as a wildcard
490: objPattern = null;
491: }
492: Iterator i = infGraph.findDataMatches(env.getBinding(clause
493: .getSubject()), env.getBinding(clause.getPredicate()),
494: env.getBinding(objPattern));
495: boolean foundMatch = false;
496: while (i.hasNext()) {
497: Triple t = (Triple) i.next();
498: // Add the bindings to the environment
499: env.push();
500: if (match(clause.getPredicate(), t.getPredicate(), env)
501: && match(clause.getObject(), t.getObject(), env)
502: && match(clause.getSubject(), t.getSubject(), env)) {
503: foundMatch |= matchClauseList(clausesCopy, context);
504: }
505: env.unwind();
506: }
507: return foundMatch;
508: }
509:
510: /**
511: * Score a Node in terms of groundedness - heuristic.
512: * Treats a variable as better than a wildcard because it constrains
513: * later clauses. Treats rdf:type as worse than any other ground node
514: * because that tends to link to lots of expensive rules.
515: */
516: public static int scoreNodeBoundness(Node n, BindingEnvironment env) {
517: if (n instanceof Node_ANY) {
518: return 0;
519: } else if (n instanceof Node_RuleVariable) {
520: Node val = env.getGroundVersion(n);
521: if (val == null) {
522: return 1;
523: } else if (val.equals(RDF.type.asNode())) {
524: return 2;
525: } else {
526: return 3;
527: }
528: } else {
529: return 3;
530: }
531: }
532:
533: // /**
534: // * Instantiate a triple pattern against the current environment.
535: // * This version handles unbound varibles by turning them into bNodes.
536: // * @param clause the triple pattern to match
537: // * @param env the current binding environment
538: // * @return a new, instantiated triple
539: // */
540: // public static Triple instantiate(TriplePattern pattern, BindingStack env) {
541: // Node s = env.getBinding(pattern.getSubject());
542: // if (s == null) s = Node.createAnon();
543: // Node p = env.getBinding(pattern.getPredicate());
544: // if (p == null) p = Node.createAnon();
545: // Node o = env.getBinding(pattern.getObject());
546: // if (o == null) o = Node.createAnon();
547: // return new Triple(s, p, o);
548: // }
549:
550: /**
551: * Test if a TriplePattern matches a Triple in the given binding
552: * environment. If it does then the binding environment is modified
553: * the reflect any additional bindings.
554: * @return true if the pattern matches the triple
555: */
556: public static boolean match(TriplePattern pattern, Triple triple,
557: BindingStack env) {
558: env.push();
559: boolean matchOK = match(pattern.getPredicate(), triple
560: .getPredicate(), env)
561: && match(pattern.getObject(), triple.getObject(), env)
562: && match(pattern.getSubject(), triple.getSubject(), env);
563: if (matchOK) {
564: env.commit();
565: return true;
566: } else {
567: env.unwind();
568: return false;
569: }
570: }
571:
572: /**
573: * Test if a pattern Node matches a Triple Node in the given binding
574: * environment. If it does then the binding environment is modified
575: * the reflect any additional bindings.
576: * @return true if the pattern matches the node
577: */
578: public static boolean match(Node pattern, Node node,
579: BindingStack env) {
580: if (pattern instanceof Node_RuleVariable) {
581: int index = ((Node_RuleVariable) pattern).getIndex();
582: return env.bind(index, node);
583: } else if (pattern instanceof Node_ANY) {
584: return true;
585: } else if (Functor.isFunctor(pattern)) {
586: if (!Functor.isFunctor(node))
587: return false;
588: Functor patternF = (Functor) pattern.getLiteralValue();
589: Functor nodeF = (Functor) node.getLiteralValue();
590: if (!patternF.getName().equals(nodeF.getName()))
591: return false;
592: Node[] patternArgs = patternF.getArgs();
593: Node[] nodeArgs = nodeF.getArgs();
594: // if (patternF.isGround()) {
595: // return Arrays.equals(patternArgs, nodeArgs);
596: // } else {
597: if (patternArgs.length != nodeArgs.length)
598: return false;
599: // Compatible functor shapes so bind an embedded variables in the pattern
600: env.push();
601: boolean matchOK = true;
602: for (int i = 0; i < patternArgs.length; i++) {
603: if (!match(patternArgs[i], nodeArgs[i], env)) {
604: matchOK = false;
605: break;
606: }
607: }
608: if (matchOK) {
609: env.commit();
610: return true;
611: } else {
612: env.unwind();
613: return false;
614: }
615: // }
616: } else {
617: return pattern.sameValueAs(node);
618: }
619: }
620:
621: //=======================================================================
622: // Inner classes
623:
624: /**
625: * Structure used in the clause index to indicate a particular
626: * clause in a rule. This is used purely as an internal data
627: * structure so we just use direct field access.
628: */
629: protected static class ClausePointer {
630:
631: /** The rule containing this clause */
632: protected Rule rule;
633:
634: /** The index of the clause in the rule body */
635: protected int index;
636:
637: /** constructor */
638: ClausePointer(Rule rule, int index) {
639: this .rule = rule;
640: this .index = index;
641: }
642:
643: /** Get the clause pointed to */
644: TriplePattern getClause() {
645: return (TriplePattern) rule.getBodyElement(index);
646: }
647: }
648:
649: /**
650: * Structure used to wrap up processed rule indexes.
651: */
652: public static class RuleStore {
653:
654: /** Map from predicate node to rule + clause, Node_ANY is used for wildcard predicates */
655: protected OneToManyMap clauseIndex;
656:
657: /** List of predicates used in rules to assist in fast data loading */
658: protected HashSet predicatesUsed;
659:
660: /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
661: protected boolean wildcardRule;
662:
663: /** Constructor */
664: RuleStore(OneToManyMap clauseIndex, HashSet predicatesUsed,
665: boolean wildcardRule) {
666: this .clauseIndex = clauseIndex;
667: this .predicatesUsed = predicatesUsed;
668: this .wildcardRule = wildcardRule;
669: }
670: }
671:
672: }
673:
674: /*
675: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
676: All rights reserved.
677:
678: Redistribution and use in source and binary forms, with or without
679: modification, are permitted provided that the following conditions
680: are met:
681:
682: 1. Redistributions of source code must retain the above copyright
683: notice, this list of conditions and the following disclaimer.
684:
685: 2. Redistributions in binary form must reproduce the above copyright
686: notice, this list of conditions and the following disclaimer in the
687: documentation and/or other materials provided with the distribution.
688:
689: 3. The name of the author may not be used to endorse or promote products
690: derived from this software without specific prior written permission.
691:
692: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
693: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
694: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
695: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
696: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
697: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
698: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
699: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
700: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
701: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
702: */
|