Executing graph path queries

Patent metadata

Field	Value
Publication number	US-10176220-B2
Application number	US-201514967684-A
Country	US
Kind code	B2
Filing date	Dec 14, 2015
Priority date	Dec 14, 2015
Publication date	Jan 8, 2019
Grant date	Jan 8, 2019

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.

First claim

We claim:

1. 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 source nodes;
joining the source node set with the edge table and applying an edge condition, the application producing a first edge of a first plurality of edges in a first path;
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 paths with edges satisfying the edge condition and connecting the source nodes to a first set of intermediate nodes;
computing a uni-directional bloom filter on the first set of intermediate nodes;
applying a selection condition to the node table and generating a set of target nodes;
joining the target node set with the edge table and applying the edge condition, the application producing a second edge of a second plurality of edges in a second path;
in reverse direction, traversing the second path, including joining the edge table with the second edges in the second path, and producing a second intermediate set of paths, wherein the second intermediate set of paths comprises paths with edges satisfying the edge condition and connecting the target nodes to a second set of intermediate nodes;
applying the bloom filter to the second set of intermediate nodes, application of the filter reducing a quantity of data items resulting from the traversal from the selected intermediate paths; 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 intermediate nodes with the second set of intermediate nodes, and applying a length condition to the set of result paths.

2. The method of claim 1 , further comprising computing a uni-directional bloom filter on the second set of intermediate nodes, and applying the bloom filter on the first set of intermediate nodes, application of the filter reducing the quantity of data items resulting from the traversal from the selected intermediate paths.

3. The method of claim 1 , further comprising computing a second bloom filter on the second set of intermediate nodes, applying the bloom filter on the first set of intermediate nodes, application of the filter reducing the quantity of data items resulting from the traversal from the selected intermediate paths.

4. The method of claim 1 , further comprising applying pre-join processing to the edge table, and creating a new table of paths, the pre-join processing reducing a quantity of join operations.

5. The method of claim 4 , further comprising applying a uni-directional bloom filter to one of the first and second intermediate set of paths.

6. The method of claim 4 , further comprising applying a bi-directional bloom filters to both the first and second intermediate set of paths.

7. A computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, 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, the processor to:
apply a selection condition to the node table and generate a set of source nodes;
join the source node set with the edge table and apply an edge condition, the application producing a first edge of a first plurality of edges in a first path;
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 paths with edges satisfying the edge condition and connecting the source nodes to a first set of intermediate nodes;
compute a uni-directional bloom filter on the first set of intermediate nodes;
apply a selection condition to the node table and generating a set of target nodes;
join the target node set with the edge table and apply the edge condition, the application producing a second edge of a second plurality of edges in a second path;
in reverse direction, traverse the second path, including joining the edge table with the second edges in the second path, and produce a second intermediate set of paths, wherein the second intermediate set of paths comprises paths with edges satisfying the edge condition and connecting the target nodes to a second set of intermediate nodes;
apply the bloom filter to the second set of intermediate nodes, application of the filter reducing a quantity of data items resulting from the traversal from the selected intermediate paths; and
return a set of result paths by joining the first intermediate set of paths with the second set of intermediate paths, including an intersection of the first set of intermediate nodes with the second set of intermediate nodes, and application of a length condition to the set of result paths.

8. The computer program product of claim 7 , further comprising the processor to compute a uni-directional bloom filter on the second set of intermediate nodes, and apply the bloom filter on the first set of intermediate nodes, application of the filter reducing the quantity of data items resulting from the traversal from the selected intermediate paths.

9. The computer program product of claim 7 , further comprising the processor to compute a second bloom filter on the second set of intermediate nodes, and apply the bloom filter on the first set of intermediate nodes, application of the filter reducing the quantity of data items resulting from the traversal from the selected intermediate paths.

10. The computer program product of claim 7 , further comprising the processor to apply pre-join processing to the edge table, and create a new table of paths, the pre-join processing reducing a quantity of join operations.

11. The computer program product of claim 10 , further comprising the processor to apply a uni-directional bloom filter to one of the first and second intermediate set of paths.

12. The computer program product of claim 11 , further comprising the processor to apply a bi-directional bloom filters to both the first and second intermediate set of paths.

13. 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 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 to:
apply a selection condition to the node table and generate a set of source nodes;
join the source node set with the edge table and apply an edge condition, the application producing a first edge of a first plurality of edges in a first path;
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

Assignees

• IBM

Inventors

• Pirahesh Mir Hamid
• Tian Yuanyuan

Classifications

• G06F17/30958

  Physics · mapped topic

• G06F17/30454 Primary

  Physics · mapped topic

• G06F17/30477

  Physics · mapped topic

• G06F16/24537 Primary

  of operators · CPC title

• G06F16/2456

  Join operations · CPC title