Query the model: precomputations for efficient inference with Bayesian Networks

Probabilistic models learned from a database can be used for the purposes of approximate query processing and predictive querying, two tasks that must be performed at interactive speeds in many real-life settings. In this paper, we propose a novel approach towards speeding up query evaluation over a probabilistic model by materializing a set of probabilistic quantities involved in query evaluation. Specifically, we consider a scenario where a Bayesian network is built over a relational database to represent the joint distribution of data attributes, and we address the problem of choosing a set of intermediate relational tables to materialize so as to maximize the expected efficiency gain in query-response time over a given workload of queries. We provide an optimal polynomial-time algorithm for the problem we consider and further discuss other alternative methods. We validate our technique using Bayesian networks learned from benchmark data. Our experimental results confirm that a small set of materialized factors with modest memory space requirements can lead to significant improvements in the running time of queries, reaching up to an average gain of 70% over a uniform workload of queries.