001: /******************************************************************
002: * File: RDFSInfGraph.java
003: * Created by: Dave Reynolds
004: * Created on: 21-Jan-03
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RDFSInfGraph.java,v 1.25 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.*;
012: import com.hp.hpl.jena.reasoner.transitiveReasoner.*;
013: import com.hp.hpl.jena.datatypes.*;
014: import com.hp.hpl.jena.graph.*;
015: import com.hp.hpl.jena.graph.impl.*;
016: import com.hp.hpl.jena.vocabulary.*;
017: import com.hp.hpl.jena.util.iterator.ExtendedIterator;
018: import com.hp.hpl.jena.util.iterator.UniqueExtendedIterator;
019:
020: import org.apache.commons.logging.Log;
021: import org.apache.commons.logging.LogFactory;
022:
023: import java.util.*;
024:
025: /**
026: * An RDFS reasoner that has been bound to both a TBox and an ABox.
027: * It cannot be bound any futher. Once this Bound reasoner has been
028: * created all the class, property and associated declarations have
029: * been extracted and cached and all queries are answerable directly
030: * from the cached results or from query rewrites.
031: *
032: * <p>Initially the subClass/subProperty caches are shared with
033: * the parent RDFSReasoner so they can be shared across instance data.
034: * However, if any update includes any such declarations then the caches
035: * have to be cloned and separated.</p>
036: *
037: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
038: * @version $Revision: 1.25 $ on $Date: 2008/01/02 12:06:44 $
039: */
040: public class RDFSInfGraph extends BaseInfGraph {
041:
042: //=======================================================================
043: // variables
044:
045: /** The precomputed cache of the subClass graph */
046: protected TransitiveGraphCache subClassCache;
047:
048: /** Flag to indicate that this cache has already been split off from
049: * the parent reasoner */
050: protected boolean haveSplitSubClassCache = false;
051:
052: /** The precomputed cache of the subProperty graph */
053: protected TransitiveGraphCache subPropertyCache;
054:
055: /** Router which maps queries onto different cache components that can answer then */
056: protected PatternRouter router;
057:
058: /** Cache of axiomatci triples to be included in the tripleCache */
059: protected FGraph axioms = new FGraph(Factory.createGraphMem());
060:
061: /** The data supplied as a tbox, may be null, will be included as part of tripleCache if not null */
062: protected Finder tbox;
063:
064: /** Cache of precomputed triples which are added to data - this includes
065: * the tbox, axioms and forward deductions */
066: protected Finder tripleCache;
067:
068: /** Optional map of property node to datatype ranges */
069: protected HashMap dtRange = null;
070:
071: /** Flag to control whether properties are eagerly scanned */
072: protected boolean scanProperties = true;
073:
074: //=======================================================================
075: // static rules and axioms
076:
077: protected static Log logger = LogFactory.getLog(RDFSInfGraph.class);
078:
079: /** The RDFS forward rule set */
080: protected static BaseFRule[] rules = new BaseFRule[] {
081: new AssertFRule(
082: "?x rdf:type rdfs:Class -> ?x rdfs:subClassOf rdfs:Resource"),
083: new AssertFRule(
084: "?x rdf:type rdfs:Class -> ?x rdfs:subClassOf ?x"),
085: new AssertFRule(
086: "?x rdf:type rdf:Property -> ?x rdfs:subPropertyOf ?x"),
087: new BackchainFRule(
088: "?p rdfs:subPropertyOf ?q -> ?s ?q ?o <- ?s ?p ?o"),
089: new BackchainFRule(
090: "?c rdfs:subClassOf ?d -> ?s rdf:type ?d <- ?s rdf:type ?c"),
091: new BackchainFRule(
092: "?p rdfs:domain ?z -> ?s rdf:type ?z <- ?s ?p _"),
093: new BackchainFRule(
094: "?p rdfs:range ?z -> ?o rdf:type ?z <- _ ?p ?s") }; // end of RDFS rule set definitions
095:
096: /** The RDFS special case backward rule set */
097: protected static BRWRule[] brules = new BRWRule[] {
098: new ResourceBRWRule(), new PropertyBRWRule() };
099:
100: /** The RDFS built in axioms */
101: protected static Triple[] baseAxioms = new Triple[] {
102: BaseFRule.parseTriple("rdf:type rdfs:range rdfs:Class"),
103:
104: BaseFRule.parseTriple("rdfs:Resource rdf:type rdfs:Class"),
105: BaseFRule.parseTriple("rdfs:Literal rdf:type rdfs:Class"),
106: BaseFRule.parseTriple("rdf:Statement rdf:type rdfs:Class"),
107: BaseFRule.parseTriple("rdf:nil rdf:type rdf:List"),
108: BaseFRule
109: .parseTriple("rdf:XMLLiteral rdf:type rdfs:Datatype"),
110:
111: BaseFRule.parseTriple("rdf:Alt rdf:type rdfs:Class"),
112: BaseFRule.parseTriple("rdf:Seq rdf:type rdfs:Class"),
113: BaseFRule.parseTriple("rdf:Bag rdf:type rdfs:Class"),
114: BaseFRule.parseTriple("rdf:XMLLiteral rdf:type rdfs:Class"),
115: BaseFRule.parseTriple("rdfs:Container rdf:type rdfs:Class"),
116: BaseFRule
117: .parseTriple("rdfs:ContainerMembershipProperty rdf:type rdfs:Class"),
118:
119: BaseFRule
120: .parseTriple("rdfs:isDefinedBy rdf:type rdf:Property"),
121: BaseFRule.parseTriple("rdfs:seeAlso rdf:type rdf:Property"),
122: BaseFRule.parseTriple("rdfs:comment rdf:type rdf:Property"),
123: BaseFRule.parseTriple("rdfs:label rdf:type rdf:Property"),
124:
125: BaseFRule.parseTriple("rdf:subject rdf:type rdf:Property"),
126: BaseFRule
127: .parseTriple("rdf:predicate rdf:type rdf:Property"),
128: BaseFRule.parseTriple("rdf:object rdf:type rdf:Property"),
129: BaseFRule.parseTriple("rdf:first rdf:type rdf:Property"),
130: BaseFRule.parseTriple("rdf:rest rdf:type rdf:Property"),
131: BaseFRule.parseTriple("rdf:type rdf:type rdf:Property"),
132: BaseFRule.parseTriple("rdfs:range rdf:type rdf:Property"),
133: BaseFRule.parseTriple("rdfs:domain rdf:type rdf:Property"),
134:
135: BaseFRule
136: .parseTriple("rdfs:subPropertyOf rdfs:domain rdf:Property"),
137: BaseFRule
138: .parseTriple("rdfs:subPropertyOf rdfs:range rdf:Property"),
139: BaseFRule
140: .parseTriple("rdfs:subClassOf rdfs:domain rdfs:Class"),
141: BaseFRule
142: .parseTriple("rdfs:subClassOf rdfs:range rdfs:Class"),
143:
144: // These may be redundant
145: BaseFRule
146: .parseTriple("rdfs:subPropertyOf rdfs:subPropertyOf rdfs:subPropertyOf"),
147: BaseFRule
148: .parseTriple("rdfs:subClassOf rdfs:subPropertyOf rdfs:subClassOf"),
149: BaseFRule
150: .parseTriple("rdf:subject rdfs:subPropertyOf rdf:subject"),
151: BaseFRule
152: .parseTriple("rdf:predicate rdfs:subPropertyOf rdf:predicate"),
153: BaseFRule
154: .parseTriple("rdf:object rdfs:subPropertyOf rdf:object"),
155: BaseFRule
156: .parseTriple("rdf:first rdfs:subPropertyOf rdf:first"),
157: BaseFRule
158: .parseTriple("rdf:rest rdfs:subPropertyOf rdf:rest"),
159: BaseFRule
160: .parseTriple("rdf:type rdfs:subPropertyOf rdf:type"),
161: BaseFRule
162: .parseTriple("rdfs:range rdfs:subPropertyOf rdfs:range"),
163: BaseFRule
164: .parseTriple("rdfs:domain rdfs:subPropertyOf rdfs:domain") };
165:
166: //=======================================================================
167: // constructors
168:
169: /**
170: * Constructor
171: * @param data the raw data graph being bound to the reasoner
172: * @param reasoner the RDFSReasoner which spawned this InfGraph
173: */
174: public RDFSInfGraph(RDFSReasoner reasoner, Graph data) {
175: super (data, reasoner);
176: this .scanProperties = reasoner.scanProperties;
177: }
178:
179: //=======================================================================
180: // global methods
181:
182: /**
183: * Returns the scanProperties flag.
184: *
185: * <p>If this is set to true then when a reasoner instance is constructed
186: * the whole data graph is scanned to detect all properties and the
187: * results are cached. This is expensive but without this
188: * some cases of rdf:_n properties will not be handled.</p>
189: *
190: * <p>This method is just here for development purposes and will
191: * be replaced by the configuration machinery</p>
192: * @return boolean
193: */
194: public boolean getScanProperties() {
195: return scanProperties;
196: }
197:
198: /**
199: * Sets the scanProperties flag
200: *
201: * <p>If this is set to true then when a reasoner instance is constructed
202: * the whole data graph is scanned to detect all properties and the
203: * results are cached. This is expensive but without this
204: * some cases of rdf:_n properties will not be handled.</p>
205: *
206: * <p>This method is just here for development purposes and will
207: * be replaced by the configuration machinery</p>
208: * @param scanProperties The scanProperties to set
209: */
210: public void setScanProperties(boolean scanProperties) {
211: this .scanProperties = scanProperties;
212: }
213:
214: //=======================================================================
215: // methods
216:
217: /**
218: * Return the schema graph, if any, bound into this inference graph.
219: */
220: public Graph getSchemaGraph() {
221: if (tbox == null)
222: return null;
223: if (tbox instanceof FGraph) {
224: return ((FGraph) tbox).getGraph();
225: } else {
226: throw new ReasonerException(
227: "RDFS1 reasoner got into an illegal state");
228: }
229: }
230:
231: /**
232: * Perform any initial processing and caching. This call is optional. Most
233: * engines either have negligable set up work or will perform an implicit
234: * "prepare" if necessary. The call is provided for those occasions where
235: * substantial preparation work is possible (e.g. running a forward chaining
236: * rule system) and where an application might wish greater control over when
237: * this prepration is done.
238: */
239: public void prepare() {
240: this .subClassCache = ((TransitiveReasoner) reasoner)
241: .getSubClassCache();
242: this .subPropertyCache = ((TransitiveReasoner) reasoner)
243: .getSubPropertyCache().deepCopy();
244: this .tbox = ((TransitiveReasoner) reasoner).getTbox();
245: haveSplitSubClassCache = false;
246:
247: // Combine a place to hold axioms and local deductions and the tbox into single cache
248: if (tbox == null) {
249: tripleCache = axioms;
250: } else {
251: tripleCache = FinderUtil.cascade(axioms, tbox);
252: }
253:
254: // Check for vocabulary definitions in the data graph
255: Graph data = fdata.getGraph();
256: if ((TransitiveEngine.checkOccuranceUtility(
257: RDFSReasoner.subPropertyOf, data, subPropertyCache)
258: || TransitiveEngine
259: .checkOccuranceUtility(RDFSReasoner.subClassOf,
260: data, subPropertyCache)
261: || TransitiveEngine.checkOccuranceUtility(
262: RDFSReasoner.domainP, data, subPropertyCache) || TransitiveEngine
263: .checkOccuranceUtility(RDFSReasoner.rangeP, data,
264: subPropertyCache))) {
265:
266: // The data graph contains some ontology knowledge so split the caches
267: // now and rebuild them using merged data
268: Finder tempTbox = tbox == null ? fdata : FinderUtil
269: .cascade(tbox, fdata);
270:
271: splitSubClassCache();
272: TransitiveEngine.cacheSubPropUtility(tempTbox,
273: subPropertyCache);
274: TransitiveEngine.cacheSubClassUtility(tempTbox,
275: subPropertyCache, subClassCache);
276: // Cache the closures of subPropertyOf because these are likely to be
277: // small and accessed a lot
278: subPropertyCache.setCaching(true);
279: }
280:
281: // add axioms
282: for (int i = 0; i < baseAxioms.length; i++) {
283: axioms.getGraph().add(baseAxioms[i]);
284: }
285: TransitiveEngine.cacheSubPropUtility(axioms, subPropertyCache);
286:
287: // identify all properties and collection properties
288: // This can be disabled in which case queries of the form (*,type,Property) will be
289: // slower and no ContainerMembershipProperty assertions will be detected
290: if (scanProperties) {
291: ExtendedIterator it = tripleCache.findWithContinuation(
292: new TriplePattern(null, null, null), fdata);
293: HashSet properties = new HashSet();
294: String memberPrefix = RDF.getURI() + "_";
295: Node sP = RDF.Property.asNode();
296: while (it.hasNext()) {
297: Triple triple = (Triple) it.next();
298: Node prop = triple.getPredicate();
299: if (prop.equals(RDF.type.asNode())
300: && prop.equals(RDF.Property.asNode())) {
301: prop = triple.getSubject();
302: }
303: if (properties.add(prop)) {
304: // Unseen property - add the subPropertyOf statement
305: subPropertyCache.addRelation(new Triple(prop, sP,
306: prop));
307: if (prop.getURI().startsWith(memberPrefix)) {
308: // A container property
309: axioms
310: .getGraph()
311: .add(
312: new Triple(
313: prop,
314: RDF.type.asNode(),
315: RDFS.ContainerMembershipProperty
316: .asNode()));
317: subPropertyCache.addRelation(new Triple(prop,
318: sP, RDFS.member.asNode()));
319: }
320: }
321: }
322: }
323:
324: // set up the router which connect queries to the appropriate processing element
325: router = new PatternRouter();
326: router.register(subPropertyCache);
327: router.register(subClassCache);
328:
329: // Run the forward rules to preload the tripleCache and build the backward rules
330: checkAllForwardRules();
331:
332: // Add fixed backward rules
333: for (int i = 0; i < brules.length; i++) {
334: addBRule(brules[i]);
335: }
336:
337: isPrepared = true;
338: }
339:
340: /**
341: * Extended find interface used in situations where the implementator
342: * may or may not be able to answer the complete query. It will
343: * attempt to answer the pattern but if its answers are not known
344: * to be complete then it will also pass the request on to the nested
345: * Finder to append more results.
346: * @param pattern a TriplePattern to be matched against the data
347: * @param continuation either a Finder or a normal Graph which
348: * will be asked for additional match results if the implementor
349: * may not have completely satisfied the query.
350: */
351: public ExtendedIterator findWithContinuation(TriplePattern pattern,
352: Finder continuation) {
353: checkOpen();
354: if (!isPrepared)
355: prepare();
356: return new UniqueExtendedIterator(router.find(pattern,
357: tripleCache, continuation, this ));
358: }
359:
360: /**
361: * Variant on find called by backward rules, additional
362: * argument used to pass set of instantiated rules to prevent
363: * run-away rule firing.
364: */
365: public ExtendedIterator findNested(TriplePattern pattern,
366: Finder continuation, HashSet firedRules) {
367: return router.find(pattern, tripleCache, continuation, this ,
368: firedRules);
369: }
370:
371: /**
372: * Variant on find called by special backward rules that only
373: * access the raw data and axioms and bypass further rules
374: */
375: public ExtendedIterator findRawWithContinuation(
376: TriplePattern pattern, Finder continuation) {
377: return tripleCache.findWithContinuation(pattern, continuation);
378: }
379:
380: /**
381: * Variant on find called by special backward rules that need
382: * to list all pre-registered properties. The iterator returns Nodes
383: * not triples.
384: */
385: public ExtendedIterator findProperties() {
386: return subPropertyCache.listAllSubjects();
387: }
388:
389: /**
390: * Variant on find called by special backward rules that need
391: * to list check for a specific preregistered property.
392: */
393: public boolean isProperty(Node prop) {
394: return subPropertyCache.isSubject(prop);
395: }
396:
397: /**
398: * Test the consistency of the bound data. This normally tests
399: * the validity of the bound instance data against the bound
400: * schema data.
401: * @return a ValidityReport structure
402: */
403: public ValidityReport validate() {
404: StandardValidityReport report = new StandardValidityReport();
405: HashMap dtRange = getDTRange();
406: for (Iterator props = dtRange.keySet().iterator(); props
407: .hasNext();) {
408: Node prop = (Node) props.next();
409: for (Iterator i = find(null, prop, null); i.hasNext();) {
410: Triple triple = (Triple) i.next();
411: report.add(checkLiteral(prop, triple.getObject()));
412: }
413: }
414: return report;
415: }
416:
417: //=======================================================================
418: // helper methods
419:
420: /**
421: * Return a map from property nodes to a list of RDFDatatype objects
422: * which have been declared as the range of that property.
423: */
424: private HashMap getDTRange() {
425: if (dtRange == null) {
426: dtRange = new HashMap();
427: for (Iterator i = find(null, RDFS.range.asNode(), null); i
428: .hasNext();) {
429: Triple triple = (Triple) i.next();
430: Node prop = triple.getSubject();
431: Node rangeValue = triple.getObject();
432: if (rangeValue.isURI()) {
433: RDFDatatype dt = TypeMapper.getInstance()
434: .getTypeByName(rangeValue.getURI());
435: if (dt != null) {
436: List range = (ArrayList) dtRange.get(prop);
437: if (range == null) {
438: range = new ArrayList();
439: dtRange.put(prop, range);
440: }
441: range.add(dt);
442: }
443: }
444: }
445: }
446: return dtRange;
447: }
448:
449: /**
450: * Check a given literal value for a property against the set of
451: * known range constraints for it.
452: * @param prop the property node whose range is under scrutiny
453: * @param value the literal node whose value is to be checked
454: * @return null if the range is legal, otherwise a ValidityReport.Report
455: * which describes the problem.
456: */
457: private ValidityReport.Report checkLiteral(Node prop, Node value) {
458: List range = (List) getDTRange().get(prop);
459: if (range != null) {
460: if (!value.isLiteral()) {
461: return new ValidityReport.Report(
462: true,
463: "dtRange",
464: "Property "
465: + prop
466: + " has a typed range but was given a non literal value "
467: + value);
468: }
469: LiteralLabel ll = value.getLiteral();
470: for (Iterator i = range.iterator(); i.hasNext();) {
471: RDFDatatype dt = (RDFDatatype) i.next();
472: if (!dt.isValidLiteral(ll)) {
473: return new ValidityReport.Report(true, "dtRange",
474: "Property " + prop + " has a typed range "
475: + dt
476: + "that is not compatible with "
477: + value);
478: }
479: }
480: }
481: return null;
482: }
483:
484: /**
485: * Run all the builtin forward rules, on all the elements in the tbox and data
486: * graphs. Checkes for all subProperties of the properties mentioned in the
487: * rules themselves.
488: */
489: private void checkAllForwardRules() {
490: // Build a search path for the rules
491: Finder caches = FinderUtil.cascade(subPropertyCache,
492: subClassCache, tripleCache);
493: // Check all rules sequentially
494: for (int i = 0; i < rules.length; i++) {
495: BaseFRule rule = rules[i];
496: TriplePattern head = rule.getHead();
497: Node pPattern = head.getPredicate();
498: if (pPattern.isVariable()) {
499: checkRule(head, rule, caches);
500: } else {
501: // Check out all subProperties of the given predicate
502: TriplePattern spPatt = new TriplePattern(null,
503: TransitiveReasoner.subPropertyOf, pPattern);
504: ExtendedIterator sps = subPropertyCache.find(spPatt);
505: while (sps.hasNext()) {
506: TriplePattern altHead = new TriplePattern(head
507: .getSubject(), ((Triple) sps.next())
508: .getSubject(), head.getObject());
509: checkRule(altHead, rule, caches);
510: }
511: }
512: }
513: }
514:
515: /**
516: * Run a single rule, with the rewritten head, against the data
517: */
518: private void checkRule(TriplePattern altHead, BaseFRule rule,
519: Finder caches) {
520: Iterator it = caches.findWithContinuation(altHead, fdata);
521: while (it.hasNext()) {
522: Triple t = (Triple) it.next();
523: rule.bindAndFire(t, this );
524: }
525: }
526:
527: /**
528: * Assert a triple into the triple cache.
529: * Called by FRules when they fire
530: */
531: public void assertTriple(Triple t) {
532: axioms.getGraph().add(t);
533: }
534:
535: /**
536: * Add a new backchaining rule into the rule set.
537: * Called by FRules when they fire
538: */
539: public void addBRule(BRWRule rule) {
540: router.register(rule);
541: }
542:
543: /**
544: * Separate the cache of subClassOf relations from the parent reasoner
545: * because new added data has changed the class lattice
546: */
547: private void splitSubClassCache() {
548: if (!haveSplitSubClassCache) {
549: subClassCache = subClassCache.deepCopy();
550: haveSplitSubClassCache = true;
551: }
552: }
553:
554: /**
555: * Printable version of the whole reasoner state.
556: * Used during debugging
557: */
558: public String toString() {
559: StringBuffer state = new StringBuffer();
560: TriplePattern all = new TriplePattern(null, null, null);
561: if (tripleCache != null) {
562: state.append("axioms + tbox\n");
563: for (Iterator i = tripleCache.find(all); i.hasNext();) {
564: state.append(TriplePattern.simplePrintString((Triple) i
565: .next()));
566: state.append("\n");
567: }
568: }
569: if (fdata != null) {
570: state.append("Bound raw data\n");
571: for (Iterator i = fdata.find(all); i.hasNext();) {
572: state.append(TriplePattern.simplePrintString((Triple) i
573: .next()));
574: state.append("\n");
575: }
576: }
577: if (router != null) {
578: state.append("Rule set\n");
579: state.append(router.toString());
580: }
581: return state.toString();
582: }
583:
584: }
585:
586: /*
587: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
588: All rights reserved.
589:
590: Redistribution and use in source and binary forms, with or without
591: modification, are permitted provided that the following conditions
592: are met:
593:
594: 1. Redistributions of source code must retain the above copyright
595: notice, this list of conditions and the following disclaimer.
596:
597: 2. Redistributions in binary form must reproduce the above copyright
598: notice, this list of conditions and the following disclaimer in the
599: documentation and/or other materials provided with the distribution.
600:
601: 3. The name of the author may not be used to endorse or promote products
602: derived from this software without specific prior written permission.
603:
604: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
605: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
606: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
607: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
608: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
609: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
610: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
611: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
612: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
613: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
614: */
|