GRAPHITE: An Extensible Graph Traversal Framework for Relational\n Database Management Systems

Graph traversals are a basic but fundamental ingredient for a variety of\ngraph algorithms and graph-oriented queries. To achieve the best possible query\nperformance, they need to be implemented at the core of a database management\nsystem that aims at storing, manipulating, and querying graph data.\nIncreasingly, modern business applications demand native graph query and\nprocessing capabilities for enterprise-critical operations on data stored in\nrelational database management systems. In this paper we propose an extensible\ngraph traversal framework (GRAPHITE) as a central graph processing component on\na common storage engine inside a relational database management system.\n We study the influence of the graph topology on the execution time of graph\ntraversals and derive two traversal algorithm implementations specialized for\ndifferent graph topologies and traversal queries. We conduct extensive\nexperiments on GRAPHITE for a large variety of real-world graph data sets and\ninput configurations. Our experiments show that the proposed traversal\nalgorithms differ by up to two orders of magnitude for different input\nconfigurations and therefore demonstrate the need for a versatile framework to\nefficiently process graph traversals on a wide range of different graph\ntopologies and types of queries. Finally, we highlight that the query\nperformance of our traversal implementations is competitive with those of two\nnative graph database management systems.\n