SYMBOLIC HYPER-GRAPH DATABASE

• US 20130212131A1
• Filed: 02/09/2012
• Published: 08/15/2013
• Est. Priority Date: 02/09/2012
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: REDDY, Subodh M.
• Granted Patent: US 9,507,875 B2
• Time in Patent Office: Days
• US Class Current: 707/798
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A graph database is described. The graph database includes one or more symbolic data stores and one or more key-value data stores. Each symbolic data store is configured to symbolically store sets of multiple hyper-graph nodes. Each key-value data store is configured to store attribute information for hyper-graph nodes and hyper-graph edges.

Claims

1. A graph database comprising:

at least one non-transitory computer-readable medium including;

one or more symbolic data stores configured to symbolically store sets of multiple hyper-graph nodes; and

one or more key-value data stores configured to store attribute information for hyper-graph nodes and hyper-graph edges.

2. The graph database according to claim 1, wherein each set has a unique identifier.

3. The graph database according to claim 2, wherein each node has a unique identifier.

4. The graph database according to claim 3, wherein each unique identifier comprises:

a global key which identifies a database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and

a local key which uniquely identifies the set or the node on the database server.

5. The graph database according to claim 1, wherein each set is stored as a persistent binary decision diagram (BDD).

6. The graph database according to claim 5, wherein each node is stored as a persistent BDD.

7. The graph database according to claim 6, wherein each BDD comprises a three element BDD (e3BDD), with at least one e3BDD including nodes having node types of:

a standard node;

a zero-suppressed reduction node; and

a one-suppressed reduction node.

8. A method of implementing a graph database comprising:

symbolically storing sets of multiple hyper-graph nodes in one or more symbolic data stores; and

storing attribute information for nodes and edges in one or more key-value data stores.

9. The method according to claim 8, further comprising assigning a unique identifier to each of the sets and the nodes.

10. The method according to claim 9, wherein each unique identifier comprises:

a global key which identifies a database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and

a local key which uniquely identifies the set or the node on the database server.

11. The method according to claim 8, wherein each set, each node, and each edge is stored as a persistent binary decision diagram (BDD).

12. The method according to claim 11, wherein each BDD comprises a three element BDD (e3BDD), with at least one e3BDD including nodes having node types of:

a standard node;

a zero-suppressed reduction node; and

a one-suppressed reduction node.

13. A non-transitory computer-readable medium storing a program that causes a processor to execute a method of implementing a graph database comprising:

symbolically storing sets of multiple hyper-graph nodes in one or more symbolic data stores; and

storing attribute information for nodes and edges in one or more key-value data stores.

14. The non-transitory computer-readable medium according to claim 13, wherein the program further causes the processor to assign a unique identifier to each of the sets and the nodes.

15. The non-transitory computer-readable medium according to claim 14, wherein each unique identifier comprises:

a global key which identifies a database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and

a local key which uniquely identifies the set or the node on the database server.

16. The non-transitory computer-readable medium according to claim 13, wherein each set, each node, and each edge is stored as a persistent binary decision diagram (BDD).

17. The non-transitory computer-readable medium according to claim 16, wherein each BDD comprises a three element BDD (e3BDD), with at least one e3BDD including nodes having node types of:

a standard node;

a zero-suppressed reduction node; and

a one-suppressed reduction node.

18. A non-transitory computer-readable medium storing a program that causes a processor to execute an implementation of a three element binary decision diagram (e3BDD) comprising:

a plurality of BDD nodes comprising three types of nodes, the three types of nodes comprising;

a standard node;

a zero-suppressed reduction node; and

a one-suppressed reduction node.

19. The non-transitory computer-readable medium according to claim 18, wherein each e3BDD comprises a persistent e3BDD.

20. The non-transitory computer-readable medium according to claim 19, wherein each e3BDD is configured to be employed in symbolically storing a set of multiple hyper-graph nodes.