Adaptable adjacency structure for querying graph data

Patent metadata

Field	Value
Publication number	US-10839012-B2
Application number	US-201815940570-A
Country	US
Kind code	B2
Filing date	Mar 29, 2018
Priority date	Mar 29, 2018
Publication date	Nov 17, 2020
Grant date	Nov 17, 2020

Abstract

A method for executing a graph algorithm is provided. The method may include responding to a request from a client to execute a graph algorithm on graph data stored in a database by determining data required to execute the graph algorithm. In response to determining that a first portion of the data required to execute the graph algorithm is absent from an existing adjacency structure that includes a second portion of the data required to execute the graph algorithm, the existing adjacency structure may be modified to include the first portion of data. The graph algorithm may be executed based on the modified adjacency structure. The execution of the graph algorithm may include querying, based on the modified adjacency structure, the graph data stored in the database. Related systems and articles of manufacture, including computer program products, are also provided.

First claim

What is claimed is:

1. A system, comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, result in operations comprising:
responding to a request from a client to execute a graph algorithm on graph data stored in a database by at least determining data required to execute the graph algorithm;
determining a matching adjacency structure does not exist based on at least a first portion of the data required to execute the graph algorithm being absent from a set of existing adjacency structures;
in response to determining the matching adjacency structure does not exist, determining, from the set of existing adjacency structures, an existing adjacency structure that includes a second portion of the data required to execute the graph algorithm;
in response to determining the existing adjacency structure that includes the second portion of the data required to execute the graph algorithm, (i) modifying the existing adjacency structure to include the first portion of the data, and (ii) executing, based at least on the modified existing adjacency structure, the graph algorithm, the graph algorithm being executed by at least querying, based on the modified existing adjacency structure, the graph data stored in the database; and
in response to determining that no existing adjacency structure includes the second portion of the data required to execute the graph algorithm, (i) generating a new adjacency structure to include at least one of a forward adjacent vertex, a forward adjacent edge, a backward adjacent vertex, a backward adjacent edge, a key dictionary, and an attribute dictionary, and (ii) executing, based at least on the new adjacency structure, the graph algorithm.

2. The system of claim 1 , further comprising:
in response to determining that the existing adjacency structure includes all of the data required to execute the graph algorithm, executing, based at least on the existing adjacency structure, the graph algorithm.

3. The system of claim 1 , wherein the graph data includes a plurality of vertices, and wherein the graph data further includes one or more edges interconnecting the plurality of vertices.

4. The system of claim 3 , wherein the database comprises a relational database that includes a vertex table storing the plurality of vertices and an edge table storing the one or more edges.

5. The system of claim 3 , wherein the data required to execute the graph algorithm includes incoming edges into and/or outgoing edges from each of the plurality of vertices.

6. The system of claim 3 , wherein the data required to execute the graph algorithm includes one or more vertices that are connected to each of the plurality of vertices by incoming edges and/or outgoing edges.

7. The system of claim 3 , wherein each vertex and/or edge is associated with an attribute, and wherein the data required to execute the graph algorithm includes an attribute dictionary enumerating a value for the attribute associated with each vertex and/or edge.

8. The system of claim 3 , wherein each vertex and/or edge is associated with a key, and wherein the data required to execute the graph algorithm includes a dictionary mapping the key to a different key assigned to each vertex and/or edge.

9. The system of claim 1 , wherein the data required to execute the graph algorithm is determined based at least on a programming code associated with the graph algorithm.

10. A computer-implemented method, comprising:
responding to a request from a client to execute a graph algorithm on graph data stored in a database by at least determining data required to execute the graph algorithm;
determining a matching adjacency structure does not exist based on at least a first portion of the data required to execute the graph algorithm being absent from a set of existing adjacency structures;
in response to determining the matching adjacency structure does not exist, determining, from the set of existing adjacency structures, an existing adjacency structure that includes a second portion of the data required to execute the graph algorithm;
in response to determining the existing adjacency structure that includes the second portion of the data required to execute the graph algorithm, (i) modifying the existing adjacency structure to include the first portion of the data, and (ii) executing, based at least on the modified existing adjacency structure, the graph algorithm, the graph algorithm being executed by at least querying, based on the modified existing adjacency structure, the graph data stored in the database; and
in response to determining that no existing adjacency structure includes the second portion of the data required to execute the graph algorithm, (i) generating a new adjacency structure to include at least one of a forward adjacent vertex, a forward adjacent edge, a backward adjacent vertex, a backward adjacent edge, a key dictionary, and an attribute dictionary, and (ii) executing, based at least on the new adjacency structure, the graph algorithm.

11. The method of claim 10 , further comprising:
in response to determining that the existing adjacency structure includes all of the data required to execute the graph algorithm, executing, based at least on the existing adjacency structure, the graph algorithm.

12. The method of claim 10 , wherein the graph data includes a plurality of vertices, and wherein the graph data further includes one or more edges interconnecting the plurality of vertices.

13. The method of claim 12 , wherein the database comprises a relational database that includes a vertex table storing the plurality of vertices and an edge table storing the one or more edges.

14. The method of claim 12 , wherein the data required to execute the graph algorithm includes incoming edges into and/or outgoing edges from each of the plurality of vertices.

15. The method of claim 12 , wherein the data required to execute the graph algorithm includes one or more vertices that are connected to each of the plurality of vertices by incoming edges and/or outgoing edges.

16. The method of claim 12 , wherein each vertex and/or edge is associated with an attribute, and wherein the data required to execute the graph algorithm includes an attribute dictionary enumerating a value for the attribute associated with each vertex and/or edge.

17. The method of claim 12 , wherein each vertex and/or edge is associated with a key, and wherein the data required to execute the graph algorithm includes a dictionary mapping the key to a different key assigned to each vertex and/or edge.

18. A non-transitory computer readable medium storing instructions, which when executed by at least one data processor, result in operations comprising:
responding to a request from a client to execute a graph algorithm on graph data stored in a database by at least determining data required to execute the graph algorithm;
determining a matching adjacency structure does not exist based on at least a first portion of the data required to execute the graph algorithm being absent from a set of existing adjacency structures;
in response to determining the matching adjacency structure does not exist, determining, from the set of existing adjacency structures, an existing adjacency structure that includes a second portion of the data required to execute the graph algorithm;
in response to determining the existing adjacency structure that includes the second portion of the data required to execute the graph algorithm, (i) modifying the

Assignees

• Sap Se

Inventors

• Bross Jan
• Kasperovics Romans
• Fischer Thomas
• Kinder Cornelia
• Paradies Marcus

Classifications

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/9024 Primary

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

• G06F16/248

  Presentation of query results · CPC title

• G06F16/284

  Relational databases · CPC title