fruleengine.java

Jena推理机

        ArrayList clauses = new ArrayList(len-1);
        
        if (len <= 1) {
            // No clauses to add, just fall through to clause matcher
        } else if (len == 2) {
            // Only one clause remaining, no reordering necessary
            Object clause = body[trigger == 0 ? 1 : 0];
            if (clause instanceof TriplePattern) {
                clauses.add(clause);
            }
         } else {
            // Pick most bound remaining clause as the best one to go first
            int bestscore = 0;
            int best = -1;
            for (int i = 0; i < len; i++) {
                if (i == trigger) continue; // Skip the clause already processed
                BindingStack env = context.getEnvStack();
                if (body[i] instanceof TriplePattern) {
                    TriplePattern clause = (TriplePattern) body[i];
                    int score = scoreNodeBoundness(clause.getSubject(), env) * 3 +
                                 scoreNodeBoundness(clause.getPredicate(), env) * 2 +
                                 scoreNodeBoundness(clause.getObject(), env) * 3;
                    if (score > bestscore) {
                        bestscore = score;
                        best = i;
                    }
                }
            }
            
            for (int i = 0; i < len; i++) {
                if (i == trigger || i == best) continue;
                if (body[i] instanceof TriplePattern) {
                    clauses.add(body[i]);
                }
            }
            if (best != -1) clauses.add(body[best]);
        }
        
        // Call a recursive clause matcher in the ordered list of clauses   
        boolean matched = matchClauseList(clauses, context);
        if (matched) {
            // We have new deductions stashed which now want to be
            // asserted as deductions and then added to processing stack
            context.flushPending();
        }
        return matched;
    }
    
    /**
     * Match each of a list of clauses in turn. For all bindings for which all
     * clauses match check the remaining clause guards and fire the rule actions.
     * @param clauses the list of clauses to match, start with last clause
     * @param context a context containing a set of new triples to be added
     * @return true if the rule actually fires
     */
    private boolean matchClauseList(List clauses, BFRuleContext context) {
        Rule rule = context.getRule();
        BindingStack env = context.getEnvStack();
        int index = clauses.size() - 1;
        if (index == -1) {
            // Check any non-pattern clauses 
            for (int i = 0; i < rule.bodyLength(); i++) {
                Object clause = rule.getBodyElement(i);
                if (clause instanceof Functor) {
                    // Fire a built in
                    if (!((Functor)clause).evalAsBodyClause(context)) {
                        return false;       // guard failed
                    }
                }
            }
            // Now fire the rule
            if (infGraph.shouldTrace()) {
                logger.info("Fired rule: " + rule.toShortString() + " = " + rule.instantiate(env));
            }
            List matchList = null;
            if (recordDerivations) {
                // Create derivation record
                matchList = new ArrayList(rule.bodyLength());
                for (int i = 0; i < rule.bodyLength(); i++) {
                    Object clause = rule.getBodyElement(i);
                    if (clause instanceof TriplePattern) {
                        matchList.add(env.instantiate((TriplePattern)clause));
                    } 
                }
            }
            for (int i = 0; i < rule.headLength(); i++) {
                Object hClause = rule.getHeadElement(i);
                if (hClause instanceof TriplePattern) {
                    Triple t = env.instantiate((TriplePattern) hClause);
                    if (!t.getSubject().isLiteral()) {
                        // Only add the result if it is legal at the RDF level.
                        // E.g. RDFS rules can create assertions about literals
                        // that we can't record in RDF
                        if ( ! context.contains(t)  ) {
                            context.add(t);
                            if (recordDerivations) {
                                infGraph.logDerivation(t, new RuleDerivation(rule, t, matchList, infGraph));
                            }
                        }
                    }
                } else if (hClause instanceof Functor) {
                    Functor f = (Functor)hClause;
                    Builtin imp = f.getImplementor();
                    if (imp != null) {
                        imp.headAction(f.getBoundArgs(env), f.getArgLength(), context);
                    } else {
                        throw new ReasonerException("Invoking undefined Functor " + f.getName() +" in " + rule.toShortString());
                    }
                } else if (hClause instanceof Rule) {
                    Rule r = (Rule)hClause;
                    if (r.isBackward()) {
                        infGraph.addBRule(r.instantiate(env));
                    } else {
                        throw new ReasonerException("Found non-backward subrule : " + r); 
                    }
                }
            }
            return true;
        }
        // More clauses left to match ...
        ArrayList clausesCopy = (ArrayList)((ArrayList)clauses).clone();
        TriplePattern clause = (TriplePattern) clausesCopy.remove(index);
        Node objPattern = env.getBinding(clause.getObject());
        if (Functor.isFunctor(objPattern)) {
            // Can't search on functor patterns so leave that as a wildcard
            objPattern = null;
        }
        Iterator i = infGraph.findDataMatches(
                            env.getBinding(clause.getSubject()),
                            env.getBinding(clause.getPredicate()),
                            env.getBinding(objPattern));
        boolean foundMatch = false;
        while (i.hasNext()) {
            Triple t = (Triple) i.next();
            // Add the bindings to the environment
            env.push();
            if (match(clause.getPredicate(), t.getPredicate(), env)
                    && match(clause.getObject(), t.getObject(), env)
                    && match(clause.getSubject(), t.getSubject(), env)) {
                foundMatch |= matchClauseList(clausesCopy, context);
            }
            env.unwind();
        }
        return foundMatch;
    }

    /**
     * Score a Node in terms of groundedness - heuristic.
     * Treats a variable as better than a wildcard because it constrains
     * later clauses. Treats rdf:type as worse than any other ground node
     * because that tends to link to lots of expensive rules.
     */
    public static int scoreNodeBoundness(Node n, BindingEnvironment env) {
        if (n instanceof Node_ANY) {
            return 0;
        } else if (n instanceof Node_RuleVariable) {
            Node val = env.getGroundVersion(n);
            if (val == null) {
                return 1;
            } else if (val.equals(RDF.type.asNode())) {
                return 2;
            } else {
                return 3;
            }
        } else {
            return 3;
        }
    }
    
