Time-based graph data model

• US 9,092,548 B2
• Filed: 03/15/2013
• Issued: 07/28/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Magnet Systems Incorporated
• Original Assignee: Magnet Systems Incorporated
• Inventors: Morsi, Magdi, Wen, Chih-Po, Chan, Robyn J., Kim, Hanju
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US13/838,143
• Publication Number:
  US 20140280302A1
• Time in Patent Office: 865 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Systems and processes for accessing data from a graph database are described. The system receives a request comprising time-based information. Time-based information of the request is compared with a first time interval, which is associated with at least one node of a graph. The node of the graph is matched based on the time-based information being at least partially within the first time interval. The system returns a result comprising an indicator of the node of the graph, wherein the node of the graph is associated with an entity, and the node of the graph includes an attribute of the entity.

Claims

1. A computer-implemented method for accessing data from a database, the method comprising:

receiving a request, the request comprising time-based information and relationship information;

comparing the time-based information of the request with a first time interval, the first time interval associated with at least one node of a graph, wherein the at least one node is associated with an entity, and the at least one node includes an attribute of the entity;

matching the at least one node of the graph, the matching of the at least one node based on the time-based information being at least partially within the first time interval;

returning a result, the result comprising a first indicator of the at least one node;

comparing the relationship information of the request with a relationship status, the relationship status associated with at least one edge of the graph; and

matching the at least one edge of the graph, the matching of the at least one edge based on the relationship information matching the relationship status, wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

2. The computer-implemented method of claim 1, the method comprising:

comparing the time-based information of the request with a second time interval, the second time interval associated with at least one edge of the graph;

matching the at least one edge of the graph, the matching of the at least one edge based on the time-based information being at least partially within the second time interval; and

wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

3. The computer-implemented method of claim 2, wherein:

the matching of the at least one node of the graph and the at least one edge of the graph are on a path with a strict match; and

the strict match requiring that edges and nodes on the path share a single valid time, the single valid time determined by identifying a single point-in-time falling within time intervals associated with each edge of the path and each node of the path.

4. The computer-implemented method of claim 3, further comprising:

accessing the at least one node based on an object identity value; and

wherein the object identity value is unique to the node, as compared to other nodes in the graph.

5. The computer-implemented method of claim 1, wherein:

the entity representation is selected from the group comprising a user, a content, an activity, and an event.

6. The computer-implemented method of claim 1, further comprising:

accessing a first version information of the entity associated with the at least one node;

accessing a second version information of the entity associated with the at least one node;

selecting one of the first version information and the second version information; and

wherein the selected version information is selected based on the time-based information, and wherein the result further indicates the selected version information.

7. The computer-implemented method of claim 6, wherein:

the first version information includes a first complete state information of the entity associated with the at least one node;

the second version information includes a second complete state information of the entity associated with the at least one node; and

the first version information is not the same as the second version information.

8. The computer-implemented method of claim 6, wherein:

the first version information includes a complete state information of the entity associated with the at least one node; and

the second version information includes a differential state information of the entity associated with the at least one node, based on the complete state information.

9. The computer-implemented method of claim 1, wherein:

the at least one edge comprises a label attribute value, the label attribute value indicating a type of participation between entities of two nodes connected by the at least one edge.

10. The computer-implemented method of claim 1, wherein:

the time-based information comprises a particular point-in-time or a particular duration of time.

11. A non-transitory computer-readable storage medium comprising computer-executable instructions which when executed by a processor, cause the processor to:

receive a request, the request comprising time-based information and relationship information;

compare the time-based information of the request with a first time interval, the first time interval associated with at least one node of a graph, wherein the at least one node is associated with an entity, and the at least one node includes an attribute of the entity;

match the at least one node of the graph, the matching of the at least one node based on the time-based information being at least partially within the first time interval;

return a result, the result comprising a first indicator of the at least one node;

compare the relationship information of the request with a relationship status, the relationship status associated with at least one edge of the graph; and

match the at least one edge of the graph based on the relationship information matching the relationship status, wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

12. The non-transitory computer-readable storage medium of claim 11, the method comprising:

comparing the time-based information of the request with a second time interval, the second time interval associated with at least one edge of the graph;

matching the at least one edge of the graph, the matching of the at least one edge based on the time-based information being at least partially within the second time interval; and

wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

13. The non-transitory computer-readable storage medium of claim 12, wherein:

the matching of the at least one node of the graph and the at least one edge of the graph are on a path with a strict match; and

the strict match requiring that edges and nodes on the path share a single valid time, the single valid time determined by identifying a single point-in-time falling within time intervals associated with each edge of the path and each node of the path.

14. The non-transitory computer-readable storage medium of claim 13, further comprising:

accessing the at least one node based on an object identity value; and

