Anytime Approximation in Probabilistic Databases via Scaled DissociationsFloris GeertsSpeeding up probabilistic inference remains a key challenge in probabilistic databases (PDBs) and the related area of statistical relational learning (SRL). Since computing probabilities for query answers is #P-hard, even for fairly simple conjunctive queries, both the PDB and SRL communities have proposed a number of approximation techniques over the years. The two prevalent techniques are either (i) MCMC-style sampling or (ii) branch-and-bound (B&B) algorithms that iteratively improve model-based bounds using a combination of variable substitution and elimination. In this talk, I present a new anytime B&B approximation scheme that encompasses all prior model-based approximation schemes proposed in the PDB and SRL literature. The approach relies on the idea of “scaled dissociations” which can improve both the upper and lower bounds of existing model-based algorithms. Here, in each iteration, a gradient-descent based optimization method finds the best scaled dissociation bounds after which Shannon expansion is performed. When applied to the well-studied problem of evaluating self-join-free conjunctive queries over tuple-independent PDBs, a consistent reduction in approximation error is experimentally observed. This is joint work with Wolfgang Gatterbauer, Peter Ivanov, Martin Theobald and Maarten Van den Heuvel and will be presented at the SIGMOD 2019 Conference.