Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings

Tal Friedman, Guy Van den Broeck

Abstract

We propose unifying techniques from probabilistic databases and relational embedding models with the goal of performing complex queries on incomplete and uncertain data. We formalize a probabilistic framework, TRACTOR, that factorizes relations into latent unary components, enabling efficient evaluation of complex logical queries.

Introduction: The Challenge of Uncertain Data

Traditional relational databases operate under the "Closed World Assumption": if a fact is not explicitly present in a table, it is assumed to be false. However, real-world data is often incomplete or uncertain. Probabilistic Databases (PDBs) address this by assigning probabilities to facts, as shown in Figure 1.

Figure 1: Example of a Probabilistic Database (PDB) with tuple probabilities.

While PDBs provide a formal logic for uncertainty, they struggle with "filling in the blanks" for missing data. Conversely, relational embeddings (like DistMult) excel at predicting missing facts but lack a consistent way to answer complex, nested queries. Simply combining them often leads to computational intractability, where even relatively simple queries become #P-hard.

The TRACTOR Framework

The authors introduce TRACTOR (TRractable prAbabilistic database CorrespondenT tO Relational embeddings) to bridge this gap. TRACTOR's core innovation is the factorization of binary relations into latent unary properties. Instead of treating a relation $R(x, y)$ as a single atomic event, it is decomposed into latent properties: $$R(x, y) \iff E(x) \land T(R) \land E(y)$$ where $E$ and $T$ are latent unary random variables representing entity and relation properties. By using a mixture of $d$ such factorized models, TRACTOR achieves the expressivity of standard vector embeddings while maintaining a sound probabilistic foundation.

Achieving Tractable Inference

The primary advantage of TRACTOR is its computational efficiency. In standard PDBs, query evaluation often hits a wall of #P-hardness due to overlapping binary relations. By "shattering" these relations into independent unary parts, TRACTOR ensures that any Union of Conjunctive Queries (UCQ) can be computed in polynomial time.

Figure 2: Complexity landscape of queries. TRACTOR enables PTIME evaluation for all UCQs, including those traditionally considered #P-hard.

As illustrated in Figure 2, many queries (such as $Q_{10}$ and $Q_{11}$) that are typically #P-hard for standard PDB algorithms become tractable under the TRACTOR model. This allows for efficient reasoning over massive, uncertain knowledge bases in linear time relative to the domain size.

Experimental Evaluation

TRACTOR was evaluated on the Bio dataset, a large-scale biomedical knowledge base containing over 8 million edges and 97,000 entities (including drugs, diseases, and proteins). The task involved answering complex multi-hop queries and logical "OR" conditions.

  • Performance: TRACTOR achieved an Average Percentile Rank (APR) of 86.3, significantly outperforming traditional embedding baselines like TransE (81.6) and Bilinear (78.6).
  • Versatility: Unlike geometric models such as GQE (Graph Query Embeddings), TRACTOR naturally handles "Union" queries (logical ORs), which are notoriously difficult for vector-only approaches.

Conclusion and Future Directions

TRACTOR demonstrates that relational embeddings are essentially a specific class of factorized probabilistic databases. While currently limited to symmetric relations, future work aims to incorporate asymmetry through complex numbers and explore "open-world" reasoning. This framework paves the way for a new generation of AI systems that can reason logically over the uncertain, latent representations learned by machine learning.

Summary updated

Abstract

We propose unifying techniques from probabilistic databases and relational embedding models with the goal of performing complex queries on incomplete and uncertain data. We formalize a probabilisti...
BibTeX
@inproceedings{friedman2020symbolic,
  author = {Tal Friedman and Guy Van den Broeck},
  title = {{Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=23e2UlXU_Xm},
}
Figure