Collaborative Research: PPoSS: A Full-stack Approach to Declarative Analytics at Scale

声明性编程语言允许用户定义问题的规则和目标，以及有效解决方案的结构，在其实现中自动执行计算机制。这种富有表现力的编程系统为非专家提供了一个机会，利用基于人工智能的编程，立即将他们的分析任务扩展到海量数据集。该项目的新颖性是一组技术，在整个计算堆栈中集成了新的优化，为声明性编程提供了数量级的可伸缩性增强。该项目的影响集中在允许非专业人员将复杂的演绎推理算法扩展到下一代基于云的集群和超级计算机。从语言学上讲，该项目的方法基于对Datalog的关键语义扩展，以支持结构化归纳数据的索引。虽然目前现有的Datalog引擎(例如Souffle)支持代数数据，但该项目的新方法也实现了所有此类ADT的索引，从而在代数数据查询的运行时实现了数量级的算法改进。在操作上，该项目推进了基于并行关系代数的最先进的实施策略，使现成的数据并行能够通过MPI快速扩展到多核集群和超级计算机。该项目寻求集成这些技术中的每一项来扩展关键应用-包括程序分析和安全审计--并通过项目对这些技术的独特综合来展示它们对大型数据集的应用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Declarative programming languages permit users to define a problem's rules and goals, and the structure of a valid solution, automating the mechanics of computation within their implementations. Such expressive programming systems provide an opportunity for non-experts to immediately scale their analytic tasks to massive datasets, leveraging AI-based programming. The project's novelties are a set of techniques, integrating novel optimizations across the full computation stack, that deliver orders-of-magnitude scalability enhancements to declarative programming. The project's impacts are centered on permitting non-specialists to scale sophisticated deductive inference algorithms to the next generation of cloud-based clusters and supercomputers.Linguistically, the project's approach is based on a key semantic extension to Datalog to support indexing for structured inductive data. While algebraic data is supported in currently existing Datalog engines (e.g., Souffle), the project’s novel approach also materializes indices for all such ADTs, enabling orders-of-magnitude algorithmic improvements in runtimes of queries over algebraic data. Operationally, the project advances state-of-the-art implementation strategies based on parallel relational algebra, which enables off-the-shelf data parallelism that rapidly scales to many-core clusters and supercomputers via MPI. The project seeks to integrate each of these technologies to scale key applications---including program analysis and security auditing---and demonstrate their application to large datasets enabled via the project’s unique synthesis of these technologies.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.