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

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

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.