PatternRouter


1   /******************************************************************
2    * File:        PatternRouter.java
3    * Created by:  Dave Reynolds
4    * Created on:  22-Jan-2003
5    * 
6    * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7    * [See end of file]
8    * $Id: PatternRouter.java,v 1.5 2005/02/21 12:16:36 andy_seaborne Exp $
9    *****************************************************************/
10  package com.hp.hpl.jena.reasoner.rdfsReasoner1;
11  
12  import com.hp.hpl.jena.reasoner.Finder;
13  import com.hp.hpl.jena.reasoner.InfGraph;
14  import com.hp.hpl.jena.reasoner.ReasonerException;
15  import com.hp.hpl.jena.reasoner.TriplePattern;
16  import com.hp.hpl.jena.reasoner.transitiveReasoner.TransitiveGraphCache;
17  import com.hp.hpl.jena.util.iterator.ExtendedIterator;
18  import com.hp.hpl.jena.graph.*;
19  
20  import org.apache.commons.logging.Log;
21  import org.apache.commons.logging.LogFactory;
22  
23  import java.util.*;
24  
25  /**
26   * A utility for mapping a TriplePattern to a sequence of operations
27   * that could satisfy it. Sources register individual patterns that
28   * they can satisfy. Then requesters use the Finder interface to 
29   * satisfy a query.
30   * 
31   * <p>Types of sources that can be registered include TransitiveGraphCaches
32   * (which are assumed complete for the predicates they cache), triple stores
33   * (via a Finder interface) and simple rewrite rules.</p>
34   * 
35   * <p>This implementation only supports TGCs and rules. It only indexes on
36   * pattern predicates and does a linear search down the rest.<br />
37   * 
38   * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
39   * @version $Revision: 1.5 $ on $Date: 2005/02/21 12:16:36 $
40   */
41  public class PatternRouter {
42      
43      protected static Log logger = LogFactory.getLog(PatternRouter.class);
44      
45      
46      /** A map from pattern predicate to a list of satisfying Finders */
47      Map patternIndex = new HashMap();
48      
49      /**
50       * Constructor
51       */
52      public PatternRouter() {
53      }
54      
55      /**
56       * Register a transitive closure cache and a means of satisfying
57       * the direct and closed versions of the cached predicate.
58       * 
59       * @param cache the TransitiveGraphCache
60       */
61      public void register(TransitiveGraphCache cache) {
62          register(new TriplePattern(null, cache.getClosedPredicate(), null), cache);
63          register(new TriplePattern(null, cache.getDirectPredicate(), null), cache);
64      }
65      
66      /**
67       * Register a backward rewrite rule
68       */
69      public void register(BRWRule rule) {
70          register(rule.getHead(), rule);
71      }
72      
73      /**
74       * Register an object against a specific search pattern
75       */
76      public void register(TriplePattern pattern, Object   satisfier) {
77          PatternEntry entry = new PatternEntry(pattern, satisfier);
78          Node predicate = pattern.getPredicate();
79          if (predicate.isVariable()) {
80              throw new ReasonerException("PatternRouter can't handle non-ground predicates in patterns: " + pattern);
81          }
82          HashSet sats = (HashSet)patternIndex.get(predicate);
83          if (sats == null) {
84              sats = new HashSet();
85              patternIndex.put(predicate, sats);
86          }
87          sats.add(entry);
88      }
89          
90      /**
91       * Process a query according to the known routing information.
92       * The set of required parameters is redundant but enables different routing
93       * tactics to be tried in the future.
94       * 
95       * @param pattern the query to be processed
96       * @param tripleCache a cascade of any generic caches which can supply additional answers
97       * @param data the raw data graph being processed
98       * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
99       */
100     public ExtendedIterator find(TriplePattern pattern, Finder tripleCache, Finder data, InfGraph infGraph) {
101         return find(pattern, tripleCache, data, infGraph, new HashSet());
102     }
103     
104     /**
105      * Process a query according to the known routing information.
106      * The set of required parameters is redundant but enables different routing
107      * tactics to be tried in the future.
108      * 
109      * @param pattern the query to be processed
110      * @param tripleCache a cascade of any generic caches which can supply additional answers
111      * @param data the raw data graph being processed
112      * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
113      * @param firedRules set of rules which have already been fired and should now be blocked
114      */
115     public ExtendedIterator find(TriplePattern pattern, Finder tripleCache, Finder data, InfGraph infGraph, HashSet firedRules) {
116         ExtendedIterator result = tripleCache.findWithContinuation(pattern, data);
117         Node predicate = pattern.getPredicate();
118         if (predicate.isVariable()) {
119             // Wildcard predicate - this is brute force search across all rules
120             for (Iterator i = patternIndex.values().iterator(); i.hasNext();) {
121                 HashSet sats = (HashSet)i.next();
122                 result = doFind(sats, result, pattern, tripleCache, data, infGraph, firedRules);
123             }
124             return result;
125         } else {
126             HashSet sats = (HashSet)patternIndex.get(predicate);
127             return doFind(sats, result, pattern, tripleCache, data, infGraph, firedRules);
128         }
129     }
130    
131     /**
132      * Process a query according to the known routing information.
133      * The set of required parameters is redundant but enables different routing
134      * tactics to be tried in the future.
135      * 
136      * @param sats the set of PatternEntry objects that might be applicable to this pattern
137      * @param result the iterator over resuls so far
138      * @param pattern the query to be processed
139      * @param tripleCache a cascade of any generic caches which can supply additional answers
140      * @param data the raw data graph being processed
141      * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
142      * @param firedRules set of rules which have already been fired and should now be blocked
143      */
144     private ExtendedIterator doFind(HashSet rules, ExtendedIterator result, 
145                                      TriplePattern pattern, Finder tripleCache, 
146                                      Finder data, InfGraph infGraph, HashSet firedRules) {
147         if (rules != null) {
148             // Scan all matches to check for complete solutions
149             for (Iterator i = rules.iterator(); i.hasNext(); ) {
150                 PatternEntry entry =  (PatternEntry) i.next();
151                 if (entry.completeFor(pattern)) {
152                     return entry.fire(pattern, data, infGraph, firedRules);
153                 }
154             }
155             // Scan again and accumulate all non-complete solutions
156             for (Iterator i = rules.iterator(); i.hasNext(); ) {
157                 PatternEntry entry =  (PatternEntry) i.next();
158                 if (entry.shouldFire(pattern)) {
159                     result = result.andThen(entry.fire(pattern, data, infGraph, firedRules));
160                 }
161             }
162         }
163         return result;
164     }
165     
166     /**
167      * Printable version of the whole reasoner state.
168      * Used during debugging
169      */
170     public String   toString() {
171         StringBuffer   state = new StringBuffer  ();
172         for (Iterator i = patternIndex.values().iterator(); i.hasNext(); ) {
173             HashSet ents = (HashSet)i.next();
174             for (Iterator j = ents.iterator(); j.hasNext(); ) {
175                 state.append(j.next().toString());
176                 state.append("\n");
177             }
178         }
179         return state.toString();
180     }
181     
182     /**
183      * Inner class used to prepresent a pattern indexed entry in the router table
184      */
185     static class PatternEntry {
186         /** The pattern which triggers this entry */
187         TriplePattern pattern;
188         
189         /** The cache/rule which is fired */
190         Object   action;
191         
192         /** Constructor */
193         PatternEntry(TriplePattern pattern, Object   action) {
194             this.pattern = pattern;
195             this.action = action;
196         }
197 
198         /**
199          * Return true if this entry is a complete solution to the given
200          * query and the router need look no further
201          */
202         public boolean completeFor(TriplePattern query) {
203             if (action instanceof BRWRule) {
204                 return ((BRWRule)action).completeFor(query);
205             } else if (action instanceof TransitiveGraphCache) {
206                 TransitiveGraphCache tgc = (TransitiveGraphCache)action;
207                 Node prop = query.getPredicate();
208                 return prop.equals(tgc.getDirectPredicate()) ||
209                         prop.equals(tgc.getClosedPredicate());
210             }
211             return false;
212         }
213             
214         /** Test if this entry should fire against the given query pattern */
215         boolean shouldFire(TriplePattern query) {
216             return pattern.compatibleWith(query);
217         }
218 
219         /**
220          * Run the action
221          * @param query the query to be processed
222          * @param data the raw data graph being processed
223          * @param infGraph link to originating inference graph, may be re-invoked after a pattern rewrite
224          * @param firedRules set of rules which have already been fired and should now be blocked
225          */
226         public ExtendedIterator fire(TriplePattern query, Finder data, InfGraph infGraph, HashSet firedRules) {
227             TriplePattern nquery = query;
228             if (nquery.getPredicate().isVariable()) {
229                 nquery = new TriplePattern(query.getSubject(), pattern.getPredicate(), query.getObject());
230             }
231             if (action instanceof TransitiveGraphCache) {
232                 return ((TransitiveGraphCache)action).find(nquery);
233             } else if (action instanceof BRWRule) {
234                 logger.debug("Fire rule: " + action);
235                 return ((BRWRule)action).execute(nquery, infGraph, data, firedRules);
236             } else {
237                 throw new ReasonerException("Illegal router action entry");
238             }
239         }
240         
241         /** Printable string for debugging */
242         public String   toString() {
243             return pattern.toString() + " <- " + action;
244         }
245         
246         /** Equality override */
247         public boolean equals(Object   o) {
248             return o instanceof PatternEntry && 
249                     pattern.equals(((PatternEntry)o).pattern) &&
250                     action.equals(((PatternEntry)o).action) ;
251         }
252             
253         /** hash function override */
254         public int hashCode() {
255             return (pattern.hashCode() >> 1) ^ action.hashCode();
256         }
257 
258     }
259     
260 }
261 
262 /*
263     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
264     All rights reserved.
265 
266     Redistribution and use in source and binary forms, with or without
267     modification, are permitted provided that the following conditions
268     are met:
269 
270     1. Redistributions of source code must retain the above copyright
271        notice, this list of conditions and the following disclaimer.
272 
273     2. Redistributions in binary form must reproduce the above copyright
274        notice, this list of conditions and the following disclaimer in the
275        documentation and/or other materials provided with the distribution.
276 
277     3. The name of the author may not be used to endorse or promote products
278        derived from this software without specific prior written permission.
279 
280     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
281     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
282     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
283     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
284     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
285     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
286     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
287     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
288     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
289     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
290 */
291
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags