Graph processing in database

Patent metadata

Field	Value
Publication number	US-2016179883-A1
Application number	US-201514611967-A
Country	US
Kind code	A1
Filing date	Feb 2, 2015
Priority date	Dec 19, 2014
Publication date	Jun 23, 2016
Grant date	—

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.

First claim

I/we claim:

1 . 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; and
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, and
convert the graph query into a structured query language (SQL) query over the first table and a second table, the SQL query retrieving the multi-valued property of the first node from the first table and obtaining data of the second node from the second table.

2 . The system of claim 1 , wherein the query translator is configured to generate the SQL query that invokes a predefined function on the multi-valued property of the first node to create a temporary junction table, the junction table associating the first node and the at least one adjacent node.

3 . The system of claim 2 , wherein the query translator is configured to generate the SQL query that includes a join between the temporary junction table and the second table.

4 . The system of claim 1 , wherein the graph query includes a pattern to be matched in the graph, and wherein the query translator is configured to:
obtain a plurality of candidate schemes for decomposition of the pattern, each of the candidate schemes resulting in a plurality of sub-patterns; determine cost for each of the candidate schemes, the cost including sub-pattern cost associated with the individual sub-patterns resulted from the candidate scheme and connection cost associated with a connection of the sub-patterns; and decompose the pattern according to one of the candidate schemes with the minimized cost.

5 . The system of claim 1 , wherein the multi-valued property includes an adjacency list that contains the reference to the at least one adjacent node.

6 . The system of claim 5 , wherein the adjacency list is a first adjacency list and the multi-valued field is a first multi-valued field, wherein each node in the graph further has a second adjacency list of a different type from the first adjacency list, and wherein the graph mapper is further configured to:
store, for each node in the graph, the second adjacency list in a second multi-valued field in the corresponding record, the second multi-valued field being separate from the first multi-valued field.

7 . 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; and 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.

8 . The method of claim 7 , further comprising:
receiving a user input indicating that the multi-valued property is a non-local property; generating, based on the user input, an annotation for the multi-valued field, the annotation indicating that the multi-valued field is used to store the multi-valued property.

9 . The method of claim 8 , wherein the annotation further indicates a sink table that stores the at least one adjacent node.

10 . The method of claim 7 , wherein the multi-valued property includes a plurality of atomic values, and wherein storing the multi-valued property comprises:
generating a representation of the plurality of atomic values with a data type that is supported by the relational database; and storing the generated representation in the multi-valued field.

11 . The method of claim 7 , wherein the multi-valued property is a first multi-valued property and the multi-valued field is a first multi-valued field, wherein the at least one of the nodes further has a second multi-valued property of a different type from the first multi-valued property, and wherein storing the data further comprises:
storing the second multi-valued property in a second multi-valued field in the corresponding record, the second multi-valued field being separate from the first multi-valued field.

12 . The method of claim 11 , further comprising:
generating a view for the graph, the view including a union multi-valued field containing the first and second multi-valued properties.

13 . 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 adjacent node of the source node; and obtaining, based on the multi-valued non-local property of the source node, data of the sink node from a sink table.

14 . The method of claim 13 , wherein obtaining the data of the sink node comprises:
creating a junction table that associates the source node and the reference to the at least one adjacent node; and obtaining the data of the sink node with a join between the junction table and the sink table.

15 . The method of claim 14 , wherein creating the junction table comprises:
recognizing, from an annotation for the multi-valued field, that the multi-valued field is used to store the multi-valued non-local property; and creating the junction table by invoking a predefined function on the multi-valued non-local property of the source node.

16 . The method of claim 14 , further comprising:
responsive to the graph query being received, translating the graph query into a table query over the source table and the sink table for the retrieving and the obtaining.

17 . The method of claim 13 , wherein the graph query includes a pattern to be matched in the graph, the method further comprising:
obtaining a plurality of candidate schemes for decomposition of the pattern, each of the candidate schemes resulting in a plurality of sub-patterns of the pattern; determining cost for each of the candidate schemes, the cost including sub-pattern cost associated with the individual sub-patterns resulted from the candidate scheme and connection cost associated with a connection of the sub-patterns; selecting one of the candidate schemes with the cost below a predefined threshold; and decomposing the pattern according to the selected candidate scheme.

18 . The method of claim 17 , wherein determining the cost comprises:
determining the sub-pattern cost associated with a sub-pattern by calculating a cardinality of the sub-pattern in the graph.

19 . The method of claim 17 , wherein obtaining the plurality of candidate schemes comprises:
obtaining at least o

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Chen Liang

Classifications

• G06F17/30466

  Physics · mapped topic

• G06F17/30469

  Physics · mapped topic

• G06F17/30498

  Physics · mapped topic

• G06F17/30439 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic