Re: Multiple derivations for backward chaining?

[Joshua TAYLOR]

On Mon, Aug 12, 2013 at 3:23 PM, Niranjan Balasubramanian
<niran...@cs.washington.edu> wrote:
> Yes, getting at *all* possible derivations is bound to be problematic. How 
> about finding K traces through the derivation graph? Is there any way to 
> force the backward-chaining procedure to run until the answer is found K 
> times (via different paths) or until the search space is exhausted?

Depending on your ruleset and how much of the derivation you need, you
can do a lot with print statements in your rules. For instance

@prefix ex: <http://example.org/> .

[(ex:A ex:B ex:C) <-
 print( derivation 1 )]
[(ex:A ex:B ex:C) <-
 print( derivation 2 )]
[(ex:A ex:B ex:C) <-
 print( derivation 3 )]

contains three rules that will produce (A B C).  When writing out an
inference model based on these rules, all three rules are fired, even
though the model only contains one statement (A B C). For instance,
here's code that iterates through the statements of an inference model
based on these rules:

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import com.hp.hpl.jena.rdf.model.InfModel;
import com.hp.hpl.jena.rdf.model.Model;
import com.hp.hpl.jena.rdf.model.ModelFactory;
import com.hp.hpl.jena.rdf.model.StmtIterator;
import com.hp.hpl.jena.reasoner.Reasoner;
import com.hp.hpl.jena.reasoner.rulesys.GenericRuleReasoner;
import com.hp.hpl.jena.reasoner.rulesys.Rule;


public class DerivationsFinder {
        final static String ruleText = "" +
                        "@prefix ex: <http://example.org/> .\n" +
                        "\n" +
                        "[(ex:A ex:B ex:C) <-\n" +
                        " print( derivation 1 )]\n" +
                        "[(ex:A ex:B ex:C) <-\n" +
                        " print( derivation 2 )]\n" +
                        "[(ex:A ex:B ex:C) <-\n" +
                        " print( derivation 3 )]\n" +
                        "";
        
        public static void main(String[] args) throws IOException {
                try ( final InputStream in = new ByteArrayInputStream( 
ruleText.getBytes() );
                          final InputStreamReader reader = new 
InputStreamReader( in );
                          final BufferedReader buff = new BufferedReader( 
reader ) ) {

                        final Reasoner reasoner = new GenericRuleReasoner( 
Rule.parseRules(
Rule.rulesParserFromReader( buff )));
                        final Model model = ModelFactory.createDefaultModel();
                        final InfModel infModel = ModelFactory.createInfModel( 
reasoner, model );
                        
                        for ( final StmtIterator it = 
infModel.listStatements(); it.hasNext(); ) {
                                System.out.println( it.next() );
                        }
                }
        }
}

The output is:

derivation '1'^^http://www.w3.org/2001/XMLSchema#int
[http://example.org/A, http://example.org/B, http://example.org/C]
derivation '2'^^http://www.w3.org/2001/XMLSchema#int
derivation '3'^^http://www.w3.org/2001/XMLSchema#int

If you can put enough debugging output in your rules, you should be
able to capture a bunch of the derivations.

-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/