Tuesday, May 18, 2004

Inferring Transitive Predicates
Now have everything happening down to the resolution point. Spent some time learning the various interfaces available in LocalQuery for building "Tuples" collections.

Reducing (or constraining) a result is typically done by creating a Given constraint object, and combining it with the data to be reduced by way of a ConstraintConjunction object. These objects can then be resolved with a LocalQuery. This would be inefficient in this case, as the code where this has to happen is already inside LocalQuery, and there is a lot of cached state available for building tuples which can't be passed into a new LocalQuery. There are no methods available inside LocalQuery to shortcut this process, and reasonably significant changes would need to be made to do a local ConstraintExpression resolution like this.

Instead I'd gone onto using the static TuplesOperations.join() method. This is at a much lower level, and seems to do what is needed here. At least, SR assures me that it will work.

A very rough outline of the algorithm I'm using is:

  1. If anchored, find all statements matching the anchor, otherwise find all statements matching the predicate.
  2. Save the resulting tuples as the initial result.
  3. Initialise an empty set of tuples for the inferred results.
  4. For each tuple in the initial result:
    1. Get the current subject, and go forward to find all objects for this subject adding them to a given clause.
    2. Call into inference function, passing the current subject, the initial result, the given, and the inferred results.

Inference function
  1. Join the given against initial result.
  2. For each object in this join result:
    1. add current subject parameter and object from join as tuples in the inferred results
    2. If object == current-subject parameter then continue to next object.
    3. If object exists in set of visited nodes for the current-subject parameter then continue to next object.
    4. Put object into a new given tuples, and in set of visted nodes.
  3. If the new given is empty then return.
  4. Call back into this inference function, passing the original current subject, the initial result, the new given, and the inferred results.

Since the inference function uses tail recursion I should probably go back and change it into an iteration (ie. a loop) rather than recursing. While I think of it, I should check if Java 1.5 is introducing tail recursion, but I don't think so.

Back Chaining
Back chaining from anchors which specify the object rather than the subject is also being supported in the code described above. This is because the "subjects" and "objects" I refer to above are actually just indexes into a tuples (typically indexes 0 and 1: predicates are fixed and are therefore not in the results). Instead of using the numbers 0 and 1, I used indexes into a two element array, with the values {0,1}. Back constraints need to swap access to subjects and predicates, so this is a simple matter of changing the array to {1,0}. After that all "subjects" are actually objects, and vice versa. I left the names as "subject" and "object" as it is often easier to think with fewer levels of abstraction.

Late last night I got back to a bit of debugging of this. This was after leaving it for a week. I'm thinking that I should also provide serialisation on the Graph, so it looks like I still have some non-test coding to do.

No comments: