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

跨越各种领域的各种各样的应用程序都将图作为一等公民，例如，通信网络、道路网络、社交网络和生物网络。这些图的节点和边通常与描述符相关联，例如，标签和属性，或者更一般地，属性。这些应用程序中的许多需要高效和实时的图形数据处理。由于关系数据系统非常成熟且无处不在，因此扩展这些系统以支持图数据是一个自然的选择。然而，关系模型和图模型之间在各个级别上存在阻抗失配，这使得扩展关系系统以有效地支持图数据非常具有挑战性。该项目将解决这种阻抗不匹配以及在支持图形的关系系统上运行的图形应用程序所面临的障碍，以便正确、高效地运行。更具体地说，该项目将解决以下研究挑战：（1）解决查询关系数据中的声明性质与查询图数据中的导航性质之间的不匹配的表达性挑战，（2）实时支持大量图和关系数据以及查询的可伸缩性挑战，以及（3）解决回答图和关系查询的复杂性以及图应用的实时处理需求的性能挑战。解决这些挑战是本项目的重点。本项目通过解决上述挑战来解决关系模型和图模型之间的阻抗不匹配。提出了在关系系统中无缝地和原生地处理大型图数据库而不会对图查询性能产生负面影响的技术。要开发的技术包括：（1）图形查询编译技术：将开发最先进的查询编译机制，以混合图形和关系查询评估管道，以有效地执行包括图形和关系运算符的编译查询处理计划，（2）Graph-as-an-index：内存中的图索引技术，将有助于使用图拓扑导航图关系数据。图索引将有效地支持基于图节点和边两者的属性数据的子图选择，以及对所选择的子图执行图操作。待开发的技术将支持动态图形，其中图形拓扑以及图形属性都可以更新。所引入的技术将容忍更新，否则会使通常离线准备的图中间表示无效，以加速图查询处理。(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.