Approximate confidence computation in probabilistic databases

TLDR

The paper presents a deterministic approximation algorithm with error guarantees for computing probabilities of propositional formulas over discrete random variables, and tunes it to capture all known tractable conjunctive queries without self‑joins on tuple‑independent probabilistic databases, achieving polynomial‑time exact computation in that case. The algorithm incrementally compiles formulas into decision diagrams using Shannon expansion, independence partitioning, and product factorization, computing lower and upper probability bounds at each step, and is implemented as an extension of the SPROUT query engine to approximate confidence values for positive relational algebra queries on general probabilistic databases. An extensive experimental effort shows that it consistently outperforms state‑of‑the‑art approximation techniques by several orders of magnitude.

Abstract

This paper introduces a deterministic approximation algorithm with error guarantees for computing the probability of propositional formulas over discrete random variables. The algorithm is based on an incremental compilation of formulas into decision diagrams using three types of decompositions: Shannon expansion, independence partitioning, and product factorization. With each decomposition step, lower and upper bounds on the probability of the partially compiled formula can be quickly computed and checked against the allowed error. This algorithm can be effectively used to compute approximate confidence values of answer tuples to positive relational algebra queries on general probabilistic databases (c-tables with discrete probability distributions). We further tune our algorithm so as to capture all known tractable conjunctive queries without self-joins on tuple-independent probabilistic databases: In this case, the algorithm requires time polynomial in the input size even for exact computation. We implemented the algorithm as an extension of the SPROUT query engine. An extensive experimental effort shows that it consistently outperforms state-of-art approximation techniques by several orders of magnitude.