XPS: EXPL: FP: Symmetric Queries as a Building Block for Efficient Parallel Query Evaluation

XPS：EXPL：FP：对称查询作为高效并行查询评估的构建块

• 批准号: 1606557
• 负责人: Yuqing Wu
• 金额: $ 29.76万
• 依托单位: Pomona College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1606557&HistoricalAwards=false
• 关键词: XPS; EXPL; FP; Symmetric; Queries

Today's applications frequently feature massive and heterogeneous data and complicated computational requirements. There have been many efforts towards efficient parallel query processing and optimization. However, the full potential of parallelism has not been realized by existing techniques and frameworks in scaling to massive datasets, especially for applications that inherently demand recursive data accesses. The project offers a theoretical methodology for tackling the problem of parallel query evaluation on massive data. The PI conjectures that to maximize parallelizability of generic queries, e.g., queries that are used frequently in analytical and transactional applications, one needs to examine queries that are inherently parallelizable as the basic unit of study. She identifies symmetric queries as a set of queries that are potentially highly parallelizable and will use such queries as a stepping stone to study parallelizable query languages and leverage the findings to design techniques for efficient evaluation of generic queries. In particular, the project focuses on three separate, yet highly related tasks: (1) design and study a set of query languages whose queries are symmetric, investigate the properties of these languages, and propose and prove theoretical bounds on the computational complexity of the languages, in terms of scaling and data skew; (2) investigate and propose data structures and algorithms for efficiently evaluating queries of these languages in a parallel manner; and (3) propose strategies including query rewrite and optimization techniques for efficient evaluation of arbitrary queries, based on the new data structures and algorithms that result from (2).During the exploratory phase of this project, the PI is conducting research activities in key areas in all three aforementioned topics. These will build the theoretical foundation, form strong collaborations with experts in related areas, and lay the groundwork for an effort suitable for a full-size XPS project. The research result of this project will be beneficial to both the database and the parallel computing communities as a new way to approach the problem of integrating the techniques of each.The research methodology and algorithms developed is to be integrated into the undergraduate- and graduate-level database courses the PI teaches, as course materials and topics for course projects. Graduate students are supported by the project as research assistants. The PI works with various initiatives to recruit and encourage undergraduate students to participate in research activities.

当今的应用程序经常具有大量异构数据和复杂的计算需求。已经有许多努力朝着高效的并行查询处理和优化。然而，并行性的全部潜力还没有实现现有的技术和框架在扩展到大规模的数据集，特别是对于应用程序，本质上需要递归的数据访问。该项目为解决海量数据的并行查询评估问题提供了一种理论方法。PI表示，为了最大限度地提高通用查询的并行性，例如，对于在分析和事务应用程序中经常使用的查询，需要检查本质上可并行的查询作为研究的基本单元。她确定对称查询作为一组查询，是潜在的高度并行化，并将使用这种查询作为垫脚石研究并行查询语言和利用研究结果设计技术，有效地评估通用查询。具体而言，该项目侧重于三个独立但高度相关的任务：（1）设计和研究一组查询是对称的查询语言，研究这些语言的属性，并提出和证明语言计算复杂性的理论界限，在缩放和数据倾斜方面;（2）研究并提出数据结构和算法，以便以并行方式有效地评估这些语言的查询;以及（3）基于从（2）得到的新的数据结构和算法，提出包括查询重写和优化技术在内的策略，以有效地评估任意查询。在该项目的探索阶段，PI正在上述所有三个主题的关键领域开展研究活动。这些将建立理论基础，与相关领域的专家形成强有力的合作，并为适合全尺寸XPS项目的工作奠定基础。这个项目的研究结果将有利于数据库和并行计算社区作为一种新的方式来解决问题的技术集成each.的研究方法和算法开发的是整合到本科生和研究生水平的数据库课程PI教，课程材料和课程项目的主题。研究生作为研究助理得到该项目的支持。PI与各种倡议合作，招募和鼓励本科生参加研究活动。