2, we present several algorithms for exact and approximate inference in Section 3. Section 4 then discusses how these algorithms are implemented in YAP-Prolog, and Section 5 reports on experiments that validate the approach. Finally, Section 6 concludes and touches upon related work.

ProbLog {#sec:problog}
=======

A ProbLog program consists of a set of labeled facts $p_i::c_i$ together with a set of definite clauses. Each ground instance (that is, each instance not containing variables) of such a fact $c_i$ is true with probability $p_i$, that is, these facts correspond to random variables. We assume that these variables are mutually independent.[^1] The definite clauses allow one to add arbitrary *background knowledge* (BK).

Figure \[fig:Ex\] shows a small probabilistic graph that we shall use as running example in the text. It can be encoded in ProbLog as follows: $$\begin{array}{lllll}
0\ldotp8 :: \mathtt{edge(a,c)\ldotp} & ~~~~ &  0\ldotp7 :: \mathtt{edge(a,b)\ldotp} & ~~~~ &  0\ldotp8 :: \mathtt{edge(c,e)\ldotp} \\
0\ldotp6 :: \mathtt{edge(b,c)\ldotp} & ~~~~ &  0\ldotp9 :: \mathtt{edge(c,d)\ldotp} & ~~~~  &  0\ldotp5 :: \mathtt{edge(e,d)\ldotp} 
\end{array}$$ Such a probabilistic graph can be used to sample subgraphs by tossing a coin for each edge. Given a ProbLog program $T=\{p_1::c_1,\cdots,p_n::c_n\} \cup BK$ and a finite set of possible substitutions 