Method and system for processing graph queries

• US 9,092,481 B2
• Filed: 02/12/2013
• Issued: 07/28/2015
• Est. Priority Date: 11/12/2012
• Status: Active Grant

• Current Assignee: Software AG
• Original Assignee: Software AG
• Inventors: Digana, Tibor
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/764,846
• Publication Number:
  US 20140136520A1
• Time in Patent Office: 896 Days
• Field of Search: 707/722
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

In certain example embodiments, a graph query retrieves data items from a data source by indicating a source node, a target node, and a plurality of edges between the source and target nodes. Each edge includes one or more relation conditions. Each relation condition defines a mapping between items of one of the source item types and items of one of the target item types. The edges are selected and traversed from the source node to the target node in accordance with the relation condition(s), producing an intermediate set of result items including items of the data source that belong to the at least one target item type and fulfill the corresponding relation condition(s). Items from the intermediate set of result items that do not fulfill the corresponding relation condition(s) are deleted as further traversals are made. The intermediate set ultimately is returned as the graph query result.

Claims

1. A computer-implemented method for processing a graph query in connection with at least one processor of a computer system, wherein the graph query serves for retrieving data items from a data source by indicating at least

a source node representing one or more source item types,

a target node representing one or more target item types, and

a plurality of edges between the source node and the target node, wherein each edge comprises one or more relation conditions, wherein each relation condition defines a mapping between items of one of the source item types and items of one of the target item types,

the method comprising:

(a) selecting a first edge of the plurality of edges;

(b) traversing the selected first edge from the source node to the target node in accordance with the one or more relation conditions of the first edge to produce an intermediate set of result items, wherein the intermediate set of result items comprises the items of the data source which belong to the at least one target item type and which fulfill the corresponding one or more relation conditions;

(c) selecting a further edge of the plurality of edges;

(d) traversing the selected further edge from the target node to the source node in accordance with the one or more relation conditions of the selected further edge, and deleting items from the intermediate set of result items produced in (b) which do not fulfill the corresponding one or more relation conditions;

(e) repeating (c) and (d) for each further edge of the plurality of edges; and

(f) returning the intermediate set of result items as the result of the graph query processed by the at least one processor.

2. The method of claim 1, wherein the selected first edge comprises a plurality of relation conditions, and wherein (b) comprises producing the intermediate set of result items as the union of the results of each relation condition.

3. The method of claim 1, further comprising performing (c)-(e) iteratively for each item in the intermediate set of result items.

4. The method of claim 1, wherein selecting a first edge of the plurality of edges in (a) comprises selecting the edge which, when traversed in (b), is expected to result in a minimal intermediate set of result items.

5. The method of claim 4, wherein the selected edge is the edge which is connected to the least amount of source items.

6. The method of claim 1, wherein the graph query indicates a target node comprising a plurality of target item types, and wherein (a) and (b) are performed iteratively for each of the plurality of target item types, so that the intermediate set of result items comprises the items of the data source which belong to any of the plurality of target item types.

7. The method of claim 6, further comprising performing (c)-(e) iteratively for each of the plurality of target item types.

8. The method of claim 1, wherein the intermediate set of result items stores IDs representing the respective items in the data source.

9. A non-transitory computer readable storage medium tangibly storing a computer program comprising instructions that, when executed, implement the method of claim 1.

17. The method of claim 1, wherein the source node and the target node are neighboring nodes connected by the plurality of edges.

18. The method of claim 1, wherein the source node and the target node are directly adjacent to each other and are connected by the plurality of edges.

19. The method of claim 1, wherein:

selecting the first edge of the plurality of edges in (a) comprises selecting the edge which, when traversed in (b), is expected to result in a minimal intermediate set of result items from the plurality of edges; and

selecting the further edge of the plurality of edges in (c) comprises selecting the edge which, when traversed in (d), is expected to result in a minimum intermediate set of results items from the plurality of edges which have not been selected.

10. A computer system for processing a graph query, wherein the graph query serves for retrieving data items from a data source by indicating at least

a source node representing one or more source item types,

a target node representing one or more target item types, and

a plurality of edges between the source node and the target node, wherein each edge comprises one or more relation conditions, wherein each relation condition defines a mapping between items of one of the source item types and items of one of the target item types,

wherein the system comprises:

processing resources including at least one processor and a memory, the processing resources cooperating to at least;

select a first edge of the plurality of edges;

traverse the selected first edge from the source node to the target node in accordance with the one or more relation conditions of the first edge to produce an intermediate set of result items, wherein the intermediate set of result items comprises the items of the data source which belong to the at least one target item type and which fulfill the corresponding one or more relation conditions;

select a further edge of the plurality of edges;

traverse the selected further edge from the target node to the source node in accordance with the one or more relation conditions of the selected further edge, and for deleting items from the intermediate set of result items which do not fulfill the corresponding one or more relation conditions;

wherein the selection of a further edge of the plurality of edges and the traversal of the selected further edge from the target node to the source node is repeated for each further edge of the plurality of edges; and

wherein the processing resources are further configured to return the intermediate set of result items as the result of the graph query.

11. The system of claim 10, wherein the selected first edge comprises a plurality of relation conditions, and wherein the traversal of the selected first edge from the source node to the target node includes producing the intermediate set of result items as the union of the results of each relation condition.

12. The system of claim 10, wherein the selection of a further edge of the plurality of edges and the traversal of the selected further edge from the target node to the source node is performed iteratively for each item in the intermediate set of result items.

13. The system of claim 10, wherein the graph query indicates a target node comprising a plurality of target item types, and wherein the selection of a first edge of the plurality of edges and the traversal of the selected first edge from the source node to the target node is performed iteratively for each of the plurality of target item types, so that the intermediate set of result items comprises the items of the data source which belong to any of the plurality of target item types.

14. The system of claim 13, wherein the selection of a further edge of the plurality of edges and the traversal of the selected further edge from the target node to the source node is performed iteratively for each of the plurality of target item types.

15. The system of claim 10, wherein the processing resources are further configured to store item IDs in the intermediate set of results, the item IDs representing the respective items in the data source.

16. The system of claim 10, further comprising a non-transitory computer readable storage medium configured to store the intermediate set of result items returned as the result of the graph query.