Package dev.roanh.gmark.util

Class SelectivityGraph

java.lang.Object

dev.roanh.gmark.util.UniqueGraph<SelectivityType,SelectivityClass>

dev.roanh.gmark.util.SelectivityGraph

public class SelectivityGraph
extends UniqueGraph<SelectivityType,SelectivityClass>

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:

• SelectivityType
• SelectivityClass
• Schema

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	SelectivityGraph.DistanceMatrix	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

Fields

Modifier and Type	Field	Description
private final RangeList<Map<SelectivityClass,UniqueGraph.GraphNode<SelectivityType,SelectivityClass>>>	index	Efficient lookup index for the graph from selectivity type to graph node.
private final Schema	schema	The graph schema used to construct

Constructor Summary

Constructors

Constructor	Description
SelectivityGraph(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 Type	Method	Description
static SelectivityGraph.DistanceMatrix	computeDistanceMatrix(Schema schema)	Computes the shortest path between any two nodes in the schema graph.
SelectivityGraph.DistanceMatrix	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.
List<PathSegment>	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).
List<PathSegment>	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).
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.

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

Methods inherited from class java.lang.Object

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

Field Details

index

private final RangeList<Map<SelectivityClass,UniqueGraph.GraphNode<SelectivityType,SelectivityClass>>> index

Efficient lookup index for the graph from selectivity type to graph node.

schema

private final Schema schema

The graph schema used to construct

Constructor Details

SelectivityGraph

public SelectivityGraph(Schema schema,
 int maxLength)

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(Selectivity, SelectivityType, int, double)

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 is null the path is started from any node that has the SelectivityClass.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:

• generateRandomPath(Selectivity, int, double)

computeNumberOfPaths

public SelectivityGraph.DistanceMatrix 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.

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

public static SelectivityGraph.DistanceMatrix computeDistanceMatrix(Schema schema)

Computes the shortest path between any two nodes in the schema graph. This is done using a modified version of the Floyd-Warshall algorithm (all-pairs shortest path).

Parameters:

schema - The schema to compute the distance matrix for.

Returns:

The distance matrix for the given graph schema.