Extended path finding operations on graph data
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.
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.