001: /******************************************************************
002: * File: PatternRouter.java
003: * Created by: Dave Reynolds
004: * Created on: 22-Jan-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: PatternRouter.java,v 1.8 2008/01/02 12:06:44 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rdfsReasoner1;
010:
011: import com.hp.hpl.jena.reasoner.Finder;
012: import com.hp.hpl.jena.reasoner.InfGraph;
013: import com.hp.hpl.jena.reasoner.ReasonerException;
014: import com.hp.hpl.jena.reasoner.TriplePattern;
015: import com.hp.hpl.jena.reasoner.transitiveReasoner.TransitiveGraphCache;
016: import com.hp.hpl.jena.util.iterator.ExtendedIterator;
017: import com.hp.hpl.jena.graph.*;
018:
019: import org.apache.commons.logging.Log;
020: import org.apache.commons.logging.LogFactory;
021:
022: import java.util.*;
023:
024: /**
025: * A utility for mapping a TriplePattern to a sequence of operations
026: * that could satisfy it. Sources register individual patterns that
027: * they can satisfy. Then requesters use the Finder interface to
028: * satisfy a query.
029: *
030: * <p>Types of sources that can be registered include TransitiveGraphCaches
031: * (which are assumed complete for the predicates they cache), triple stores
032: * (via a Finder interface) and simple rewrite rules.</p>
033: *
034: * <p>This implementation only supports TGCs and rules. It only indexes on
035: * pattern predicates and does a linear search down the rest.<br />
036: *
037: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
038: * @version $Revision: 1.8 $ on $Date: 2008/01/02 12:06:44 $
039: */
040: public class PatternRouter {
041:
042: protected static Log logger = LogFactory
043: .getLog(PatternRouter.class);
044:
045: /** A map from pattern predicate to a list of satisfying Finders */
046: Map patternIndex = new HashMap();
047:
048: /**
049: * Constructor
050: */
051: public PatternRouter() {
052: }
053:
054: /**
055: * Register a transitive closure cache and a means of satisfying
056: * the direct and closed versions of the cached predicate.
057: *
058: * @param cache the TransitiveGraphCache
059: */
060: public void register(TransitiveGraphCache cache) {
061: register(new TriplePattern(null, cache.getClosedPredicate(),
062: null), cache);
063: register(new TriplePattern(null, cache.getDirectPredicate(),
064: null), cache);
065: }
066:
067: /**
068: * Register a backward rewrite rule
069: */
070: public void register(BRWRule rule) {
071: register(rule.getHead(), rule);
072: }
073:
074: /**
075: * Register an object against a specific search pattern
076: */
077: public void register(TriplePattern pattern, Object satisfier) {
078: PatternEntry entry = new PatternEntry(pattern, satisfier);
079: Node predicate = pattern.getPredicate();
080: if (predicate.isVariable()) {
081: throw new ReasonerException(
082: "PatternRouter can't handle non-ground predicates in patterns: "
083: + pattern);
084: }
085: HashSet sats = (HashSet) patternIndex.get(predicate);
086: if (sats == null) {
087: sats = new HashSet();
088: patternIndex.put(predicate, sats);
089: }
090: sats.add(entry);
091: }
092:
093: /**
094: * Process a query according to the known routing information.
095: * The set of required parameters is redundant but enables different routing
096: * tactics to be tried in the future.
097: *
098: * @param pattern the query to be processed
099: * @param tripleCache a cascade of any generic caches which can supply additional answers
100: * @param data the raw data graph being processed
101: * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
102: */
103: public ExtendedIterator find(TriplePattern pattern,
104: Finder tripleCache, Finder data, InfGraph infGraph) {
105: return find(pattern, tripleCache, data, infGraph, new HashSet());
106: }
107:
108: /**
109: * Process a query according to the known routing information.
110: * The set of required parameters is redundant but enables different routing
111: * tactics to be tried in the future.
112: *
113: * @param pattern the query to be processed
114: * @param tripleCache a cascade of any generic caches which can supply additional answers
115: * @param data the raw data graph being processed
116: * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
117: * @param firedRules set of rules which have already been fired and should now be blocked
118: */
119: public ExtendedIterator find(TriplePattern pattern,
120: Finder tripleCache, Finder data, InfGraph infGraph,
121: HashSet firedRules) {
122: ExtendedIterator result = tripleCache.findWithContinuation(
123: pattern, data);
124: Node predicate = pattern.getPredicate();
125: if (predicate.isVariable()) {
126: // Wildcard predicate - this is brute force search across all rules
127: for (Iterator i = patternIndex.values().iterator(); i
128: .hasNext();) {
129: HashSet sats = (HashSet) i.next();
130: result = doFind(sats, result, pattern, tripleCache,
131: data, infGraph, firedRules);
132: }
133: return result;
134: } else {
135: HashSet sats = (HashSet) patternIndex.get(predicate);
136: return doFind(sats, result, pattern, tripleCache, data,
137: infGraph, firedRules);
138: }
139: }
140:
141: /**
142: * Process a query according to the known routing information.
143: * The set of required parameters is redundant but enables different routing
144: * tactics to be tried in the future.
145: *
146: * @param sats the set of PatternEntry objects that might be applicable to this pattern
147: * @param result the iterator over resuls so far
148: * @param pattern the query to be processed
149: * @param tripleCache a cascade of any generic caches which can supply additional answers
150: * @param data the raw data graph being processed
151: * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
152: * @param firedRules set of rules which have already been fired and should now be blocked
153: */
154: private ExtendedIterator doFind(HashSet rules,
155: ExtendedIterator result, TriplePattern pattern,
156: Finder tripleCache, Finder data, InfGraph infGraph,
157: HashSet firedRules) {
158: if (rules != null) {
159: // Scan all matches to check for complete solutions
160: for (Iterator i = rules.iterator(); i.hasNext();) {
161: PatternEntry entry = (PatternEntry) i.next();
162: if (entry.completeFor(pattern)) {
163: return entry.fire(pattern, data, infGraph,
164: firedRules);
165: }
166: }
167: // Scan again and accumulate all non-complete solutions
168: for (Iterator i = rules.iterator(); i.hasNext();) {
169: PatternEntry entry = (PatternEntry) i.next();
170: if (entry.shouldFire(pattern)) {
171: result = result.andThen(entry.fire(pattern, data,
172: infGraph, firedRules));
173: }
174: }
175: }
176: return result;
177: }
178:
179: /**
180: * Printable version of the whole reasoner state.
181: * Used during debugging
182: */
183: public String toString() {
184: StringBuffer state = new StringBuffer();
185: for (Iterator i = patternIndex.values().iterator(); i.hasNext();) {
186: HashSet ents = (HashSet) i.next();
187: for (Iterator j = ents.iterator(); j.hasNext();) {
188: state.append(j.next().toString());
189: state.append("\n");
190: }
191: }
192: return state.toString();
193: }
194:
195: /**
196: * Inner class used to prepresent a pattern indexed entry in the router table
197: */
198: static class PatternEntry {
199: /** The pattern which triggers this entry */
200: TriplePattern pattern;
201:
202: /** The cache/rule which is fired */
203: Object action;
204:
205: /** Constructor */
206: PatternEntry(TriplePattern pattern, Object action) {
207: this .pattern = pattern;
208: this .action = action;
209: }
210:
211: /**
212: * Return true if this entry is a complete solution to the given
213: * query and the router need look no further
214: */
215: public boolean completeFor(TriplePattern query) {
216: if (action instanceof BRWRule) {
217: return ((BRWRule) action).completeFor(query);
218: } else if (action instanceof TransitiveGraphCache) {
219: TransitiveGraphCache tgc = (TransitiveGraphCache) action;
220: Node prop = query.getPredicate();
221: return prop.equals(tgc.getDirectPredicate())
222: || prop.equals(tgc.getClosedPredicate());
223: }
224: return false;
225: }
226:
227: /** Test if this entry should fire against the given query pattern */
228: boolean shouldFire(TriplePattern query) {
229: return pattern.compatibleWith(query);
230: }
231:
232: /**
233: * Run the action
234: * @param query the query to be processed
235: * @param data the raw data graph being processed
236: * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
237: * @param firedRules set of rules which have already been fired and should now be blocked
238: */
239: public ExtendedIterator fire(TriplePattern query, Finder data,
240: InfGraph infGraph, HashSet firedRules) {
241: TriplePattern nquery = query;
242: if (nquery.getPredicate().isVariable()) {
243: nquery = new TriplePattern(query.getSubject(), pattern
244: .getPredicate(), query.getObject());
245: }
246: if (action instanceof TransitiveGraphCache) {
247: return ((TransitiveGraphCache) action).find(nquery);
248: } else if (action instanceof BRWRule) {
249: logger.debug("Fire rule: " + action);
250: return ((BRWRule) action).execute(nquery, infGraph,
251: data, firedRules);
252: } else {
253: throw new ReasonerException(
254: "Illegal router action entry");
255: }
256: }
257:
258: /** Printable string for debugging */
259: public String toString() {
260: return pattern.toString() + " <- " + action;
261: }
262:
263: /** Equality override */
264: public boolean equals(Object o) {
265: return o instanceof PatternEntry
266: && pattern.equals(((PatternEntry) o).pattern)
267: && action.equals(((PatternEntry) o).action);
268: }
269:
270: /** hash function override */
271: public int hashCode() {
272: return (pattern.hashCode() >> 1) ^ action.hashCode();
273: }
274:
275: }
276:
277: }
278:
279: /*
280: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
281: All rights reserved.
282:
283: Redistribution and use in source and binary forms, with or without
284: modification, are permitted provided that the following conditions
285: are met:
286:
287: 1. Redistributions of source code must retain the above copyright
288: notice, this list of conditions and the following disclaimer.
289:
290: 2. Redistributions in binary form must reproduce the above copyright
291: notice, this list of conditions and the following disclaimer in the
292: documentation and/or other materials provided with the distribution.
293:
294: 3. The name of the author may not be used to endorse or promote products
295: derived from this software without specific prior written permission.
296:
297: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
298: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
299: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
300: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
301: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
302: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
303: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
304: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
305: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
306: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
307: */
|