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