Symbolic hyper-graph database

Patent metadata

Field	Value
Publication number	US-9507875-B2
Application number	US-201213370022-A
Country	US
Kind code	B2
Filing date	Feb 9, 2012
Priority date	Feb 9, 2012
Publication date	Nov 29, 2016
Grant date	Nov 29, 2016

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.

First claim

What is claimed is:

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;
one or more of the multiple hyper-graph nodes associated with a first unique identifier including one or more first global keys and a first local key, the one or more first global keys including a binary integer associated with a database server and the first local key uniquely identifying the one or more multiple hyper-graph nodes stored on the database server;
a second unique identifier including one or more second global keys and a second local key and identifying a set of multiple hyper-graph nodes representing a set operation of a union of hyper-graph nodes with comparable relationships based on having similar edges; and
one or more key-value data stores configured to store attribute information for hyper-graph nodes and hyper-graph edges, the attribute information including a first symbolic key and a first value, the first symbolic key identifying at least one of the one or more hyper-graph nodes symbolically stored by the one or more symbolic data stores, and the first value including an object key and data that is associated with the object key, the attribute information also including a second symbolic key and a second value associated with the set of multiple hyper-graph nodes representing the set operation;

wherein each set is stored as a three element binary decision diagram (e3BDD).

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:
the global key which identifies the database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and
the local key which uniquely identifies the set or the node on the database server.

5. The graph database of claim 1 , wherein the binary integer included in the one or more global keys is configured to be padded with one or more leading zeroes to accommodate expansion of the number of binary digits in the global key responsive to additional database servers being added.

6. The graph database of claim 1 , wherein at least one e3BDD includes nodes having node types of:
a standard node;
a zero-suppressed reduction node generated by zero-suppressed node elimination of a first original binary decision diagram (BDD); and
a one-suppressed reduction node generated by one-suppressed node elimination of a second original BDD.

7. A method of implementing a graph database comprising:
symbolically storing sets of multiple hyper-graph nodes in one or more symbolic data stores, one or more of the multiple hyper-graph nodes associated with a first unique identifier including one or more first global keys and a first local key, the one or more first global keys including, a binary integer associated with a database server and the first local key uniquely identifying the one or more multiple, hyper-graph nodes stored on the database server, at least one of the sets of multiple hyper-graph nodes representing a set operation of a union of hyper-graph nodes with comparable relationships based on having similar edges, each hyper-graph node in the at least one of the sets of multiple hyper-graph nodes also being stored with its own unique identifier;
associating a second unique identifier, including one or more second global keys and a second local key, with each of the one or more sets of multiple hypergraph nodes representing the set operation; and
storing attribute information for nodes and edges in one or more key-value data stores, including for the at least one of the sets of multiple hyper-graph nodes, the attribute information including a symbolic key and a value, the symbolic key identifying at least one of the multiple hyper-graph nodes symbolically stored by the one or more symbolic data stores, and data that is associated with the object key;
wherein each set, each node, and each edge is stored as a three element BDD (e3BDD).

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

9. The method according to claim 8 , wherein each unique identifier comprises:
the global key which identifies the database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and
the local key which uniquely identifies the set or the node on the database server.

10. The method of claim 7 , wherein at least one e3BDD includes nodes having node types of:
a standard node;
a zero-suppressed reduction node generated by zero-suppressed node elimination of a first original binary decision diagram (BDD); and
a one-suppressed reduction node generated by one-suppressed node elimination of a second original BDD.

11. 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, one or more of the multiple hyper-graph nodes associated with a first unique identifier including, one or more first global keys and a first local key, the one or more first global keys including a binary integer associated with a database server and the first local key uniquely identifying the one or more multiple hyper-graph nodes stored on the database server, at least one of the sets of multiple hyper-graph nodes representing a set operation of a union of hyper-graph nodes with comparable relationships based on having similar edges, each hyper-graph node in the at least one of the sets of multiple hyper-graph nodes also being, stored with its own unique identifier;
associating a second unique identifier, including one or more second global keys and a second local key, with each of the one or more sets of multiple hyper-graph nodes representing the set operation; and
storing attribute information for nodes and edges in one or more key-value data stores, including for the at least one of the sets of multiple hyper-graph nodes, the attribute information including a symbolic key and a value, the symbolic key identifying at least one of the multiple hyper-graph nodes symbolically stored by the one or more symbolic data stores, and data that is associated with the object key;
wherein each set, each node, and each edge is stored as a three element BDD (e3BDD).

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

13. The non-transitory computer-readable medium according to claim 12 , wherein each unique identifier comprises:
the global key which identifies the database server in a distributed group of interconnected database servers in which information regarding the set or the node is stored; and
the local key which uniquely identifies the set or the node on the database server.

14. The non-transitory computer-readable medium of claim 11 , wherein at least one e3BDD includes nodes having node types of:
a standard node;
a zero-suppressed reduction node generated by zero-suppressed node elimination of a first original binary decision diagram (BDD); and
a one-suppressed reduction node generated by one-suppressed node elimination of a second original BDD.

15. A system, comprising:

Assignees

• Reddy Subodh M
• Fujitsu Ltd

Inventors

• Reddy Subodh M

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9027

  Trees · CPC title

• G06F17/30961

  Physics · mapped topic

• G06F17/30958 Primary

  Physics · mapped topic