Translating queries into graph queries using primitives

Patent metadata

Field	Value
Publication number	US-9672247-B2
Application number	US-201615046209-A
Country	US
Kind code	B2
Filing date	Feb 17, 2016
Priority date	Sep 18, 2015
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

In order to facilitate the requesting of desired information from a graph database that stores a graph, a system may translate an initial query into a query that can be executed against the graph database. In particular, using primitives, the system may translate a query associated with a type of database (such as a relational database) into the query. The graph may include nodes, edges between the nodes, and predicates to represent and store data with index-free adjacency. Moreover, the primitives may include: a rule based on edges in the graph that expresses a relational schema in the type of database, and information associated with a compound key that specifies a relationship between nodes, edges and predicates in the graph corresponding to a table in the type of database. Then, the system may execute the query against the graph database, and may receive a result that includes a subset of the graph.

First claim

What is claimed is:

1. A computer-system-implemented method for translating a first query into an edge query, the method comprising:
receiving the first query, at a computer, wherein the first query is associated with a first type of database;
translating the first query, at the computer using primitives, into the edge query, wherein:
the edge query is associated with a graph database storing a graph; and
the graph comprises nodes, edges between the nodes, and predicates to represent data with index-free adjacency;

executing the edge query against the graph database, wherein the edge query identifies an edge associated with a predicate that specifies one or more of the nodes of the graph; and
receiving a result in response to the edge query.

2. The method of claim 1 , wherein the first type of database has a different data model than the graph database.

3. The method of claim 1 , wherein the first type of database includes one of: a relational database, and a hierarchical database.

4. The method of claim 1 , wherein the result includes a subset of the graph.

5. The method of claim 1 , wherein the primitives include:
a rule based on edges in the graph that expresses a relational schema in the first type of database; and
information associated with a compound key that specifies a relationship between the nodes, the edges and the predicates of the graph corresponding to a table in the first type of database.

6. The method of claim 1 , wherein the first query is compatible with a Structured Query Language.

7. The method of claim 1 , wherein the edge query is compatible with datalog.

8. The method of claim 1 , wherein the edge query is compatible with a query language that is declarative so that it expresses computational logic without expressing an associated control flow and is complete so that an arbitrary computation is represented by the query language.

9. The method of claim 1 , wherein the method further comprises:
defining a compound relationship in the graph using the primitives; and
generating a compound key to identify the compound relationship.

10. The method of claim 1 , further comprising:
verifying the subset of the graph to confirm that the edge query was performed correctly.

11. An apparatus, comprising:
one or more processors;
memory; and
a program module, wherein the program module is stored in the memory and, during operation of the apparatus, is executed by the one or more processors to translate a first query into an edge query, the program module including:
instructions for receiving the first query, wherein the first query is associated with a first type of database;
instructions for translating the first query into the edge query, wherein:
the edge query is associated with a graph database storing a graph; and
the graph comprises nodes, edges between the nodes, and predicates to represent data with index-free adjacency;

instructions for executing the edge query against the graph database, wherein the edge query identifies an edge associated with a predicate that specifies one or more of the nodes of the graph; and
instructions for receiving a result in response to the edge query.

12. The apparatus of claim 11 , wherein the first type of database has a different data model than the graph database.

13. The apparatus of claim 11 , wherein the first type of database includes one of: a relational database, and a hierarchical database.

14. The apparatus of claim 11 , wherein the result includes a subset of the graph.

15. The apparatus of claim 11 , wherein the primitives include:
a rule based on edges in the graph that expresses a relational schema in the first type of database; and
information associated with a compound key that specifies a relationship between the nodes, the edges and the predicates of the graph corresponding to a table in the first type of database.

16. The apparatus of claim 11 , wherein the program module further includes instructions for:
defining a compound relationship in the graph using the primitives; and
generating a compound key to identify the compound relationship.

17. The apparatus of claim 11 , wherein:
the program module further includes instructions for verifying the subset of the graph to confirm that the edge query was performed correctly; and
verifying the subset of the graph comprises comparing the subset of the graph with a predefined subset of the graph.

18. A system, comprising:
a processing module comprising a non-transitory computer readable medium storing instructions that, when executed, cause the system to:
receive a first query associated with a first type of database;
translate the first query, using primitives, into an edge query associated with a graph database storing a graph, wherein the graph comprises nodes, edges between the nodes, and predicates to represent data with index-free adjacency;
execute the edge query against the graph database, wherein the edge query identifies an edge associated with a predicate that specifies one or more of the nodes of the graph; and
receive a result in response to the edge query.

19. The system of claim 18 , wherein the instructions further cause the system to:
define a compound relationship in the graph using the primitives; and
generate a compound key to identify the compound relationship.

20. The system of claim 18 , wherein:
the result includes a subset of the graph;
the instructions further cause the system to verify the subset of the graph to confirm that the edge query was performed correctly; and
verifying the subset of the graph comprises comparing the subset of the graph with a predefined subset of the graph.

Assignees

• Linkedin Corp

Inventors

• Shankar Srinath
• Liu Huaxin
• Stephenson Robert W
• Meyer Scott M

Classifications

• G06F16/2452 Primary

  Query translation · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/24575

  using context · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/282

  Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes · CPC title