III: Medium: Collaborative Research: Reasoning about Optimizers for Data-Intensive Systems

III：媒介：协作研究：数据密集型系统优化器的推理

• 批准号: 1955488
• 负责人: Alvin Cheung
• 金额: $ 50万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-09-01 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1955488&HistoricalAwards=false
• 关键词: III; Medium; Collaborative; Research; Reasoning

Today, we witness an explosion of new data-intensive systems, both for traditional data processing and for machine learning, and these systems critically require powerful optimizers for their declarative languages. Developing and verifying such optimizers is very difficult: in the past, they were developed only by a small number of commercial database vendors with dedicated teams, while most modern systems are developed by small teams without such expertise. To address this challenge, this project studies and implements automated methods for verifying query optimization rules in data-intensive systems.Specifically, this project will have four research focuses: (1) We will develop an axiomatic foundation based on algebraic identities in a semiring, implement it as a framework, and apply it to verify optimization rules in existing systems. (2) We will extend the framework to reason about languages that combine linear algebra with relational algebra, for example languages that manipulate vectors, matrices, and tensors, and extend the verifier to reason about tensor optimization rules. (3) We will conduct a theoretical study of the completeness and decidability of the semiring-based axiomatic system used for verifying optimization rules, and specialize this study for various query language fragments. (4) We will build a new cloud-based infrastructure for automated reasoning of declarative query languages, to enable researchers to easily develop executable semantics for different data-intensive systems, formal methods researchers to develop new techniques targeted for query language reasoning, and application developers to build new applications that make use of our infrastructure.All software artifacts developed in this project will be released to the public, with plans to incorporate their usage in both the undergraduate and graduate curricula. Any collected benchmarks from open source will be aggregated into a repository that is publicly accessible, with the goal to enable researchers and practitioners in the field to experiment and reproduce the results.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）我们将对用于验证优化规则的基于半程的公理系统的完整性和可决定性进行理论研究，并专门研究本研究的各种查询语言片段。 （4）我们将建立一个新的基于云的基础架构，用于自动询问的查询语言的自动推理，使研究人员能够轻松地为不同的数据密集型系统开发可执行的语义，正式的方法研究人员开发针对查询语言推理的新技术，并将应用程序释放到我们的Infrastrupture.Stoction.sprotight.shoptif的应用程序中。本科和研究生课程。从开源的任何收集的基准测试都将汇总到一个可公开访问的存储库中，目的是使该领域的研究人员和从业人员能够实验和重现结果。这项奖项反映了NSF的法定任务，并认为通过基金会的知识分子和更广泛的影响，可以通过评估来进行评估，以评估CRITERIA。

项目成果

Demonstration of Chestnut: An In-memory Data Layout Designer for Database Applications

栗子演示：数据库应用的内存数据布局设计器

• DOI: 10.1145/3318464.3384712
• 发表时间: 2020
• 期刊: ACM SIGMOD Conference
• 作者: Mingwei Samuel, Cong Yan

Towards Auto-Generated Data Systems

走向自动生成的数据系统

• DOI: 10.14778/3611540.3611635
• 发表时间: 2023
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Cheung, Alvin;Ahmad, Maaz Bin;Haynes, Brandon;Kittivorawong, Chanwut;Laddad, Shadaj;Liu, Xiaoxuan;Wang, Chenglong;Yan, Cong
• 通讯作者: Yan, Cong

Leveraging Application Data Constraints to Optimize Database-Backed Web Applications

利用应用程序数据约束来优化数据库支持的 Web 应用程序

• DOI: 10.14778/3583140.3583141
• 发表时间: 2023
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Liu, Xiaoxuan;Wang, Shuxian;Sun, Mengzhu;Pan, Sicheng;Li, Ge;Jha, Siddharth;Yan, Cong;Yang, Junwen;Lu, Shan;Cheung, Alvin
• 通讯作者: Cheung, Alvin