Graph processing in database
AssigneeMicrosoft Technology Licensing, LLC
InventorLiang Chen
Life of this patent
Estimating the term…
Abstract
The subject matter described herein relates to database middleware for enabling graph processing. A middleware between the graph data and underlying relational or SQL database is proposed. The local properties and topology information of nodes in the graph can be stored in a single node table in the database, thereby eliminating the need for a physical junction table. The middleware may efficiently translate graph queries into SQL queries over related tables. In some examples, the middleware may optimize the translated queries using the topology knowledge which is oblivious to the database query engine.
Claims20
A computer-implemented system comprising:
- a graph mapper configured to store data representing a graph into a first table in a relational database, each node in the graph having a single-valued property and a multi-valued property, the multi-valued property being a non-local property and containing a reference to at least one other node, the mapper configured to store each node in a corresponding record in the first table by:
- storing the single-valued property in a single-valued field, and
- storing the multi-valued property in a multi-valued field;
- and
- a query translator configured to:
- receive a graph query on the graph, the query retrieves an adjacency list for a first node, and
- convert the graph query into a relational database query over the first table and a second table using the adjacency list, the relational database query retrieving the multi-valued property of the first node from the first table and obtaining data of the other node from the second table.
A computer-implemented method comprising:
- receiving a request to store data representing a graph including a plurality of nodes, at least one of the nodes having a single-valued property and a multi-valued property, the multi-valued property being a non-local property and including a reference to at least one other node;
- storing the data in a table in a relational database, each of records in the table corresponding to one of the nodes, the storing comprising storing the at least one of the nodes in the corresponding record by:
- storing the single-valued property in a single-valued field, and
- storing the multi-valued property in a multi-valued field;
- and
- using an adjacency list to convert a graph query on the graph to a relational database query over a first table and a second table, the relational database query retrieving the multi-valued property of the first node from the first table and obtaining data of the other node from the second table.
A computer-implemented method comprising:
- receiving a graph query on data representing a graph including a plurality of nodes, the graph query involving a traversal from a source node to a sink node that is adjacent to the source node;
- retrieving, from a source table in a relational database, a record corresponding to the source node, the record containing a multi-valued field that stores a multi-valued non-local property of the source node, the multi-valued non-local property including a reference to at least one other node of the source node;
- obtaining, based on the multi-valued non-local property of the source node, data of the sink node from a sink table with a relational database query that is converted from the graph query;
- storing, for each node in the graph, an adjacency list in the multi-valued field, the adjacency list containing the reference to the at least one other node;
- transforming the adjacency list to a temporary table;
- and
- using the temporary table to locate the corresponding record.
Dependencies are inferred from the claim text.