Package dev.roanh.gmark.lang.cpq

Class QueryGraphCPQ.Row

java.lang.Object

dev.roanh.gmark.lang.cpq.QueryGraphCPQ.Row

Enclosing class:

QueryGraphCPQ

private static final class QueryGraphCPQ.Row
extends Object

A row instance represents a single potential homomorphism mapping for a partial map. A row also tracks information about past attributes that are required to construct a complete homomorphism mapping.

See Also:

• QueryGraphCPQ.PartialMap

Field Summary

Fields

Modifier and Type	Field	Description
private BitSet	best	The best (smallest) complete mapping as represented by this row.
private int	cost	The cost of the smallest complete mapping for this row.
private QueryGraphCPQ.QueryGraphComponent[]	match	The targets that this row maps the attributes from the partial map to.
private List<QueryGraphCPQ.OptionSet>	other	A list of option sets that complete the entire homomorphism mapping when combined with the match for this row.
private int	write	Current write index in match, this is the next position that a query graph component will be written to by add(QueryGraphComponent).

Constructor Summary

Constructors

Modifier	Constructor	Description
private	Row(int size)	Constructs a new row with space for the given number of mapping targets.

Method Summary

Modifier and Type	Method	Description
void	add(QueryGraphCPQ.QueryGraphComponent comp)	Adds a new match component to this row.
private void	computeBestUsage(int size)	Computes the best usage for this row.
private void	computeBestUsage(int offset, BitSet workSet, int size)	Computes the best usage for this row.
QueryGraphCPQ.QueryGraphComponent	get(int idx)	Gets the match component at the given index.
String	toString()
private void	updateBest(BitSet used)	Updates best mapping candidate for this row with the given candidate if this candidate has a lower cost than the current best candidate.

Methods inherited from class java.lang.Object

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

Field Details

match

private QueryGraphCPQ.QueryGraphComponent[] match

The targets that this row maps the attributes from the partial map to.

other

private List<QueryGraphCPQ.OptionSet> other

A list of option sets that complete the entire homomorphism mapping when combined with the match for this row. When constructing the complete mapping exactly one option from each option set has to be used.

write

private int write

Current write index in match, this is the next position that a query graph component will be written to by add(QueryGraphComponent).

best

private BitSet best

The best (smallest) complete mapping as represented by this row. This bitset can be seen as a map from QueryGraphCPQ.QueryGraphComponent.getID() to a boolean, where true means the component was used in the mapping. The cost of this mapping is given by cost and both are computed by computeBestUsage(int).

See Also:

• computeBestUsage(int)
• cost

cost

private int cost

The cost of the smallest complete mapping for this row. This value is computed by computeBestUsage(int) and is Integer.MAX_VALUE before that.

See Also:

• computeBestUsage(int)
• best

Constructor Details

Row

private Row(int size)

Constructs a new row with space for the given number of mapping targets.

Parameters:

size - The number of mapping targets to allocate space for.

Method Details

computeBestUsage

private void computeBestUsage(int size)

Computes the best usage for this row. This is the selection of options from the option sets in other that together with match results in the mapping with the smallest number of distinct targets. For this computation exactly one option from each option set has to be used. The result of this computation is stored in #best and its cost in #cost.

Parameters:

size - The size of the entire original query graph as the combined count of vertices and edges.

computeBestUsage

private void computeBestUsage(int offset,
 BitSet workSet,
 int size)

Computes the best usage for this row. This is the selection of options from the option sets in other that together with match results in the mapping with the smallest number of distinct targets. For this computation exactly one option from each option set has to be used. The result of this computation is stored in #best and its cost in #cost.

Parameters:

offset - The current option set to pick from.

workSet - The set of picked mappings so far encoded as a bit set with bits set based on component IDs.

size - The size of the entire original query graph as the combined count of vertices and edges.

updateBest

private void updateBest(BitSet used)

Updates best mapping candidate for this row with the given candidate if this candidate has a lower cost than the current best candidate. The cost is evaluated as the total number of distinct mapping targets.

Parameters:

used - A set of picked mappings that together form the complete candidate encoded as a bit set with bits set based on component IDs.

get

public QueryGraphCPQ.QueryGraphComponent get(int idx)

Gets the match component at the given index.

Parameters:

idx - The index to get.

Returns:

The match component at the given index.

add

public void add(QueryGraphCPQ.QueryGraphComponent comp)

Adds a new match component to this row.

Parameters:

comp - The component to append.

toString

public String toString()

Overrides:

toString in class Object