Caching of subgraphs and integration of cached subgraphs into graph query results

Patent metadata

Field	Value
Publication number	US-10445361-B2
Application number	US-201715399989-A
Country	US
Kind code	B2
Filing date	Jan 6, 2017
Priority date	Dec 15, 2016
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Systems, methods, and computer readable devices embodying instructions are provided herein for reducing latencies and/or improving computational efficiency when traversing data stored in a relational graph by caching subgraphs and enabling the utilization thereof. More specifically, after a user performs a graph query, the resulting subgraphs of the graph query are cached in a reusable form. Subsequent graph queries are able to identify cached subgraphs based on the graph query. Further, the subsequent graph query is operable to integrate the cached subgraphs as part of the result of subsequent graph query, which may include a portion or the entire result of the subsequent graph query being composed from cached subgraphs, thereby improving the computational efficiency and performance of querying relational graphs, reducing the query execution cost required to traverse the relational graphs, and improving the functionality of the computing devices hosting the relational graphs and running the queries.

First claim

We claim:

1. A method for reducing computational resource expenditures by caching subgraphs and integrating the cached subgraphs into graph query results, comprising:
receiving, at a graph server hosting a graph database, a graph query;
querying the graph database according to the graph query;
caching a subgraph, into a subgraph cache, resulting from querying the graph database, wherein the cached subgraph is identifiable by a characteristic associated with the graph query such that the cached subgraph is retrievable for integration into results for a subsequent graph query associated with the characteristic;
transmitting the cached subgraph;
receiving the subsequent graph query;
parsing the subsequent graph query to traverse an Abstract Syntax Tree (AST) associated with the cached subgraph, wherein the AST is a tree representation of an abstract syntactic structure of the cached subgraph, wherein the tree representation has two or more AST levels;
identifying the cached subgraph by the AST level; and
transmitting the cached subgraph in response to the subsequent graph query.

2. The method of claim 1 , further comprising receiving the subsequent graph query, wherein the subsequent graph query is a second query received after the graph query.

3. The method of claim 2 , further comprising analyzing the subsequent graph query for a subsequent characteristic associated with the subsequent graph query.

4. The method of claim 3 , further comprising identifying the cached subgraph, based on the subsequent characteristic being associated with the AST level.

5. The method of claim 4 , wherein the cached subgraph is an exact match for the subsequent graph query.

6. The method of claim 4 , wherein the cached subgraph represents a portion of a response to the subsequent graph query.

7. The method of claim 2 , wherein receiving the subsequent graph query further comprises a first element and a second element.

8. The method of claim 7 , wherein the cached subgraph is a partial match for the subsequent graph query.

9. The method of claim 7 , further comprising analyzing the subsequent graph query for a first characteristic associated with the first element.

10. The method of claim 9 , further comprising identifying the cached subgraph, based on the first characteristic.

11. The method of claim 10 , further comprising expanding the cached subgraph based on the second element of the subsequent graph query.

12. The method of claim 11 , wherein expanding the cached subgraph based on the second element of the subsequent graph query includes querying the subgraph cache with the second element of the subsequent graph query.

13. The method of claim 10 , further comprising identifying a second subgraph, in the subgraph cache, based on a second characteristic associated with the second element.

14. The method of claim 13 , further comprising combining the cached subgraph and the second subgraph.

15. The method of claim 14 , further comprising caching the combined subgraph.

16. A computer readable storage medium including computer readable instructions, which when executed by a processing unit perform steps for reducing computational resource expenditures by caching subgraphs and integrating the cached subgraphs into graph query results, comprising:
receiving, at a graph server hosting a graph database, a graph query, wherein the graph query includes a first element and a second element;
analyzing the graph query for a characteristic associated with the first element of the graph query;
identifying a subgraph, cached by the graph server, based on the characteristic associated with the first element;
expanding the subgraph based on the second element of the graph query;
caching the expanded subgraph;
transmitting the expanded subgraph;
receiving a subsequent graph query;
parsing the subsequent graph query to traverse an Abstract Syntax Tree (AST) associated with the cached expanded subgraph, wherein the AST is a tree representation of an abstract syntactic structure of the cached expanded subgraph, wherein the tree representation has two or more AST levels;
identifying the expanded cached subgraph by the AST level; and
transmitting the expanded cached subgraph in response to the subsequent graph query.

17. The computer readable storage medium of claim 16 , further comprising identifying another subgraph, cached by the graph server, based on the characteristic associated with the second element.

18. The computer readable storage medium of claim 17 , wherein expanding the another subgraph based on the second element of the graph query further comprises combining the subgraph and the another subgraph.

19. The computer readable storage medium of claim 16 , wherein expanding the subgraph based on the second element of the graph query further includes traversing the subgraph based on the second element of the graph query.

20. A system for reducing computational resource expenditures by caching subgraphs and integrating the cached subgraphs into graph query results, comprising:
a processing unit; and
a memory including computer readable instructions, which when executed by the processing unit, causes the system to be configured to:
receive, at a graph server hosting a graph database, a graph query, wherein the graph query includes a first element and a second element;
analyze the graph query for a characteristic associated with the first element;
identify a first subgraph, cached by the graph server, based on the characteristic associated with the first element;
identify a second subgraph, cached by the graph server, based on the characteristic associated with the second element;
combine the first subgraph and the second subgraph;
cache the combined subgraph;
transmit the combined subgraphs
receiving a subsequent graph query;
parsing the subsequent graph query to traverse an Abstract Syntax Tree (AST) associated with the cached expanded subgraph, wherein the AST is a tree representation of an abstract syntactic structure of the cached expanded subgraph, wherein the tree representation has two or more AST levels;
identifying the expanded cached subgraph by the AST level; and
transmitting the expanded cached sub graph in response to the subsequent graph query.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kreutzer Tor
• Kvalnes Åge
• Valvåg Steffen Viken
• Johansen Amund Kronen
• Eidesen Dag Steinnes
• Heen Peter Dahle
• Karlberg Jan-Ove Almli

Classifications

• G06F16/532 Primary

  Query formulation, e.g. graphical querying · CPC title

• G06F12/0893

  Caches characterised by their organisation or structure · CPC title

• G06F16/9024 Primary

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