Package dev.roanh.gmark.lang.cpq

Class QueryGraphCPQ.PartialMap

java.lang.Object
dev.roanh.gmark.lang.cpq.QueryGraphCPQ.PartialMap
Enclosing class:
QueryGraphCPQ
private static final class QueryGraphCPQ.PartialMap extends Object
Object used to store partial mapping required for the query homomorphism testing algorithm.
See Also:

  • Field Details

    • left

      private List<QueryGraphCPQ.QueryGraphComponent> left
      The left hand side of the map, this is the side of the map with graph parts that need to be matched to equivalent parts in the other graph. This list essentially represents the attribute names of the relation for this map.

    • matches

      private QueryGraphCPQ.Row[] matches
      The parts of the other graph that are equivalent to the left part of the original graph. This array is essentially a list of rows in the relation, each representing a valid way of mapping all attributes.

  • Constructor Details

    • PartialMap

      private PartialMap(List<QueryGraphCPQ.QueryGraphComponent> left)
      Constructs a new partial map with the given set of graph parts to match to parts of the other graph.
      Parameters:
      left - The parts of the graph to match for.

  • Method Details

    • sort

      private void sort()
      Sorts the relation for this map on attribute names. This enforces a total order on the left elements and sorts the corresponding matches at the same time. This sort takes linear time in the largest distance between two elements of the left array.

    • swap

      private int swap(int i, int j)
      Swaps the element at the i-th and j-th position in left and all matches.
      Parameters:
      i - The first element position.
      j - The second element position.
      Returns:
      The QueryGraphCPQ.QueryGraphComponent.getID() of the element originally at the j-th position.

    • semiJoinSingle

      private void semiJoinSingle(QueryGraphCPQ.PartialMap other)
      Performs a natural left semi join of this partial map with the given other partial map. This is effectively a filtering operation where anything in this map is dropped if it does not have any overlap with at least one list in the given other partial map. The result of the semi join is stored in this map. Both maps are required to be sorted before running this join.
      Parameters:
      other - The other partial map to join with.
      See Also:

    • semiJoin

      private void semiJoin(QueryGraphCPQ.PartialMap other)
      Performs a natural left semi join of this partial map with the given other partial map. This is effectively a filtering operation where anything in this map is dropped if it does not have any overlap with at least one list in the given other partial map. The result of the semi join is stored in this map. Both maps are required to be sorted before running this join.

      Information about attributes from the given other map that did not appear in this map is also collected and attached to the rows in the matches stored at this map. As a result this join makes it possible to reconstruct complete graph homomorphism mappings.

      Parameters:
      other - The other partial map to join with.
      See Also:

    • toString

      public String toString()
      Overrides:
      toString in class Object