Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs (Technical Report)

The significant interest in combining logic and probability for reasoning in uncertain, relational domains has led to a multitude of formalisms, inc luding the family of probabilistic logic programming (PLP) languages based on the dis tribution semantics [Sato, 1995] with languages and systems such as PRISM [Sato, 1995], ICL [Poole, 2008], ProbLog [De Raedt et al., 2007; Fierens et al., 2015] and PIT A [Riguzzi and Swift, 2011]. State-of-the-art inference for PLP uses a reduction to weig hted model counting (WMC) [Chavira and Darwiche, 2008], where the dependency structure of the logic program a nd the queries is first transformed into a propositional formula in a suitable form at that supports efficient WMC. While the details of this transformation differ across approaches, a key part of it is determining the relevant ground program with respect t o the queries of interest, i.e., all groundings of rules that contribute to some deriva tion of a query. This grounding step has received little attention, as its cost is domina ted by the cost of constructing the propositional formula in typical PLP benchmarks that op erate on biological, social or hyperlink networks, where formulas are complex. However, it has been observed 1 that the grounding step is the bottleneck that often makes it impossible to apply PLP inference in the context of ontology-based data access over probabilistic data (pOBDA) [Schoenfisch and Stuckenschmidt, 2017; van Bremen et al., 20 19], where determining the relevant grounding explores a large search space, but on ly small parts of this space contribute to the formulas.