Fast path traversal in a relational database-based graph structure

A machine-readable storage medium encoded with instructions executable by a processor, wherein the instructions cause the processor to perform operations comprising:

• obtaining a first plurality of relational tables from a relational database, wherein each table of the first plurality of relational tables stores connectivity information for a graph that comprises a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes represents a data item stored in the relational database, each edge represents a relationship between two data items represented by two nodes of the plurality of nodes, and wherein each node of the plurality of nodes is assigned an initial identifier;
• clustering the plurality of nodes into a plurality of clusters, wherein each cluster of the plurality of clusters contains a subset of the plurality of nodes;
• assigning to each node in the plurality of nodes a new identifier;
• and
• constructing a second plurality of relational tables, wherein each table of the second plurality of relational tables stores connectivity information for the graph, and wherein each node of the plurality of nodes is identified in the second plurality of relational tables by the new identifier, such that a number of data blocks that must be loaded to a computer memory to traverse a path through the graph is minimized by reading index records from a relational table of the second plurality of relational tables.

A computer-implemented method, comprising:

• obtaining a first set of nodes of a graph, wherein each node in the first set of nodes represents a data item stored in a relational database, each edge of the graph represents a relationship between two data items represented by two nodes of the first set of nodes, and wherein each node in the first set of nodes is identified by an initial identifier;
• for each node in the first set of nodes, obtaining an identifier of a cluster of nodes to which the node belongs, wherein the identifier of the cluster is obtained by consulting a connectivity table;
• constructing, for each node in the first set of nodes, a new identifier that is based on the initial identifier identifying the node and the identifier of the cluster to which the node belongs;
• and
• traversing a path through the graph that connects two nodes in the first set of nodes, wherein the traversing is performed by reading index records from a relational table that identifies each node in the first plurality of nodes by its respective new identifier, and wherein the reading minimizes a number of data blocks that must be loaded to a computer memory to traverse the path.