  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.
