Query execution across multiple graphs

Patent metadata

Field	Value
Publication number	US-11874829-B2
Application number	US-202117532395-A
Country	US
Kind code	B2
Filing date	Nov 22, 2021
Priority date	Apr 21, 2017
Publication date	Jan 16, 2024
Grant date	Jan 16, 2024

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 first query for information stored in a graph, wherein the graph comprises a plurality of graph subparts;
executing the first query in a graph subpart of the plurality of graph subparts to identify one or more cross-graph reference resources associated with one or more other graph subparts of the graph, the one or more cross-graph reference resources comprising at least one of:
a second query used to identify a resource in the one or more other graph subparts of the graph;
a subpart identifier used to identify the one or more other graph subparts of the graph; or
a property identifier used to identify one or more properties associated with the resource in the one or more other graph subparts of the graph;

generating, based on the one or more cross-graph reference resources, a query execution context associated with the first query, the query execution context comprising a traversal path indicating one or more resources or relationships that are traversed while executing the first query; and
providing the query execution context to at least one of the one or more other graph subparts of the graph, the query execution context enabling continued execution of the first query in the at least one of the one or more other graph subparts.

2. The system of claim 1 , wherein executing the first query in the graph subpart of the plurality of graph subparts comprises:
identifying, based on the first query, the graph subpart from the plurality of graph subparts based on determining a parameter of the first query is present in the 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 an intermediate result comprises the one or more cross-graph reference resources.

4. The system of claim 3 , wherein the intermediate result comprises one or more partial matches for the first query, wherein a partial match comprises content identified in the graph subpart and stored in at least one of the one or more other graph subparts.

5. The system of claim 3 , wherein the intermediate result comprises the one or more cross-graph reference resources.

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

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

8. The system of claim 1 , the set of operations further comprising:
executing the first query in the at least one of the one or more other graph subparts;
identifying, in the at least one of one or more other graph subparts, a set of resources satisfying the first query, the set of resources including at least one resource corresponding to the one or more cross-graph reference resources; and
providing at least the set of resources in response to the first query.

9. A computer-implemented method comprising:
receiving a first query for information in a first graph subpart of a graph, the first query indicating an anchor resource to be used when executing the first query to identify a context or a starting resource for evaluating the first query;
traversing the first graph subpart to generate a traversal path associated with the first query, wherein the traversal path is comprised of one or more first resources and one or more relationships;
determining whether a first resource of the traversal path is a cross-graph reference resource associated with a second graph subpart of the graph, the cross-graph reference resource comprising at least one of:
a second query used to identify a second resource in the second graph subpart;
a subpart identifier used to identify the second graph subpart; or
a property identifier used to identify one or more properties associated with the second resource;

based on determining that the first resource of the traversal path is the cross-graph reference resource, storing the traversal path in a traversal path data structure for transmission to the second graph subpart; and
based on determining that the first resource of the traversal path is not the cross-graph reference resource, providing the traversal path as a result to the first query.

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

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

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

13. The computer-implemented method of claim 9 , wherein the first query is received from another graph subpart.

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

15. A computer-implemented method comprising:
receiving a first query for information stored in a graph comprising a plurality of graph subparts;
identifying a first graph subpart from the plurality of graph subparts;
traversing the first graph subpart to generate a traversal path associated with the first query, wherein the traversal path is comprised of one or more first resources and one or more relationships;
determining a first resource of the traversal path is a cross-graph reference resource associated with a second graph subpart of the graph, the second graph subpart storing one or more properties for a second resource corresponding to the cross-graph reference resource, the second resource being stored in the second graph subpart, the one or more properties not being stored in the graph subpart, the cross-graph reference resource comprising at least one of:
a second query used to identify the second resource;
a subpart identifier used to identify the second graph subpart; or
a property identifier used to identify the one or more properties for the second resource;

generating a query execution context associated with the first query comprising at least a part of the traversal path and at least a part of the first query; and
providing, to the second graph subpart, the query execution context for continued execution of the first query in the second graph subpart.

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

17. The computer-implemented method of claim 15 , further comprising:
based on determining that the first resource of the traversal path is not the cross-graph reference resource, providing the traversal path as a result to the first query.

18. The computer-implemented method of claim 15 , wherein identifying the first graph subpart comprises identifying the first graph subpart based on determining a parameter of the first

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/2471 Primary

  Distributed queries · CPC title

• G06F16/9024

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