Storing graph data in a relational database

• US 10,387,497 B2
• Filed: 06/18/2015
• Issued: 08/20/2019
• Est. Priority Date: 05/21/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fokoue-Nkoutche, Achille B., Hu, Gang, Kementsietsidis, Anastasios, Srinivas, Kavitha, Sun, Wen B., Xie, Guo Tong
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Caiado, Antonio J
• Application Number:
  US14/742,735
• Publication Number:
  US 20160342709A1
• Time in Patent Office: 1,524 Days
• Field of Search: 707760, 707647, 707 1434, 715738, 386285, 386278, 386280, 706 50, 382103, 382165, 382217, 382284
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Embodiments include methods, systems and computer program products for storing graph data for a directed graph in a relational database. Aspects include creating a plurality of relational tables for the graph data, using a processor on a computer, the plurality of relational tables including adjacency tables and attribute tables. Each row of the attribute tables is dedicated to a subject of the graph data in the dataset and stores a JavaScript Object Notation (JSON) object corresponding to the subject. Each row of the adjacency tables includes a hashtable containing properties and values of the subject for that row.

Claims

1. A method of storing graph data for a directed graph in a relational database, the method comprising:

creating a plurality of relational tables for the graph data, wherein the graph data comprises a plurality of vertexes and a plurality of edges, using a processor on a computer, the plurality of relational tables including adjacency tables and attribute tables wherein;

each row of the attribute tables is dedicated to a subject of the graph data in the dataset and stores a JavaScript Object Notation (JSON) object corresponding to the subject; and

each row of the adjacency tables comprises a hashtable comprising properties and values of the subject for that row, wherein the hashtable further comprises an index value corresponding to a value shared by a plurality of edges originating from at least one vertex in the plurality of vertexes, wherein the index value further corresponds to a secondary adjacency table comprising edge data for edges originating from the at least one vertex in the plurality of vertexes;

wherein the adjacency tables include;

an incoming adjacency table, wherein each row of the incoming adjacency table is dedicated to one of the plurality of vertexes of the graph data and stores data regarding edges that terminate at that vertex; and

an outgoing adjacency table, wherein each row of the outgoing adjacency table is dedicated to one of the plurality of the vertexes of the graph data and stores data regarding edges that originate at that vertex;

receiving a query for traversing the graph data stored in the relational database;

parsing the query into a set of ordered operations;

translating each of the set of ordered operations into a fragment using a template selected based on an operation type, wherein the template comprises at least one of a common table expression fragment and a stored procedure;

assembling the fragments into a single query; and

transmitting the single query to the relational database for processing.

2. The method of claim 1, wherein the attribute table includes a vertex attribute table, wherein each row of the vertex attribute table is dedicated to one of a plurality of vertexes of the graph data and stores a JavaScript Object Notation (JSON) object corresponding to that vertex.

3. The method of claim 1, wherein the attribute table includes an edge attribute table, wherein each row of the edge attribute table is dedicated to one of the plurality of edges of the directed graph and stores a JavaScript Object Notation (JSON) object corresponding to that edge.