一句话：提出 Praline，扩展 Datalog 以在输入事实相关时进行精确概率推断，并用 δ-exact 算法高效求出紧的概率界。
概率逻辑编程（如 ProbLog）将逻辑推理与概率推断结合以计算输出关系的概率，但已有工作未考虑输入事实之间可能存在的统计相关性。本文提出 Praline，一种面向（部分已知）输入相关性的 Datalog 扩展，用于精确概率推断。作者将推断任务形式化为约束优化问题，其解可给出输出事实可靠且精确的概率界；然而该优化问题复杂度高，单独使用往往难以扩展到大规模程序。为此，论文提出更高效的 δ-exact 推断算法，结合约束求解、静态分析和迭代精化。在包括侧信道分析在内的真实基准上的实证评估表明，该方法不仅能有效扩展，还能给出紧的概率界。
Probabilistic extensions of logic programming languages, such as ProbLog, integrate logical reasoning with probabilistic inference to evaluate probabilities of output relations; however, prior work does not account for potential statistical correlations among input facts. This paper introduces Praline, a new extension to Datalog designed for precise probabilistic inference in the presence of (partially known) input correlations. We formulate the inference task as a constrained optimization problem, where the solution yields sound and precise probability bounds for output facts. However, due to the complexity of the resulting optimization problem, this approach alone often does not scale to large programs. To address scalability, we propose a more efficient 𝛿-exact inference algorithm that leverages constraint solving, static analysis, and iterative refinement. Our empirical evaluation on challenging real-world benchmarks, including side-channel analysis, demonstrates that our method not only scales effectively but also delivers tight probability bounds.
@article{paperbot3007,
title = {Probabilistic Inference for Datalog with Correlated Inputs},
author = {Jingbo Wang and Shashin Halalingaiah and Weiyi Chen and Chao Wang and Işıl Dillig},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA2},
year = {2025},
doi = {10.1145/3763058}
}