//    /**
//     * Instantiate a triple pattern against the current environment.
//     * This version handles unbound varibles by turning them into bNodes.
//     * @param clause the triple pattern to match
//     * @param env the current binding environment
//     * @return a new, instantiated triple
//     */
//    public static Triple instantiate(TriplePattern pattern, BindingStack env) {
//        Node s = env.getBinding(pattern.getSubject());
//        if (s == null) s = Node.createAnon();
//        Node p = env.getBinding(pattern.getPredicate());
//        if (p == null) p = Node.createAnon();
//        Node o = env.getBinding(pattern.getObject());
//        if (o == null) o = Node.createAnon();
//        return new Triple(s, p, o);
//    }
    
    /**
     * Test if a TriplePattern matches a Triple in the given binding
     * environment. If it does then the binding environment is modified
     * the reflect any additional bindings.
     * @return true if the pattern matches the triple
     */
    public static boolean match(TriplePattern pattern, Triple triple, BindingStack env) {
        env.push();
        boolean matchOK = match(pattern.getPredicate(), triple.getPredicate(), env)
                        && match(pattern.getObject(), triple.getObject(), env)
                        && match(pattern.getSubject(), triple.getSubject(), env);
        if (matchOK) {
            env.commit();
            return true;
        } else {
            env.unwind();
            return false;
        }
    }
    
    /**
     * Test if a pattern Node matches a Triple Node in the given binding
     * environment. If it does then the binding environment is modified
     * the reflect any additional bindings.
     * @return true if the pattern matches the node
     */
    public static boolean match(Node pattern, Node node, BindingStack env) {
        if (pattern instanceof Node_RuleVariable) {
            int index = ((Node_RuleVariable)pattern).getIndex();
            return env.bind(index, node);
        } else if (pattern instanceof Node_ANY) {
            return true;
        } else if (Functor.isFunctor(pattern)) {
            if (!Functor.isFunctor(node)) return false;
            Functor patternF = (Functor) pattern.getLiteralValue();
            Functor nodeF = (Functor) node.getLiteralValue();
            if (!patternF.getName().equals(nodeF.getName())) return false;
            Node[] patternArgs = patternF.getArgs();
            Node[] nodeArgs = nodeF.getArgs();
//            if (patternF.isGround()) {
//                return Arrays.equals(patternArgs, nodeArgs);
//            } else {
                if (patternArgs.length != nodeArgs.length) return false;
                // Compatible functor shapes so bind an embedded variables in the pattern
                env.push();
                boolean matchOK = true;
                for (int i = 0; i < patternArgs.length; i++) {
                    if (!match(patternArgs[i], nodeArgs[i], env)) {
                        matchOK = false;
                        break;
                    }
                }
                if (matchOK) {
                    env.commit();
                    return true;
                } else {
                    env.unwind();
                    return false;
                }
//            }
        } else {
            return pattern.sameValueAs(node);
        }
    }
    
//=======================================================================
// Inner classes

    /**
     * Structure used in the clause index to indicate a particular
     * clause in a rule. This is used purely as an internal data
     * structure so we just use direct field access.
     */
    protected static class ClausePointer {
        
        /** The rule containing this clause */
        protected Rule rule;
        
        /** The index of the clause in the rule body */
        protected int index;
        
        /** constructor */
        ClausePointer(Rule rule, int index) {
            this.rule = rule;
            this.index = index;
        }
        
        /** Get the clause pointed to */
        TriplePattern getClause() {
            return (TriplePattern)rule.getBodyElement(index);
        }
    }
    
    /**
     * Structure used to wrap up processed rule indexes.
     */
    public static class RuleStore {
    
        /** Map from predicate node to rule + clause, Node_ANY is used for wildcard predicates */
        protected OneToManyMap clauseIndex;
    
        /** List of predicates used in rules to assist in fast data loading */
        protected HashSet predicatesUsed;
    
        /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
        protected boolean wildcardRule;
        
        /** Constructor */
        RuleStore(OneToManyMap clauseIndex, HashSet predicatesUsed, boolean wildcardRule) {
            this.clauseIndex = clauseIndex;
            this.predicatesUsed = predicatesUsed;
            this.wildcardRule = wildcardRule;
        }
    }

}


/*
    (c) Copyright 2003, 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.
*/