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项目的努力奠定基础。该项目的研究结果将对数据库和平行计算社区都有益，这是解决每个每个技术的问题的新方法。开发的研究方法和算法将集成到本科和研究生级别的数据库课程中，PI是PI的课程材料和课程项目的主题。该项目作为研究助理的支持。 PI与各种举措合作，招募并鼓励本科生参加研究活动。