Query-time analytics on graph queries spanning subgraphs

Patent metadata

Field	Value
Publication number	US-10467229-B2
Application number	US-201615282718-A
Country	US
Kind code	B2
Filing date	Sep 30, 2016
Priority date	Sep 30, 2016
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

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 claimed:

1. A method for reducing bandwidth consumption by extending graph queries to refine results prior to transmission, comprising:
receiving, at a graph server hosting a graph database, a single request from a user device, the single request including a graph query comprising criteria to produce a subgraph and an analytic to refine the subgraph produced by the graph query;
querying the graph database according to the criteria of the graph query to produce the subgraph;
extending the graph query based on the analytic to identify properties of the subgraph at a same time the graph database is being queried;
refining the subgraph based on the properties and the analytic; and
returning the refined subgraph to the user device.

2. The method of claim 1 , wherein the refined subgraph is returned according to an ordering based on relative values of the properties.

3. The method of claim 1 , wherein the refined subgraph is reduced in size relative to the subgraph based on values of the properties.

4. The method of claim 1 , wherein returning the refined subgraph comprises returning one or more of the properties.

5. The method of claim 1 , wherein the single request includes a second query, the graph server further operable to further refine the graph query, as an iteration based on the second query, prior to returning the refined graph query to the user device.

6. The method of claim 1 , wherein the single request includes a second analytic, the graph server further operable to further extend and refine the graph query, as an iteration based on the second analytic, prior to returning the refined graph query to the user device.

7. 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.

8. A system for reducing bandwidth consumption by extending graph queries to refine results prior to transmission, comprising:
a processor; and
a memory storage device including instructions that when executed by the processor provide:
a graph database hosting a relational database accessible via queries made in a first language;
a library defining one or more functions in a second language;
a graph server in communication with a user device, the graph database, and the library, the graph server operable to:
receive a single request from the user device that includes a graph query formatted in the first language and comprising criteria to produce a subgraph and an analytic formatted according to the second language to refine the subgraph produced by the graph query;
query the graph database according to the criteria of the graph query to produce the subgraph of the relational database;
call the library to extend the graph query based on the analytic and return properties of the subgraph based on the analytic at a same time the graph database is being queried;
refine the graph query based on the returned properties; and
transmit the refined graph query to the user device.

9. The system of claim 8 , wherein the single request includes a second query, the graph server further operable to further refine the graph query, as an iteration based on the second query, prior to transmitting the refined graph query.

10. The system of claim 8 , wherein the single request includes a second analytic, the graph server further operable to further extend and refine the graph query, as an iteration based on the second analytic, prior to transmitting the refined graph query.

11. The system of claim 8 , wherein refining the graph query returns a value of the properties, the value selected from the group consisting of:
a maximum;
a minimum; and
an average.

12. The system of claim 8 , wherein refining the graph query includes ordering nodes comprising the subgraph based on a ranking of the properties.

13. The system of claim 8 , wherein the subgraph produced is stored in the graph database.

14. The system of claim 8 , wherein producing the subgraph calls a previously stored subgraph from storage in the graph database.

15. A hardware computer-readable storage medium including instructions for reducing bandwidth consumption by extending graph queries to refine results prior to transmission, comprising:
receiving, at a graph server hosting a graph database comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, a single request from a user device, the single request including a graph query comprising criteria to produce a view and an analytic to refine the view produced by the graph query;
querying the graph database according to the criteria of the graph query to produce the view, the view including a subset of nodes and edges comprising the graph database;
extending the graph query based on the analytic to identify one or more nodes included in the view having specified properties at a same time the graph database is being queried;
refining the view based on the identified one or more nodes having the specified properties; and
returning the refined view to the user device.

16. The hardware computer-readable storage medium of claim 15 , wherein extending the graph query further comprises identifying one or more edges associated with the identified one or more nodes.

17. The hardware computer-readable storage medium of claim 16 , wherein extending the graph query further comprises identifying external nodes outside of the view but that are connected to the identified one or more nodes by the identified one or more edges.

18. The hardware computer-readable storage medium of claim 17 , wherein extending the graph query further comprises analyzing the external nodes.

19. The hardware computer-readable storage medium of claim 15 , wherein the refined view is returned according to an ordering based on relative values of the specified properties.

20. The hardware computer-readable storage medium of claim 15 , wherein the single request includes additional queries and additional analytics, the graph server further operable to further extend and refine the graph query, as an iteration based on the additional queries and additional analytics, prior to returning the refined graph query to the user device.

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/2425

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

• G06F16/24549 Primary

  Run-time optimisation · CPC title

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F16/9024 Primary

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