com.bigdata.bop.paths

Class ArbitraryLengthPathTask

java.lang.Object

com.bigdata.bop.paths.ArbitraryLengthPathTask

All Implemented Interfaces:

Callable<Void>

public class ArbitraryLengthPathTask
extends Object
implements Callable<Void>

Execute a subquery that represents an arbitrary length path between a single input variable and a single output variable. Continue this in rounds, using the output of the previous round as the input of the next round. This has the effect of producing the transitive closure of the subquery operation. IMPORTANT: The input binding set is expected to be a distinct projection over the variables that are bound through the operator; in the general case, this requires a JVMDistinctBindingSetsOp over these variable(s) prior to calling the operator. In particular, this operator does *not* join with incoming bindings, but discards all variables that are not bound by the associated ALP node.

The basic idea behind this operator is to run a series of rounds until the solutions produced by each round reach a fixed point. Regardless of the the actual schematics of the arbitrary length path (whether there are constants or variables on the left and right side), we use two transitivity variables to keep the operator moving. Depending on the schematics of the arbitrary length path, we can run on forward (left side is input) or reverse (right side is input). For each intermediate solution, the binding for the transitivity variable on the output side is re-mapped to input for the next round.

This operator does not use internal parallelism, but it is thread-safe and multiple instances of this operator may be run in parallel by the query engine for parallel evaluation of different binding set chunks flowing through the pipeline. However, there are much more efficient query plan patterns for most use cases. E.g., (a) creating a hash index with all source solutions, (b) flooding a sub-section of the query plan with the source solutions from the hash index; and (c) hash joining the solutions from the sub-section of the query plan back against the hash index to reunite the solutions from the subquery with those in the parent context.

Author:

Mike Personick, Michael Schmidt TODO There should be two version of this operator. One for the JVM heap and another for the native heap. This will help when large amounts of data are materialized by the internal collections. TODO think about whether the whole SolutionKey mechanism is required at all, now that we have a distinct projection at the end. It might well be enough to store the input for the previous rounds in a map. This would also be more "precise" than remembering the solutions: for paths such as s1 -p-> s2 -p-> s3 and s1 -p-> s3 and an ALP such as s1 p* ?x, we currently visit s3 twice, once in the first round and once in the second round. This is unnecessary overhead and it might help saving a lot in case of cycles (where we currently run through over and over again).

Constructor Summary

Constructors

Constructor and Description
ArbitraryLengthPathTask(ArbitraryLengthPathOp controllerOp, BOpContext<IBindingSet> context)

Method Summary

Methods

Modifier and Type	Method and Description
Void	call()

Methods inherited from class java.lang.Object

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

Constructor Detail

ArbitraryLengthPathTask

public ArbitraryLengthPathTask(ArbitraryLengthPathOp controllerOp,
                       BOpContext<IBindingSet> context)

Method Detail

call

public Void call()
          throws Exception

Specified by:

call in interface Callable<Void>

Throws:

Exception