transitivegraphcache.java

Jena推理机

    /**
     * Register a new relation instance in the cache
     */
    private void addRelation(Node start, Node end) {
        if (start.equals(end)) return;      // Reflexive case is built in
        GraphNode startN = getLead(start);
        GraphNode endN = getLead(end);
    	
    	// Check if this link is already known about
    	if (startN.pathTo(endN)) {
    		// yes, so no work to do
    		return;
    	}

    	boolean needJoin = endN.pathTo(startN);
        Set members = null;
        if (needJoin) {
        	// Reduce graph to DAG by factoring out SCCs
//	        startN.assertLinkTo(endN);
            // First find all the members of the new component
            members = new HashSet();
            members.add(endN);
            startN.visitPredecessors(new Visitor() {
                public List visit(GraphNode node, GraphNode processing, Object members, Object endN) {
                    if (((GraphNode)endN).pathTo(node)) ((Set)members).add(node);
                    return null;
                } }, members, endN);
            // Then create the SCC
            startN.makeLeadNodeFor(members);
            // Now propagate the closure in the normalized graph
            startN.propagateSCC();
        } else {
	    	// Walk all predecessors of start retracting redundant direct links
	    	// and adding missing closed links
	        startN.propagateAdd(endN);
	        startN.assertLinkTo(endN);
        }
        
    	if (needJoin) {
    		// Create a new strongly connected component
    	}
    }
    
    /**
     * Remove an instance of a relation from the cache.
     */
    public void removeRelation(Triple t) {
    	Node start = t.getSubject();
    	Node end = t.getObject();
    	if (start == end) {
    		return;		// Reflexive case is built in
    	}
    	GraphNode startN = getLead(start);
    	GraphNode endN = getLead(end);
    	if (startN != endN && !(startN.directPathTo(endN))) {
    		// indirect link can't be removed by itself
    		return;
    	}
    	// This is a remove of a direct link possibly within an SCC
    	// Delay as long as possible and do deletes in a batch
    	if (deletesPending == null) {
    		deletesPending = new HashSet();
    	}
    	deletesPending.add(t);
    }

    /**
     * Process outstanding delete actions
     */
    private void processDeletes() {
    	// The kernel is the set of start nodes of deleted links
    	Set kernel = new HashSet();
    	for (Iterator i = deletesPending.iterator(); i.hasNext(); ) {
    		Triple t = (Triple)i.next();
    		GraphNode start = (GraphNode)nodeMap.get(t.getSubject());
    		kernel.add(start);
    	}
    	
    	// The predecessor set of kernel
    	Set pKernel = new HashSet();
    	pKernel.addAll(kernel);
    	for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
    		GraphNode n = (GraphNode)i.next();
    		for (Iterator j = kernel.iterator(); j.hasNext();) {
    			GraphNode target = (GraphNode)j.next();
    			if (n.pathTo(target)) {
    				pKernel.add(n); break;
    			}
    		}
    	}
    	
    	// Cut the pKernel away from the finge of nodes that it connects to
    	for (Iterator i = pKernel.iterator(); i.hasNext(); ) {
    		GraphNode n = (GraphNode)i.next();
    		for (Iterator j = n.succ.iterator(); j.hasNext(); ) {
    			GraphNode fringe = (GraphNode)j.next();
    			if (! pKernel.contains(fringe)) {
    				fringe.pred.remove(n);
    			}
    		}
    		n.succ.clear();
    		n.succClosed.clear();
    		n.pred.clear();
    	}
    	
    	// Delete the triples
    	originalTriples.removeAll(deletesPending);
    	deletesPending.clear();
    	
    	// Reinsert the remaining links
    	for (Iterator i = originalTriples.iterator(); i.hasNext(); ) {
    		Triple t = (Triple)i.next();
    		GraphNode n = (GraphNode)nodeMap.get(t.getSubject());
    		if (pKernel.contains(n)) {
    			addRelation(t);
    		}
    	}
    }
    
    /**
     * Extended find interface used in situations where the implementator
     * may or may not be able to answer the complete query. 
     * <p>
     * In this case any query on the direct or closed predicates will
     * be assumed complete, any other query will pass on to the continuation.</p>
     * @param pattern a TriplePattern to be matched against the data
     * @param continuation either a Finder or a normal Graph which
     * will be asked for additional match results if the implementor
     * may not have completely satisfied the query.
     */
    public ExtendedIterator findWithContinuation(TriplePattern pattern, Finder continuation) {
        Node p = pattern.getPredicate();
        
        if (p.isVariable()) {
            // wildcard predicate so return merge of cache and continuation
            return find(pattern).andThen(continuation.find(pattern));
        } else if (p.equals(directPredicate) || p.equals(closedPredicate)) {
            // Satisfy entire query from the cache
            return find(pattern);
        } else {
            // No matching triples in this cache so just search the continuation
            return continuation.find(pattern);
        }
        
    }
    
    /**
     * Return true if the given pattern occurs somewhere in the find sequence.
     */
    public boolean contains(TriplePattern pattern) {
        ClosableIterator it = find(pattern);
        boolean result = it.hasNext();
        it.close();
        return result;
    }
    /**
     * Return an iterator over all registered subject nodes
     */
    public ExtendedIterator listAllSubjects() {
        return WrappedIterator.create(nodeMap.keySet().iterator());
    }
   
    /**
     * Return true if the given Node is registered as a subject node
     */
    public boolean isSubject(Node node) {
        return nodeMap.keySet().contains(node);
    }
    
    /**
     * Cache all instances of the given predicate which are
     * present in the given Graph.
     * @param graph the searchable set of triples to cache
     * @param predicate the predicate to cache, need not be the registered
     * predicate due to subProperty declarations
     * @return returns true if new information has been cached
     */
    public boolean cacheAll(Finder graph, Node predicate) {
        ExtendedIterator it = graph.find(new TriplePattern(null, predicate, null));
        boolean foundsome = it.hasNext();
        while (it.hasNext()) {
            Triple triple = (Triple) it.next();
            addRelation(triple);
        }
        it.close();
        return foundsome;
    }
    
    /**
     * Basic pattern lookup interface.
     * @param pattern a TriplePattern to be matched against the data
     * @return a ExtendedIterator over all Triples in the data set
     *  that match the pattern
     */
    public ExtendedIterator find(TriplePattern pattern) {
    	if (deletesPending != null && deletesPending.size() > 0) {
    		processDeletes();
    	}

    	Node s = pattern.getSubject();
        Node p = pattern.getPredicate();
        Node o = pattern.getObject();
        
        if (p.isVariable() || p.equals(directPredicate) || p.equals(closedPredicate)) {
            boolean closed = !p.equals(directPredicate);
            Node pred = closedPredicate; // p.isVariable() ? closedPredicate : p;
            if (s.isVariable()) {
                if (o.isVariable()) {
                    // list all the graph contents
//                    ExtendedIterator result = null;
//                    for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
//                        ExtendedIterator nexti = ((GraphNode)i.next()).listTriples(closed, this);
//                        if (result == null) {
//                            result = nexti;
//                        } else {
//                            result = result.andThen(nexti);
//                        }
//                    }
//                    if (result == null) {
//                        return NullIterator.instance;
//                    }
                    return new FullGraphWalker(closed, closedPredicate, nodeMap);
                } else {
                    // list all backwards from o
                    GraphNode gn_o = (GraphNode)nodeMap.get(o);
                    if (gn_o == null) return NullIterator.instance;
                    return gn_o.listPredecessorTriples(closed, this);
                }
            } else {
                GraphNode gn_s = (GraphNode)nodeMap.get(s);
                if (gn_s == null) return NullIterator.instance;
                if (o.isVariable()) {
                    // list forward from s
                    return gn_s.listTriples(closed, this);
                } else {
                    // Singleton test
                    GraphNode gn_o = (GraphNode)nodeMap.get(o);
                    gn_s = gn_s.leadNode();
                    if (gn_o == null) return NullIterator.instance;
                    gn_o = gn_o.leadNode();
                    if ( closed ? gn_s.pathTo(gn_o) : gn_s.directPathTo(gn_o) ) {
                        return new SingletonIterator(new Triple(s, pred, o));
                    } else {
                        return NullIterator.instance;
                    }
                }
            }
        } else {
            // No matching triples in this cache
            return NullIterator.instance;
        }
    }
    
    /**
     * Create a deep copy of the cache contents.
     * Works by creating a completely new cache and just adding in the
     * direct links.
     */
    public TransitiveGraphCache deepCopy() {
        TransitiveGraphCache copy = new TransitiveGraphCache(directPredicate, closedPredicate);
        Iterator i = find(new TriplePattern(null, directPredicate, null));
        while (i.hasNext()) {
            Triple t = (Triple)i.next();
            copy.addRelation(t.getSubject(), t.getObject());
        }
        return copy;
    }
    
    /**
     * Clear the entire cache contents. 
     */
    public void clear() {
        nodeMap.clear();
    }
	
    /**
     * Enable/disabling caching of the Triples representing the relationships. If this is
     * enabled then a number of triples quadratic in the graph depth will be stored. If it
     * is disabled then all queries will turn over storage dynamically creating the result triples.
     */
    public void setCaching(boolean enable) {
    	if (! enable && cacheTriples) {
    		// Switching off so clear the existing cache
    		for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
    			((GraphNode)i.next()).clearTripleCache();
    		}
    	}
    	cacheTriples = enable;
    }
    
    /**
     * Dump a description of the cache to a string for debug.
     */
    public String dump() {
    	StringBuffer sb = new StringBuffer();
    	for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
    		GraphNode n = (GraphNode)i.next();
    		sb.append(n.dump());
    		sb.append("\n");
    	}
    	return sb.toString();
    }
    
//  ----------------------------------------------------------------------
//  Internal utility methods    
//  ----------------------------------------------------------------------
    
    /**
     * Return the lead node of the strongly connected component corresponding
     * to the given RDF node. 
     */
    private GraphNode getLead(Node n) {
    	GraphNode gn = (GraphNode)nodeMap.get(n);
        if (gn == null) {
            gn = new GraphNode(n);
            nodeMap.put(n, gn);
            return gn;
        } else {
            return gn.leadNode();
        }
    }
    
}


/*
    (c) Copyright 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
    All rights reserved.

    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
    are met:

    1. Redistributions of source code must retain the above copyright
       notice, this list of conditions and the following disclaimer.

    2. Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.

    3. The name of the author may not be used to endorse or promote products
       derived from this software without specific prior written permission.

    THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/