In the past few years, a multitude of different formalisms combining probabilistic reasoning with logics, databases, or logic programming has been developed. Prominent examples include PHA and ICL [@Poole:93; @Poole00], PRISM [@SatoKameya:01], SLPs [@Muggleton96], ProbView [@Lakshmanan], CLP($\cal BN$) [@Costa03:uai], CP-logic [@Vennekens], Trio [@Trio], probabilistic Datalog (pD) [@Fuhr00], and probabilistic databases [@DalviS04]. Although these logics have been traditionally studied in the knowledge representation and database communities, the focus is now often on a machine learning perspective, which imposes new requirements. First, these logics must be simple enough to be learnable and at the same time sufficiently expressive to support interesting probabilistic inferences. Second, because learning is computationally expensive and requires answering long sequences of possibly complex queries, inference in such logics must be fast, although inference in even the simplest probabilistic logics is computationally hard.

In this paper, we study these problems in the context of a simple probabilistic logic, ProbLog [@DeRaedt07], which has been used for learning in the context of large biological networks where edges are labeled with probabilities. Large and complex networks of biological concepts (genes, proteins, phenotypes, etc.) can be extracted from public databases, and probabilistic links between concepts can be obtained by various techniques [@Sevon06]. ProbLog 