001: /******************************************************************
002: * File: TransitiveEngine.java
003: * Created by: Dave Reynolds
004: * Created on: 23-Jun-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: TransitiveEngine.java,v 1.12 2008/01/02 12:07:50 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.transitiveReasoner;
010:
011: import com.hp.hpl.jena.graph.*;
012: import com.hp.hpl.jena.reasoner.*;
013: import com.hp.hpl.jena.util.iterator.ExtendedIterator;
014: import com.hp.hpl.jena.vocabulary.RDFS;
015:
016: import java.util.*;
017:
018: /**
019: * Uses two transitive graph caches to store a subclass and a subproperty
020: * lattice and use them within a larger inference graph.
021: *
022: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
023: * @version $Revision: 1.12 $ on $Date: 2008/01/02 12:07:50 $
024: */
025: public class TransitiveEngine {
026:
027: /** The precomputed cache of the subClass graph */
028: protected TransitiveGraphCache subClassCache;
029:
030: /** The precomputed cache of the subProperty graph */
031: protected TransitiveGraphCache subPropertyCache;
032:
033: /** The base data set from which the caches can be rebuilt */
034: protected Finder data;
035:
036: /** True if the internal data structures have been initialized */
037: protected boolean isPrepared = false;
038:
039: /** The set of predicates which are aliases for subClassOf */
040: protected static HashSet subClassAliases;
041:
042: /** The set of predicates which are aliases for subPropertyOf */
043: protected static HashSet subPropertyAliases;
044:
045: /** Classification flag: not relevant to this engine */
046: private static final int NOT_RELEVANT = 1;
047:
048: /** Classification flag: simple or indirect subClass */
049: private static final int SUBCLASS = 2;
050:
051: /** Classification flag: simple subProperty */
052: private static final int SUBPROPERTY = 4;
053:
054: /** Mask for the lattice update cases */
055: // private static final int UPDATE_MASK = SUBCLASS | SUBPROPERTY;
056: private static final int UPDATE_MASK = SUBCLASS | SUBPROPERTY
057: | NOT_RELEVANT;
058:
059: /** Classification flag: subProperty of subClass */
060: private static final int REBUILD_SUBCLASS = 8;
061:
062: /** Classification flag: subProperty of subProperty */
063: private static final int REBUILD_SUBPROPERTY = 16;
064:
065: /** The direct (minimal) version of the subPropertyOf property */
066: public static Node directSubPropertyOf;
067:
068: /** The direct (minimal) version of the subClassOf property */
069: public static Node directSubClassOf;
070:
071: /** The normal subPropertyOf property */
072: public static Node subPropertyOf;
073:
074: /** The normal subClassOf property */
075: public static Node subClassOf;
076:
077: // Static initializer
078: static {
079: directSubPropertyOf = TransitiveReasoner.directSubPropertyOf;
080: directSubClassOf = TransitiveReasoner.directSubClassOf;
081: subPropertyOf = RDFS.subPropertyOf.asNode();
082: subClassOf = RDFS.subClassOf.asNode();
083: }
084:
085: /**
086: * Constructor.
087: * @param subClassCache pre-initialized subclass TGC
088: * @param subPropertyCache pre-initialized subproperty TGC
089: */
090: public TransitiveEngine(TransitiveGraphCache subClassCache,
091: TransitiveGraphCache subPropertyCache) {
092: this .subClassCache = subClassCache;
093: this .subPropertyCache = subPropertyCache;
094: }
095:
096: /**
097: * Constructor.
098: * @param tengine an instance of TransitiveEngine to be cloned
099: */
100: public TransitiveEngine(TransitiveEngine tengine) {
101: this .subClassCache = tengine.getSubClassCache().deepCopy();
102: this .subPropertyCache = tengine.getSubPropertyCache()
103: .deepCopy();
104: }
105:
106: /**
107: * Prepare the engine by inserting any new data not already included
108: * in the existing caches.
109: * @param baseData the base dataset on which the initial caches were based, could be null
110: * @param newData a dataset to be added to the engine, not known to be already
111: * included in the caches from construction time
112: * @return a concatenation of the inserted data and the original data
113: */
114: public Finder insert(Finder baseData, FGraph newData) {
115: Graph newDataG = newData.getGraph();
116: if (baseData != null) {
117: data = FinderUtil.cascade(baseData, newData);
118: } else {
119: data = newData;
120: }
121: if ((TransitiveEngine.checkOccuranceUtility(subPropertyOf,
122: newDataG, subPropertyCache) || TransitiveEngine
123: .checkOccuranceUtility(subClassOf, newDataG,
124: subPropertyCache))) {
125: subClassCache = new TransitiveGraphCache(directSubClassOf,
126: subClassOf);
127: subPropertyCache = new TransitiveGraphCache(
128: directSubPropertyOf, subPropertyOf);
129: TransitiveEngine
130: .cacheSubPropUtility(data, subPropertyCache);
131: TransitiveEngine.cacheSubClassUtility(data,
132: subPropertyCache, subClassCache);
133: }
134: return data;
135: }
136:
137: /**
138: * Return the cache of the subclass lattice.
139: */
140: public TransitiveGraphCache getSubClassCache() {
141: return subClassCache;
142: }
143:
144: /**
145: * Return the cache of the subclass lattice.
146: */
147: public TransitiveGraphCache getSubPropertyCache() {
148: return subPropertyCache;
149: }
150:
151: /**
152: * Set the closure caching flags.
153: * @param cacheSP true if caching of subPropertyOf closure is wanted
154: * @param cacheSC true if caching of subClassOf closure is wanted
155: */
156: public void setCaching(boolean cacheSP, boolean cacheSC) {
157: subPropertyCache.setCaching(cacheSP);
158: subClassCache.setCaching(cacheSC);
159: }
160:
161: /**
162: * Build alias tables for subclass and subproperty.
163: */
164: private void prepare() {
165: if (isPrepared)
166: return;
167: subClassAliases = new HashSet();
168: subClassAliases.add(subClassOf);
169: subClassAliases.add(directSubClassOf);
170:
171: subPropertyAliases = new HashSet();
172: subPropertyAliases.add(subPropertyOf);
173: subPropertyAliases.add(directSubPropertyOf);
174:
175: Iterator subProps = subPropertyCache.find(new TriplePattern(
176: null, subPropertyOf, subPropertyOf));
177: while (subProps.hasNext()) {
178: Triple spT = (Triple) subProps.next();
179: Node spAlias = spT.getSubject();
180: subPropertyAliases.add(spAlias);
181: Iterator subClasses = subPropertyCache
182: .find(new TriplePattern(null, spAlias, subClassOf));
183: while (subClasses.hasNext()) {
184: subClassAliases.add(((Triple) subClasses.next())
185: .getObject());
186: }
187: }
188: isPrepared = true;
189: }
190:
191: /**
192: * Classify an incoming triple to detect whether it is relevant to this engine.
193: * @param t the triple being added
194: * @return a classification flag, as specified in the above private properties
195: */
196: private int triage(Triple t) {
197: if (!isPrepared)
198: prepare();
199: Node predicate = t.getPredicate();
200: if (subClassAliases.contains(predicate)) {
201: return SUBCLASS;
202: } else if (subPropertyAliases.contains(predicate)) {
203: Node target = t.getObject();
204: if (subClassAliases.contains(target)) {
205: return REBUILD_SUBCLASS | SUBPROPERTY;
206: } else if (subPropertyAliases.contains(target)) {
207: return REBUILD_SUBCLASS | REBUILD_SUBPROPERTY;
208: } else {
209: return SUBPROPERTY;
210: }
211: } else {
212: return NOT_RELEVANT;
213: }
214:
215: }
216:
217: /**
218: * Return a Finder instance appropriate for the given query.
219: */
220: public Finder getFinder(TriplePattern pattern, Finder continuation) {
221: if (!isPrepared)
222: prepare();
223: Node predicate = pattern.getPredicate();
224: if (predicate.isVariable()) {
225: // Want everything in the cache, the tbox and the continuation
226: return FinderUtil.cascade(subPropertyCache, subClassCache,
227: continuation);
228: } else if (subPropertyAliases.contains(predicate)) {
229: return subPropertyCache;
230: } else if (subClassAliases.contains(predicate)) {
231: return subClassCache;
232: } else {
233: return continuation;
234: }
235: }
236:
237: /**
238: * Add one triple to caches if it is relevant.
239: * @return true if the triple affected the caches
240: */
241: public synchronized boolean add(Triple t) {
242: int triageClass = triage(t);
243: switch (triageClass & UPDATE_MASK) {
244: case SUBCLASS:
245: subClassCache.addRelation(t);
246: break;
247: case SUBPROPERTY:
248: subPropertyCache.addRelation(t);
249: break;
250: case NOT_RELEVANT:
251: return false;
252: }
253: // If we get here we might need to some cache rebuilding
254: if ((triageClass & REBUILD_SUBPROPERTY) != 0) {
255: TransitiveEngine
256: .cacheSubPropUtility(data, subPropertyCache);
257: isPrepared = false;
258: }
259: if ((triageClass & REBUILD_SUBCLASS) != 0) {
260: TransitiveEngine.cacheSubClassUtility(data,
261: subPropertyCache, subClassCache);
262: isPrepared = false;
263: }
264: return true;
265: }
266:
267: /**
268: * Removes the triple t (if relevant) from the caches.
269: * @return true if the triple affected the caches
270: */
271: public synchronized boolean delete(Triple t) {
272: int triageClass = triage(t);
273: switch (triageClass & UPDATE_MASK) {
274: case SUBCLASS:
275: subClassCache.removeRelation(t);
276: break;
277: case SUBPROPERTY:
278: subPropertyCache.removeRelation(t);
279: break;
280: case NOT_RELEVANT:
281: return false;
282: }
283: // If we get here we might need to some cache rebuilding
284: if ((triageClass & REBUILD_SUBPROPERTY) != 0) {
285: subPropertyCache.clear();
286: TransitiveEngine
287: .cacheSubPropUtility(data, subPropertyCache);
288: isPrepared = false;
289: }
290: if ((triageClass & REBUILD_SUBCLASS) != 0) {
291: subClassCache.clear();
292: TransitiveEngine.cacheSubClassUtility(data,
293: subPropertyCache, subClassCache);
294: isPrepared = false;
295: }
296: return true;
297: }
298:
299: /**
300: * Test if there are any usages of prop within the given graph.
301: * This includes indirect usages incurred by subProperties of prop.
302: *
303: * @param prop the property to be checked for
304: * @param graph the graph to be check
305: * @return true if there is a triple using prop or one of its sub properties
306: */
307: public boolean checkOccurance(Node prop, Graph graph) {
308: return checkOccuranceUtility(prop, graph, subPropertyCache);
309: }
310:
311: // ----------------------------------------------------------------------------
312: // Global helper routines, maintined in this for just to suppor the (now deprecated)
313: // rdfs1 reasoner.
314:
315: /**
316: * Caches all subClass declarations, including those that
317: * are defined via subProperties of subClassOf. Public to allow other reasoners
318: * to use it but not of interest to end users.
319: *
320: * @param graph a graph whose declarations are to be cached
321: * @param spCache the existing state of the subPropertyOf cache
322: * @param scCache the existing state of the subClassOf cache, will be updated
323: * @return true if there were new metalevel declarations discovered.
324: */
325: public static boolean cacheSubClassUtility(Finder graph,
326: TransitiveGraphCache spCache, TransitiveGraphCache scCache) {
327: if (graph == null)
328: return false;
329:
330: scCache.cacheAll(graph, TransitiveReasoner.subClassOf);
331:
332: // Check for any properties which are subProperties of subClassOf
333: boolean foundAny = false;
334: ExtendedIterator subClasses = spCache.find(new TriplePattern(
335: null, TransitiveReasoner.subPropertyOf,
336: TransitiveReasoner.subClassOf));
337: while (subClasses.hasNext()) {
338: foundAny = true;
339: Triple t = (Triple) subClasses.next();
340: Node subClass = t.getSubject();
341: if (!subClass.equals(TransitiveReasoner.subClassOf)) {
342: scCache.cacheAll(graph, subClass);
343: }
344: }
345:
346: return foundAny;
347: }
348:
349: /**
350: * Test if there are any usages of prop within the given graph.
351: * This includes indirect usages incurred by subProperties of prop.
352: * Public to allow other reasoners
353: * to use it but not of interest to end users.
354: *
355: * @param prop the property to be checked for
356: * @param graph the graph to be check
357: * @param spCache the subPropertyOf cache to use
358: * @return true if there is a triple using prop or one of its sub properties
359: */
360: public static boolean checkOccuranceUtility(Node prop, Graph graph,
361: TransitiveGraphCache spCache) {
362: boolean foundOne = false;
363: ExtendedIterator uses = graph.find(null, prop, null);
364: foundOne = uses.hasNext();
365: uses.close();
366: if (foundOne)
367: return foundOne;
368:
369: ExtendedIterator propVariants = spCache.find(new TriplePattern(
370: null, TransitiveReasoner.subPropertyOf, prop));
371: while (propVariants.hasNext() && !foundOne) {
372: Triple t = (Triple) propVariants.next();
373: Node propVariant = t.getSubject();
374: uses = graph.find(null, propVariant, null);
375: foundOne = uses.hasNext();
376: uses.close();
377: }
378: propVariants.close();
379: return foundOne;
380: }
381:
382: /**
383: * Caches all subPropertyOf declarations, including any meta level
384: * ones (subPropertyOf subPropertyOf). Public to allow other reasoners
385: * to use it but not of interest to end users.
386: *
387: * @param graph a graph whose declarations are to be cached
388: * @param spCache the existing state of the subPropertyOf cache, will be updated
389: * @return true if there were new metalevel declarations discovered.
390: */
391: public static boolean cacheSubPropUtility(Finder graph,
392: TransitiveGraphCache spCache) {
393: if (graph == null)
394: return false;
395:
396: spCache.cacheAll(graph, TransitiveReasoner.subPropertyOf);
397:
398: // Check for any properties which are subProperties of subProperty
399: // and so introduce additional subProperty relations.
400: // Each one discovered might reveal indirect subPropertyOf subPropertyOf
401: // declarations - hence the double iteration
402: boolean foundAny = false;
403: boolean foundMore = false;
404: HashSet cached = new HashSet();
405: do {
406: ExtendedIterator subProps = spCache.find(new TriplePattern(
407: null, TransitiveReasoner.subPropertyOf,
408: TransitiveReasoner.subPropertyOf));
409: while (subProps.hasNext()) {
410: foundMore = false;
411: Triple t = (Triple) subProps.next();
412: Node subProp = t.getSubject();
413: if (!subProp.equals(TransitiveReasoner.subPropertyOf)
414: && !cached.contains(subProp)) {
415: foundAny = true;
416: cached.add(subProp);
417: spCache.cacheAll(graph, subProp);
418: foundMore = true;
419: }
420: }
421: } while (foundMore);
422:
423: return foundAny;
424: }
425:
426: }
427:
428: /*
429: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
430: All rights reserved.
431:
432: Redistribution and use in source and binary forms, with or without
433: modification, are permitted provided that the following conditions
434: are met:
435:
436: 1. Redistributions of source code must retain the above copyright
437: notice, this list of conditions and the following disclaimer.
438:
439: 2. Redistributions in binary form must reproduce the above copyright
440: notice, this list of conditions and the following disclaimer in the
441: documentation and/or other materials provided with the distribution.
442:
443: 3. The name of the author may not be used to endorse or promote products
444: derived from this software without specific prior written permission.
445:
446: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
447: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
448: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
449: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
450: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
451: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
452: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
453: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
454: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
455: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
456: */
|