Graph data derivatives

Patent metadata

Field	Value
Publication number	US-10810259-B2
Application number	US-201815940560-A
Country	US
Kind code	B2
Filing date	Mar 29, 2018
Priority date	Mar 29, 2018
Publication date	Oct 20, 2020
Grant date	Oct 20, 2020

Abstract

A method for executing a graph algorithm 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 by at least generating a derivative graph of a graph, the graph algorithm being executed on the graph, the graph being associated with a read-only graph data stored in a database, the executing of the graph algorithm a temporary attribute associated with the read-only graph data, the temporary attribute storing one or more modifications made to the read-only graph data by the executing of the graph algorithm, the read-only graph data including a plurality of vertices and one or more edges interconnecting the plurality of vertices, the database being a relational database that includes a vertex table and an edge table for storing the read-only graph data, and the read-only graph data being stored by storing a first attribute associated with each of the plurality of vertices and/or the each of one or more edges;
in response to determining that the derivative graph is defined as a snapshot of the graph, applying a change to the temporary attribute associated with the graph without propagating the change to the derivative graph;
in response to determining that the derivative graph is defined as a view of the graph, propagating the change to the derivative graph; and
executing, based at least on the derivative graph, the graph algorithm.

2. The system of claim 1 , wherein the graph algorithm modifies the read-only graph data by at least changing the first attribute, and/or adding a second attribute to each of the plurality of vertices and/or each of the one or more edges.

3. The system of claim 1 , wherein the derivative graph inherits, from the graph, the temporary attribute such that the derivative graph includes the temporary attribute.

4. The system of claim 1 , wherein the derivative graph is defined as the snapshot and/or the view based at least on a declaration included in programming code implementing the graph algorithm, and wherein the declaration indicates whether the derivative graph is the snapshot and/or the view of the graph.

5. The system of claim 1 , wherein the derivative graph comprises a sub-graph of the graph, and wherein the sub-graph includes some but not all of a plurality of vertices and/or edges comprising the graph.

6. The system of claim 1 , wherein the derivative graph comprises an inverse graph of the graph, and wherein the inverse graph reverses a directionality of one or more edges interconnecting a plurality of vertices comprising the graph.

7. A computer-implemented method, comprising:
responding to a request from a client to execute a graph algorithm by at least generating a derivative graph of a graph, the graph algorithm being executed on the graph, the graph being associated with a read-only graph data stored in a database, the executing of the graph algorithm modifying a temporary attribute associated with the read-only graph data, the temporary attribute storing one or more modifications made to the read-only graph data by the executing of the graph algorithm, the read-only graph data including a plurality of vertices and one or more edges interconnecting the plurality of vertices, the database being a relational database that includes a vertex table and an edge table for storing the read-only graph data, and the read-only graph data being stored by storing a first attribute associated with each of the plurality of vertices and/or the each of one or more edges;
in response to determining that the derivative graph is defined as a snapshot of the graph, applying a change to the temporary attribute associated with the graph without propagating the change to the derivative graph;
in response to determining that the derivative graph is defined as a view of the graph, propagating the change to the derivative graph; and
executing, based at least on the derivative graph, the graph algorithm.

8. The method of claim 7 , wherein the graph algorithm modifies the read-only graph data by at least changing the first attribute, and/or adding a second attribute to each of the plurality of vertices and/or each of the one or more edges.

9. The method of claim 7 , wherein the derivative graph inherits, from the graph, the temporary attribute such that the derivative graph includes the temporary attribute.

10. The method of claim 7 , wherein the derivative graph is defined as the snapshot and/or the view based at least on a declaration included in programming code implementing the graph algorithm, and wherein the declaration indicates whether the derivative graph is the snapshot and/or the view of the graph.

11. The method of claim 7 , wherein the derivative graph comprises a sub-graph of the graph, and wherein the sub-graph includes some but not all of a plurality of vertices and/or edges comprising the graph.

12. The method of claim 7 , wherein the derivative graph comprises an inverse graph of the graph, and wherein the inverse graph reverses a directionality of one or more edges interconnecting a plurality of vertices comprising the graph.

13. 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 by at least generating a derivative graph of a graph, the graph algorithm being executed on the graph, the graph being associated with a read-only graph data stored in a database, the executing of the graph algorithm modifying a temporary attribute associated with the read-only graph data, the temporary attribute storing one or more modifications made to the read-only graph data by the executing of the graph algorithm, the read-only graph data including a plurality of vertices and one or more edges interconnecting the plurality of vertices, the database being a relational database that includes a vertex table and an edge table for storing the read-only graph data, and the read-only graph data being stored by storing a first attribute associated with each of the plurality of vertices and/or the each of one or more edges;
in response to determining that the derivative graph is defined as a snapshot of the graph, applying a change to the temporary attribute associated with the graph without propagating the change to the derivative graph;
in response to determining that the derivative graph is defined as a view of the graph, propagating the change to the derivative graph; and
executing, based at least on the derivative graph, the graph algorithm.

Assignees

• Sap Se

Inventors

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

Classifications

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/23

  Updating · CPC title

• G06F16/9024 Primary

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