RDFSInfGraph


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