On the Evaluation of Reachability and Sub-pattern Recognition Queries in Very Large Graph Databases

随着Web技术的出现，出现了许多新的应用，如社交网络、语义Web和Web挖掘，这些应用都需要处理类似于图的数据，因为它具有处理对象之间复杂关系的表达能力。此外，许多其他研究领域需要将其数据建模为图形。这些技术包括传染病跟踪、计算机视觉、知识发现、生物网络、化学信息学、电网和网络流量，仅举几例。为了查询数据图，两种类型的查询被广泛使用：-可达性查询，询问是否存在从一个节点到另一个节点的路径。- 图模式查询，查找与模式图同构的所有子图。可达性查询被认为是许多高级图操作的最基本构建块之一。作为一个例子，考虑一个网络，它将位置或人表示为节点，将疾病传播（如COVID-19、SARS）表示为边。人们可能想知道某种疾病是否从一个城市或一个人传播给其他人。作为另一个例子，在生物网络中，节点是分子，或反应，或活细胞的物理相互作用，而边是它们之间的相互作用。我们可能想找到所有的基因，它们的表达直接或间接地受到某种分子的影响。另外，在图论中，子图同构（识别）是为了检验子结构的同一性。两个图G（V，E）和G ′（V ′，E ′）是同构的，如果存在从V到V ′的双射f，使得（u，v）在E中，如果（f（u），f（v））在E ′中.这是一个NP完全问题。出于这个原因，已经提出了图匹配的不同变体，这些变体可以在多项式时间内进行评估，但在实践中非常有用。例如，我们可以允许模式中的边匹配目标中的路径，或者将模式定义为约束，以找到所有满足约束的子图。此外，在一些新兴的应用中，如社交网络，图中的边通常是类型化的，表示各种关系，如婚姻，友谊，合作，建议，等等。这是另一个重要的区别于传统的图论，提出了新的挑战，寻求有效的算法来评估可达性查询和图模式查询。 我们已经在有类型图和无类型图的可达性查询和子图识别方面进行了很长时间的研究，并开发出了比现有策略具有更好的理论时间复杂度的高效算法。我们所有的研究成果都发表在一些期刊上，如ACM Transactions on Database Systems，IEEE Transactions on Knowledge and Data Engineering，Journal of Super Computing和Intl。数据工程会议。这个项目的目标是建立一个软件系统来评估可达性查询和图模式查询的无类型和类型的图与我们的算法正在使用。

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 need to model their data as graphs. Instances include trace of infectious diseases, computer vision, knowledge discovery, biological networks, cheminformatics, electrical power grids, and network traffic, just to name a few. To query data graphs, 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. As an example, consider a network that represents locations, or people as nodes and disease transmission, such as COVID-19, SARS as edges. One may want to know whether a certain disease is spread from a city or a person to the others. As another example, in biological networks, nodes are either molecules, or reactions, or physical interaction of living cells, and edges are interactions among them. We may want to find all genes whose expressions are directly or indirectly influenced by a certain molecule. In addition, in the graph theory, the subgraph isomorphism (recognition) is to check sub-structure identity. Two graphs G(V, E) and G'(V', E') are isomorphic if there exists a bijection f, from V to V', such that (u, v) is in E if (f(u), f(v)) is in E'. It is an NP-complete problem. For this reason, different variants of graph matchings have been suggested, which can be evaluated in polynomial time but quite useful in practice. For example, we can allow an edge in a pattern to match a path in a target, or define a pattern as a constraint to find all those subgraphs satisfying the constraint. Further, in some emerging applications, such as social networks, edges in a graph are typically typed, denoting various relationships such as marriage, friendship, co-work, advice, and so on. It is another important difference from the traditional graph theory, posing new challenges in seeking for efficient algorithms to evaluate reachability queries and graph pattern queries. We have worked on the reachability queries and sub-graph recognition on both typed and untyped graphs for a long time, and developed efficient algorithms with better theoretic time complexity than the existing strategies. All our research results have been published in some prestiges venues, such as ACM Transactions on Database Systems, IEEE Transactions on Knowledge and Data Engineering, Journal of Super Computing, and Intl. Conf. Data Enginerring. The goal of this project is to build a software system to evaluate reachability queries and graph pattern queries on both untyped and typed graphs with our algorithms being utilized.