Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue

Abstract

The role of uncertainty in data management has become more prominent than ever before, especially because of the growing importance of machine learning-driven applications that produce large uncertain databases. A well-known approach to querying such databases is to blend rule-based reasoning with uncertainty. However, techniques proposed so far struggle with large databases. In this paper, we address this problem by presenting a new technique for probabilistic reasoning that exploits Trigger Graphs (TGs) -- a notion recently introduced for the non-probabilistic setting. The intuition is that TGs can effectively store a probabilistic model by avoiding an explicit materialization of the lineage and by grouping together similar derivations of the same fact. Firstly, we show how TGs can be adapted to support the possible world semantics. Then, we describe techniques for efficiently computing a probabilistic model, and formally establish the correctness of our approach. We also present an extensive empirical evaluation using a prototype called LTGs. Our comparison against other leading engines shows that LTGs is not only faster, even against approximate reasoning techniques, but can also reason over probabilistic databases that existing engines cannot scale to.

References in corpus (5)

• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
• On the Implementation of the Probabilistic Logic Programming Language ProbLog
• The Magic of Logical Inference in Probabilistic Programming
• Oblivious Bounds on the Probability of Boolean Functions