Query-time analytics on graph queries spanning subgraphs

Patent metadata

Field	Value
Publication number	US-11086873-B2
Application number	US-201916588309-A
Country	US
Kind code	B2
Filing date	Sep 30, 2019
Priority date	Sep 30, 2016
Publication date	Aug 10, 2021
Grant date	Aug 10, 2021

Abstract

Reductions in latencies and improvements in computational efficiency when analyzing data stored in a relational graph by integrating analytical capabilities into graph queries. Instead of a user having to run a graph query and then perform analytics on the resulting subgraph via separate requests, the user is enabled to run analytics at the time the graph query is run via a single request to the database maintaining the relationship graph, which improves the computationally efficiency of analyzing relational graphs and thereby improves the functionality of the computing devices hosting the relational graphs and running the queries and analytics.

First claim

We claim:

1. A method for extending graph queries to refine results prior to transmission, the method comprising:
receiving, from a user device at a graph server hosting a graph database, a request that includes a graph query comprising criteria to produce a subgraph and an analytic including one or more properties for use in refining the subgraph produced;
querying the graph database according to the criteria of the graph query to produce the subgraph;
extending the graph query based on the one or more properties included in the analytic at a same time the graph database is being queried;
refining the subgraph based on the analytic; and
returning the refined subgraph to the user device.

2. The method of claim 1 , wherein extending the graph query based on the analytic comprises:
identifying properties of the subgraph.

3. The method of claim 2 , wherein refining the subgraph comprises:
refining the subgraph further based on the properties of the subgraph.

4. The method of claim 3 , further comprising:
determining an order associated with the refined subgraph based on values of the properties of the subgraph; and
returning the refined subgraph to the user device according to the order.

5. The method of claim 3 , further comprising:
reducing a size of the refined subgraph relative to the subgraph based on values of the properties of the subgraph.

6. The method of claim 2 , further comprising:
returning values of the properties of the subgraph, the values including one or more of a maximum value, a minimum value, and an average value.

7. The method of claim 1 , further comprising:
prior to returning the refined subgraph to the user device, one or more of:
iteratively refining the subgraph based on an additional graph query included in the request; and
iteratively extending the graph query and refining the subgraph based on an additional analytic included in the request.

8. The method of claim 1 , wherein extending the graph query further comprises:
calling a library defining one or more functions foreign to a graph query language in which the graph query is formatted, wherein the analytic references the one or more functions inline with the graph query.

9. A server for extending graph queries to refine results prior to transmission, comprising:
a processing unit; and
a memory coupled to the processing unit and storing instructions that, when executed by the processing unit, cause the processing unit to:
receive, from a user device, a request that includes a graph query comprising criteria to produce a subgraph and an analytic including one or more properties for use in refining the subgraph produced;
query a graph database hosted by the server according to the criteria of the graph query to produce the subgraph;
extend the graph query based on the one or more properties included in the analytic;
refine the subgraph based on the analytic; and
return the refined subgraph to the user device.

10. The server of claim 9 , wherein the graph query is formatted in a first language, the analytic is formatted in a second language, and the processing unit is further caused to:
produce the subgraph based on the criteria that is supported by the first language of the graph query; and
call a library to extend the graph query based on the analytic, wherein the library defines one or more functions in the second language that are referenced by the analytic inline with the graph query.

11. The server of claim 10 , wherein the library is one of:
stored on the server prior to receiving the request;
included within the request; or
specified within the request, wherein the processing unit is further caused to download the library for storage on the server.

12. The server of claim 9 , wherein the graph database includes a relational graph comprising entities represented as nodes and relationships between the entities represented as edges connecting related nodes, and the subgraph produced is a subgraph of the relational graph.

13. The server of claim 12 , wherein the subgraph produced includes a subset of the nodes matching the criteria and associated edges that are connected to a node within the subset of the nodes.

14. The server of claim 13 , wherein the subgraph is further refined based on a property of one or more of the subset of the nodes and the associated edges.

15. The server of claim 14 , wherein to refine the subgraph based on the analytic, the processing unit is further caused to:
order the subset of the nodes based on a value of the property for each node within the subset of the nodes.

16. The server of claim 14 , wherein to refine the subgraph based on the analytic, the processing unit is further caused to:
reduce a size of the subgraph by removing, from the subset of the nodes and the associated edges, one or more nodes and edges not having the property.

17. The server of claim 9 , wherein the processing unit is further caused to:
store the refined subgraph in the graph database for use in producing subsequent subgraphs.

18. Computer storage media including instructions, which when executed by a processing unit perform a method for extending graph queries to refine results prior to transmission, the instructions comprising:
receiving, from a user device at a graph server hosting a graph database that includes a relational graph, a request that includes a graph query comprising criteria to produce a view of the relational graph and an analytic including one or more properties for use in refining the view produced;
querying the graph database according to the criteria of the graph query to produce the view;
extending the graph query based on the one or more properties included in the analytic;
refining the view based on the analytic; and
returning the refined view to the user device.

19. The computer storage media of claim 18 , wherein the relational graph comprises entities represented as nodes and relationships between the entities represented as edges connecting related nodes, the view produced includes a subset of the nodes matching the criteria of the graph query and associated edges that are connected to a node within the subset of the nodes, and the view is refined based on a property of one or more of the subset of the nodes and the associated edges that is specified by the analytic.

20. The computer storage media of claim 18 , wherein the request includes one or more of an additional graph query and an additional analytic, and prior to returning the refined view to the user device, the instructions further comprise one or more of:
iteratively refining the view based on the additional graph query; and
iteratively extending the graph query and refining the view based on the additional analytic.

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• G06F16/9024 Primary

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

• G06F16/24549 Primary

  Run-time optimisation · CPC title

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F16/2425

  Iterative querying; Query formulation based on the results of a preceding query · CPC title