Extended path finding operations on graph data

Patent metadata

Field	Value
Publication number	US-10776371-B2
Application number	US-201815946385-A
Country	US
Kind code	B2
Filing date	Apr 5, 2018
Priority date	Apr 5, 2018
Publication date	Sep 15, 2020
Grant date	Sep 15, 2020

Abstract

A method for performing a path finding operation in graph data stored in a database is provided. The method may include receiving, from a client, a request to perform a weighted path operation on at least portion of the graph data. The portion of the graph data may correspond to a graph. The request may specify attributes associated with vertices and/or edges included in the graph. In response to the request, the weighted path operation may be performed by at least identifying a shortest path between two endpoints in the graph. The shortest path may minimize the one or more attributes of vertices and/or edges included in the shortest path. 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:
receiving, from a client, a request to perform a weighted path operation on at least a portion of graph data stored in a database, the portion of the graph data corresponding to a graph, the request specifying one or more attributes associated with a plurality of vertices and/or edges included in the graph; and
in response to the request, performing the weighted path operation by at least identifying a shortest path between two endpoints in the graph, the shortest path minimizing the one or more attributes of one or more vertices and/or edges included in the shortest path.

2. The system of claim 1 , wherein the database comprises a relational database that includes a vertex table and an edge table for storing the graph data, and wherein the storage of the graph data includes storing, in the vertex table and/or the edge table, the one or more attributes associated with the plurality of vertices and/or edges included in the graph.

3. The system of claim 1 , further comprising:
determining, for each of the plurality of vertices and/or edges, a weight corresponding to a function of the one or more attributes specified by the request.

4. The system of claim 3 , wherein a same weight is assigned to each of the plurality of vertices and/or edges in order for the shortest path to minimize a quantity of intervening vertices and/or edges between the two endpoints.

5. The system of claim 3 , wherein the shortest path is associated with a first weight comprising a sum of one or more weights associated with the one or more vertices and/or edges included in the shortest path, wherein the shortest path is identified based at least on the first weight being less than a second weight of at least one other path between the two endpoints, and wherein the first weight and/or the second weight are stored as a weight attribute of a corresponding path.

6. The system of claim 1 , further comprising:
responding to another request from the client by at least extracting, from the shortest path, at least a portion of an ordered sequence comprising the one or more vertices and/or edges included in the shortest path.

7. The system of claim 1 , wherein the performance of the weighted path operation further comprises generating a weighted path object corresponding to the shortest path.

8. The system of claim 7 , wherein the weighted path object comprises a snapshot of the graph, wherein the snapshot of the graph inherits all attributes and/or temporary attributes associated with the plurality of vertices and/or edges included in the graph, and wherein changes to the attributes and/or temporary attributes are not propagated to the snapshot of the graph.

9. The system of claim 1 , wherein the two end points comprise a vertex and/or an edge from the graph.

10. The system of claim 1 , wherein the weighted path operation comprises a stored procedure such that executable code associated with the weighted path operation is stored in the database.

11. A computer-implemented method, comprising:
receiving, from a client, a request to perform a weighted path operation on at least a portion of graph data stored in a database, the portion of the graph data corresponding to a graph, the request specifying one or more attributes associated with a plurality of vertices and/or edges included in the graph; and
in response to the request, performing the weighted path operation by at least identifying a shortest path between two endpoints in the graph, the shortest path minimizing the one or more attributes of one or more vertices and/or edges included in the shortest path.

12. The method of claim 11 , wherein the database comprises a relational database that includes a vertex table and an edge table for storing the graph data, and wherein the storage of the graph data includes storing, in the vertex table and/or the edge table, the one or more attributes associated with the plurality of vertices and/or edges included in the graph.

13. The method of claim 11 , further comprising:
determining, for each of the plurality of vertices and/or edges, a weight corresponding to a function of the one or more attributes specified by the request.

14. The method of claim 13 , wherein a same weight is assigned to each of the plurality of vertices and/or edges in order for the shortest path to minimize a quantity of intervening vertices and/or edges between the two endpoints.

15. The method of claim 13 , wherein the shortest path is associated with a first weight comprising a sum of one or more weights associated with the one or more vertices and/or edges included in the shortest path, wherein the shortest path is identified based at least on the first weight being less than a second weight of at least one other path between the two endpoints, and wherein the first weight and/or the second weight are stored as a weight attribute of a corresponding path.

16. The method of claim 11 , further comprising:
responding to another request from the client by at least extracting, from the shortest path, at least a portion of an ordered sequence comprising the one or more vertices and/or edges included in the shortest path.

17. The method of claim 11 , wherein the performance of the weighted path operation further comprises generating a weighted path object corresponding to the shortest path.

18. The method of claim 17 , wherein the weighted path object comprises a snapshot of the graph, wherein the snapshot of the graph inherits all attributes and/or temporary attributes associated with the plurality of vertices and/or edges included in the graph, and wherein changes to the attributes and/or temporary attributes are not propagated to the snapshot of the graph.

19. The method of claim 11 , wherein the two end points comprise a vertex and/or an edge from the graph.

20. A non-transitory computer-readable medium storing instructions, which when executed by at least one data processor, result in operations comprising:
receiving, from a client, a request to perform a weighted path operation on at least a portion of graph data stored in a database, the portion of the graph data corresponding to a graph, the request specifying one or more attributes associated with a plurality of vertices and/or edges included in the graph; and
in response to the request, performing the weighted path operation by at least identifying a shortest path between two endpoints in the graph, the shortest path minimizing the one or more attributes of one or more vertices and/or edges included in the shortest path.

Assignees

• Sap Se

Inventors

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

Classifications

• G06F16/2465 Primary

  Query processing support for facilitating data mining operations in structured databases · CPC title

• G06F16/2458 Primary

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title

• G06F16/9024

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