Compiling Probabilistic Inference into Relational Queries

24 concepts16 papers1 proposal

The fields of statistical machine learning and relational databases have traditionally developed in isolation. Machine learning relies on continuous optimization, graphical models, and probabilistic inference to handle uncertainty. Databases rely on discrete relational algebra, structured query language (SQL), and deterministic logic to manage massive datasets.

As data volumes grow, traditional probabilistic inference engines struggle to scale because they process data in flat files or custom in-memory structures. The core insight of a long-running research direction is that we do not need to build bespoke, scalable inference engines from scratch. Instead, we can exploit a deep mathematical isomorphism: the foundational operations of probabilistic inference map directly onto the core primitives of relational algebra.

By compiling probabilistic reasoning into relational queries, we can offload the heavy lifting of statistical inference to mature, highly optimized Relational Database Management Systems (RDBMS).

The Isomorphism Between Probabilities and Relations

To understand why this integration works, consider the two fundamental operations in probabilistic graphical models: combining factors (multiplying potentials) and marginalization (summing out variables).

In a relational database, these operations have exact structural equivalents:

  1. Factor Multiplication maps to a Relational Join: Computing a joint probability distribution $P(A, B) = P(A) \times P(B|A)$ requires matching rows where the attribute $A$ aligns. In an RDBMS, this is a standard inner join accompanied by a multiplication of the probability columns.
  2. Marginalization maps to an Aggregate Query: Summing out a variable to find a marginal probability, such as $P(A) = \sum_B P(A, B)$, requires grouping the data by $A$ and summing the probabilities. In SQL, this is a GROUP BY clause combined with a SUM aggregation.

As S. K. Michael Wong et al. demonstrated, probabilistic queries can be systematically translated into standard SQL by introducing specialized relational operators, such as "product joins" and "generalized joins," to simulate potential multiplication within a relational framework. This mapping allows practitioners to automatically inherit decades of database research in indexing, caching, and query optimization.

Probabilistic Domain                 Relational Database Domain
┌──────────────────────────┐         ┌──────────────────────────┐
│   Factor Multiplication  │ ──────> │      Relational Join     │
└──────────────────────────┘         └──────────────────────────┘
┌──────────────────────────┐         ┌──────────────────────────┐
│      Marginalization     │ ──────> │   SQL Aggregate (SUM)    │
└──────────────────────────┘         └──────────────────────────┘

This structural equivalence is not merely a conceptual convenience; it is a formal mathematical relationship. Christopher Jermaine and Christopher M. Jermaine highlighted that lifted inference in graphical models is mathematically equivalent to SQL aggregate query evaluation. Recognizing this equivalence allows database query optimizers to treat complex statistical reasoning as a native query evaluation problem, a paradigm formalized by Raghu Ramakrishnan through the introduction of Marginal Probability Factor (MPF) queries.

First-Order Query Rewriting and Ontological Lifting

When dealing with large-scale knowledge bases, uncertainty often coexists with complex logical rules or ontologies (such as Datalog or OWL profiles). Evaluating queries under these constraints typically requires reasoning over an astronomical number of "possible worlds."

To keep this tractable, researchers use a technique called first-order query rewriting. Instead of materializing all possible probabilistic outcomes, the system expands the user's query using the logical rules of the ontology before looking at the data. The expanded query is then compiled into standard first-order logic (SQL) that can be executed directly by a probabilistic database engine.

                  ┌───────────────────────────┐
                  │  Ontology-Mediated Query  │
                  └─────────────┬─────────────┘
                                │
                                ▼ [First-Order Query Rewriting]
                  ┌───────────────────────────┐
                  │   Expanded SQL Query      │
                  └─────────────┬─────────────┘
                                │
                                ▼ [Standard Execution Engine]
                  ┌───────────────────────────┐
                  │ Probabilistic DB Engine   │
                  └───────────────────────────┘

Carsten Lutz and Jean Christoph Jung proved that traditional query rewriting techniques can be successfully "lifted" to probabilistic settings (Lutz and Jung, 2012; Lutz and Jung, 2013). This lifting ensures that the semantic constraints of an ontology are preserved during probabilistic inference.

Furthermore, Ismail Ilkan Ceylan et al. extended this mechanism to open-world probabilistic databases. By mapping ontology-mediated queries into equivalent, tractable first-order forms, the system can compute exact answer probabilities and handle open-world probability intervals using existing database architectures without losing logical rigor.

