is essentially an extension of Prolog where a program defines a distribution over all its possible non-probabilistic subprograms. Facts are labeled with probabilities and treated as mutually independent random variables indicating whether or not the corresponding fact belongs to a randomly sampled program. The success probability of a query is defined as the probability that it succeeds in such a random subprogram. The semantics of ProbLog is not new: it is an instance of the distribution semantics [@Sato:95]. This is a well-known semantics for probabilistic logics that has been (re)defined multiple times in the literature, often in a more limited database setting; cf. [@Dantsin; @Poole:93; @Fuhr00; @Poole00; @DalviS04]. Sato has, however, shown that the semantics is also well-defined in the case of a countably infinite set of random variables and formalized it in his well-known distribution semantics [@Sato:95]. However, even though relying on the same semantics, in order to allow efficient inference, systems such as PRISM [@SatoKameya:01] and PHA [@Poole:93] additionally require all proofs of a query to be mutually exclusive. Thus, they cannot easily represent the type of network analysis tasks that motivated ProbLog. ICL [@Poole00] extends PHA to the case where proofs need not be mutually exclusive. In 