Message passing in a distributed graph database

Patent metadata

Field	Value
Publication number	US-9990443-B2
Application number	US-201615264267-A
Country	US
Kind code	B2
Filing date	Sep 13, 2016
Priority date	Oct 28, 2015
Publication date	Jun 5, 2018
Grant date	Jun 5, 2018

Abstract

A system executes a query associated with an application against a graph database by providing, to a first shard of the graph database, the query and a first query header that specifies the first shard. The query includes a subject, a predicate and an object, and the graph database stores a graph that includes nodes, edges between the nodes, and predicates to represent and store data. In response to the query, the system receives results and associated result headers from the first shard and a second shard, where the result headers specify that the results are partial results that are particular fractions of a total result. Furthermore, a combination of the partial results provides the total result to the query that includes a subset of the graph. Note that the subset of the graph may include desired information expressed within an associated structure of the graph.

First claim

What is claimed is:

1. A computer-system-implemented method for querying a graph database, the method comprising:
receiving the query and a first query header at a first shard of the graph database, from a computer system separate from the graph database, wherein:
the graph database stores a graph comprising nodes, edges between the nodes, and predicates to represent data;
the query includes one or more of a subject, a predicate, and an object; and
the first query header specifies the first shard;

executing the query at the first shard of the graph database;
receiving first results and a first result header from the first shard, wherein the first result header specifies that the first results are first partial results; and
receiving second results and a second result header from a second shard of the graph database, wherein the second result header specifies that the second results are second partial results;
wherein the second results and the second result header are received from the second shard without a corresponding query being provided to the second shard by the computer system.

2. The method of claim 1 , wherein the graph represents the data with index-free adjacency.

3. The method of claim 1 , wherein the method further comprises combining the first partial results and the second partial results to obtain a total result.

4. The method of claim 1 , wherein the first result header includes information that indicates that the query was subdivided by the first shard and forwarded by the first shard to another shard.

5. The method of claim 1 , wherein at least one of the first partial results and the second partial results are received in a set of packets having associated sub-result headers that specify a total number of packets and a position of a given packet in the set of packets.

6. The method of claim 1 , further comprising:
providing the query and a second query header to the second shard;
wherein the second query header specifies the second shard.

7. The method of claim 1 , wherein the method further comprises storing information in a request map that indicates the query was sent to the first shard.

8. The method of claim 1 , wherein the subset of the graph includes the desired information expressed within an associated structure of the graph.

9. The method of claim 1 , wherein the data is associated with entities in a professional network.

10. The method of claim 1 , wherein the method further comprises:
receiving another query that is compatible with a type of database different from the graph database; and
converting the other query into the query.

11. The method of claim 10 , wherein the type of database includes one of a relational database and a hierarchical database.

12. An apparatus, comprising:
one or more processors;
memory; and
a program module, wherein the program module is stored in the memory and, during operation of the apparatus, is executed by the one or more processors to query a graph database, the program module including:
instructions for receiving the query and a first query header at a first shard of the graph database, from a computer system separate from the graph database, wherein:
the graph database stores a graph comprising nodes, edges between the nodes, and predicates to represent data;
the query includes one or more of a subject, a predicate, and an object; and
the first query header specifies the first shard;

instructions for executing the query at the first shard of the graph database;
instructions for receiving first results and a first result header from the first shard, wherein the first result header specifies that the first results are first partial results; and
instructions for receiving second results and a second result header from a second shard of the graph database, wherein the second result header specifies that the second results are second partial results;
wherein the second results and the second result header are received from the second shard without a corresponding query being provided to the second shard by the computer system.

13. The apparatus of claim 12 , wherein the graph represents the data with index-free adjacency.

14. The apparatus of claim 12 , wherein the program module comprises:
instructions for combining the first partial results and the second partial results to obtain a total result; and
instructions for providing at least a portion of the total result to an application associated with the query.

15. The apparatus of claim 12 , wherein at least one of the first partial results and the second partial results are received in a set of packets having associated sub-result headers that specify a total number of packets and a position of a given packet in the set of packets.

16. The apparatus of claim 12 , wherein:
the program module further comprises instructions for providing the query and a second query header to the second shard; and
the second query header specifies the second shard.

17. The apparatus of claim 12 , wherein the program module further comprises instructions for storing information in a request map that indicates the query was sent to the shard.

18. The apparatus of claim 12 , wherein the first result header includes information that indicates that the query was subdivided by the first shard and forwarded by the first shard to another shard.

19. The apparatus of claim 12 , wherein the program module further comprises:
instructions for receiving another query that is compatible with a type of database different from the graph database; and
instructions for converting the other query into the query.

20. A system, comprising:
a processing module comprising a non-transitory computer readable medium storing instructions that, when executed, cause the system to:
receive the query and a first query header at a first shard of the graph database, from a computer system separate from the graph database, wherein:
the graph database stores a graph comprising nodes, edges between the nodes, and predicates to represent data;
the query includes one or more of a subject, a predicate, and an object; and
the first query header specifies the first shard;

execute the query at the first shard of the graph database;
receive first results and a first result header from the first shard, wherein the first result header specifies that the first results are first partial results; and
receive second results and a second result header from a second shard of the graph database, wherein the second result header specifies that the second results are second partial results;

wherein the second results and the second result header are received from the second shard without a corresponding query being provided to the second shard by the computer system.

Assignees

• Linkedin Corp
• Microsoft Technology Licensing Llc

Inventors

• Song Yongling
• Carter Andrew J
• Ehrlich Joshua D
• Meyer Scott M

Classifications

• G06F17/30979 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic

• G06F16/9024 Primary

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

• G06F16/90335 Primary

  Query processing · CPC title