$\{\theta_{j1}, \ldots \theta_{ji_j}\}$ for each probabilistic fact $p_j::c_j$, let $L_T$ denote the maximal set of *logical* facts that can be added to $BK$, that is, $L_T=\{c_1\theta_{11}, \ldots , c_1\theta_{1i_1}, \cdots, c_n\theta_{n1}, \ldots , c_n\theta_{ni_n}\}$. As the random variables corresponding to facts in $L_T$ are mutually independent, the ProbLog program defines a probability distribution over ground logic programs $L \subseteq L_T$: $$P(L|T)=\prod\nolimits_{c_i\theta_j\in L}p_i\prod\nolimits_{c_i\theta_j\in L_T\backslash L}(1-p_i)\ldotp$$ Since the background knowledge $BK$ is fixed and there is a one-to-one mapping between ground definite clause programs and Herbrand interpretations, a ProbLog program thus also defines a distribution over its Herbrand interpretations. Sato has shown how this semantics can be generalized to the countably infinite case; we refer to [@Sato:95] for details. For ease of readability, in the remainder of this paper we will restrict ourselves to the finite case and assume all probabilistic facts in a ProbLog program to be ground. We extend our example with the following background knowledge: $$\begin{array}{lll}
\mathtt{path(X,Y)} &  \mathtt{:-} &  \mathtt{edge(X,Y)\ldotp} \\
\mathtt{path(X,Y)} &  \mathtt{:-} &  \mathtt{edge(X,Z), path(Z,Y)\ldotp} 
\end{array}$$ We can then ask for the probability that there exists a path between two nodes, say *c* and *d*, in our probabilistic graph, that is, we query for the probability 