GRAPH PROCESSING SYSTEM
A graph comprising nodes and edges is stored by a distributed system as a collection of nodes and half-edges stored with their respective nodes. A message processor is associated with a node as needed to process messages passed between nodes, such that a given node has zero or one message processor assigned to it at a given time. Queries of the graph are resolved by processing a first portion of the query at a first node, and forwarding the results with the remaining portions of the query to a node linked by an edge to the present node.
1 . A system, comprising:
one or more processors;
one or more memories having stored thereon instructions that, in response to execution by the one or more processors, cause the system to at least:
receive a request to perform a query of a graph database with respect to a time period;
generate results for the query of the graph database with respect to the time period, wherein to generate the results, the system at least:
selects at least one node of the graph to process a portion of the query;
replays events associated with the selected at least one node, the events corresponding to the time period; and
evaluates a portion of the query applicable to the node based, at least in part, on the replayed events corresponding to the time period.
2 . The system of claim 1 , wherein to generate results for the query of the graph with respect to the time period, the system at least:
forwards results of evaluating the portion of the query applicable to the selected at least one node to one or more other nodes.
3 . The system of claim 1 , wherein the results for the query are generated based, at least in part, on a snapshot of a previously computed state.
4 . The system of claim 1 , wherein the query is processed based, at least in part, on a storage engine to store and retrieve node-related data.
5 . The system of claim 1 , wherein the query is processed with respect to an indicated window of time.
6 . The system of claim 1 , wherein the query is pinned to the time period.
7 . The system of claim 1 , the one or more memories having stored thereon further instructions that, in response to execution by the one or more processors, cause the system to at least maintain one or more index nodes, wherein the one or more index nodes comprising at least one of identifiers of nodes having a specific property or identifiers of edges of a specific type.
8 . The system of claim 1 , wherein the system generates a notification when a criteria or pattern defined by the query is matched.
9 . The system of claim 1 , wherein the query is a semantic query.
10 . The system of claim 1 , wherein the time period corresponds to at least one of a window of time or a point in time.
11 . A computer-implemented method, comprising:
receiving a request to perform a query of a graph database with respect to one or more indicated times;
generating results for the query of the graph database with respect to the one or more indicated times, by at least:
selecting at least one node of the graph to process a portion of the query;
replaying events associated with the selected at least one node, the events corresponding to the one or more indicated times; and
evaluating one or more portions of the query applicable to the node based, at least in part, on the replayed events corresponding to the one or more indicated times.
12 . The method of claim 11 , further comprising:
generating results for the query of the graph with respect to the one or more indicated times by at least forwarding results of evaluating the one or more portions of the query applicable to the selected at least one node to one or more other nodes.
13 . The method of claim 11 , wherein the results for the query are generated based, at least in part, on a snapshot of a previously computed state.
14 . The method of claim 11 , wherein the query is processed based, at least in part, on a storage engine to store and retrieve node-related data.
15 . The method of claim 11 , wherein the query is a standing query.
16 . The method of claim 11 , wherein the query is a semantic query.
17 . A non-transitory computer-readable medium comprising instructions stored thereon, wherein the instructions, when performed by one or more processors of one or more computing devices, cause the one or more computing devices to at least:
receive a request to perform a query of a graph database with respect to a time period;
generate results for the query of the graph database with respect to the time period by at least:
selecting at least one node of the graph to process a portion of the query;
replaying events associated with the selected at least one node, the events corresponding to the time period; and
evaluating a portion of the query applicable to the node based, at least in part, on the replayed events corresponding to the time period.
18 . The non-transitory computer-readable medium of claim 17 , having stored thereon further instructions that, when performed by the one or more processors, cause the one or more computing devices to generate results for the query of the graph with respect to the time period by at least forwarding results of evaluating the portion of the query applicable to the selected at least one node to one or more other nodes.
19 . The non-transitory computer-readable medium of claim 17 , wherein the query is processed based, at least in part, on a storage engine to store and retrieve node-related data.
20 . The non-transitory computer-readable medium of claim 17 , having stored thereon further instructions that, when performed by the one or more processors, cause the one or more computing devices to maintain one or more index nodes each comprising at least one of identifiers of nodes having a specific property or identifiers of edges of a specific type.