Branch threading in graph databases

Patent metadata

Field	Value
Publication number	US-11567995-B2
Application number	US-201916523095-A
Country	US
Kind code	B2
Filing date	Jul 26, 2019
Priority date	Jul 26, 2019
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

The disclosed embodiments provide a system for processing queries of a graph database storing a graph, wherein the graph comprises a set of edges defined by a first linkage, a second linkage, and a third linkage. During operation, the system maintains the base version of an index of the graph database. Upon branching a version of the graph database from a first offset representing a virtual time in the base version of the graph database, the system creates a branched version of the index from a second offset corresponding to the virtual time in the base version of the index. The system then processes queries of the graph database based on the offsets and references from the branched version of the index to the base version of the index.

First claim

What is claimed is:

1. A method, comprising:
executing one or more processes for storing a graph in a base version of a graph database, wherein the graph comprises a set of edges defined by a first linkage, a second linkage, and a third linkage;
maintaining, by the one or more processes, a base version of an index of the graph database, wherein the index comprises:
an edge store comprising a first one-linkage structure storing values of the third linkage, a second one-linkage structure storing values of the second linkage, and a two-linkage structure storing values of the second and third linkages;
a first hash map storing mappings from values of the first linkage to the two-linkage structure and the second one-linkage structure; and
a second hash map storing mappings from the values of the first and second linkages to the first one-linkage structure;

upon branching a version of the graph database from a virtual time in the base version of the graph database, creating, by the one or more processes, a branched version of the index from offsets corresponding to the virtual time in the first and second one-linkage structures and the two-linkage structure in the base version of the index; and
using the one or more processes to process queries of the graph database based on the offsets and references from the branched version of the index to the base version of the index, wherein using the one or more processes to process the queries of the graph database comprises:
when the queries include a first query of the branched version that comprises a write of a first edge comprising a value of the first linkage that maps to the two-linkage structure of the base version:
writing values of the second and third linkages in the first edge to the two-linkage structure of the branched version; and
storing a first reference from the two-linkage structure of the branched version to the two-linkage structure in the base version.

2. The method of claim 1 , wherein using the one or more processes to process the queries of the graph database further comprises:
mapping the value of the first linkage in the first hash map of the branched version to the two-linkage structure in the branched version.

3. The method of claim 1 , wherein using the one or more processes to process the queries of the graph database further comprises:
when the queries include a second query of the branched version that comprises a write of a second edge that increases a number of edges comprising the value of the first linkage in the branched version beyond a threshold:
writing values of the second linkage mapped to the value of the first linkage in the second edge and the two-linkage structure in the base version and the branched version to the second one-linkage structure in the branched version;
writing values of the third linkage mapped to the value of the first linkage in the second edge and the two-linkage structure in the base version and the branched version to the first one-linkage structure in the branched version; and
mapping the value of the first linkage in the first hash map of the branched version to the second one-linkage structure in the branched version.

4. The method of claim 3 , wherein using the one or more processes to process the queries of the graph database further comprises:
storing a second reference from the second one-linkage structure in the branched version to the two-linkage structure in the branched version.

5. The method of claim 3 , wherein using the one or more processes to process the queries of the graph database further comprises:
mapping the value of the first linkage and a value of the second linkage in the second edge in the second hash map of the branched version to the first one-linkage structure in the branched version.

6. A method, comprising:
executing one or more processes for storing a graph in a base version of a graph database, wherein the graph comprises a set of edges defined by a first linkage, a second linkage, and a third linkage;
maintaining, by the one or more processes, a base version of an index of the graph database, wherein the index comprises:
an edge store comprising a first one-linkage structure storing values of the third linkage, a second one-linkage structure storing values of the second linkage, and a two-linkage structure storing values of the second and third linkages;
a first hash map storing mappings from values of the first linkage to the two-linkage structure and the second one-linkage structure; and
a second hash map storing mappings from the values of the first and second linkages to the first one-linkage structure;

upon branching a version of the graph database from a virtual time in the base version of the graph database, creating, by the one or more processes, a branched version of the index from offsets corresponding to the virtual time in the first and second one-linkage structures and the two-linkage structure in the base version of the index; and
using the one or more processes to process queries of the graph database based on the offsets and references from the branched version of the index to the base version of the index, wherein using the one or more processes to process the queries of the graph database comprises:
when the queries include a first query of the base version that comprises a write of an edge that increases a number of edges comprising a value of the first linkage in the base version beyond a threshold:
writing values of the second linkage mapped to the value of the first linkage in the edge and the two-linkage structure in the base version to the second one-linkage structure in the base version;
writing values of the third linkage mapped to the value of the first linkage in the edge and the two-linkage structure in the base version to the first one-linkage structure in the base version;
mapping the value of the first linkage in the first hash map of the base version to the second one-linkage structure in the base version; and
storing a reference from the second one-linkage structure in the base version to the two-linkage structure in the base version.

7. The method of claim 6 , wherein using the one or more processes to process the queries of the graph database further comprises:
when the queries include a second query of the branched version that comprises a read of edges comprising the value of the first linkage:
performing a lookup of the first hash map of the base version to access the second one-linkage structure in the base version;
using the reference in the second one-linkage structure to access the two-linkage structure in the base version; and
scanning offsets prior to an offset of the two-linkage structure in the base version that corresponds to the virtual time for the edges comprising the value of the first linkage.

8. A method, comprising:
executing one or more processes for storing a graph in a base version of a graph database, wherein the graph comprises a set of edges defined by a first linkage, a second linkage, and a third linkage;
maintaining, by the one or more processes, a base version of an index of the graph database, wherein the index comprises:
an edge store comprising a first one-linkage structure storing values of the third linkage, a second one-linkage structure storing values of the second linkage, and a two-linkage structure storing values of the second and third linkages;
a first hash map storing mappings from values of the first linkage to the two-linkage structure and the second one-linkage structure; and
a second hash map storing mappings from the values of the first and second linkages to the first one-linkage structure;

upon branching a version of the graph database from a virtual time in the base version of the

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Yang Yiming
• Rodriguez Andrew
• Carter Andrew J
• Meyer Scott M

Classifications

• G06F16/9024 Primary

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

• G06F16/903

  Querying (for retrieval from the web G06F16/953) · CPC title