Reachability Queries and Graph Pattern Queries in Graph Databases

图数据库中的可达性查询和图模式查询

• 批准号: 239074-2012
• 负责人: Chen, Yangjun
• 金额: $ 1.02万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570564
• 关键词: Reachability; Queries; Graph; Pattern; 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.

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