Back to results
US 11,106,671 B2Granted
Executing graph path queries
AssigneeInternational Business Machines Corporation
InventorsMir Hamid Pirahesh, Yuanyuan Tian
Life of this patent
Estimating the term…
Abstract
Embodiments of the invention relate to executing graph path queries. A database stores data entities and attributes in node tables and stores links between nodes in an edge table. Edges form a path between a source node and a target node. A source node set is generated and joined with the edge table to produce a first intermediate set. Similarly, a target node set is generated and joined with the edge table to produce a second intermediate set. A result path is generated through a joining of the first and second intermediate paths and application of a length condition.
Claims20
A system comprising:
- a processing unit in communication with memory;
- a functional unit in communication with the processing unit, the functional unit having one or more tools configured to process a graph path query with data entities and attributes stored in a node table and links between nodes identified in the node table stored in an edge table, the edge table including a plurality of edges between a source node and a target node, and attributes of the edges,
- the functional unit comprising a source manager and a target manager;
- the source manager configured to:
- apply a selection condition to the node table and generate a set of one or more source nodes;
- join the source node set with the edge table and apply an edge condition, the application producing a first edge in a first path;
- and
- in a forward direction, traverse the first path, and join the first edge with the edge table to produce a first intermediate set of paths, wherein the first intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more source nodes to a first set of one or more intermediate nodes;
- and
- the target manager configured to:
- apply a selection condition to the node table and generate a set of one or more target nodes;
- join the target node set with the edge table and apply the edge condition, the application producing a second edge in a second path;
- and
- in reverse direction, traverse the second path, including joining the edge table with the second edge in the second path, and produce a second intermediate set of paths, wherein the second intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more target nodes to a second set of one or more intermediate nodes;
- and
- a set of result paths returned from a join of the first intermediate set of paths with the second set of intermediate paths, the returned set of result paths including an intersection of the first set of one or more intermediate nodes with the second set of one or more intermediate nodes, and a length condition applied to the join.
13 more elements
A computer program product comprising:
- a tangible computer readable storage medium;
- and
- computer readable program code embodied with the computer readable storage medium, the program code executable by a processor to:
- process a graph path query with data entities and attributes stored in a node table and links between nodes identified in the node table stored in an edge table, the edge table including a plurality of edges between a source node and a target node, and attributes of the edges;
- apply a selection condition to the node table and generate a set of one or more source nodes;
- join the source node set with the edge table and apply an edge condition, the application producing a first edge in a first path;
- in a forward direction, traverse the first path, including join the first edge with the edge table and produce a first intermediate set of paths, wherein the first intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more source nodes to a first set of one or more intermediate nodes;
- apply a selection condition to the node table and generate a set of one or more target nodes;
- join the target node set with the edge table and apply the edge condition, the application producing a second edge in a second path;
- in reverse direction, traverse the second path, including joining the edge table with the second edge in the second path, and produce a second intermediate set of paths, wherein the second intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more target nodes to a second set of one or more intermediate nodes;
- and
- return a set of result paths by joining the first intermediate set of paths with the second set of intermediate paths, the returned set of result paths including an intersection of the first set of one or more intermediate nodes with the second set of one or more intermediate nodes, and application of a length condition to the set of result paths.
9 more elements
A computer-implemented method for processing a graph path query, wherein the graph path query retrieves paths and each path being a sequence of connected edges, the method comprising:
- storing data entities and data attributes in a node table;
- storing links between nodes identified in the node table in an edge table, the edge table including a plurality of edges between a source node and a target node, and attributes of the edges;
- applying a selection condition to the node table and generating a set of one or more source nodes;
- joining the source node set with the edge table and applying an edge condition, the application producing a first edge in a first path;
- in a forward direction, traversing the first path, including joining the first edge with the edge table and producing a first intermediate set of paths, wherein the first intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more source nodes to a first set of one or more intermediate nodes;
- applying a selection condition to the node table and generating a set of one or more target nodes;
- joining the target node set with the edge table and applying the edge condition, the application producing a second edge in a second path;
- in reverse direction, traversing the second path, including joining the edge table with the second edge in the second path, and producing a second intermediate set of paths, wherein the second intermediate set of paths comprises one or more paths with one or more edges satisfying the edge condition and connecting the one or more target nodes to a second set of one or more intermediate nodes;
- and
- returning a set of result paths by joining the first intermediate set of paths with the second set of intermediate paths, including intersecting the first set of one or more intermediate nodes with the second set of one or more intermediate nodes, and applying a length condition to the set of result paths.
7 more elements
Dependencies are inferred from the claim text.