Directed Graph Representation and Traversal in Relational Databases

Abstract

Graph representation in computers has always been a hot topic due to the number of applications that directly benefit from graphs. Multiple methods have emerged in computer science to represent graphs in numerical/logical formats; most of these methods rely heavily on pointers. However, most current business applications also rely heavily on relational databases as a primary source of storing information. Moreover, most databases are relational by nature, and this does not provide the best-fit scenario to represent graphs. In this work, we present a solution to representing a graph in a relational database. Moreover, we will also provide a set of procedures to traverse this graph and determine the connection path between two given nodes. This work was implemented in an online social/travel website which can be found at http://www.tripbot.com [1].