that a randomly sampled subgraph contains the edge from *c* to *d*, or the path from *c* to *d* via *e* (or both of these).

![ Example of a probabilistic graph: edge labels indicate the probability that the edge is part of the graph.[]{data-label="fig:Ex"}](graph)

Formally, the *success probability* $P_s(q|T)$ of a query $q$ in a ProbLog program $T$ is the marginal of $P(L|T)$ with respect to $q$, i.e. $$P_s(q|T) = \sum\nolimits_{L\subseteq L_T}P(q|L)\cdot P(L|T)\;, \label{eq:p_suc}$$ where $P(q|L) = 1$ if there exists a $\theta$ such that $L\cup BK\models
q\theta$, and $P(q|L)=0$ otherwise. In other words, the success probability of query $q$ is the probability that the query $q$ is *provable* in a randomly sampled logic program.

In our example, $40$ of the $64$ possible subprograms allow one to prove *path$(c,d)$*, namely all those that contain at least the edge from *c* to *d* or both the edge from *c* to *e* and from *e* to *d*, so the success probability of that query is the sum of the probabilities of these programs: $P_s(path(c,d)|T)=P(\{ab,ac,bc,cd,ce,ed\}|T)+\ldots +P(\{cd\}|T)=0\ldotp94$, where $xy$ is used as a shortcut for *edge$(x,y)$* when listing elements of a subprogram. We will use this convention throughout the paper. Clearly, listing all subprograms 