DNF formula grows with the number of proofs, its evaluation can become quite expensive, and ultimately infeasible. For instance, when searching for paths in graphs or networks, even in small networks with a few dozen edges there are easily $O(10^6)$ possible paths between two nodes. ProbLog therefore includes several approximation methods.

### Bounded Approximation

The first approximation algorithm, a slight variant of the one proposed in [@DeRaedt07], uses DNF formulae to obtain both an upper and a lower bound on the probability of a query. It is closely related to work by [@Poole93:jrnl] in the context of PHA, but adapted towards ProbLog. The method relies on two observations.

First, we remark that the DNF formula describing sets of proofs is *monotone*, meaning that adding more proofs will never decrease the probability of the formula being true. Thus, formulae describing subsets of the full set of proofs of a query will always give a lower bound on the query’s success probability. In our example, the lower bound obtained from the shorter proof would be $P(cd|T) = 0\ldotp9$, while that from the longer one would be $P(ce\wedge ed|T) = 0\ldotp4$.

Our second observation is that the probability of a proof $b_1 \wedge 