Incremental Inference for Probabilistic Datalog

Abstract

Abstract Several extensions of Datalog perform probabilistic inference by allowing users to annotate input facts and rules with probabilities. While extremely useful in many domains (e.g., quantitative program analysis), existing systems typically do not support incremental inference , meaning that even small changes trigger costly recomputation from scratch. This paper presents (Stands for Probabilistic INcremental Querying), the first incremental solving framework for probabilistic Datalog. Given a previously solved program and a set of changes, updates query probabilities by reusing the old derivation graphs and compiled decision diagrams. The key idea is to translate structural changes into parametric updates whenever sound to avoid redundant recomputation. Our framework combines an incremental derivation graph construction algorithm with an adaptive BDD construction technique that safely reuses existing BDDs via weight calibration whenever possible. Experimentally, achieves an average speedup of $$17\times $$ 17 × over recomputation from scratch on a representative set of program analysis benchmarks.