*c* to *e* and from *e* to *d* (with probability $0\ldotp8\cdot 0\ldotp5=0\ldotp4$). Thus, $P_x(path(c,d)|T)=0\ldotp9$.

The ProbLog semantics is essentially a distribution semantics [@Sato:95]. Sato has rigorously shown that this class of programs defines a joint probability distribution over the set of possible least Herbrand models of the program (allowing functors), that is, of the background knowledge $BK$ together with a subprogram $L \subseteq L_T$; for further details we refer to [@Sato:95]. The distribution semantics has been used widely in the literature, though often under other names or in a more restricted setting; see e.g. [@Dantsin; @Poole:93; @Fuhr00; @Poole00; @DalviS04].

Inference in ProbLog {#sec:inference}
====================

This section discusses algorithms for computing exactly or approximately the success and explanation probabilities of ProbLog queries. It additionally contributes a new algorithm for Monte Carlo approximation of success probabilities.

Exact Inference {#sec:exact}
---------------

Calculating the *success probability* of a query using Equation (\[eq:p\_suc\]) directly is infeasible for all but the tiniest programs, as the number of subprograms to be checked is exponential in the number of probabilistic facts. However, as we have seen in our example in Section \[sec:problog\], we can describe all subprograms allowing for a specific proof by means of the facts that 