IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0967684
(2015-12-14)
|
등록번호 |
US-10176220
(2019-01-08)
|
발명자
/ 주소 |
- Pirahesh, Mir Hamid
- Tian, Yuanyuan
|
출원인 / 주소 |
- International Business Machines Corporation
|
대리인 / 주소 |
Lieberman & Brandsorfer, LLC
|
인용정보 |
피인용 횟수 :
0 인용 특허 :
10 |
초록
▼
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
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.
대표청구항
▼
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 tabl
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; andreturning 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; andreturn 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 set of paths comprises paths with edges satisfying the edge condition and connecting the source nodes to a first set of intermediate nodes; andcompute a uni-directional filter on the first set of intermediate nodes;the target manager to: 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; andand apply the filter to the second set of intermediate nodes, application of the filter to reduce a quantity of data items from traversal from the selected intermediate paths; anda set of result paths returned from a join of the first intermediate set of paths with the second set of intermediate paths, and a length condition applied to the join. 14. The system of claim 13 further comprising the target manager to compute a second filter on the second set of intermediate nodes, and apply the filter on the first set of intermediate nodes, application of the filter to reduce the quantity of data items from the traversal from the selected intermediate paths. 15. The system of claim 13, wherein the functional unit further comprises an edge manager to apply pre-join processing to the edge table, and create a new table of paths, the pre-join processing to reduce the quantity of join operations. 16. The system of claim 15, further comprising the edge manager to apply a uni-directional filter to one of the first and second intermediate set of paths. 17. The system of claim 15, further comprising the edge manager to apply a bi-directional filter to both the first and second intermediate set of paths.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.