Back to results
US 9,870,393 B2Granted
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.
Claims19
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 adjacent 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;
- a query translator configured to:
- receive a graph query on the graph, the query including a traversal from a first node to a second node that is adjacent to the first node,
- convert the graph query into a structured query language (SQL) query over the first table and a second table, and
- retrieve the multi-valued property of the first node from the first table and obtain data of the second node from the second table with the SQL query;
- and
- the graph mapper further configured to:
- store, 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 adjacent node,
- transform the adjacency list to a temporary table;
- and
- use the temporary table to locate the corresponding record.
10 more elements
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 adjacent 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;
- receiving a graph query on the graph, the query including a traversal from a first node to a second node that is adjacent to the first node,
- converting the graph query into a structured query language (SQL) query over the first table and a second table;
- retrieving the multi-valued property of the first node from the first table and obtain data of the second node from the second table with the SQL 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 adjacent node;
- transforming the adjacency list to a temporary table;
- and
- using the temporary table to locate the corresponding record.
8 more elements
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;
- converting the graph query into a structured query language (SQL) query over the first table and a second table;
- 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 adjacent 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 the SQL 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 adjacent node;
- transforming the adjacency list to a temporary table;
- and
- using the temporary table to locate the corresponding record.
5 more elements
Dependencies are inferred from the claim text.