Generative Datalog is the first component of PPDL (short for Probabilistic-Programming Datalog), a recently proposed probabilistic programming language. Specifically, generative Datalog provides constructs to refer to parameterized probability distribution, and is used for the specification of stochastic processes. Possible outcomes of such a stochastic process are possibly filtered according to logical constraints, which constitute the second component of PPDL. This speech is about generative Datalog, and hints on the possibility to represent non-measurable sets by combining generative Datalog constructs with addition over real numbers and a single, atomic, ground constraint.
Many probabilistic programming languages extend a deterministic programming language with primitive constructs for expressing random choices [1, 2]. Generative Datalog [3, 4] is not an exception and extends Datalog with ∆ -terms, primitive constructs for representing parametrized probability distributions. Semantically, generative Datalog programs are mapped to existential Datalog programs, so to represent the uncertainty of ∆ -terms. In such existential Datalog programs the outcome of ∆ -terms is encoded by means of auxiliary predicates, so that only ground ∆ -terms that are involved in the computation of inferred facts are eventually represented in models. Hence, the evaluation of a generative Datalog program is seen as a probabilistic process, and as such the semantics of generative Datalog can be formalized in terms of probability spaces, whose existence is claimed by Theorem 3.8 in [4].
On the other hand, PPDL (short for Probabilistic-Programming Datalog) [3, 4] adds logical constraints to generative Datalog, and assumes that the set of filtered possible outcomes is a measurable set (see Definition 5.3 in [ 4]). While in the finite case measurability of such a set is clear, the general case is non-trivial. In fact, non-measuable sets can be represented by combining generative Datalog constructs with addition over real numbers and a single, atomic, ground constraint. (Details on the construction are given in the invited speech.) This fact has implications on any extension of generative Datalog with constructs that allow for expressing constraints, among them default negation under stable model semantics [5]: if real addition is supported by the language, there exists no probability space for models of the general case.
Many other probabilistic logic languages exists in the literature. Some of them attach probabilities to database facts [6, 7, 8, 9, 10], or to rules [11, 12, 13, 14] and other provides constructs similar to ∆ -terms [15, 16, 17, 18, 19, 20]. A comparison between these languages is out of the scope of this speech, and the reader is referred to [4] for details. 2. Probability Spaces and Parametrized Probability Distribution A probability space is a triple (Ω , ℱ , ) satisfying the following conditions: • Ω is the sample space, a nonempty set comprising all possible outcomes (of the modeled probabilistic process). • ℱ ⊆ 2Ω is the event space, a collection of all the events to consider, where an event is a set of possible outcomes. ℱ must be a -algebra, ie.
– ℱ contains the sample space: Ω ∈ ℱ ; – ℱ is closed under complement: if ∈ ℱ , then (Ω ∖ ) ∈ ℱ ; – ℱ is closed under countable unions: if ∈ ℱ for ∈ N, then (︀ ⋃︀∈N )︀ ∈ ℱ . • : ℱ → [0, 1] is the probability measure, a function on events such that – is countably additive: if ∈ ℱ (for all ∈ N) are pairwise disjoint sets, then (⋃︀∈N ) = ∑︀∈N ().
– the measure of the sample space is equal to one: (Ω) = 1 .
Example 1. Throwing a (6-faces) die is a classical example of probabilistic process. In this case, the sample space Ω is {1, 2, 3, 4, 5, 6} (or [1..6] for a more compact notation), ie. the possible outcome of the probabilistic process is one of the six faces of the die. The event space ℱ can be the powerset of Ω , hence comprising elementary events such as {1} (the die lands on 1) and complex events such as {1, 3, 5} (the die lands on an odd number) — note that the event space can also be smaller, if there is no need to consider all the events. As for the probability measure , assuming that the die is unbiased, it just divides the cardinality of the event by 6, ie. : ↦→ |6| . So, ({1}) = 16 and ({1, 3, 5}) = 36 = 12 . ■
When Ω is countable, and all elementary events (ie. singletons) belongs to ℱ , the simpler notion of discrete probability distribution can be employed, ie. a function : Ω → [0, 1] such that ∑︀∈Ω () = 1. Let Ω denote the set of all discrete probability distributions over Ω . A parametrized probability distribution over Ω is a function : R → Ω, that is, (p) is a discrete probability distribution over Ω for every parameter instantiation p ∈ R.
Example 2 (Continuing Example 1). The constant function = { ↦→ 61 | ∈ [1..6]} is a discrete probability distribution characterizing the throw of an unbiased die. Biased dice can be represented by the parametrized probability distribution Die : R6 → [0..6] satisfying the following conditions:
Die(1, . . . , 6)() = for all ∈ [1..6]; • if ∈ [0, 1] for all ∈ [1..6] and ∑︀6=1 = 1, then Die(1, . . . , 6)(0) = 0 and • otherwise, Die(1, . . . , 6)(0) = 1 and Die(1, . . . , 6)() = 0 for all ∈ [1..6]. Note that outcome 0 is associated with incorrect instantiations of the parameters.
A ∆ -term is an expression of the form (P; S), where : R → Ω is a parametrized probability distribution over some Ω , each element in P and S is a constant or a variable, and |P| = . Elements in S contribute to a signature to distinguish diferent runs of the probabilistic process associated with (p), for any grounding p of P. Intuitively, each of those runs returns a possible outcome from Ω , according to the probability distribution (p).
Example 3 (Continuing Example 2). Each throw of a (possibly biased) die may result in a diferent outcome, which can be represented by the ∆ -term Die(1, . . . , 6; id ), where id is an identifier for a specific throw of the die — eg.
Die( 16 , . . . , 61 ; 1) and Die( 16 , . . . , 61 ; 2) to represent two throws of an unbiased die. Note that two ∆ -terms with diferent values for the parameters 1, . . . , 6 are necessarily associated with diferent throws, as they must either refer to diferent dice or to a die that is altered between the two throws — eg.
Die( 16 + , 16 − , 16 , 61 , 61 , 61 ; 1), for some ∈]0, 16 ], must refer to diferent throws. Die( 16 , . . . , 16 ; 1) and
Generative Datalog programs are Datalog programs whose head atoms possibly contains
∆ -terms — to simplify the presentation, at most one ∆ -term per rule. Their semantics is defined
a ∆ -term (P; S) with the following rules:
via an existential Datalog program obtained by replacing every rule (X) ←
(X) containing
Odd (
︂(
︂( 1 6 ; ︂) ←
Iteration( + 1) ←
Program Π ∃ is obtained from Π by replacing rule (
Π(Ω ⊇Π ) =
∏︁
Result (p,s,)∈
(p)().
are the only Result Die instances in 2′ and 3′, and Die( 16 )(
The probability space associated with a generative Datalog program Π is the triple
space associated with Π , ie. the set of possible outcomes of Π .
model of Π ∃
(Ω Π, ℱΠ, Π), defined next. A possible outcome of a generative Datalog program Π is a minimal
such that (p)() > 0 for every Result (p, s, ) ∈ . Let Ω Π be the sample
1 = {Odd (
• 3 = 1 ∪ {Result Die(
A derivation wrt. a generative Datalog program Π is a finite sequence = [1, . . . , ] of fLaecttsℐΠsudcehntohtaettheissedteorifvdeedribvyatsioomnse wunrts.aΠtis,fieadndrulleet oΩf⊇ΠΠ d∃e∪no{te1t,h.e. .s,eto−f1p}o,fsosirbalell ou∈tc[o1m..es]. of Π extending , ie. { ∈ Ω Π | ⊇ }. The event space associated with Π , denoted ℱΠ, is the -algebra generated from {Ω ⊇Π | ∈ ℐΠ} (ie. its closure under complement and countable (eg. {4} ∈/ ℱΠ).
Example 6 (Continuing Example 5). Recall minimal models 2, 3, 4 from Example 5. Let 1′
be the derivation [Odd (
The probability measure associated with a generative Datalog program Π , denoted Π, is such that the probability of the set of possible outcomes of Π extending a derivation is the product of the probabilities of the ∆ -terms represented in , ie.
use integer addition (rule 5), which could be also expressed by ∆ -terms ■ ■ ■ ■
Example 4 concludes by suggesting that addition over integers can be expressed by ∆ -terms without the need for an ad-hoc construct. The next example better clarify the idea. Example 8. Integer addition can be represented by the ∆ -term Add : R2 → Z∪{⊥} such that: • if , ∈ Z, then Add(, )( + ) = 1 and Add(, )() = 0 for all ̸= + ; • otherwise, Add(, )(⊥) = 1 and Add(, )() = 0 for all ̸= ⊥.
Accordingly, rule (
Iteration(Add(, 1)) ←
Seen(, ), Odd ().
Similarly, ∆ -terms can encode addition over rational numbers or any other countable set. ■
Essentially, Add(, ) in the example above is a Kronecker delta (the discrete anolog of the Dirac delta function) assigning 1 to + , and 0 to all other numbers, for all integers , . The same idea can be adapted to represent any function over any countable set (eg. integer multiplication and addition over rational numbers), but also any relation over uncountable sets (eg. greater than or less than). On the other hand, real addition cannot be encoded in this way because ∆ -terms by definition are associated with parametrized probability distributions over a countable sample space. (Such a restriction is overcome in [21], where parametrized probability distribution over uncountable sample spaces are supported.) Support for real addition in the language has implications on the existence of probability spaces for filtered models of generative Datalog programs, as hinted in the reminder of this section.
A non-measurable set is a set which cannot be assigned a meaningful “volume”. In ZermeloFraenkel set theory, the axiom of choice entails that non-measurable subsets of R exist. Classical examples are Vitali sets, defined next.
Definition 1. A Vitali set is a subset of [0, 1] such that, for each real number , there is exactly one number ∈ such that − is a rational number.
We now hint on how to associate a Vitali set with filtered-out possible outcomes of a generative Datalog program with real addition. Each possible outcome of such a program represents a diferent real number in the unit interval [0, 1], together with all rational numbers √ being a truncation of the binary representation of — eg. if = 22 ( ≃ 0.1011012), its truncations are 0.12, 0.1012, 0.10112, 0.1011012, and so on. Intuitively, and its truncations are produced by repeatedly appending to “0.” a binary digit chosen at random; digits are appended by using real addition, and generated by a ∆ -term selecting 0 or 2− with probability 0.5, for any integer parameter .
It remains to filter-out possible outcomes containing members of the Vitali set . For this purpose, the membership relation for can be represented by a ∆ -term employing a Kronecker delta. So, we can detect if the real number in a possible outcome belongs to , but we should avoid to recognize as a member of any of its truncations. This is achieved by taking a Vitali set containing the rational number 1, and therefore such that ∖ {1} is a set of irrational numbers (by Definition 1).
Summing up, the probability measure of the filtered-out possible outcomes would be the Lebesgue measure of the Vitali set , which is known to be a non-measurable set. Details on the construction are given in the invited speech.
This speech is about some ongoing research with Matthias Lanzinger, Michael Morak, and Andreas Pieris. This work was partially supported by the projects PON-MISE MAP4ID (CUP B21B19000650008) and PON-MISE S2BDW (CUP B28I17000250008), by the LAIA lab (part of the SILA labs) and by GNCS-INdAM. [9] T. Vieira, M. Francis-Landau, N. W. Filardo, F. Khorasani, J. Eisner, Dyna: toward a selfoptimizing declarative language for machine learning applications, in: T. Shpeisman, J. Gottschlich (Eds.), Proceedings of the 1st ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL@PLDI 2017, Barcelona, Spain, June 18, 2017, ACM, 2017, pp. 8–17. URL: https://doi.org/10.1145/3088525.3088562. doi:10. 1145/3088525.3088562. [10] F. G. Cozman, D. D. Mauá, The joy of probabilistic answer set programming: Semantics, complexity, expressivity, inference, Int. J. Approx. Reason. 125 (2020) 218–239. URL: https://doi.org/10.1016/j.ijar.2020.07.004. doi:10.1016/j.ijar.2020.07.004. [11] P. M. Domingos, D. Lowd, Markov Logic: An Interface Layer for Artificial Intelligence, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2009. URL: https://doi.org/10.2200/S00206ED1V01Y200907AIM007. doi:10.2200/S00206ED1V01Y200907AIM007. [12] F. Niu, C. Ré, A. Doan, J. W. Shavlik, Tufy: Scaling up statistical inference in markov logic networks using an RDBMS, Proc. VLDB Endow. 4 (2011) 373–384. URL: http://www.vldb. org/pvldb/vol4/p373-niu.pdf. doi:10.14778/1978665.1978669. [13] F. Niu, C. Zhang, C. Ré, J. W. Shavlik, Deepdive: Web-scale knowledge-base construction using statistical learning and inference, in: M. Brambilla, S. Ceri, T. Furche, G. Gottlob (Eds.), Proceedings of the Second International Workshop on Searching and Integrating New Web Data Sources, Istanbul, Turkey, August 31, 2012, volume 884 of CEUR Workshop Proceedings, CEUR-WS.org, 2012, pp. 25–28. URL: http://ceur-ws.org/Vol-884/VLDS2012_p25_Niu.pdf. [14] J. Lee, S. Talsania, Y. Wang, Computing LPMLN using ASP and MLN solvers, Theory Pract. Log. Program. 17 (2017) 942–960. URL: https://doi.org/10.1017/S1471068417000400. doi:10.1017/S1471068417000400. [15] V. S. Costa, D. Page, J. Cussens, Clp(BN ): Constraint logic programming for probabilistic knowledge, in: L. D. Raedt, P. Frasconi, K. Kersting, S. Muggleton (Eds.), Probabilistic Inductive Logic Programming - Theory and Applications, volume 4911 of Lecture Notes in Computer Science, Springer, 2008, pp. 156–188. URL: https://doi.org/10.1007/978-3-540-78652-8_ 6. doi:10.1007/978-3-540-78652-8\_6. [16] D. Poole, The independent choice logic and beyond, in: L. D. Raedt, P. Frasconi, K. Kersting, S. Muggleton (Eds.), Probabilistic Inductive Logic Programming - Theory and Applications, volume 4911 of Lecture Notes in Computer Science, Springer, 2008, pp. 222–243. URL: https://doi.org/10.1007/978-3-540-78652-8_8. doi:10.1007/978-3-540-78652-8\_8. [17] C. Baral, M. Gelfond, J. N. Rushton, Probabilistic reasoning with answer sets, Theory Pract. Log. Program. 9 (2009) 57–144. URL: https://doi.org/10.1017/S1471068408003645. doi:10.1017/S1471068408003645. [18] J. Vennekens, M. Denecker, M. Bruynooghe, Cp-logic: A language of causal probabilistic events and its relation to logic programming, Theory Pract. Log. Program. 9 (2009) 245–308.
URL: https://doi.org/10.1017/S1471068409003767. doi:10.1017/S1471068409003767. [19] B. Gutmann, I. Thon, A. Kimmig, M. Bruynooghe, L. D. Raedt, The magic of logical inference in probabilistic programming, Theory Pract. Log. Program. 11 (2011) 663–680.
URL: https://doi.org/10.1017/S1471068411000238. doi:10.1017/S1471068411000238. [20] D. Nitti, T. D. Laet, L. D. Raedt, Probabilistic logic programming for hybrid relational domains, Mach. Learn. 103 (2016) 407–449. URL: https://doi.org/10.1007/s10994-016-5558-8. doi:10.1007/s10994-016-5558-8. [21] M. Grohe, B. L. Kaminski, J. Katoen, P. Lindner, Generative datalog with continuous distributions, in: D. Suciu, Y. Tao, Z. Wei (Eds.), Proceedings of the 39th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, ACM, 2020, pp. 347–360. URL: https://doi.org/10.1145/3375395. 3387659. doi:10.1145/3375395.3387659.