is infeasible in practice; an alternative approach will be discussed in Section \[sec:exact\].

A ProbLog program also defines the probability of a *specific* proof $E$, also called *explanation*, of some query $q$, which is again a marginal of $P(L|T)$. Here, an *explanation* is a minimal subset of the probabilistic facts that together with the background knowledge entails $q\theta$ for some substitution $\theta$. Thus, the probability of such an explanation $E$ is that of sampling a logic program $L\cup E$ that contains at least all the probabilistic facts in $E$, that is, the marginal with respect to these facts: $$P(E|T)  =   \sum\nolimits_{ L\subseteq (L_T\backslash E)} P(L\cup E |T) = \prod\nolimits_{c_i \in E}p_i\label{eq:deriv_px}$$ The *explanation probability* $P_x(q|T)$ is then defined as the probability of the most likely explanation or proof of the query $q$ $$P_x(q|T)  =  \max\nolimits_{E\in E(q)}P(E|T)
=   \max\nolimits_{E\in E(q)} \prod_{c_i \in E}p_i,\label{eq:p_exp}$$ where $E(q)$ is the set of all explanations for query $q$, i.e., all minimal sets $E\subseteq L_T$ of probabilistic facts such that $E \cup BK \models q$ [@Kimmig07].

In our example, the set of all explanations for *path$(c,d)$* contains the edge from *c* to *d* (with probability 0.9) as well as the path consisting of the edges from 