Asynchronously flattening graphs in relational stores

A computing device for asynchronously flattening graphs in a relational store, the computing device comprising:

• a memory configured to store instructions;
• and
• a processor coupled to the memory, the processor executing an application in conjunction with the instructions stored in the memory, wherein the application is configured to:
• retrieve forward paths of a start node from a paths table through a forward expand operation that includes:
• selection of a subset of paths with a start identification (id) matching the start node as the forward paths from the paths table;
• retrieve reverse paths of an end node from the paths table through a reverse expand operation that includes:
• selection of another subset of paths with an end id matching the end node as the reverse paths from the paths table;
• join the forward paths to the reverse paths through one of a cross-join operation and an iteration/join operation to determine link paths between the start node and the end node;
• re-execute the forward expand operation, the reverse expand operation, and the cross-join operation to remove one or more of the link paths if a reference count for the one or more of the link paths is zero;
• combine the link paths, the forward paths, and the reverse paths in the paths table;
• one of adjust reference counts in the paths table and duplicate records according to added link paths;
• add the link paths as a link between the start node and the end node into a links table, wherein the link in the links table corresponds to the link paths in the paths table;
• and
• utilize the reference counts to count a number of the forward and reverse paths between the start node and the end node.

A computer-readable memory device with instructions stored thereon for asynchronously flattening graphs in a relational store, the instructions comprising:

• retrieving forward paths of a start node from a paths table through a forward expand operation that includes:
• selection of a subset of paths with a start identification (id) matching the start node as the forward paths from the paths table;
• retrieving reverse paths of an end node from the paths table through a reverse expand operation that includes:
• selection of another subset of paths with an end id matching the end node as the reverse paths from the paths table;
• joining the forward paths to the reverse paths through a cross-join operation to determine link paths between the start node and the end node;
• re-executing the forward expand operation, the reverse expand operation, and the cross-join operation to remove one or more of the link paths if a reference count for the one or more of the link paths is zero;
• combining the link paths, the forward paths, and the reverse paths in the paths table;
• one of adjusting reference counts in the paths table and duplicating records according to added link paths;
• sorting the link paths by start id of the start node;
• adding the link paths as a link between the start node and the end node into a links table, wherein the link in the links table corresponds to the link paths in the paths table;
• including one or more of a link identification (id) and a link type for links in the links table;
• and
• utilizing one or more of the link type of associated with the links and a path type of the link paths associated with the links to indicate whether the link paths are bidirectional or unidirectional;
• and
• utilizing the reference counts to count a number of the forward and reverse paths between the start node and the end node.