Distributed graph database writes

• US 10,628,492 B2
• Filed: 07/20/2017
• Issued: 04/21/2020
• Est. Priority Date: 07/20/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ma, Xiaobin, Meyer, Scott M., Rodriguez, Andrew, Moustafa, Walaa Eldin M.
• Primary Examiner(s): Le, Thu Nguyet T
• Application Number:
  US15/655,303
• Publication Number:
  US 20190026334A1
• Time in Patent Office: 1,006 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

The disclosed embodiments provide a system for processing queries of a graph database. During operation, the system executes a set of processes for maintaining the graph database storing a graph, wherein the graph includes a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates. When a write query of the graph database is received, the system uses one or more of the processes to process the write query by using a schema of the graph database to validate the write query. Next, the system transmits the validated write query to a set of shards containing the graph database. Finally, the system processes the write query at each shard when a shard identifier representing the shard is matched to one or more attributes in the write query.

Claims

1. A method, comprising:

executing a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates;

when a write query of the graph database is received, using one or more of the processes to process the write query by;

using a schema of the graph database to validate the write query;

transmitting the validated write query to a set of shards comprising the graph database; and

for each shard in the set of shards, processing the write query at the shard when a shard identifier representing the shard is matched to one or more attributes in the write query;

when an additional write query fails validation using the schema, retrieving a latest version of the schema from one or more of the shards; and

using the latest version of the schema to revalidate the additional write query.

2. The method of claim 1, wherein using the schema to validate the write query comprises:

executing the write query in a branch of the graph database; and

validating the write query when the executed write query succeeds.

3. The method of claim 1, wherein processing the write query at the shard when the shard identifier representing the shard is matched to the one or more attributes in the write query comprises:

generating one or more shard identifiers from the one or more attributes; and

when the one or more shard identifiers includes the shard identifier representing the shard, executing a portion of the write query associated with the shard identifier at the shard.

4. The method of claim 3, wherein the one or more shard identifiers are generated from hashes of the one or more attributes.

5. The method of claim 3, wherein the one or more shard identifiers are generated from a set of identity-giving nodes in a compound from the write query.

6. The method of claim 5, wherein the one or more shard identifiers are further generated from a non-identity-giving attribute associated with the compound.

7. The method of claim 3, wherein the one or more shard identifiers are generated from a subject and an object in an edge from the write query.

8. The method of claim 7, wherein:

the one or more shard identifiers are further generated from an additional object in an existing edge comprising the subject and a predicate from the edge, wherein the predicate has a cardinality of 1; and

wherein processing the portion of the query associated with the shard identifier at the shard comprises deleting the existing edge at the shard.

9. The method of claim 1, wherein the schema is used to validate at least one of:

a predicate; and

a compound.

10. The method of claim 1, wherein each shard in the set of shards comprises:

a log-based representation of the graph database; and

an index of the graph database.

11. The method of claim 1, further comprising:

when the write query includes a new edge with a subject, an object, and a predicate, applying an implicit delete functionality at the shard to delete an existing edge comprising at least the predicate and the subject.

12. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

execute a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates;

when a write query of the graph database is received, use one or more of the processes to process the write query by;

using a schema of the graph database to validate the write query;

transmitting the validated write query to a set of shards comprising the graph database; and

for each shard in the set of shards, processing the write query at the shard when a shard identifier representing the shard matches one or more attributes in the write query;

retrieve a latest version of the schema from one or more of the shards when an additional write query fails validation using the schema; and

use the latest version of the schema to revalidate the additional write query.

13. The system of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

when the write query includes a new edge with a subject, an object, and a predicate, apply an implicit delete functionality at the shard to delete an existing edge comprising at least the predicate and the subject.

14. The apparatus of claim 12, wherein using the schema to validate the write query comprises:

executing the write query in a branch of the graph database; and

validating the write query when the executed write query succeeds.

15. The apparatus of claim 12, wherein processing the write query at the shard when the shard identifier representing the shard is matched to the one or more attributes in the write query comprises:

generating one or more shard identifiers from the one or more attributes; and

when the one or more shard identifiers includes the shard identifier representing the shard, executing a portion of the write query associated with the shard identifier at the shard.

16. The apparatus of claim 15, wherein each portion in the one or more portions comprises at least one of:

an edge; and

a compound.

17. The apparatus of claim 15, wherein the one or more shard identifiers are generated from hashes of the one or more attributes.

18. The apparatus of claim 15, wherein the one or more shard identifiers are generated from at least one of:

a set of identity-giving nodes in a compound from the write query;

a non-identity-giving attribute associated with the compound;

a subject and an object in an edge from the write query; and

an additional object in an existing edge comprising the subject and a predicate from the edge, wherein the predicate has a cardinality of 1.

19. A system, comprising:

a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates;

a broker comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to process a query of the graph database by;

using a schema of the graph database to validate the write query;

transmitting the validated write query to a set of shards comprising the graph database;

retrieving a latest version of the schema from one or more of the shards when an additional write query fails validation using the schema; and

using the latest version of the schema to revalidate the additional write query; and

the set of shards, wherein each shard in the set of shards comprises a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to process the write query at the shard when a shard identifier representing the shard is matched to one or more attributes in the write query.

20. The system of claim 19, wherein processing the write query at the shard when the shard identifier representing the shard is matched to the one or more attributes in the write query comprises:

generating one or more shard identifiers from the one or more attributes; and

when the one or more shard identifiers includes the shard identifier for the shard, executing a portion of the write query associated with the shard identifier at the shard.