wherein the object identity value is unique to the node, as compared to other nodes in the graph.

15. The non-transitory computer-readable storage medium of claim 11, wherein:

the entity representation is selected from the group comprising a user, a content, an activity, and an event.

16. The non-transitory computer-readable storage medium of claim 11, further comprising:

accessing a first version information of the entity associated with the at least one node;

accessing a second version information of the entity associated with the at least one node;

selecting one of the first version information and the second version information; and

wherein the selected version information is selected based on the time-based information, and wherein the result further indicates the selected version information.

17. The non-transitory computer-readable storage medium of claim 16, wherein:

the first version information includes a first complete state information of the entity associated with the at least one node;

the second version information includes a second complete state information of the entity associated with the at least one node; and

the first version information is not the same as the second version information.

18. The non-transitory computer-readable storage medium of claim 16, wherein:

the first version information includes a complete state information of the entity associated with the at least one node; and

the second version information includes a differential state information of the entity associated with the at least one node, based on the complete state information.

19. The non-transitory computer-readable storage medium of claim 11, wherein:

the at least one edge comprises a label attribute value, the label attribute value indicating a type of participation between entities of two nodes connected by the at least one edge.

20. The non-transitory computer-readable storage medium of claim 11, wherein:

the time-based information comprises a particular point-in-time or a particular duration of time.

21. An apparatus for accessing data from a database, the apparatus comprising:

a memory configured to store data; and

a computer processor configured to;

receive a request, the request comprising time-based information and relationship information;

compare the time-based information of the request with a first time interval, the first time interval associated with at least one node of a graph, wherein the at least one node is associated with an entity, and the at least one node includes an attribute of the entity;

match the at least one node of the graph based on the time-based information being at least partially within the first time interval;

return a result, the result comprising a first indicator of the at least one node;

access a relationship information;

compare the relationship information of the request with a relationship status, the relationship status associated with at least one edge of the graph; and

match the at least one edge of the graph, the matching of the at least one edge based on the relationship information matching the relationship status, wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

22. The apparatus of claim 21, the computer processor further configured to:

compare the time-based information of the request with a second time interval, the second time interval associated with at least one edge of the graph;

match the at least one edge of the graph, the matching of the at least one edge based on the time-based information being at least partially within the second time interval; and

wherein the result further comprises a second indicator of the at least one edge, and the at least one edge connects the at least one node to a second node.

23. The apparatus of claim 22, wherein:

the matching of the at least one node of the graph and the at least one edge of the graph are on a path with a strict match; and

the strict match requiring that edges and nodes on the path share a single valid time, the single valid time determined by identifying a single point-in-time falling within time intervals associated with each edge of the path and each node of the path.

24. The apparatus of claim 23, the computer processor further configured to:

access the at least one node based on an object identity value; and

wherein the object identity value is unique to the node, as compared to other nodes in the graph.

25. The apparatus of claim 21, wherein:

the entity representation is selected from the group comprising a user, a content, an activity, and an event.

26. The apparatus of claim 21, the computer processor further configured to:

access a first version information of the entity associated with the at least one node;

access a second version information of the entity associated with the at least one node;

select one of the first version information and the second version information; and

wherein the selected version information is selected based on the time-based information, and wherein the result further indicates the selected version information.

27. The apparatus of claim 26, wherein:

the first version information includes a first complete state information of the entity associated with the at least one node;

the second version information includes a second complete state information of the entity associated with the at least one node; and

the first version information is not the same as the second version information.

28. The apparatus of claim 26, wherein:

the first version information includes a complete state information of the entity associated with the at least one node; and

the second version information includes a differential state information of the entity associated with the at least one node, based on the complete state information.

29. The apparatus of claim 21, wherein:

the at least one edge comprises a label attribute value, the label attribute value indicating a type of participation between entities of two nodes connected by the at least one edge.

30. The apparatus of claim 21, wherein:

the time-based information comprises a particular point-in-time or a particular duration of time.

31. A non-transitory computer-readable storage medium comprising computer-executable instructions for accessing data from a database, the instructions when executed by a processor causing the processor to:

receive a request, the request comprising a node constraint value and an edge constraint value;

traverse at least a portion of a graph of the graph database, the traversal being in response to receiving the request;

determine a first match of a first node of the graph, the first match based on the node constraint;

determine a second match of a second node of the graph, the second match based on the edge constraint;

return a result, the result comprising a first indicator of the first node and a second indicator of the second node;

wherein the first node is associated with a first entity, the first node includes an attribute of the first entity, and the first node comprises a first version information of the first entity and a second version information of the first entity; and

wherein the second node is associated with a second entity, the second node includes an attribute of the second entity, and the second node comprises a third version information of the second entity and a fourth version information of second the entity.