Given a first-order sentence ? and domain size n, how can one sample model of on the {1, . , n} efficiently as n scales? We consider two variants this problem: uniform sampling regime, in which goal is to uniformly at random, symmetric weighted models are according number groundings each predicate appearing them. Solutions problem have applications scalable generation combinatorial structures, well several statistical-relational such Markov logic networks probabilistic programs. In paper, we...

We consider the problem of weighted first-order model counting (WFOMC): given a sentence ϕ and domain size n ∈ ℕ, determine sum models over {1, ..., n}. Past work has shown that any using at most two logical variables admits an algorithm for WFOMC runs in time polynomial (Van den Broeck 2011; Van Broeck, Meert, Darwiche 2014). In this paper, we extend result to two-variable with addition tree axiom, stating some distinguished binary relation forms graph-theoretic sense.

We study ontology-mediated querying over probabilistic data for the case when ontology is formulated in EL(hdr), an expressive member of EL family description logics. leverage techniques that have been developed (i) classical and (ii) logic programming provide implementation based on our findings. include both theoretical considerations experimental evaluation approach.

Abstract We present onto2problog , a tool that supports ontology-mediated querying of probabilistic data via logic programming engines. Our conjunctive queries on under ontologies encoded in the description $$\mathcal{ELH}^{dr}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow><mml:mi>ELH</mml:mi></mml:mrow><mml:mrow><mml:mi>dr</mml:mi></mml:mrow></mml:msup></mml:math> thus capturing large part OWL 2 EL profile.

We study the symmetric weighted first-order model counting task and present ApproxWFOMC, a novel anytime method for efficiently bounding count of sentence given an unweighted oracle. The algorithm has applications to inference in variety probabilistic representations, such as Markov logic networks programs. Crucially many applications, no assumptions are made on form input sentence. Instead, makes use symmetry inherent problem by imposing cardinality constraints number possible true...

Given a propositional formula ψ, the model counting problem, also referred to as #SAT, seeks compute number of satisfying assignments (or models) ψ. Modern search-based algorithms are built on conflict-driven clause learning, combined with caching certain subformulas (called components) encountered during search process. Despite significant progress in these over years, state-of-the-art counters often struggle handle large but structured instances that typically arise combinatorial settings....

We consider the problem of computing probability a query over tuple-independent probabilistic database, known as theprobabilistic evaluation (PQE) problem. The is well-known to be #¶-hard in data complexity for conjunctive queries general, well several subclasses queries. Existing approximation approaches dealing with hard have centred on lineage which can intractable all but smallest due exponential dependence size length. In this paper, we take first step towards bridging gap, by showing...

We study the problem of constructing relational marginal polytope (RMP) a given set first-order formulas. Past work has shown that RMP construction can be reduced to weighted model counting (WFOMC). However, existing reductions in literature are intractable practice, since they typically require an infeasibly large number calls WFOMC oracle. In this paper, we propose algorithm construct RMPs using fewer oracle calls. As application, also show how apply new improve approximation scheme for...

Query evaluation over probabilistic databases is notoriously intractable -- not only in combined complexity, but often data complexity as well. This motivates the study of approximation algorithms, and particularly FPRASes, with runtime polynomial both query instance size. In this paper, we focus on tuple-independent binary signatures, i.e., graphs, when can devise FPRASes for evaluation. We settle problem a variety classes, by proving approximability results (conditional) inapproximability...

We study the symmetric weighted first-order model counting task and present ApproxWFOMC, a novel anytime method for efficiently bounding count in presence of an unweighted oracle. The algorithm has applications to inference variety probabilistic representations, such as Markov logic networks programs. Crucially many applications, we make no assumptions on form input sentence. Instead, our makes use symmetry inherent problem by imposing cardinality constraints number possible true groundings...