Reachability Queries and Graph Pattern Queries in Graph Databases

随着网络技术的出现，出现了许多新的应用，例如社交网络， 语义Web和Web挖掘，由于其处理对象之间复杂关系的表达能力，需要使用类似图形的数据。此外，许多其他研究领域也需要将其数据建模为图形。这些技术包括计算机视觉、知识发现、生物网络、图形挖掘、化学信息学、电网和网络流量，仅举几例。 为了查询图形数据，两种查询被广泛使用： - 可达性查询，询问是否存在从一个节点到另一个节点的路径。 - 图模式查询，查找与模式图同构的所有子图。 可达性查询被认为是许多高级图的最基本的构建块之一 操作，而子图同构是检查结构同一性。两个图G（V，E）和G '（V'，E '）是同构的，如果存在一个双射f：V => V'使得边（u，v）在E中，如果边（f（u），f（v））在E '中.这是一个NP完全问题。 我们已经在可达性查询上工作了很长时间，并开发了一个有效的算法， 评估无类型图中的可达性查询[5]，具有比任何现有策略更好的理论时间复杂度。所谓无类型图，我们的意思是边没有被标记。最近，我们设计了另一种算法来压缩传递闭包以支持可达性检查[7]。更重要的是，压缩可以针对不同的应用调整到不同的级别。我们对类型图的可达性的研究在提交给TKDE的一篇新论文中进行了总结[9]。 本项目的目标是建立一个原型图数据库系统，我们将开发有效的方法来存储图和压缩传递闭包，以及有效的策略来评估可达性查询和图模式查询的无类型图和有类型图。

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.