Query execution across multiple graphs

Patent metadata

Field	Value
Publication number	US-11243949-B2
Application number	US-201715493761-A
Country	US
Kind code	B2
Filing date	Apr 21, 2017
Priority date	Apr 21, 2017
Publication date	Feb 8, 2022
Grant date	Feb 8, 2022

Abstract

Examples of the present disclosure describe systems and methods for query execution across multiple graphs. In an example, a graph or isolated collection may be split into multiple subparts, such that each subpart may store information of the isolated collection. Cross-collection reference resources may be used to reference resources that are stored by other isolated collection subparts. A breadth-first search of an isolated collection subpart may be performed in order to identify matches or potential matches in an isolated collection subpart. In an example, a potential match may comprise a cross-collection reference resource, which may reference a resource in another isolated collection subpart. Once query execution has completed in the isolated collection subpart, query execution may be paused and transferred to another isolated collection subpart that comprises a resource referenced by a cross-collection resource reference. Accordingly, query execution may resume in the subsequent isolated collection subpart.

First claim

What is claimed is:

1. A system comprising: at least one processor; and a memory storing instructions that when executed by the at least one processor perform a set of operations comprising: receiving a query for information stored in a graph, wherein the graph is stored as a plurality of graph subparts; executing the query in a first graph subpart of the plurality of graph subparts to generate an intermediate result associated with the first graph subpart, wherein the intermediate result comprises a cross-graph reference resource of the first graph subpart that indicates a second graph subpart of the plurality of graph subparts, wherein the cross-graph reference resource comprises at least one of: a resource identifier of one or more resources in the second graph subpart, a query used to identify the one or more resources in the second graph subpart, a subpart identifier for the second graph subpart, or one or more properties associated with the one or more resources in the second graph subpart; generating, based on the cross-graph reference resource, a query execution context associated with the query for information comprising at least a part of the intermediate result from the first graph subpart and at least a part of the query; and providing, to the second graph subpart indicated by the cross-graph reference resource, the query execution context to continue execution of the query for information in the second graph subpart indicated by the cross-graph reference resource.

2. The system of claim 1 , wherein executing the query in the first graph subpart of the plurality of graph subparts comprises:
identifying, based on the query for information, the first graph subpart from the plurality of graph subparts based on determining a parameter of the query for information is present in the first graph subpart.

3. The system of claim 1 , wherein generating the query execution context and providing the query execution context is performed based on a determination that the intermediate result comprises the cross-graph reference resource.

4. The system of claim 1 , wherein the intermediate result comprises one or more partial matches for the query, wherein a partial match comprises information identified in the first graph subpart and stored in the second graph subpart.

5. The system of claim 1 , wherein the set of operations further comprises:
generating a compiled query for the received query, wherein the compiled query is executable in a virtual machine.

6. The system of claim 1 , wherein the query execution context comprises a security context indicating access control information for information in the graph.

7. The system of claim 1 , wherein the first graph subpart is stored by the system and wherein the second graph subpart is stored by another system.

8. A computer-implemented method for executing a query for information in a first graph subpart of a graph that is stored as a plurality of graph subparts, the method comprising:
receiving the query for information in the first graph subpart;
traversing the graph subpart to generate a traversal path associated with the query for information, wherein the traversal path is comprised of one or more resources and one or more relationships;
determining that the traversal path is a cross-graph reference resource of the first graph subpart that indicates a second graph subpart of the plurality of graph subparts;
based on determining that the traversal path includes a cross-graph reference resource, storing the traversal path in a traversal path data structure for transmission to the second graph subpart indicated by the cross-graph reference resource, wherein the cross-graph reference resource comprises at least one of:
a resource identifier of one or more resources in the second graph subpart,
a query used to identify the one or more resources in the second graph subpart,
a subpart identifier for the second graph subpart, or
one or more properties associated with the one or more resources in the second graph subpart; and

transmitting the traversal path data structure to the second graph subpart indicated by the cross-graph reference resource.

9. The computer-implemented method of claim 8 , wherein query for information comprises execution context information, and wherein traversing the first graph subpart comprises evaluating the first graph subpart from one or more resources identified in the execution context information.

10. The computer-implemented method of claim 9 , wherein the execution context information comprises the traversal path data structure.

11. The computer-implemented method of claim 8 , wherein the query for information is received from a third graph subpart of the plurality of graph subparts.

12. The computer-implemented method of claim 8 , further comprising generating a compiled query for the received query, wherein the compiled query is executable in a virtual machine.

13. The computer-implemented method of claim 9 , wherein the execution context information comprises a security context indicating access control information for information in the graph.

14. A computer-implemented method for executing a query for information across a plurality of graph subparts of a graph, the method comprising:
receiving the query for information stored in the graph;
identifying a graph subpart from the plurality of graph subparts;
traversing the first graph subpart to generate a traversal path associated with the query for information, wherein the traversal path is comprised of one or more resources and one or more relationships;
determining whether a resource of the traversal path is a cross-graph reference resource of the first graph subpart that indicates a second graph subpart of the plurality of graph subparts;
based on determining that the resource of the traversal path is a cross-graph reference resource, generating a query execution context associated with the query for information comprising at least a part of the traversal path and at least a part of the query, wherein the cross-graph reference resource comprises at least one of:
a resource identifier of one or more resources in the second graph subpart,
a query used to identify the one or more resources in the second graph subpart,
a subpart identifier for the second graph subpart, or
one or more properties associated with the one or more resources in the second graph subpart; and

providing, to the second graph subpart indicated by the cross-graph reference resource, the query execution context to continue execution of the query for information in the second graph subpart of the plurality of graph subparts indicated by the cross-graph reference resource.

15. The computer-implemented method of claim 14 , wherein the query for information comprises execution context information, and wherein traversing the first graph subpart comprises evaluating the first graph subpart from one or more resources identified in the execution context information.

16. The computer-implemented method of claim 14 , wherein the first graph subpart is identified based on determining a parameter of the query for information is present in the first graph subpart from the plurality of graph subparts.

17. The computer-implemented method of claim 14 , further comprising generating a compiled query for the received query, wherein the compiled query is executable in a virtual machine.

18. The computer-implemented method of claim 14 , wherein the query execution context comprises a security context indicating access control information for information in the gr

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kreutzer Tor
• Johansen Amund Kronen
• Valvåg Steffen Viken
• Kvalnes Åge
• Karlberg Jan-Ove

Classifications

• G06F16/2471 Primary

  Distributed queries · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title