Efficient, in-memory, relational representation for heterogeneous graphs

Patent metadata

Field	Value
Publication number	US-12361065-B2
Application number	US-202117330046-A
Country	US
Kind code	B2
Filing date	May 25, 2021
Priority date	Apr 18, 2018
Publication date	Jul 15, 2025
Grant date	Jul 15, 2025

Abstract

Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

First claim

What is claimed is:

1. A method, performed by one or more computers, and comprising:
reading a one-to-one mapping between a) a plurality of database tables in a relational database
and b) a plurality of vertex types in a graph being constructed in a volatile memory;
for each column of a plurality of columns in the database table, populating, in the volatile memory, based on the one-to-one mapping, a respective distinct vertex property vector that contains only a plurality of values from the column;
for each row of a plurality of rows in the database table:
i) creating, in the graph, a vertex, which represents the row, as an instance of the distinct vertex type of the database table;
ii) associating the vertex with a unique offset;

wherein for each column of the plurality of columns, said populating comprises storing a value from the column of the row into the vertex property vector at the unique offset of the vertex; and
reading the graph by accessing the vertex property vector of the distinct vertex type of the database table.

2. The method of claim 1 wherein said reading comprises executing a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of columns of a particular database table unless the particular database table is associated with a vertex type of said one or more vertex types.

3. The method of claim 1 wherein:
the method further comprises associating said distinct vertex type with a plurality of distinct edge types;
the reading of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

4. The method of claim 1 further comprising:
assigning a unique serial number to said distinct vertex type;
identifying a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.

5. The method of claim 4 wherein said identifying pair consists of at most 128 bits.

6. The method of claim 4 wherein said identifying pair consists of at most 64 bits.

7. The method of claim 4 wherein the unique serial number of the particular vertex type and said unique offset of the particular vertex are bit packed within said identifying pair.

8. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
reading a one-to-one mapping between a) a plurality of database tables in a relational database
and b) a plurality of vertex types in a graph being constructed in a volatile memory;
for each column of a plurality of columns in the database table, populating, in the volatile memory, based on the one-to-one mapping, a respective distinct vertex property vector that contains only a plurality of values from the column;
for each row of a plurality of rows in the database table:
i) creating, in the graph, a vertex, which represents the row, as an instance of the distinct vertex type of the database table;
ii) associating the vertex with a unique offset;

wherein for each column of the plurality of columns, said populating comprises storing a value from the column of the row into the vertex property vector at the unique offset of the vertex; and
reading the graph by accessing the vertex property vector of the distinct vertex type of the database table.

9. The one or more non-transitory computer-readable media of claim 8 wherein said reading comprises executing a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of columns of a particular database table unless the particular database table is associated with a vertex type of said one or more vertex types.

10. The one or more non-transitory computer-readable media of claim 8 wherein:
the instructions further cause associating said distinct vertex type with a plurality of distinct edge types;
the reading of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

11. The one or more non-transitory computer-readable media of claim 8 wherein the instructions further cause:
assigning a unique serial number to said distinct vertex type;
identifying a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.

12. The one or more non-transitory computer-readable media of claim 11 wherein said identifying pair consists of at most 128 bits.

13. The one or more non-transitory computer-readable media of claim 11 wherein said identifying pair consists of at most 64 bits.

14. The one or more non-transitory computer-readable media of claim 11 wherein the unique serial number of the particular vertex type and said unique offset of the particular vertex are bit packed within said identifying pair.

15. A computer configured to:
read a one-to-one mapping between a) a plurality of database tables in a relational database
and b) a plurality of vertex types in a graph being constructed in a volatile memory;
for each column of a plurality of columns in the database table, populate, in the volatile memory, based on the one-to-one mapping, a respective distinct vertex property vector that contains only a plurality of values from the column;
for each row of a plurality of rows in the database table:
i) create, in the graph, a vertex, which represents the row, as an instance of the distinct vertex type of the database table;
ii) associate the vertex with a unique offset;

wherein for each column of the plurality of columns, said populate comprises store a value from the column of the row into the vertex property vector at the unique offset of the vertex; and
read the graph by accessing the vertex property vector of the distinct vertex type of the database table.

16. The computer of claim 15 wherein said read comprises execute a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of columns of a particular database table unless the particular database table is associated with a vertex type of said one or more vertex types.

17. The computer of claim 15 wherein:
the computer is further configured to associate said distinct vertex type with a plurality of distinct edge types;
the read of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

18. The computer of claim 15 wherein the computer is further configured to:
assign a unique serial number to said distinct vertex type;
identify a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.

Assignees

• Oracle Int Corp

Inventors

• Hilloulin Damien
• Bartolini Davide
• Van Rest Oskar
• Weld Alexander
• Hong Sungpack
• Chafi Hassan

Classifications

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/288

  Entity relationship models · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title