PROCESSING DELETED EDGES IN GRAPH DATABASES

1 . A method, comprising:

executing one or more 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; and

when a query of the graph database is received, processing the query at the one or more processes by:

matching a query time of the query to a virtual time in a log-based representation of the graph database;

using an edge store for the graph database to access a subset of the edges matching the query;

generating a result of the query by materializing updates to the subset of the edges before the virtual time; and

providing the result in a response to the query.

2 . The method of claim 1 , wherein materializing updates to the subset of the edges before the virtual time comprises:

traversing the edge store in order of decreasing offset in the log-based representation to obtain updates to the subset of the edges before the virtual time; and

applying the updates to the subset of the edges to produce the result.

3 . The method of claim 2 , wherein traversing the edge store in order of decreasing offset in the log-based representation to obtain the updates to the subset of the edges before the virtual time comprises:

generating a set of deleted edges during traversal of the edge store in order of decreasing offset in the log-based representation.

4 . The method of claim 3 , wherein applying the updates to the subset of the edges to produce the result comprises:

during traversal of the edge store in order of decreasing offset in the log-based representation, checking an addition of an edge in the edge store against the set of deleted edges; and

materializing the edge in the result when the edge is not found in the set of deleted edges.

5 . The method of claim 4 , wherein applying the updates to the subset of the edges to produce the result further comprises:

obtaining an indication of a deletion of the edge from an entry for the edge prior to checking the addition of the edge against the set of deleted edges.

6 . The method of claim 1 , wherein materializing updates to the subset of the edges before the virtual time comprises:

obtaining an indication of deleted edges for a page in the edge store; and

when the indication specifies a lack of deleted edges in the page, including updates to the subset of the edges in the pages up to the virtual time.

7 . The method of claim 1 , wherein using the edge store to access the subset of the edges matching the query comprises:

performing a lookup of a hash map to obtain one or more offsets into the edge store, wherein the edge store comprises a one-linkage structure and a two-linkage structure; and

accessing the one or more offsets in the edge store to obtain the subset of the edges matching the query.

8 . The method of claim 7 , wherein accessing the one or more offsets into the edge store to obtain the subset of edges matching the query comprises:

obtaining, from the lookup of the index, a first offset in the one-linkage structure; and

using a first entry at the first offset in the one-linkage structure to access the subset of the edges matching the query in the edge store.

9 . The method of claim 1 , wherein matching the query time of the query to the virtual time in the log-based representation of the graph database comprises:

identifying a latest offset in the log-based representation at the query time.

10 . The method of claim 1 , wherein the edges in the edge store are stored in order of increasing offset in a log-based on representation of the graph database.

11 . The method of claim 1 , wherein the subset of the edges comprises:

a subject;

a predicate;

an object; and

an offset.

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 one or more 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; and

when a query of the graph database is received, process the query at the one or more processes by:

matching a query time of the query to a virtual time in a log-based representation of the graph database;

using an edge store for the graph database to access a subset of the edges matching the query;

generating a result of the query by materializing updates to the subset of the edges before the virtual time; and

providing the result in a response to the query.

13 . The apparatus of claim 12 , wherein materializing updates to the subset of the edges before the virtual time comprises:

traversing the edge store in order of decreasing offset in the log-based representation to obtain updates to the subset of the edges before the virtual time; and

applying the updates to the subset of the edges to produce the result.

14 . The apparatus of claim 13 , wherein traversing the edge store in order of decreasing offset in the log-based representation to obtain the updates to the subset of the edges before the virtual time comprises:

generating a set of deleted edges during traversal of the edge store in order of decreasing offset in the log-based representation.

15 . The apparatus of claim 14 , wherein applying the updates to the subset of the edges to produce the result comprises:

during traversal of the edge store in order of decreasing offset in the log-based representation, checking an addition of an edge in the edge store against the set of deleted edges; and

materializing the edge in the result when the edge is not found in the set of deleted edges.

16 . The apparatus of claim 15 , wherein applying the updates to the subset of the edges to produce the result further comprises:

obtaining an indication of a deletion of the edge from an entry for the edge prior to checking the addition of the edge against the set of deleted edges.

17 . The apparatus of claim 12 , wherein materializing updates to the subset of the edges before the virtual time comprises:

obtaining an indication of deleted edges for a page in the edge store; and

when the indication specifies a lack of deleted edges in the page, including updates to the subset of the edges in the pages up to the virtual time.

18 . The apparatus of claim 12 , wherein matching the query time of the query to the virtual time in the log-based representation of the graph database comprises:

identifying a latest offset in the log-based representation at the query time.

19 . A system, comprising:

a management module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system 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; and

a processing module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to use one or more of the processes to process the query by:

matching a query time of the query to a virtual time in a log-based representation of the graph database;

using an edge store for the graph database to access a subset of the edges matching the query;

generating a result of the query by materializing updates to the subset of the edges before the virtual time; and

providing the result in a response to the query.

20 . The system of claim 19 , wherein materializing updates to the subset of the edges before the virtual time comprises:

traversing the edge store in order of decreasing offset in the log-based representation to obtain updates to the subset of the edges before the virtual time; and

applying the updates to the subset of the edges to produce the result.