A first plurality of relational tables is obtained from a relational database. 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 nodes, and each of the nodes is assigned an initial identifier. The nodes are clustered into a plurality of clusters. Each cluster contains a subset of the nodes, and all nodes in each subset are close to each other according to a metric. Each node is assigned a new identifier. The new identifier comprises a concatenation of an identifier associated with the cluster to which the node belongs and an identifier associated with the node. A second plurality of relational tables is constructed and stores connectivity information for the graph. The node is identified in the second plurality of relational tables by the new identifier.