Fast in-memory technique to build a reverse CSR graph index in an RDBMS

A method comprising:

• obtaining a mapping of a relational schema of a database to a graph data model, wherein:
• the relational schema identifies one or more vertex tables that correspond to one or more respective vertex types in the graph data model and one or more edge tables that correspond to one or more respective edge types in the graph data model, and
• each edge type in the one or more edge types is associated with a respective source vertex type of the one or more vertex types and a respective target vertex type of the one or more vertex types;
• populating, based on said mapping, a forward compressed sparse row (CSR) representation for forward traversal of edges of an edge type of the one or more edge types, wherein each edge of the edge type:
• originates at a source vertex of the source vertex type of the edge type, and
• terminates at a target vertex of the target vertex type of the edge type,
• wherein the forward CSR representation comprises:
• a forward destination array that indicates which vertices of the target vertex type of the edge type terminate which respective edges of the edge type, and
• a forward source array that indicates a respective forward range of offsets into the forward destination array for each vertex of the source vertex type of the edge type;
• populating, based on the forward CSR representation, a reverse CSR representation of the edge type for reverse traversal of the edges of the edge type, wherein the reverse CSR representation comprises:
• a reverse source array that indicates which vertices of the source vertex type of the edge type originate which respective edges of the edge type, and
• a reverse destination array that indicates a respective reverse range of offsets into the reverse source array for each vertex of the target vertex type of the edge type;
• wherein said populating the reverse CSR representation comprises for each edge of the edge type:
• calculating an offset into the reverse source array by summing a value of an element of the reverse destination array that corresponds to the target vertex of the edge plus a value of a respective counter for the target vertex;
• based on said offset, storing, into an element of the reverse source array, at least one selected from the group consisting of:
• an identifier of the edge, and
• the offset, into the forward source array, of the source vertex of the edge.

One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

• obtaining a mapping of a relational schema of a database to a graph data model, wherein:
• the relational schema identifies one or more vertex tables that correspond to one or more respective vertex types in the graph data model and one or more edge tables that correspond to one or more respective edge types in the graph data model, and
• each edge type in the one or more edge types is associated with a respective source vertex type of the one or more vertex types and a respective target vertex type of the one or more vertex types;
• populating, based on said mapping, a forward compressed sparse row (CSR) representation for forward traversal of edges of an edge type of the one or more edge types, wherein each edge of the edge type:
• originates at a source vertex of the source vertex type of the edge type, and
• terminates at a target vertex of the target vertex type of the edge type,
• wherein the forward CSR representation comprises a forward destination array that indicates which vertices of the target vertex type of the edge type terminate which respective edges of the edge type;
• while populating the forward destination array for each edge of the edge type, incrementing a respective counter for the target vertex that terminates the edge;
• populating, based on the forward CSR representation, a reverse CSR representation of the edge type for reverse traversal of the edges of the edge type, wherein the reverse CSR representation comprises:
• a reverse source array that indicates which vertices of the source vertex type of the edge type originate which respective edges of the edge type, and
• a reverse destination array that indicates a respective reverse range of offsets into the reverse source array for each vertex of the target vertex type of the edge type,
• wherein for each edge of the edge type, said counter for the vertex that terminates the edge comprises a respective element of the reverse destination array for the vertex.

One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

• obtaining a mapping of a relational schema of a database to a graph data model, wherein:
• the relational schema identifies one or more vertex tables that correspond to one or more respective vertex types in the graph data model and one or more edge tables that correspond to one or more respective edge types in the graph data model, and
• each edge type in the one or more edge types is associated with a respective source vertex type of the one or more vertex types and a respective target vertex type of the one or more vertex types;
• populating, based on said mapping, a forward compressed sparse row (CSR) representation for forward traversal of edges of an edge type of the one or more edge types, wherein each edge of the edge type:
• originates at a source vertex of the source vertex type of the edge type, and
• terminates at a target vertex of the target vertex type of the edge type,
• wherein the forward CSR representation comprises:
• a forward destination array that indicates which vertices of the target vertex type of the edge type terminate which respective edges of the edge type, and
• a forward source array that indicates a respective forward range of offsets into the forward destination array for each vertex of the source vertex type of the edge type;
• populating, based on the forward CSR representation, a reverse CSR representation of the edge type for reverse traversal of the edges of the edge type, wherein the reverse CSR representation comprises:
• a reverse source array that indicates which vertices of the source vertex type of the edge type originate which respective edges of the edge type, and
• a reverse destination array that indicates a respective reverse range of offsets into the reverse source array for each vertex of the target vertex type of the edge type;
• wherein said populating the reverse CSR representation comprises for each edge of the edge type:
• calculating an offset into the reverse source array by summing a value of an element of the reverse destination array that corresponds to the target vertex of the edge plus a value of a respective counter for the target vertex;
• based on said offset, storing, into an element of the reverse source array, at least one selected from the group consisting of:
• an identifier of the edge, and
• the offset, into the forward source array, of the source vertex of the edge.