001: /******************************************************************
002: * File: BasicBackwardRuleInfGraph.java
003: * Created by: Dave Reynolds
004: * Created on: 03-May-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: BasicBackwardRuleInfGraph.java,v 1.11 2008/01/02 12:09:44 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
010:
011: import com.hp.hpl.jena.reasoner.rulesys.*;
012: import com.hp.hpl.jena.reasoner.rulesys.impl.*;
013: import com.hp.hpl.jena.reasoner.*;
014: import com.hp.hpl.jena.graph.*;
015:
016: import java.util.*;
017:
018: import com.hp.hpl.jena.util.OneToManyMap;
019: import com.hp.hpl.jena.util.iterator.*;
020: import org.apache.commons.logging.Log;
021: import org.apache.commons.logging.LogFactory;
022:
023: /**
024: * An inference graph that runs a set of rules using a tabled
025: * backward chaining interpreter.
026: *
027: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
028: * @version $Revision: 1.11 $ on $Date: 2008/01/02 12:09:44 $
029: */
030: public class BasicBackwardRuleInfGraph extends BaseInfGraph implements
031: BackwardRuleInfGraphI {
032:
033: //=======================================================================
034: // variables
035:
036: /** Set for rules being used */
037: protected List rules;
038:
039: /** Table of derivation records, maps from triple to RuleDerivation */
040: protected OneToManyMap derivations;
041:
042: /** An optional graph of separate schema assertions that should also be processed */
043: protected FGraph fschema;
044:
045: /** Cache of deductions made from the rules */
046: protected FGraph fdeductions;
047:
048: /** A finder that searches across the data, schema and axioms */
049: protected Finder dataFind;
050:
051: /** The core rule engine which includes all the memoized results */
052: protected BRuleEngine engine;
053:
054: /** Single context for the reasoner, used when passing information to builtins */
055: protected BBRuleContext context;
056:
057: /** Cache of temporary property values inferred through getTemp calls */
058: protected TempNodeCache tempNodecache;
059:
060: /** performance stats - number of rules passing initial trigger */
061: int nRulesTriggered = 0;
062:
063: /** performance stats - number of rules fired */
064: long nRulesFired = 0;
065:
066: /** threshold on the numbers of rule firings allowed in a single operation */
067: long nRulesThreshold = DEFAULT_RULES_THRESHOLD;
068:
069: /** Flag which, if true, enables tracing of rule actions to logger.info */
070: boolean traceOn = false;
071:
072: /** Default setting for rules threshold */
073: public static final long DEFAULT_RULES_THRESHOLD = 500000;
074:
075: static Log logger = LogFactory
076: .getLog(BasicBackwardRuleInfGraph.class);
077:
078: //=======================================================================
079: // Core methods
080:
081: /**
082: * Constructor. Create a new backward inference graph to process
083: * the given data. The parent reasoner supplies the ruleset and
084: * any additional schema graph.
085: *
086: * @param reasoner the parent reasoner
087: * @param ruleStore the indexed set of rules to use
088: * @param data the data graph to be processed
089: * @param schema optional precached schema (use null if not required)
090: */
091: public BasicBackwardRuleInfGraph(Reasoner reasoner,
092: RuleStore ruleStore, Graph data, Graph schema) {
093: super (data, reasoner);
094: if (schema != null) {
095: fschema = new FGraph(schema);
096: }
097: rules = ruleStore.getAllRules();
098: // Set up the backchaining engine
099: engine = new BRuleEngine(this , ruleStore);
100: tempNodecache = new TempNodeCache(this );
101: }
102:
103: /**
104: * Return the schema graph, if any, bound into this inference graph.
105: */
106: public Graph getSchemaGraph() {
107: return fschema.getGraph();
108: }
109:
110: /**
111: * Perform any initial processing and caching. This call is optional. Most
112: * engines either have negligable set up work or will perform an implicit
113: * "prepare" if necessary. The call is provided for those occasions where
114: * substantial preparation work is possible (e.g. running a forward chaining
115: * rule system) and where an application might wish greater control over when
116: * this prepration is done.
117: */
118: public void prepare() {
119: if (!isPrepared) {
120: fdeductions = new FGraph(Factory.createGraphMem());
121: extractAxioms();
122: dataFind = fdata;
123: if (fdeductions != null) {
124: dataFind = FinderUtil.cascade(dataFind, fdeductions);
125: }
126: if (fschema != null) {
127: dataFind = FinderUtil.cascade(dataFind, fschema);
128: }
129:
130: context = new BBRuleContext(this );
131: }
132:
133: isPrepared = true;
134: }
135:
136: /**
137: * Replace the underlying data graph for this inference graph and start any
138: * inferences over again. This is primarily using in setting up ontology imports
139: * processing to allow an imports multiunion graph to be inserted between the
140: * inference graph and the raw data, before processing.
141: * @param data the new raw data graph
142: */
143: public void rebind(Graph data) {
144: fdata = new FGraph(data);
145: engine.reset();
146: isPrepared = false;
147: }
148:
149: /**
150: * Cause the inference graph to reconsult the underlying graph to take
151: * into account changes. Normally changes are made through the InfGraph's add and
152: * remove calls are will be handled appropriately. However, in some cases changes
153: * are made "behind the InfGraph's back" and this forces a full reconsult of
154: * the changed data.
155: */
156: public void rebind() {
157: engine.reset();
158: isPrepared = false;
159: }
160:
161: /**
162: * Extended find interface used in situations where the implementator
163: * may or may not be able to answer the complete query. It will
164: * attempt to answer the pattern but if its answers are not known
165: * to be complete then it will also pass the request on to the nested
166: * Finder to append more results.
167: * @param pattern a TriplePattern to be matched against the data
168: * @param continuation either a Finder or a normal Graph which
169: * will be asked for additional match results if the implementor
170: * may not have completely satisfied the query.
171: */
172: public ExtendedIterator findWithContinuation(TriplePattern pattern,
173: Finder continuation) {
174: checkOpen();
175: if (!isPrepared)
176: prepare();
177: ExtendedIterator result = null;
178: if (continuation == null) {
179: result = WrappedIterator.create(new TopGoalIterator(engine,
180: pattern));
181: } else {
182: result = WrappedIterator.create(
183: new TopGoalIterator(engine, pattern)).andThen(
184: continuation.find(pattern));
185: }
186: return result.filterDrop(Functor.acceptFilter);
187: }
188:
189: /**
190: * Returns an iterator over Triples.
191: * This implementation assumes that the underlying findWithContinuation
192: * will have also consulted the raw data.
193: */
194: public ExtendedIterator graphBaseFind(Node subject, Node property,
195: Node object) {
196: return findWithContinuation(new TriplePattern(subject,
197: property, object), null);
198: }
199:
200: /**
201: * Basic pattern lookup interface.
202: * This implementation assumes that the underlying findWithContinuation
203: * will have also consulted the raw data.
204: * @param pattern a TriplePattern to be matched against the data
205: * @return a ExtendedIterator over all Triples in the data set
206: * that match the pattern
207: */
208: public ExtendedIterator find(TriplePattern pattern) {
209: return findWithContinuation(pattern, null);
210: }
211:
212: /**
213: * Flush out all cached results. Future queries have to start from scratch.
214: */
215: public void reset() {
216: engine.reset();
217: isPrepared = false;
218: version++;
219: }
220:
221: /**
222: * Add one triple to the data graph, run any rules triggered by
223: * the new data item, recursively adding any generated triples.
224: */
225: public synchronized void performAdd(Triple t) {
226: fdata.getGraph().add(t);
227: reset();
228: }
229:
230: /**
231: * Removes the triple t (if possible) from the set belonging to this graph.
232: */
233: public void performDelete(Triple t) {
234: fdata.getGraph().delete(t);
235: reset();
236: }
237:
238: //=======================================================================
239: // support for proof traces
240:
241: /**
242: * Set to true to enable derivation caching
243: */
244: public void setDerivationLogging(boolean recordDerivations) {
245: this .recordDerivations = recordDerivations;
246: if (recordDerivations) {
247: derivations = new OneToManyMap();
248: } else {
249: derivations = null;
250: }
251: }
252:
253: /**
254: * Return the derivation of at triple.
255: * The derivation is a List of DerivationRecords
256: */
257: public Iterator getDerivation(Triple t) {
258: if (derivations == null) {
259: return new NullIterator();
260: } else {
261: return derivations.getAll(t);
262: }
263: }
264:
265: /**
266: * Change the threshold on the number of rule firings
267: * allowed during a single operation.
268: * @param threshold the new cutoff on the number rules firings per external op
269: */
270: public void setRuleThreshold(long threshold) {
271: nRulesThreshold = threshold;
272: }
273:
274: /**
275: * Set the state of the trace flag. If set to true then rule firings
276: * are logged out to the Log at "INFO" level.
277: */
278: public void setTraceOn(boolean state) {
279: traceOn = state;
280: engine.setTraceOn(state);
281: }
282:
283: /**
284: * Return true if tracing is switched on
285: */
286: public boolean isTraceOn() {
287: return traceOn;
288: }
289:
290: /**
291: * Dump an a summary of the goal table state to stdout.
292: * Just debugging, do not use for real.
293: */
294: public void dump() {
295: engine.dump();
296: }
297:
298: // =======================================================================
299: // Interface between infGraph and the goal processing machinery
300:
301: /**
302: * Log a dervivation record against the given triple.
303: */
304: public void logDerivation(Triple t, Object derivation) {
305: derivations.put(t, derivation);
306: }
307:
308: /**
309: * Match a pattern just against the stored data (raw data, schema,
310: * axioms) but no derivation.
311: */
312: public ExtendedIterator findDataMatches(TriplePattern pattern) {
313: return dataFind.find(pattern);
314: }
315:
316: /**
317: * Process a call to a builtin predicate
318: * @param clause the Functor representing the call
319: * @param env the BindingEnvironment for this call
320: * @param rule the rule which is invoking this call
321: * @return true if the predicate succeeds
322: */
323: public boolean processBuiltin(ClauseEntry clause, Rule rule,
324: BindingEnvironment env) {
325: if (clause instanceof Functor) {
326: context.setEnv(env);
327: context.setRule(rule);
328: return ((Functor) clause).evalAsBodyClause(context);
329: } else {
330: throw new ReasonerException("Illegal builtin predicate: "
331: + clause + " in rule " + rule);
332: }
333: }
334:
335: /**
336: * Assert a new triple in the deduction graph, bypassing any processing machinery.
337: */
338: public void silentAdd(Triple t) {
339: fdeductions.getGraph().add(t);
340: }
341:
342: /**
343: * Retrieve or create a bNode representing an inferred property value.
344: * @param instance the base instance node to which the property applies
345: * @param prop the property node whose value is being inferred
346: * @param pclass the (optional, can be null) class for the inferred value.
347: * @return the bNode representing the property value
348: */
349: public Node getTemp(Node instance, Node prop, Node pclass) {
350: return tempNodecache.getTemp(instance, prop, pclass);
351: }
352:
353: // =======================================================================
354: // Rule engine extras
355:
356: /**
357: * Find any axioms (rules with no body) in the rule set and
358: * add those to the auxilliary graph to be included in searches.
359: */
360: protected void extractAxioms() {
361: Graph axioms = fdeductions.getGraph();
362: for (Iterator i = rules.iterator(); i.hasNext();) {
363: Rule rule = (Rule) i.next();
364: if (rule.bodyLength() == 0) {
365: // An axiom
366: for (int j = 0; j < rule.headLength(); j++) {
367: Object axiom = rule.getHeadElement(j);
368: if (axiom instanceof TriplePattern) {
369: axioms.add(((TriplePattern) axiom).asTriple());
370: }
371: }
372: }
373: }
374: }
375:
376: }
377:
378: /*
379: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
380: All rights reserved.
381:
382: Redistribution and use in source and binary forms, with or without
383: modification, are permitted provided that the following conditions
384: are met:
385:
386: 1. Redistributions of source code must retain the above copyright
387: notice, this list of conditions and the following disclaimer.
388:
389: 2. Redistributions in binary form must reproduce the above copyright
390: notice, this list of conditions and the following disclaimer in the
391: documentation and/or other materials provided with the distribution.
392:
393: 3. The name of the author may not be used to endorse or promote products
394: derived from this software without specific prior written permission.
395:
396: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
397: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
398: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
399: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
400: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
401: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
402: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
403: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
404: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
405: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
406: */
|