com.bigdata.rdf.inf
Class Justification

java.lang.Object
  com.bigdata.rdf.inf.Justification

All Implemented Interfaces:

Comparable<Justification>

public class Justification
extends Object
implements Comparable<Justification>

A justification for a StatementEnum.Inferred statement. The head is the entailed statement. The tail of the justification is one or more triple pattern(s). Consider rdf1

               (?u ?a ?y) -> (?a rdf:type rdf:Property)
 

Then the triple pattern for the tail is:

           (0 ?a 0)
 

where 0 reprents a IRawTripleStore#NULL term identifier.

So a justification chain for rdf1 would be:

           head := [?a rdf:type rdf:Property]
           
           tail := [0 ?a 0]
 

In fact, the total bindings for the rule are represented as a long[] with the head occupying the 1st N positions in that array and the bindings for the tail appearing thereafter in the declared order of the predicates in the tail.

When a StatementEnum.Explicit statement is to be retracted from the database we need to determined whether or not there exists a grounded justification for that statement (same head). For each justification for that statement we consider the tail. If there exists either an explicit statement that satisifies the triple pattern for the tail or if there exists an inference that satisifies the triple pattern for the tail and the inference can be proven to be grounded by recursive examination of its justifications, then the head is still valid and is converted from an explicit statement into an inference.

This looks more or less like: Find all statements matching the pattern. If any are explicit, then that part of the tail is grounded. If none are explicit, then chase the justification recursively. Only retract a justification when it can no longer be grounded.

The concept of grounded vs ungrounded justifications is described in Inferencing and Truth Maintenance in RDF Schema : Exploring a naive practical approach by Jeen Broekstra and Arjohn Kampman.

Version:

$Id: Justification.java 5287 2011-10-04 20:19:12Z thompsonbry $

Author:

Bryan Thompson

TODO:

the tails could be represented more efficiently if we only stored the variable bindings and not all values in each tail. however, we might then need the rule on hand in order to decode the tail(s) and substitute in the missing constants.

Nested Class Summary

static class

Justification.VisitedSPOSet A collection of SPO objects (either fully bound or query patterns) that have already been visited.

Field Summary

static boolean	DEBUG True iff the log level is DEBUG or less.
static boolean	INFO True iff the log level is INFO or less.
protected static org.apache.log4j.Logger	log
IRule	rule From the ctor, but not persisted.

Constructor Summary

Justification(int N, IV[] ids)
Used by the JustificationTupleSerializer to materialize justifications.

Justification(ISolution solution)
Construct a justification directly an ISolution.

Method Summary

int	compareTo(Justification o) Places the justifications into an ordering that clusters them based on the entailment is being justified.
boolean	equals(Justification o)
SPO	getHead() Returns the head as an SPO.
static byte[]	getKey(IKeyBuilder keyBuilder, Justification jst) Serialize a justification as an index key.
SPO[]	getTail() Returns the tail as an SPO[].
static boolean	isGrounded(InferenceEngine inf, TempTripleStore focusStore, AbstractTripleStore db, ISPO head, boolean testHead, boolean testFocusStore, Justification.VisitedSPOSet visited)
static boolean	isGrounded(InferenceEngine inf, TempTripleStore focusStore, AbstractTripleStore db, SPO head, boolean testHead, boolean testFocusStore) Return true iff a grounded justification chain exists for the statement.
String	toString()
String	toString(AbstractTripleStore db)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

log

protected static final transient org.apache.log4j.Logger log

INFO

public static final boolean INFO

True iff the log level is INFO or less.

DEBUG

public static final boolean DEBUG

True iff the log level is DEBUG or less.

rule

public final transient IRule rule

From the ctor, but not persisted.

Constructor Detail

Justification

public Justification(ISolution solution)

Construct a justification directly an ISolution.

Parameters:

solution - The solution. FIXME If [rule == null] then this ctor will thrown an AssertionError. In the original rule execution layer the bindings were are long[] and the were encoded by position. At the moment the bindingSet is indexed by the IVariable (essentially by the variable name). This means that we MUST have the IRule on hand in order extract the bindings that we need.

Modify the new rule execution layer to assign variables an integer index in [0:nvars] for each rule and then we can do positional decoding of the binding set and loose the requirement for the rule when generating justifications.

This might not be that important for scale-out since the solutions are, I believe, processed solely in a local buffer for Insert and Delete and only serialized for Query.

Justification

public Justification(int N,
                     IV[] ids)

Used by the JustificationTupleSerializer to materialize justifications.

Parameters:

ids - The bindings on the head and tail(s).

Method Detail

getHead

public SPO getHead()

Returns the head as an SPO.

Note: The StatementEnum associated with the head is actually unknown, but it is marked as StatementEnum.Inferred in the returned object. In order to discover the StatementEnum for the head you MUST either already know it (this is not uncommon) or you MUST read one of the statement indices.

Returns:

getTail

public SPO[] getTail()

Returns the tail as an SPO[].

Note: The StatementEnum associated triple patterns in the tail is actually unknown, but it is marked as StatementEnum.Inferred in the returned object. In fact, since the tail consists of triple patterns and not necessarily fully bound triples, the concept of a StatementEnum is not even defined.

Returns:

getKey

public static byte[] getKey(IKeyBuilder keyBuilder,
                            Justification jst)

Serialize a justification as an index key. The key length is a function of the #of bindings in the justification.

Parameters:

keyBuilder - A key builder.

Returns:

The key.

equals

public boolean equals(Justification o)

compareTo

public int compareTo(Justification o)

Places the justifications into an ordering that clusters them based on the entailment is being justified.

Specified by:

compareTo in interface Comparable<Justification>

toString

public String toString()

Overrides:

toString in class Object

toString

public String toString(AbstractTripleStore db)

isGrounded

public static boolean isGrounded(InferenceEngine inf,
                                 TempTripleStore focusStore,
                                 AbstractTripleStore db,
                                 SPO head,
                                 boolean testHead,
                                 boolean testFocusStore)

Return true iff a grounded justification chain exists for the statement.

Parameters:

focusStore - The focusStore contains the set of statements that are being retracted from the database. When looking for grounded justifications we do NOT consider any statement that is found in this store. This prevents statements that are being retracted from providing either their own justification or the justiciation of any other statement that is being retracted at the same time.

db - The database from which the statements are to be retracted and in which we will search for grounded justifications.

head - A triple pattern. When invoked on a statement during truth maintenance this will be fully bound. However, during recursive processing triple patterns may be encountered in the tail of Justifications that are not fully bound. In such cases we test for any statement matching the triple pattern that can be proven to be grounded.

testHead - When true the head will be tested against the database on entry before seeking a grounded justification chain. When false head will not be tested directly but we will still seek a grounded justification chain.

testFocusStore -

visited - A set of head (whether fully bound or query patterns) that have already been considered. This parameter MUST be newly allocated on each top-level call. It is used in order to avoid infinite loops by rejecting for further consideration any head which has already been visited.

Returns:

True iff the statement is entailed by a grounded justification chain in the database.

TODO:

this is depth 1st. would breadth 1st be faster?

isGrounded

public static boolean isGrounded(InferenceEngine inf,
                                 TempTripleStore focusStore,
                                 AbstractTripleStore db,
                                 ISPO head,
                                 boolean testHead,
                                 boolean testFocusStore,
                                 Justification.VisitedSPOSet visited)