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.