Package dev.roanh.gmark.util
Class SelectivityGraph
java.lang.Object
dev.roanh.gmark.util.UniqueGraph<SelectivityType,SelectivityClass>
dev.roanh.gmark.util.SelectivityGraph
The selectivity graph is a directed graph between
selectivity types
. Given some
maximum path length this graph shows between which selectivity
types a path of length at most the given maximum path length
exists. Originally the selectivity graph is unlabelled, but
within gMark it is labelled with the selectivity class needed
to follow an edge. That is the links are as follows
(t1,s1) s2> (t2,s1*s2)
. See Also:

Nested Class Summary
Modifier and TypeClassDescriptionstatic final class
Matrix that encoder pair wise information for all selectivity types in a graph.Nested classes/interfaces inherited from class dev.roanh.gmark.util.UniqueGraph
UniqueGraph.GraphEdge<V,
E>, UniqueGraph.GraphNode<V, E> 
Field Summary
Modifier and TypeFieldDescriptionprivate final RangeList<Map<SelectivityClass,
UniqueGraph.GraphNode<SelectivityType, SelectivityClass>>> Efficient lookup index for the graph from selectivity type to graph node.private final Schema
The graph schema used to construct 
Constructor Summary
ConstructorDescriptionSelectivityGraph
(Schema schema, int maxLength) Constructs a new selectivity graph based off the given graph schema and with the given maximum path length. 
Method Summary
Modifier and TypeMethodDescriptioncomputeDistanceMatrix
(Schema schema) Computes the shortest path between any two nodes in the schema graph.computeNumberOfPaths
(Selectivity selectivity, int length) Computes a distance matrix containing for each pair of selectivity types how many paths of at most the given maximum length and with the given selectivity exist.generateRandomPath
(Selectivity selectivity, int length, double star) Randomly generates a path through the selectivity graph with the requested length that ends at a node with the given selectivity (meaning that this is also the selectivity of the path as a whole).generateRandomPath
(Selectivity selectivity, SelectivityType start, int length, double star) Randomly generates a path through the selectivity graph with the requested length that ends at a node with the given selectivity (meaning that this is also the selectivity of the path as a whole).resolve
(Type type, SelectivityClass sel) Resolves the given selectivity type presented as a type and selectivity class to the associated graph node adding a new node if required.Methods inherited from class dev.roanh.gmark.util.UniqueGraph
addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueNode, copy, getEdge, getEdge, getEdgeCount, getEdges, getNode, getNodeCount, getNodes, removeNodeIf, toAdjacencyList

Field Details

index
private final RangeList<Map<SelectivityClass,UniqueGraph.GraphNode<SelectivityType, indexSelectivityClass>>> Efficient lookup index for the graph from selectivity type to graph node. 
schema
The graph schema used to construct


Constructor Details

SelectivityGraph
Constructs a new selectivity graph based off the given graph schema and with the given maximum path length. Parameters:
schema
 The graph schema to use.maxLength
 The maximum path length.


Method Details

resolve
private UniqueGraph.GraphNode<SelectivityType,SelectivityClass> resolve(Type type, SelectivityClass sel) Resolves the given selectivity type presented as a type and selectivity class to the associated graph node adding a new node if required. Parameters:
type
 The type of the selectivity type.sel
 The selectivity of the selectivity type. Returns:
 The graph node associated with the given selectivity type.

generateRandomPath
public List<PathSegment> generateRandomPath(Selectivity selectivity, int length, double star) throws GenerationException Randomly generates a path through the selectivity graph with the requested length that ends at a node with the given selectivity (meaning that this is also the selectivity of the path as a whole). Finally, the multiplicity of the path can be specified (Kleene star probability). Parameters:
selectivity
 The selectivity of the path to generate.length
 The length of the path to generate.star
 The probability that a path segment can have a Kleene star above it, should be between 0 and 1. Returns:
 A list of path segments representing the edges in the generated path.
 Throws:
GenerationException
 When something going wrong while generating the path. Most likely meaning not valid path was found satisfying all the requirements. See Also:

generateRandomPath
public List<PathSegment> generateRandomPath(Selectivity selectivity, SelectivityType start, int length, double star) throws GenerationException Randomly generates a path through the selectivity graph with the requested length that ends at a node with the given selectivity (meaning that this is also the selectivity of the path as a whole). Optionally a starting selectivity type can be provided. Finally, the multiplicity of the path can be specified (Kleene star probability). Parameters:
selectivity
 The selectivity of the path to generate.start
 The selectivity type to start from, if this isnull
the path is started from any node that has theSelectivityClass.EQUALS
selectivity.length
 The length of the path to generate.star
 The probability that a path segment can have a Kleene star above it, should be between 0 and 1. Returns:
 A list of path segments representing the edges in the generated path.
 Throws:
GenerationException
 When something going wrong while generating the path. Most likely meaning not valid path was found satisfying all the requirements. See Also:

computeNumberOfPaths
Computes a distance matrix containing for each pair of selectivity types how many paths of at most the given maximum length and with the given selectivity exist. Parameters:
selectivity
 The selectivity of the paths to count.length
 The maximum length of the paths to count. Returns:
 The number of paths for each pair of selectivity types.

computeDistanceMatrix
Computes the shortest path between any two nodes in the schema graph. This is done using a modified version of the FloydWarshall algorithm (allpairs shortest path). Parameters:
schema
 The schema to compute the distance matrix for. Returns:
 The distance matrix for the given graph schema.
