Combining merkle trees in graph databases

Patent metadata

Field	Value
Publication number	US-10242065-B1
Application number	US-201615197863-A
Country	US
Kind code	B1
Filing date	Jun 30, 2016
Priority date	Jun 30, 2016
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

Combining a Merkle tree with a graph database by defining a Merkle tree with each node having a hashed value of the metadata for the node and any children of that node, associating non-hashed data with the hashed data for each node, wherein the non-hashed data has an up-pointer from a child node to any of its immediate parent node, and defining bi-directional edges between the nodes of the Merkle tree having a graph database structure to create a reference for the up-pointers associated with each Merkle tree node. The bi-directional edges with up-pointers along with the Merkle tree hash scheme allows efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing the database, and further allows efficient path definitions by allowing database processes to walk up edges.

First claim

The invention claimed is:

1. A computer implemented method of implementing a Merkle tree having bi-directional edges to process data in a database, the method comprising:
defining, by a hardware processor executing a database management process, a Merkle tree with each node having a hashed value of the metadata for the node and that of any children of that node;
associating non-hashed data with the hashed data for each node, wherein the non-hashed data comprises an initial up-pointer from a child node to any of its immediate parent node;
defining, by the processor, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;
combining the Merkle tree and graph database to define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, and wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and
storing the Merkle tree in a memory coupled to the processor.

2. The method of claim 1 wherein the non-hashed data is associated with the hashed data by encoding the initial up-pointer according to a defined scheme and concatenating the non-hashed data with the hashed data.

3. The method of claim 1 wherein the non-hashed data is associated with the hashed data by encoding the initial up-pointer according to a defined scheme and defining a separate data structure for the non-hashed data, and associating it with a corresponding Merkle tree node through an index or pointer.

4. The method of claim 1 further comprising assigning a weighted value to each up-pointer to represent a bias associated with a corresponding node.

5. The method of claim 1 wherein the database represents a deduplicated storage catalog maintained in a large-scale data storage network executing a backup process from one or more data sources to a plurality of storage devices.

6. The method of claim 5 wherein network devices and resources are stored as corresponding data elements in a storage catalog processed by the database management process associated with a backup management server, and wherein functions using the Merkle tree for the data elements include deduplication, path traversal, and garbage collection processes.

7. A method of implementing a graph database having hash-encoded nodes to process data in a database, comprising:
defining, by a hardware processor executing a database management process, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;
labeling each node with the hashed value of the node and any children to integrate a Merkle tree structure into the graph database;
labeling each node with initial up-pointers to the node's parent node; wherein the integrated Merkle tree and graph database define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and
storing the Merkle tree in a memory coupled to the processor.

8. The method of claim 7 , wherein database records are stored in the nodes of the graph database, and the bi-directional edges comprise typed, directed arcs.

9. The method of claim 8 wherein each node and edge is assigned named attributes that are encoded to include the initial up-pointers as non-hashed data and the hashed value of the node in the Merkle tree format.

10. The method of claim 7 further comprising assigning a weighted value to each up-pointer to represent a bias associated with a corresponding node.

11. The method of claim 7 wherein the database represents a deduplicated storage catalog maintained in a large-scale data storage network executing a backup process from one or more data sources to a plurality of storage devices.

12. The method of claim 11 wherein network devices and resources are stored as corresponding data elements in a storage catalog processed by the database management process associated with a backup management server, and wherein functions using the Merkle tree for the data elements include deduplication, path traversal, and garbage collection processes.

13. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to execute a method of implementing a Merkle tree in a graph database to process data in a database, comprising:
defining, by a hardware processor executing a database management process, a Merkle tree with each node having a hashed value of the metadata for the node and that of any children of that node;
associating non-hashed data with the hashed data for each node, wherein the non-hashed data comprises an initial up-pointer from a child node to any of its immediate parent node;
defining, by the processor, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;
combining the Merkle tree and graph database to define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and
storing the Merkle tree in a memory coupled to the processor.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Starling Jennifer
• Brenner Adam
• Norton Jeffrey
• Auchmoody Scott
• Malamut Mark D

Classifications

• G06F17/30958

  Physics · mapped topic

• G06F17/30528 Primary

  Physics · mapped topic

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• G06F17/30327

  Physics · mapped topic

• H04L9/50 Primary

  using hash chains, e.g. blockchains or hash trees · CPC title