Reachability Queries and Graph Pattern Queries in Graph Databases

点击翻译按钮获取中文摘要

With the advent of web technology, numerous new applications have emerged, such as social networks, semantic web, and web mining, which need to work with graph-like data due to its expressive power to handle complex relationships among objects. In addition, many other research areas also need to model their data as graphs. Instances include computer vision, knowledge discovery, biological networks, graph mining, cheminformatics, electrical power grids, and network traffic, just to name a few. To query graph data, two kinds of queries are being widely used: - Reachability queries, asking whether there exists a path from one node to another. - Graph pattern queries, to find all subgraphs that are isomorphic to a pattern graph. The reachability query is deemed to be one of the most basic building blocks for many advanced graph operations while the subgraph isomorphism is to check structure identity. Two graphs G(V, E) and G'(V', E') are isomorphic if there exists a bijection f: V => V' such that edge (u, v) is in E if edge (f(u), f(v)) is in E'. It is an NP-complete problem. We have worked on the reachability queries for a long time, and developed an efficient algorithm for evaluating reachability queries in untyped graphs [5], with a better theoretic time complexity than any existing strategy. By an untyped graph, we mean that the edges are not labeled. Recently, we have designed another algorithm to compress transitive closures to support reachability checkings [7]. More importantly, the compression can be adjusted to different levels for different applications. Our research on the reachability for typed graphs is summarized in a new paper submitted to TKDE [9]. The goal of this project is to establish a prototype graph database system, for which we will develop efficient methods to store graphs and compressed transitive closures, as well as efficient strategies to evaluate reachability queries and graph pattern queries on both untyped and typed graphs.