KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > transitiveReasoner > TransitiveEngine


1 /******************************************************************
2  * File: TransitiveEngine.java
3  * Created by: Dave Reynolds
4  * Created on: 23-Jun-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: TransitiveEngine.java,v 1.8 2005/02/21 12:18:19 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.transitiveReasoner;
11
12 import com.hp.hpl.jena.graph.*;
13 import com.hp.hpl.jena.reasoner.*;
14 import com.hp.hpl.jena.util.iterator.ExtendedIterator;
15 import com.hp.hpl.jena.vocabulary.RDFS;
16
17 import java.util.*;
18
19 /**
20  * Uses two transitive graph caches to store a subclass and a subproperty
21  * lattice and use them within a larger inference graph.
22  *
23  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
24  * @version $Revision: 1.8 $ on $Date: 2005/02/21 12:18:19 $
25  */
26 public class TransitiveEngine {
27     
28     /** The precomputed cache of the subClass graph */
29     protected TransitiveGraphCache subClassCache;
30     
31     /** The precomputed cache of the subProperty graph */
32     protected TransitiveGraphCache subPropertyCache;
33     
34     /** The base data set from which the caches can be rebuilt */
35     protected Finder data;
36     
37     /** True if the internal data structures have been initialized */
38     protected boolean isPrepared = false;
39     
40     /** The set of predicates which are aliases for subClassOf */
41     protected static HashSet subClassAliases;
42     
43     /** The set of predicates which are aliases for subPropertyOf */
44     protected static HashSet subPropertyAliases;
45     
46     /** Classification flag: not relevant to this engine */
47     private static final int NOT_RELEVANT = 1;
48     
49     /** Classification flag: simple or indirect subClass */
50     private static final int SUBCLASS = 2;
51     
52     /** Classification flag: simple subProperty */
53     private static final int SUBPROPERTY = 4;
54     
55     /** Mask for the lattice update cases */
56 // private static final int UPDATE_MASK = SUBCLASS | SUBPROPERTY;
57 private static final int UPDATE_MASK = SUBCLASS | SUBPROPERTY | NOT_RELEVANT;
58     
59     /** Classification flag: subProperty of subClass */
60     private static final int REBUILD_SUBCLASS = 8;
61     
62     /** Classification flag: subProperty of subProperty */
63     private static final int REBUILD_SUBPROPERTY = 16;
64     
65     /** The direct (minimal) version of the subPropertyOf property */
66     public static Node directSubPropertyOf;
67     
68     /** The direct (minimal) version of the subClassOf property */
69     public static Node directSubClassOf;
70     
71     /** The normal subPropertyOf property */
72     public static Node subPropertyOf;
73     
74     /** The normal subClassOf property */
75     public static Node subClassOf;
76     
77     // Static initializer
78 static {
79         directSubPropertyOf = TransitiveReasoner.directSubPropertyOf;
80         directSubClassOf = TransitiveReasoner.directSubClassOf;
81         subPropertyOf = RDFS.subPropertyOf.getNode();
82         subClassOf = RDFS.subClassOf.getNode();
83     }
84    
85     /**
86      * Constructor.
87      * @param subClassCache pre-initialized subclass TGC
88      * @param subPropertyCache pre-initialized subproperty TGC
89      */
90     public TransitiveEngine(TransitiveGraphCache subClassCache,
91                              TransitiveGraphCache subPropertyCache) {
92          this.subClassCache = subClassCache;
93          this.subPropertyCache = subPropertyCache;
94     }
95    
96     /**
97      * Constructor.
98      * @param tengine an instance of TransitiveEngine to be cloned
99      */
100     public TransitiveEngine(TransitiveEngine tengine) {
101          this.subClassCache = tengine.getSubClassCache().deepCopy();
102          this.subPropertyCache = tengine.getSubPropertyCache().deepCopy();
103     }
104     
105     /**
106      * Prepare the engine by inserting any new data not already included
107      * in the existing caches.
108      * @param baseData the base dataset on which the initial caches were based, could be null
109      * @param newData a dataset to be added to the engine, not known to be already
110      * included in the caches from construction time
111      * @return a concatenation of the inserted data and the original data
112      */
113     public Finder insert(Finder baseData, FGraph newData) {
114         Graph newDataG = newData.getGraph();
115         if (baseData != null) {
116             data = FinderUtil.cascade(baseData, newData);
117         } else {
118             data = newData;
119         }
120         if ((TransitiveEngine.checkOccuranceUtility(subPropertyOf, newDataG, subPropertyCache) ||
121                TransitiveEngine.checkOccuranceUtility(subClassOf, newDataG, subPropertyCache))) {
122              subClassCache = new TransitiveGraphCache(directSubClassOf, subClassOf);
123              subPropertyCache = new TransitiveGraphCache(directSubPropertyOf, subPropertyOf);
124              TransitiveEngine.cacheSubPropUtility(data, subPropertyCache);
125              TransitiveEngine.cacheSubClassUtility(data, subPropertyCache, subClassCache);
126          }
127          return data;
128     }
129
130     /**
131      * Return the cache of the subclass lattice.
132      */
133     public TransitiveGraphCache getSubClassCache() {
134         return subClassCache;
135     }
136
137     /**
138      * Return the cache of the subclass lattice.
139      */
140     public TransitiveGraphCache getSubPropertyCache() {
141         return subPropertyCache;
142     }
143     
144     /**
145      * Set the closure caching flags.
146      * @param cacheSP true if caching of subPropertyOf closure is wanted
147      * @param cacheSC true if caching of subClassOf closure is wanted
148      */
149     public void setCaching(boolean cacheSP, boolean cacheSC) {
150         subPropertyCache.setCaching(cacheSP);
151         subClassCache.setCaching(cacheSC);
152     }
153     
154     /**
155      * Build alias tables for subclass and subproperty.
156      */
157     private void prepare() {
158         if (isPrepared) return;
159         subClassAliases = new HashSet();
160         subClassAliases.add(subClassOf);
161         subClassAliases.add(directSubClassOf);
162         
163         subPropertyAliases = new HashSet();
164         subPropertyAliases.add(subPropertyOf);
165         subPropertyAliases.add(directSubPropertyOf);
166         
167         Iterator subProps = subPropertyCache.find(new TriplePattern(null, subPropertyOf, subPropertyOf));
168         while (subProps.hasNext()) {
169             Triple spT = (Triple) subProps.next();
170             Node spAlias = spT.getSubject();
171             subPropertyAliases.add(spAlias);
172             Iterator subClasses = subPropertyCache.find(new TriplePattern(null, spAlias, subClassOf));
173             while (subClasses.hasNext()) {
174                 subClassAliases.add(((Triple)subClasses.next()).getObject());
175             }
176         }
177         isPrepared = true;
178     }
179     
180     /**
181      * Classify an incoming triple to detect whether it is relevant to this engine.
182      * @param t the triple being added
183      * @return a classification flag, as specified in the above private properties
184      */
185     private int triage(Triple t) {
186         if (!isPrepared) prepare();
187         Node predicate = t.getPredicate();
188         if (subClassAliases.contains(predicate)) {
189             return SUBCLASS;
190         } else if (subPropertyAliases.contains(predicate)) {
191             Node target = t.getObject();
192             if (subClassAliases.contains(target)) {
193                 return REBUILD_SUBCLASS | SUBPROPERTY;
194             } else if (subPropertyAliases.contains(target)) {
195                 return REBUILD_SUBCLASS | REBUILD_SUBPROPERTY;
196             } else {
197                 return SUBPROPERTY;
198             }
199         } else {
200             return NOT_RELEVANT;
201         }
202         
203     }
204     
205     /**
206      * Return a Finder instance appropriate for the given query.
207      */
208     public Finder getFinder(TriplePattern pattern, Finder continuation) {
209         if (!isPrepared) prepare();
210         Node predicate = pattern.getPredicate();
211         if (predicate.isVariable()) {
212             // Want everything in the cache, the tbox and the continuation
213 return FinderUtil.cascade(subPropertyCache, subClassCache, continuation);
214         } else if (subPropertyAliases.contains(predicate)) {
215             return subPropertyCache;
216         } else if (subClassAliases.contains(predicate)) {
217             return subClassCache;
218         } else {
219             return continuation;
220         }
221     }
222     
223     /**
224      * Add one triple to caches if it is relevant.
225      * @return true if the triple affected the caches
226      */
227     public synchronized boolean add(Triple t) {
228         int triageClass = triage(t);
229         switch (triageClass & UPDATE_MASK) {
230             case SUBCLASS:
231                 subClassCache.addRelation(t);
232                 break;
233             case SUBPROPERTY:
234                 subPropertyCache.addRelation(t);
235                 break;
236             case NOT_RELEVANT:
237                 return false;
238         }
239         // If we get here we might need to some cache rebuilding
240 if ((triageClass & REBUILD_SUBPROPERTY) != 0) {
241             TransitiveEngine.cacheSubPropUtility(data, subPropertyCache);
242             isPrepared = false;
243         }
244         if ((triageClass & REBUILD_SUBCLASS) != 0) {
245             TransitiveEngine.cacheSubClassUtility(data, subPropertyCache, subClassCache);
246             isPrepared = false;
247         }
248         return true;
249     }
250     
251     /**
252      * Removes the triple t (if relevant) from the caches.
253      * @return true if the triple affected the caches
254      */
255     public synchronized boolean delete(Triple t) {
256         int triageClass = triage(t);
257         switch (triageClass & UPDATE_MASK) {
258             case SUBCLASS:
259                 subClassCache.removeRelation(t);
260                 break;
261             case SUBPROPERTY:
262                 subPropertyCache.removeRelation(t);
263                 break;
264             case NOT_RELEVANT:
265                 return false;
266         }
267         // If we get here we might need to some cache rebuilding
268 if ((triageClass & REBUILD_SUBPROPERTY) != 0) {
269             subPropertyCache.clear();
270             TransitiveEngine.cacheSubPropUtility(data, subPropertyCache);
271             isPrepared = false;
272         }
273         if ((triageClass & REBUILD_SUBCLASS) != 0) {
274             subClassCache.clear();
275             TransitiveEngine.cacheSubClassUtility(data, subPropertyCache, subClassCache);
276             isPrepared = false;
277         }
278         return true;
279     }
280
281     
282     /**
283      * Test if there are any usages of prop within the given graph.
284      * This includes indirect usages incurred by subProperties of prop.
285      *
286      * @param prop the property to be checked for
287      * @param graph the graph to be check
288      * @return true if there is a triple using prop or one of its sub properties
289      */
290     public boolean checkOccurance(Node prop, Graph graph) {
291         return checkOccuranceUtility(prop, graph, subPropertyCache);
292     }
293
294 // ----------------------------------------------------------------------------
295 // Global helper routines, maintined in this for just to suppor the (now deprecated)
296 // rdfs1 reasoner.
297
298     /**
299      * Caches all subClass declarations, including those that
300      * are defined via subProperties of subClassOf. Public to allow other reasoners
301      * to use it but not of interest to end users.
302      *
303      * @param graph a graph whose declarations are to be cached
304      * @param spCache the existing state of the subPropertyOf cache
305      * @param scCache the existing state of the subClassOf cache, will be updated
306      * @return true if there were new metalevel declarations discovered.
307      */
308     public static boolean cacheSubClassUtility(Finder graph, TransitiveGraphCache spCache, TransitiveGraphCache scCache) {
309         if (graph == null) return false;
310     
311         scCache.cacheAll(graph, TransitiveReasoner.subClassOf);
312         
313         // Check for any properties which are subProperties of subClassOf
314 boolean foundAny = false;
315         ExtendedIterator subClasses
316             = spCache.find(new TriplePattern(null, TransitiveReasoner.subPropertyOf, TransitiveReasoner.subClassOf));
317         while (subClasses.hasNext()) {
318             foundAny = true;
319             Triple t = (Triple)subClasses.next();
320             Node subClass = t.getSubject();
321             if (!subClass.equals(TransitiveReasoner.subClassOf)) {
322                 scCache.cacheAll(graph, subClass);
323             }
324         }
325         
326         return foundAny;
327     }
328
329     /**
330      * Test if there are any usages of prop within the given graph.
331      * This includes indirect usages incurred by subProperties of prop.
332      * Public to allow other reasoners
333      * to use it but not of interest to end users.
334      *
335      * @param prop the property to be checked for
336      * @param graph the graph to be check
337      * @param spCache the subPropertyOf cache to use
338      * @return true if there is a triple using prop or one of its sub properties
339      */
340     public static boolean checkOccuranceUtility(Node prop, Graph graph, TransitiveGraphCache spCache) {
341         boolean foundOne = false;
342         ExtendedIterator uses = graph.find( null, prop, null );
343         foundOne = uses.hasNext();
344         uses.close();
345         if (foundOne) return foundOne;
346         
347         ExtendedIterator propVariants
348            = spCache.find(new TriplePattern(null, TransitiveReasoner.subPropertyOf, prop));
349         while (propVariants.hasNext() && !foundOne) {
350             Triple t = (Triple)propVariants.next();
351             Node propVariant = t.getSubject();
352             uses = graph.find( null, propVariant, null );
353             foundOne = uses.hasNext();
354             uses.close();
355         }
356         propVariants.close();
357         return foundOne;
358     }
359
360     /**
361      * Caches all subPropertyOf declarations, including any meta level
362      * ones (subPropertyOf subPropertyOf). Public to allow other reasoners
363      * to use it but not of interest to end users.
364      *
365      * @param graph a graph whose declarations are to be cached
366      * @param spCache the existing state of the subPropertyOf cache, will be updated
367      * @return true if there were new metalevel declarations discovered.
368      */
369     public static boolean cacheSubPropUtility(Finder graph, TransitiveGraphCache spCache) {
370         if (graph == null) return false;
371         
372         spCache.cacheAll(graph, TransitiveReasoner.subPropertyOf);
373         
374         // Check for any properties which are subProperties of subProperty
375 // and so introduce additional subProperty relations.
376 // Each one discovered might reveal indirect subPropertyOf subPropertyOf
377 // declarations - hence the double iteration
378 boolean foundAny = false;
379         boolean foundMore = false;
380         HashSet cached = new HashSet();
381         do {
382             ExtendedIterator subProps
383                 = spCache.find(new TriplePattern(null, TransitiveReasoner.subPropertyOf, TransitiveReasoner.subPropertyOf));
384             while (subProps.hasNext()) {
385                 foundMore = false;
386                 Triple t = (Triple)subProps.next();
387                 Node subProp = t.getSubject();
388                 if (!subProp.equals(TransitiveReasoner.subPropertyOf) && !cached.contains(subProp)) {
389                     foundAny = true;
390                     cached.add(subProp);
391                     spCache.cacheAll(graph, subProp);
392                     foundMore = true;
393                 }
394             }
395         } while (foundMore);
396         
397         return foundAny;
398     }
399
400 }
401
402
403
404 /*
405     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
406     All rights reserved.
407
408     Redistribution and use in source and binary forms, with or without
409     modification, are permitted provided that the following conditions
410     are met:
411
412     1. Redistributions of source code must retain the above copyright
413        notice, this list of conditions and the following disclaimer.
414
415     2. Redistributions in binary form must reproduce the above copyright
416        notice, this list of conditions and the following disclaimer in the
417        documentation and/or other materials provided with the distribution.
418
419     3. The name of the author may not be used to endorse or promote products
420        derived from this software without specific prior written permission.
421
422     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
423     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
424     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
425     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
426     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
427     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
428     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
429     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
430     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
431     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
432 */
Popular Tags