Reachability Query Based On The Interval Labeling Index And Its Application On Outsourced Database

Graph is an important part of data structure. In graph model, nodes represent entities in real life, while edges represent the relations between entities. Many practical problems can be represented by graphs such as biological, web and social network. With the development of the Internet, to efficiently analyze and query graph has been a hot topic in recent years.Since many practical problems can be modeled by graphs. Reachability queries on directed graphs have attracted much attention recently. For reachability query, interval labeling index has been studied extensively recently. However, all of the existing techniques have high update cost.In this thesis, we propose dynamic algorithms to process updating efficiently. Our algorithms adopt the idea of “gap” and can process different kinds of updating. We adopt the binary indexed tree to optimize the result of reachability query. Our experiments show that our method can effectively process the updates on graphs.For some companies, the cost of processing data is so large that outsourcing the database is a reasonable choice. In recent years, graph data query authentication of outsourcing becomes a hot research topic. However, as a basic query, there has been no published authentication mechanism on reachability query.Based on the reachability query algorithms, we design a reasonable authentication index data structure and a reasonable mechanism to authenticate reachability query in outsourced database. We adopt the idea of MB-tree to reduce the verification object size. Our index data structure can be used exactly in outsourced database. We evaluate the mechanism, and the result shows that the cost of our mechanism is rather small and can be used when the query is frequent.