Abstract
Traditional Datalog is deterministic, and while Probabilistic Programming Datalog (PPDL) introduced discrete randomness, it struggled with continuous distributions. This paper establishes a rigorous mathematical foundation for Generative Datalog (GDatalog), leveraging measure theory and Markov processes to handle continuous outcomes. We prove that GDatalog produces well-defined probability distributions over database instances, ensuring semantic continuity and independence from rule execution order.
Introduction
In modern AI and data science, the integration of declarative logic with probabilistic reasoning is essential for handling uncertainty in structured data. While Datalog provides a powerful framework for the former, extending it to the probabilistic domain has historically been limited to discrete distributions. Real-world phenomena—such as sensor noise or financial fluctuations—are inherently continuous. This paper addresses the challenge of defining a mathematically sound semantics for Datalog programs that sample from uncountable outcome spaces, bridging the gap between logic programming and continuous probability.
Theoretical Framework
The authors construct the semantics of GDatalog by translating probabilistic rules into existential rules. A rule sampling from a Gaussian distribution is interpreted as asserting the existence of a value drawn from that distribution.
To manage the uncountable nature of continuous possible worlds, the framework utilizes Measure Theory and Standard Borel Spaces. The set of all possible database instances is treated as a measurable space, allowing for the assignment of probabilities to sets of worlds. The execution of a program, known as a "chase," is modeled as a discrete-time Markov process where each step transitions the database to a new random state. A core theoretical contribution is proving the equivalence of sequential and parallel chase policies, ensuring that the final distribution is invariant to the order of rule application.
Key Insights: Semantic Continuity and Symbolic Independence
A significant motivation for this work was a "glitch" in previous PPDL semantics where infinitesimal changes in distribution parameters could lead to discontinuous jumps in output probabilities. The new semantics ensures Semantic Continuity, where the output distribution varies smoothly with input parameters.
Consider the rule sets $\mathcal{G}_0$ and $\mathcal{G}_\epsilon$ shown above. In $\mathcal{G}_\epsilon$, a small perturbation $\epsilon$ is introduced. The resulting probability distribution, illustrated below, shows how the framework maintains a consistent mapping as $\epsilon$ approaches zero, avoiding the abrupt jumps seen in earlier frameworks.
Furthermore, the framework achieves Independence from Symbolic Names. In earlier systems, identical distributions with different labels could produce different behaviors. GDatalog ensures that semantics depend solely on the mathematical properties of the distributions, not their identifiers.
Results and Compositionality
The paper demonstrates that GDatalog is mathematically sound and well-defined. The Equivalence Theorem (Theorem 6.1) confirms that any measurable chase policy yields the same output distribution. Additionally, the language is compositional: it can consume a Probabilistic Database (PDB) and produce another PDB, facilitating integration with existing data management systems.
Limitations and Future Directions
Despite these advances, several challenges remain. Determining the termination of a probabilistic program is an undecidable problem in general. Furthermore, conditioning on "measure zero" events—such as an exact temperature reading—remains a hurdle due to the Borel-Kolmogorov paradox. Future work will focus on efficient representations of these infinite sets of possible worlds and developing practical query engines for continuous probabilistic logic.
Summary updated