Weighted model counting admits an FPRAS on DNF structures. We study weighted model integration, which is a generalization of weighted model counting, and pose the following question: Does weighted model integration on DNF structures admit an FPRAS? Building on classical results, we show that this problem can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each of which can be a weak (i.e., approximate), or a strong (i.e., exact) oracle, and in all cases, comes along with accuracy guarantees. We experimentally verify our approach, and show that our algorithm scales to large problem instances, which are currently out of reach for existing, general-purpose weighted model integration solvers.

Propositional model counting (MC), or #SAT, is the task of counting the number of satisfying assignments for a given propositional formula [14]. Weighted model counting (WMC), or weighted #SAT, additionally incorporates a weight function over the set of all possible assignments. Offering an elegant formalism for encoding various probabilistic inference problems, WMC is a unifying approach for probabilistic inference. In particular, probabilistic graphical models [20], probabilistic planning [10], probabilistic logic programming [25], probabilistic databases [30] and probabilistic ontologies [2] can greatly benefit from advances in WMC. Two important special cases of WMC are weighted #CNF and weighted #DNF, where the former requires the input formula to be in CNF, and the latter to be in DNF. Both of these problems have a wide variety of applications. Inference in probabilistic graphical models typically reduces to solving weighted #CNF instances, while query evaluation in probabilistic databases reduces to solving weighted #DNF instances. The major bottleneck in WMC is its inherent computational complexity.

Probabilistic databases (PDBs) are usually incomplete, e.g., containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend OpenPDBs by Datalog+/- ontologies, under which both upper and lower probabilities of queries become even more informative, enabling us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NP^PP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints.