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

III：小：内存图关系数据系统的本机编译、查询处理和索引

基本信息

批准号：
1910216
负责人：
Walid Aref
金额：
$ 49.95万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910216&HistoricalAwards=false
关键词：
III Small Native Compilation Query

项目摘要

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.

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

项目成果

期刊论文数量（25）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

STULL: Unbiased Online Sampling for Visual Exploration of Large Spatiotemporal Data

STULL：用于大型时空数据可视化探索的无偏在线采样

DOI：
10.1109/vast50239.2020.00012
发表时间：
2020-10
期刊：
2020 IEEE Conference on Visual Analytics Science and Technology (VAST
影响因子：
0
作者：
Wang, Guizhen;Guo, Jingjing;Tang, Mingjie;Queiroz Neto, Jose Florencio;Yau, Calvin;Daghistani, Anas;Karimzadeh, Morteza;Aref, Walid G.;Ebert, David S.
通讯作者：
Ebert, David S.

Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems

提示：分布式微批量流处理系统的动态数据分区

DOI：
10.1145/3318464.3389713
发表时间：
2020-05
期刊：
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
影响因子：
0
作者：
Abdelhamid, Ahmed S.;Mahmood, Ahmed R.;Daghistani, Anas;Aref, Walid G.
通讯作者：
Aref, Walid G.

An Investigation of Grid-enabled Tree Indexes for Spatial Query Processing

用于空间查询处理的支持网格的树索引的研究