public class GreedyTraversalPlan extends Object
| Constructor and Description |
|---|
GreedyTraversalPlan() |
| Modifier and Type | Method and Description |
|---|---|
static GraqlTraversal |
createTraversal(PatternAdmin pattern,
GraknGraph graph)
Create a traversal plan using the default maxTraersalAttempts.
|
static GraqlTraversal |
createTraversal(PatternAdmin pattern,
GraknGraph graph,
long maxTraversalAttempts)
Create a semi-optimal traversal plan using a greedy approach
|
public static GraqlTraversal createTraversal(PatternAdmin pattern, GraknGraph graph)
pattern - a pattern to find a query plan forcreateTraversal(PatternAdmin, GraknGraph, long)public static GraqlTraversal createTraversal(PatternAdmin pattern, GraknGraph graph, long maxTraversalAttempts)
We can interpret building a plan as a decision tree, where each branch represents selecting a fragment to traverse next. A path from the root to a leaf of the tree represents a traversal plan.
Under this definition, this traversal optimisation plan takes a brute-force approach. It traverses a certain number of branches (defined in MAX_TRAVERSAL_ATTEMPTS) and calculates the estimated complexity of each partial plan produced. The lowest complexity partial plan is chosen, then the brute-force search is re-started from that position until a full plan is produced.
With fixed MAX_TRAVERSAL_ATTEMPTS, this method is O(n) where n is the size of the query. In general, it produces optimal or nearly-optimal results, so a 'smarter' method may not be necessary.
pattern - a pattern to find a query plan formaxTraversalAttempts - number of traversal plans to testCopyright © 2017 Grakn Labs Ltd. All rights reserved.