Optimizations Of Graph Queries In Relational Databases

Graph structure has powerful ability. It is well used in our real life to model different objects and the relations between them. It is becoming ubiquitous in many fields of computer science. Traditional relational databases use tables to describe and store data and do well in processing tabular data. However, there are some diffculties in processing graph data in relational databases. In this paper, we make a comprehensive analysis on the features of relational databases and graph data, and present a novel solution to support effcient operations in relational databases.First we introduce GraphView, a middleware that based relational database system. It supports a complete set of interfaces that can be called by users to define their own graph data. GraphView will import these data into the database and it is fully transparent to users. GraphView adopts a special NodeTable to present the nodes in graphs,and all edges are converted into binary strings and stored in the same NodeTable. We make a detailed discussion on this structure and the implementation mechanisms behind it, and we also analyze its performance advantage in cache locality.Then we extend the standard SQL language to support more ?exible graph queries.We add a new MATCH clause in SQL to model graph patterns. We introduce the grammar of this extended query language and make use of it on some examples. This language will be translated by GraphView and executed in relational databases. We will discuss the optimizations in translating and design a cost model to evaluate different translation plans. And we will present a heuristic translate algorithm that can find out an approximately optimal solution in a very short time.We use GraphView to solve some classic graph applications, and make a discussion on the optimization algorithms in processing graphs. We will describe how to implement these optimization mechanisms in GraphView.At last, we conduct a comprehensive experimental evaluation on GraphView and the algorithms based on it. We compare it with standard SQL databases and graph databases. The experimental results show that our solution is much more effcient in processing graph queries.