also used in the context of biological networks (not represented as Prolog programs) by [@Sevon06]. The use of a Monte Carlo method for probabilistic logic programs was suggested already by [@Dantsin], although he neither provides details nor reports on an implementation. Our approach differs from the MCMC method for Stochastic Logic Programs (SLPs) introduced by [@Cussens00] in that we do not use a Markov chain, but restart from scratch for each sample. Furthermore, SLPs are different in that they directly define a distribution over all proofs of a query. Investigating similar probabilistic backtracking approaches for ProbLog is a promising future research direction.

Implementation {#sec:implementation}
==============

This section discusses the main building blocks used to implement ProbLog on top of the YAP-Prolog system. An overview is shown in Figure \[fig:problog\_imp\], with a typical ProbLog program, including ProbLog facts and background knowledge (BK), at the top.

![ProbLog Implementation: A ProbLog program (top) requires the ProbLog library which in turn relies on functionality from the tries and array libraries. ProbLog queries (bottom-left) are sent to the YAP engine, and may require calling the BDD library CUDD via SimpleCUDD.[]{data-label="fig:problog_imp"}](implementation "fig:")\[fig:problog\]

The implementation requires ProbLog programs to use the `problog` module. Each program consists of 