Systems and methods for using graph data structures
AssigneeRoyal Bank of Canada
InventorJason Xiao Han CHEN
Life of this patent
Estimating the term…
Abstract
An approach and corresponding computer system adapted for combining relational and non-relational data storage and indexing techniques is proposed. The approach utilizes graph data structures that are specifically configured for supporting performance improvements in relational querying while maintaining the advantages from a non-relational database. The graph data structures can be used for graph traversals and graph operations, among others, which can improve an overall computational complexity level associated with various operations at the cost of storage.
Claims20
A computer implemented database system, the system comprising a computer processor configured to:
- store one or more data sets in a non-relational database, each of said data sets being stored as documents configured for indexing, said non-relational database using one or more storage primitives of a non-relational search library, said storage primitives including an identifying metadata field for each data object in said one or more data sets;
- prior to a start of a runtime duration, generate, by a graph pre-build engine, a graph index data structure representative of a mapping of key edges between different nodes of a graph, wherein each node represents a key field within an index, and wherein each edge comprises a description indicating how the one or more nodes are related;
- store the graph index data structure in the non-relational database;
- generate, by a graph data structure generator, a graph data structure based on said graph index data structure, wherein edges of said graph data structure are defined using said identifying metadata fields of each node;
- receive a relational query for said non-relational database;
- process, by a graph traversal engine, said relational query by traversing the identifying metadata fields of said nodes of said graph data structure using an identifier-based retrieval function and without using a search function;
- and
- return a result of said relational query.
A computer implemented method for improving performance of a database system, the method comprising:
- receiving one or more data sets for storage in a non-relational database, each of said data sets being stored as documents optimized for indexing, said non-relational database using one or more storage primitives of a non-relational search library, said storage primitives including an identifying metadata field for each data object in said one or more data sets;
- prior to a start of a run-time duration, generating, by a graph pre-build engine, a graph index data structure representative of a data mapping of key edges between different nodes of a graph, wherein each node represents a key field within an index, and wherein each edge comprises a description indicating how the one or more nodes are related;
- storing said graph index data structure in said non-relational database;
- generating, by a graph data structure generator, a graph data structure based on said graph index data structure, wherein edges of said graph data structure are defined using identifying metadata fields of each node;
- receiving a relational query for said non-relational database;
- processing, by a graph traversal engine, said relational query by traversing the identifying metadata fields of said nodes of said graph data structure using an identifier-based retrieval function and without using a search function;
- and
- returning a result of said relational query.
Dependencies are inferred from the claim text.