标题： FlowLog：通过增量性实现的高效可扩展Datalog 显示英文标题

标题： FlowLog: Efficient and Extensible Datalog via Incrementality

摘要： 基于Datalog的语言正在程序分析和图处理等领域重新获得流行，作为一种强大的抽象来表达递归计算。 然而，现有系统常常在效率和可扩展性之间面临权衡。 像Souffle这样的引擎通过领域特定设计实现了高效率，但缺乏通用灵活性。 而像RecStep这样的系统则通过在传统数据库上分层Datalog来提供模块化，但在集成Datalog特定优化方面存在困难。 本文通过介绍FlowLog来弥合这一差距，这是一个新的Datalog引擎，它为每个规则使用显式的关系IR，以清晰地将递归控制（例如半朴素执行）与每个规则的逻辑计划分开。 这种界限使我们能够在逻辑层保留细粒度的、Datalog感知的优化，同时在执行时复用现成的数据库原语。 在逻辑层面（即IR），我们应用了经过验证的SQL优化，如逻辑融合和子计划重用。 为了应对递归工作负载的高波动性，我们采用了一种以稳健性优先的方法，将结构优化器（避免最坏情况连接）与横向信息传递（早期过滤）相结合。 构建在Differential Dataflow之上——一个用于流数据分析的成熟框架——FlowLog支持批处理和增量Datalog，并添加了称为布尔（或代数）特化的新型递归感知优化。 我们的评估显示，FlowLog在广泛的递归工作负载中优于最先进的Datalog引擎和现代数据库，在保持简单和可扩展架构的同时实现了卓越的可扩展性。 显示英文摘要

摘要： Datalog-based languages are regaining popularity as a powerful abstraction for expressing recursive computations in domains such as program analysis and graph processing. However, existing systems often face a trade-off between efficiency and extensibility. Engines like Souffle achieve high efficiency through domain-specific designs, but lack general-purpose flexibility. Others, like RecStep, offer modularity by layering Datalog on traditional databases, but struggle to integrate Datalog-specific optimizations. This paper bridges this gap by presenting FlowLog, a new Datalog engine that uses an explicit relational IR per-rule to cleanly separate recursive control (e.g., semi-naive execution) from each rule's logical plan. This boundary lets us retain fine-grained, Datalog-aware optimizations at the logical layer, but also reuse off-the-shelf database primitives at execution. At the logical level (i.e. IR), we apply proven SQL optimizations, such as logic fusion and subplan reuse. To address high volatility in recursive workloads, we adopt a robustness-first approach that pairs a structural optimizer (avoiding worst-case joins) with sideways information passing (early filtering). Built atop Differential Dataflow--a mature framework for streaming analytics--FlowLog supports both batch and incremental Datalog and adds novel recursion-aware optimizations called Boolean (or algebraic) specialization. Our evaluation shows that FlowLog outperforms state-of-the-art Datalog engines and modern databases across a broad range of recursive workloads, achieving superior scalability while preserving a simple and extensible architecture.