Scalable Probabilistic Databases with Factor Graphs and MCMC

Michael L. Wick, Andrew McCallum, Gerome Miklau

Abstract

Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing modifications to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.

Introduction

Managing uncertain data is a classic challenge in computer science. Traditional Probabilistic Databases (PDBs) typically face a trade-off between accuracy and scalability. Systems that assume data independence are fast but fail to capture real-world dependencies, such as the contextual relationship between entities in a text document. Conversely, systems that utilize complex graphical models to capture these dependencies often find query evaluation to be #P-hard, making them computationally intractable for large datasets. Furthermore, most PDBs struggle with "closure"—the ability to perform standard relational algebra like Joins or Aggregations without breaking the underlying probabilistic model.

This paper introduces a scalable approach to PDBs that bridges this gap by combining the expressive power of Factor Graphs with the efficiency of Markov chain Monte Carlo (MCMC) sampling. By decoupling the database representation from the probabilistic model, the system can evaluate complex queries over millions of uncertain records with high fidelity.

System Architecture and Methodology

The proposed architecture is decoupled into two primary components: a standard relational database and an external factor graph. The database stores a single "possible world" (a specific configuration of data), while the factor graph defines the probability distribution over all possible worlds using "factors" to score compatibility between data values.

Figure 1: Overview of the decoupled architecture showing the database, templated factor graphs, and unrolled graphs for NER and Entity Resolution tasks.

To explore the space of possible worlds, the system employs MCMC sampling (specifically Metropolis-Hastings). Instead of calculating exact probabilities, the system "walks" through different versions of the database by proposing small, local changes—such as updating a named entity label. These changes are accepted or rejected based on the factor graph’s score. This approach allows the system to be query-agnostic; because it samples standard database states, it can handle counts, averages, and complex joins natively without requiring specialized probabilistic SQL operators.

The "Secret Sauce": Materialized View Maintenance

The core technical innovation lies in how queries are handled during the sampling process. Running a full query on every MCMC sample is prohibitively expensive. However, because each MCMC step only modifies a few tuples, the authors leverage materialized view maintenance. Instead of re-computing a query $Q$ from scratch for a new world $w'$, the system computes only the change ($\Delta$) relative to the previous world $w$. This "delta-query" approach transforms linear-time queries into near constant-time updates, enabling massive scalability.

Experimental Evaluation

The system was evaluated on a large-scale Information Extraction (IE) task involving Named Entity Recognition (NER) and Entity Resolution. The researchers used the NYT Corpus, consisting of 10 million tokens from 1,788 New York Times articles. The model employed was a skip-chain Conditional Random Field (CRF), a complex graphical model where identical strings across a document are linked, creating a non-tree-structured graph where exact inference is impossible.

Key Results

The empirical results demonstrate a dramatic improvement in performance. On the 10-million-tuple dataset, a naive sampling approach that re-runs queries was projected to take 227 hours. In contrast, the view-maintenance approach completed the same task in under 2.5 hours.

Figure 4: Comparison of execution time between materialized sampling and naive sampling as the number of tuples increases.

As shown in the performance analysis, the time required for an MCMC step remains relatively constant regardless of the total database size, provided the proposal distribution only modifies a constant number of variables. Additionally, the system provides an "any-time" solution, allowing users to trade off between latency and result fidelity. Parallelization further enhances performance; running multiple MCMC chains in parallel improves the "mixing" of the chains, leading to higher accuracy in less time than a single chain could achieve.

Conclusion and Future Work

By integrating MCMC sampling with materialized view maintenance, this work provides a viable path for scaling probabilistic databases to real-world, large-scale applications. The system successfully recovers marginal probabilities for complex aggregate queries that were previously considered impossible to calculate exactly in such large, loopy models.

Future research directions include the automatic optimization of "jump functions" (proposal distributions) to more effectively explore the space of possible worlds based on specific queries. Additionally, addressing the latency between in-memory MCMC operations and disk-based query execution remains a key systems challenge for further refining the performance of probabilistic database engines.

Summary updated

Abstract

Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing {\em modifications} to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.
BibTeX
@article{wick2010scalable,
  author = {Michael L. Wick and Andrew McCallum and Gerome Miklau},
  title = {{Scalable Probabilistic Databases with Factor Graphs and MCMC}},
  journal = {PVLDB2010},
  year = {2010},
  url = {https://openreview.net/forum?id=slUsxSzV40},
}

Loading related content...

Figure