Scaling Complex Statistical Models via Database Engines

The practical benefit of this paradigm becomes evident when scaling complex statistical relational models, such as Markov Logic Networks (MLNs). MLNs combine first-order logic with probabilistic graphical models by assigning weights to logical formulas. However, "grounding" these networks—instantiating all possible combinations of constants for every logical predicate—creates a massive computational bottleneck.

By repurposing an RDBMS as an execution engine, grounding and inference tasks can be converted into standard database queries. As Sunita Sarawagi noted, leveraging mature database optimization and storage capabilities allows systems to scale statistical inference far beyond the limits of traditional flat-file processing methods.

In practice, frameworks like Tuffy and DeepDive implement this by executing grounding via highly optimized SQL joins. Alexis Brenon et al. demonstrated that mapping these tasks to relational database queries slashes processing times from days to seconds in real-world applications like smart-home activity recognition.

This relation-centric approach is highly versatile and applies to several other machine learning architectures:

  • Big Data Pipelines: Karthik Raman et al. formulated probabilistic inference across modular pipelines as relational algebra primitives. By passing multiple hypotheses and their uncertainties as database rows, they prevent early errors from cascading through the pipeline.
  • Decision Forests: Hong Guan et al. showed that decision forest inference can be decomposed into a series of relational operators. By using a relational cross-product to align data blocks with individual trees, the database engine naturally achieves model parallelism.
  • Analytical Processing (OLAP): Raghu Ramakrishnan et al. integrated constraint management and probabilistic inference into standard OLAP systems, using SQL queries to dynamically generate dependency structures for imprecise datasets.

Bidirectional Compilation: From SQL to Learned Models

The integration between relational algebra and probabilistic inference is not a one-way street. While we can compile probabilistic models into SQL queries, we can also compile SQL queries into probabilistic models.

                  ┌───────────────────────────┐
                  │      Incoming SQL Query   │
                  └─────────────┬─────────────┘
                                │
                                ▼ [Probabilistic Query Translation]
                  ┌───────────────────────────┐
                  │ Mathematical Operations   │
                  └─────────────┬─────────────┘
                                │
                                ▼ [Direct Evaluation]
                  ┌───────────────────────────┐
                  │ Relational Sum-Product Net│
                  └───────────────────────────┘

This bidirectional relationship is exemplified by DeepDB, a framework introduced by Alejandro Molina et al.. Instead of using a database to execute a model, DeepDB models the database's underlying data distribution using a Relational Sum-Product Network (RSPN).

When a user submits an analytical SQL query, the system performs probabilistic query translation. It compiles the relational algebra of the SQL query into a set of mathematical operations (such as conditional expectations) evaluated directly by the RSPN. This allows the database to estimate query cardinalities and perform approximate query processing (AQP) in milliseconds, completely bypassing the need to scan physical data rows.

Extending Query Interfaces

To make these capabilities accessible, standard query languages must be extended to treat probabilities as first-class citizens. Early work by S. R. Vasanthakumar et al. achieved this by introducing an extended SQL (ESQL) with probabilistic operators, allowing an RDBMS to handle complex, ranked text searches via external function calls in the database pipeline.

In the context of the Semantic Web, Volker Tresp et al. extended SPARQL to include probabilistic weights. This extension allows users to retrieve both verified hard facts and predicted relationships in a single query operation, ranking results by their statistical likelihood.

Similarly, Kangqi Luo et al. demonstrated that natural language relations can be mapped to structured knowledge base queries by learning a distribution over candidate database schemas, effectively treating semantic parsing as a probabilistic querying task.

Ultimately, the convergence of relational databases and probabilistic inference works because it respects the strengths of both fields. By recognizing that multiplying probabilities is a join and summing them is an aggregation, this paradigm transforms the RDBMS from a deterministic data store into a high-performance engine for large-scale statistical reasoning.

Key Foundational Work

A Method for Implementing a Probabilistic Model as a Relational Database (1995) — contributed 4 concept elements to this direction.
Integrating INQUERY with an RDBMS to Support Text Retrieval (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_first_order_query_rewriting_lifting_136fdf23,
  title = {first-order query rewriting lifting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-query-rewriting-lifting/rdr_136fdf23e2894b46927007172ebc5bf3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_first_order_query_rewriting_lifting_136fdf23_v1,
  title = {first-order query rewriting lifting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-query-rewriting-lifting/rdr_136fdf23e2894b46927007172ebc5bf3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake