US 2017/0255709 A1 · ATOMIC UPDATING OF GRAPH DATABASE INDEX STRUCTURES

Abstract

The disclosed embodiments provide a system for updating an index structure of a graph database storing a graph. During operation, the system includes, in the index structure, a first compressed edge store containing a first compact representation of edges in the graph at a first virtual time and a first series of updates to the edges after the first virtual time. At a second virtual time, the system creates a second compact representation of the edges from the first compact representation and the first series of updates. The system then appends, to the second compact representation, a second series of updates to the edges after the second virtual time to produce a second compressed edge store. Finally, the system updates the index structure by atomically replacing, in the index structure, a reference to the first compressed edge store with a reference to the second compressed edge store.

Claims20

Dependent claims

A method, comprising:

providing, by a computer system, an index structure for use in 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;
including, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time;
creating, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
appending, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store;
and
updating the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

3 more elements

An apparatus, comprising:

one or more processors;
and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
provide an index structure for use in 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;
include, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time;
create, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
append, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store;
and
update the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

6 more elements

A system, comprising:

a management module comprising a non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to:
provide an index structure for use in 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;
and
include, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time;
and
an update module comprising a non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to:
create, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
append, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store;
and
update the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

7 more elements

Dependencies are inferred from the claim text.

Atomic updating of graph database index structures

Life of this patent

Atomic updating of graph database index structures

Life of this patent

Abstract

Claims20