III: Small: Native Compilation, Query Processing, and Indexing for In-memory Graph Relational Data Systems

跨越不同领域的各种应用都将图形作为一等公民，例如通信网络、道路网络、社交网络和生物网络。这些图的节点和边通常与描述符相关联，例如，标签和属性，或者更一般地，属性。这些应用中的许多都需要对图形数据进行高效和实时的处理。由于关系数据系统非常成熟且无处不在，因此扩展这些系统以支持图形数据是自然而然的选择。然而，在不同级别的关系模型和图形模型之间存在阻抗不匹配，这使得扩展关系系统以有效地支持图形数据非常具有挑战性。该项目将解决阻抗不匹配的问题，以及运行在支持图形的关系系统上的图形应用程序所面临的障碍，以便正常和高效地运行。更具体地说，该项目将解决以下研究挑战：(1)解决查询关系数据的声明性性质和查询图形数据的导航性质之间的不匹配的表达能力挑战；(2)支持大量图形和关系数据以及实时查询的可扩展性挑战；以及(3)解决回答图形和关系查询的复杂性以及图形应用程序的实时处理需求的性能挑战。解决这些挑战是本项目的重点。本项目解决如何通过解决上述挑战来克服关系模型和图形模型之间的阻抗失配。提出了在不影响图形查询性能的情况下，对关系系统中的大型图形数据库进行无缝本地处理的技术。要开发的技术包括：(1)图形查询编译技术：最先进的查询编译机制将被开发为图形和关系查询评估流水线的混合，以高效地执行包括图形和关系运算符的已编译的查询处理计划，(2)图形即索引：存储器中的图形索引技术，将促进使用图形拓扑来导航图形关系数据。图索引将有效地支持基于图节点和边的属性数据的子图选择，并对所选子图执行图操作。要开发的技术将支持动态图形，其中图形拓扑和图形属性都可以更新。引入的技术将允许更新，否则将使通常离线准备以加速图查询处理的图中间表示无效。(3)原生图+关系查询执行：引入图导航运算符，在原生模式下对图形数据进行操作，同时在查询求值管道内与关系代数运算符无缝集成。开发的查询处理技术将允许在同一查询评估流水线内的关系和图形数据上进行双向导航，以允许其他不可行的查询优化策略，并有效地评估查询评估流水线中的交错图和关系运算符，以及(4)用于查询优化目的的交错关系和图操作的成本计算。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A wide variety of applications spanning various domains have graphs as first-class citizens, e.g., communication networks, road networks, social networks, and biological networks. The nodes and edges of these graphs are often associated with descriptors, e.g., labels and properties, or more generally, attributes. Many of these applications need efficient and real-time processing of the graph data. Because relational data systems are very mature and ubiquitous, extending these systems to support graph data is a natural choice. However, there is an impedance mismatch between the relational model and the graph model at the various levels that makes extending relational systems to efficiently support graph data very challenging. This project will address this impedance mismatch and the hurdles that face graph applications that run over graph-enabled relational systems in order to function properly and efficiently. More specifically, this project will address the following research challenges: (1) The expressiveness challenge to address the mismatch between the declarative nature in querying relational data and the navigational nature in querying graph data, (2) the scalability challenge to support large amounts of graph and relational data and queries in real-time, and (3) the performance challenge to address the complexity in answering graph and relational queries and the real-time processing needs of graph applications. Addressing these challenges is the focus of this project.This project addresses how to overcome the impedance mismatch between the relational and graph models by addressing the above challenges. Techniques are proposed to seamlessly and natively process large graph databases inside relational systems without negatively affecting the graph query performance. The techniques to be developed include: (1) Graph query compilation techniques: State-of-art query compilation mechanisms will be developed to mixes of graph and relational query evaluation pipelines to efficiently execute compiled query processing plans that include both graph and relational operators, (2) Graph-as-an-index: In-memory graph indexing techniques that will facilitate the navigation of the graph relational data using the graph topology. The graph indexes will efficiently support sub-graph selection based on the attribute data of both the graph nodes and edges, and performing graph operations on the selected sub-graphs. The techniques to be developed will support dynamic graphs where both the graph topology as well as the graph attributes can be updated. The introduced techniques will tolerate updates that would otherwise invalidate graph intermediate representations that are typically prepared offline to speedup graph query processing. (3) Native graph+relational query execution: Introduce graph navigation operators that operate over graph data in native mode, yet seamlessly integrate with relational algebra operators inside query evaluation pipelines. The developed query processing techniques will permit bidirectional navigation over the relational and the graph data within the same query evaluation pipeline to permit further query optimization strategies that are infeasible otherwise, and to efficiently evaluate interleaved graph and relational operators in query evaluation pipelines, and (4) Costing of the interleaved relational and graph operations for query optimization purposes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.