  Probabilistic inference over large data sets is a challenging data management
problem since exact inference is generally #P-hard and is most often solved
approximately with sampling-based methods today. This paper proposes an
alternative approach for approximate evaluation of conjunctive queries with
standard relational databases: In our approach, every query is evaluated
entirely in the database engine by evaluating a fixed number of query plans,
each providing an upper bound on the true probability, then taking their
minimum. We provide an algorithm that takes into account important schema
information to enumerate only the minimal necessary plans among all possible
plans. Importantly, this algorithm is a strict generalization of all known
PTIME self-join-free conjunctive queries: A query is in PTIME if and only if
our algorithm returns one single plan. Furthermore, our approach is a
generalization of a family of efficient ranking methods from graphs to
hypergraphs. We also adapt three relational query optimization techniques to
evaluate all necessary plans very fast. We give a detailed experimental
evaluation of our approach and, in the process, provide a new way of thinking
about the value of probabilistic methods over non-probabilistic methods for
ranking query answers. We also note that the techniques developed in this paper
apply immediately to lifted inference from statistical relational models since
lifted inference corresponds to PTIME plans in probabilistic databases.
