Declarative Statistical Modeling with Datalog
Vince Barany
LogicBlox, Inc.

Balder ten Cate
LogicBlox, Inc.

Benny Kimelfeld
LogicBlox, Inc.

arXiv:1412.2221v2 [cs.DB] 5 Jan 2015

ABSTRACT

Zografoula Vagena
LogicBlox, Inc.

is phrased over the outcome of the program). Recently,
DARPA initiated the project of Probabilistic Programming for Advancing Machine Learning, aimed at advancing PP systems (with a focus on a specific collection of systems, e.g., [29,31,37]) towards facilitating the
development of algorithms based on machine learning.
In probabilistic programming, a statistical model is
typically phrased by means of two components. The
first component is a generative process that produces
a random possible world by straightforwardly following instructions with randomness, and in particular,
sampling from common numerical probability functions;
this gives the prior distribution. The second component
allows to phrase constraints that the relevant possible
worlds should satisfy, and, semantically, transforms the
prior distribution into the posterior distribution—the
subspace conditional on the constraints.
As an example, in supervised text classification (e.g.,
spam detection) the goal is to classify a text document into one of several known classes (e.g., spam/nonspam). Training data consists of a collection of documents labeled with classes, and the goal of learning is to
build a model for predicting the classes of unseen documents. One common approach to this task assumes
a generative process that produces random parameters
for every class, and then uses these parameters to define a generator of random words in documents of the
corresponding class [30, 32]. So, the prior distribution
generates parameters and documents for each class, and
the posterior is defined by the actual documents of the
training data. In unsupervised text classification the
goal is to cluster a given set of documents, so that different clusters correspond to different topics (which are
not known in advance). Latent Dirichlet Allocation [9]
approaches this problem in a similar generative way as
the above, with the addition that each document is associated with a distribution over topics.
While the agenda of probabilistic programming is the
deployment of programming languages to developing
statistical models, in this framework paper we explore
this agenda from the point of view of database programming. Specifically, we propose and investigate an extension of Datalog for declarative specification of statistical
models on top of a database. We believe that Datalog
can be naturally extended to a language for building
statistical models, since its essence is the production of
new facts from known (database) facts. Of course, traditionally these facts are deterministic, and our exten-

Formalisms for specifying general statistical models, such as
probabilistic-programming languages, typically consist of two
components: a specification of a stochastic process (the prior),
and a specification of observations that restrict the probability
space to a conditional subspace (the posterior). Use cases of
such formalisms include the development of algorithms in machine learning and artificial intelligence. We propose and investigate a declarative framework for specifying statistical models on
top of a database, through an appropriate extension of Datalog.
By virtue of extending Datalog, our framework offers a natural integration with the database, and has a robust declarative
semantics (that is, semantic independence from the algorithmic
evaluation of rules, and semantic invariance under logical program transformations).
Our proposed Datalog extension provides convenient mechanisms
to include common numerical probability functions; in particular,
conclusions of rules may contain values drawn from such functions. The semantics of a program is a probability distribution
over the possible outcomes of the input database with respect to
the program; these possible outcomes are minimal solutions with
respect to a related program that involves existentially quantified variables in conclusions. Observations are naturally incorporated by means of integrity constraints over the extensional and
intensional relations. We focus on programs that use discrete
numerical distributions, but even then the space of possible outcomes may be uncountable (as a solution can be infinite). We
define a probability measure over possible outcomes by applying
the known concept of cylinder sets to a probabilistic chase procedure. We show that the resulting semantics is robust under
different chases. We also identify conditions guaranteeing that
all possible outcomes are finite (and then the probability space
is discrete). We argue that the framework we propose retains
the purely declarative nature of Datalog, and allows for natural
specifications of statistical models.

1.

Dan Olteanu
Oxford University
& LogicBlox, Inc.

INTRODUCTION

Formalisms for specifying general statistical models
are commonly used for developing machine learning and
artificial intelligence algorithms for problems that involve inference under uncertainty. A substantial scientific effort has been made on developing such formalisms
and corresponding system implementations. An intensively studied concept in that area is that of Probabilistic Programming [21] (PP), where the idea is that the
programming language allows for building general random procedures, while the system executes the program
not in the standard programming sense, but rather by
means of inference. Hence, a PP system is built around
a language and an inference engine (which is typically
based on variants of Markov Chain Monte Carlo, most
notably Metropolis-Hastings). An inference task is a
probability-aware aggregate operation over all the possible worlds, such as finding the most likely possible
world, or estimating the probability of an event (which
1

example such a rule states that “if the premise holds,
then there exists a fact Visits(c, b, x) where x is associated with the distribution Poisson and the parameter
λ.” In particular, if the program contains the aforementioned Rule (1), then Rule (3) has no effect; similarly, if
the tuple (c, b, λ) is in both Client and PreferredClient,
then in the presence of Rule (2) the outcome does not
change if one of these tuples is removed.
In this paper we focus on numerical probability distributions that are discrete (e.g., the aforementioned
ones). Our framework has a natural extension to continuous distributions (e.g., Gaussian or Pareto), but our
analysis requires a nontrivial generalization that we defer to future work.
When applying the program G to an input instance
I, the probability space is over all the minimal solutions
b such that all the numerical samples have
of I w.r.t. G,
a positive probability. To define the probabilities of a
sample in this probability space, we consider two cases.
In the case where all the possible outcomes are finite, we
get a discrete probability distribution, and the probability of a possible outcome can be defined immediately
from its content. But in general, a possible outcome
can be infinite, and moreover, the set of all possible
outcomes can be uncountable. Hence, in the general
case we define a probability measure space. To make
the case for the coherence of our definitions (i.e., our
definitions yield proper probability spaces), we define a
natural notion of a probabilistic chase where existential
variables are produced by invoking the corresponding
numerical distributions. We use cylinder sets [6] to define a measure space based on a chase, and prove that
this definition is robust, since one establishes the same
probability measure no matter which chase is used.

sion enables the production of probabilistic facts that,
in particular, involve numbers from available numerical distributions. And by virtue of extending Datalog, our framework offers a natural integration with the
database, and has a robust declarative semantics: a program is a set of rules that is semantically invariant under
transformations that retain logical equivalence. Moreover, the semantics of a program (i.e., the probability
space it specifies) is fully determined by the satisfaction of rules, and does not depend on the specifics of
any execution engine.
In par with languages for probabilistic programming,
our proposed extension consists of two parts: a generative Datalog program that specifies a prior probability space over (finite or infinite) sets of facts that we
call possible outcomes, and a definition of the posterior probability by means of observations, which come
in the form of an ordinary logical constraint over the
extensional and intensional relations.
The generative component of our Datalog extension provides convenient mechanisms to include conventional parameterized numerical probability functions (e.g., Poisson, geometrical, etc.). Syntactically,
this extension allows to sample values in the conclusion of rules, according to specified parameterized
distributions. As an example, consider the relation
Client(ssn, branch, avgVisits) that represents clients of
a service provider, along with their associated branch
and average number of visits (say, per month). The following distributional rule models a random number of
visits for that client in the branch.
Visits(c, b, Poisson[λ]) ← Client(c, b, λ)

(1)

Note, however, that a declarative interpretation of the
above rule is not straightforward. Suppose that we have
another rule of the following form:
Visits(c, b, Poisson[λ]) ← PreferredClient(c, b, λ)

Related Work. Our contribution is a marriage between probabilistic programming and the declarative
specification of Datalog. The key features of our approach are the ability to express probabilistic models
concisely and declaratively in a Datalog extension with
probability distributions as first-class citizens. Existing formalisms that associate a probabilistic interpretation with logic are either not declarative (at least in
the Datalog sense) or depart from the probabilistic programming paradigm (e.g., by lacking the support for numerical probability distributions). We next discuss representative related formalisms and contrast them with
our work. They can be classified into three broad categories: (1) imperative specifications over logical structures, (2) logic over probabilistic databases, and (3)
indirect specifications over the Herbrand base. (Some
of these formalisms belong to more than one category.)
The first category includes imperative probabilistic
programming languages [43], such as BLOG [31], that
can express probability distributions over logical structures, via generative stochastic models that can draw
values at random from numerical distributions, and con-

(2)

Then, what would be the semantics if a person is both
a client and a preferred client? Do we sample twice for
that person? And what if the two λs of the two facts
are not the same? Is sampling according to one rule
considered a satisfaction of the other rule? What if we
have also the following rule:
Visits(c, b, Poisson[λ]) ← Client(c, b, λ), Active(b) (3)
From the viewpoint of Datalog syntax, Rule (3) is logically implied by Rule (1), since the premise of Rule (3)
implies the premise of Rule (1). Hence, we would like
the addition of Rule (3) to have no effect on the program. This means that some rule instantiations will not
necessarily fire an actual sampling.
To make sense of rules such as the above, we associate
b such that
with every program G an auxiliary program G,
Gb does not use distributions, but is rather an ordinary
Datalog program where a rule can have an existentially
quantified variable in the conclusion. Intuitively, in our
2

dition values of program variables on observations. In
contrast with closed-universe languages such as SQL
and logic programs, BLOG considers open-universe
probability models that allow for uncertainty about the
existence and identity of objects. Instantiations of this
category also do not focus on a declarative specification,
and indeed, their semantics is dependent on their particular imperative implementations. P-log [7] is a Prologbased language for specifying Bayesian networks. Although declarative in nature, the semantics inherently
assumes a form of acyclicity that allows the rules to be
executed serially. Here we are able to avoid such an
assumption since our approach is based on the minimal
solutions of an existential Datalog program.
The formalisms in the second category view the generative part of the specification of a statistical model
as a two-step process. In the first step, facts are being
randomly generated by a mechanism external to the
program. In the second step, a logic program, such as
Prolog [27] or Datalog [1], is evaluated over the resulting random structure. This approach has been taken
by PRISM [40], the Independent Choice Logic [38], and
to a large extent by probabilistic databases [41] and
their semistructured counterparts [26]. The focus of our
work, in contrast, is on a formalism that completely defines the statistical model, without referring to external
processes.
One step beyond the second category and closer to
our work is taken by uncertainty-aware query languages
for probabilistic data such as TriQL [42], I-SQL, and
world-set algebra [4, 5]. The latter two are natural
analogs to SQL and relational algebra for the case of incomplete information and probabilistic data [4]. They
feature constructs such as repair-key, choice-of,
possible, certain, and group-worlds-by that can
construct possible worlds representing all repairs of a
relation with respect to (w.r.t.) key constraints, close
the possible worlds by unioning or intersecting them,
or group the worlds into sets with the same results to
sub-queries. World-set algebra has been extended to
(world-set) Datalog, fixpoint, and while-languages [14]
to define Markov chains. While such languages cannot
explicitly specify probability distributions, they may
simulate a specific categorical distribution indirectly using non-trivial programs with specialized language constructs like repair-key on input tuples with weights
representing samples from the distribution.
MCDB [25] and SimSQL [11] propose SQL extensions
(with for-loops and probability distributions) coupled
with Monte Carlo simulations and parallel database
techniques for stochastic analytics in the database. In
contrast, our work focuses on existential Datalog with
recursion and probability spaces over the minimal solutions of the data w.r.t. the Datalog program.
Formalisms in the third category are indirect specifications of probability spaces over the Herbrand base,
which is the set of all the facts that can be obtained

using the predicate symbols and the constants of the
database. This category includes Markov Logic Networks (MLNs) [15, 33], where the logical rules are used
as a compact and intuitive way of defining factors. In
other words, the probability of a possible world is the
product of all the numbers (factors) that are associated with the rules that the world satisfies. This approach is applied in DeepDive [34], where a database is
used for storing relational data and extracted text, and
database queries are used for defining the factors of a
factor graph. We view this approach as indirect since a
rule does not determine directly the distribution of values. Moreover, the semantics of rules is such that the
addition of a rule that is logically equivalent to (or implied by, or indeed equal to) an existing rule changes the
semantics and thus the probability distribution. A similar approach is taken by Probabilistic Soft Logic [10],
where in each possible world every fact is associated
with a weight (degree of truth).
Further formalisms in this category are probabilistic
Datalog [19], probabilistic Datalog+/- [22], and probabilistic logic programming (ProbLog) [27]. In these formalisms, every rule is associated with a probability. For
ProbLog, the semantics is not declarative as the rules
follow a certain evaluation order; for probabilistic Datalog, the semantics is purely declarative. Both semantics
are different from ours and that of the other formalisms
mentioned thus far. A Datalog rule is interpreted as a
rule over a probability distribution over possible worlds,
and it states that, for a given grounding of the rule,
the marginal probability of being true is as stated in
the rule. Probabilistic Datalog+/- uses MLNs as the
underlying semantics. Besides our support for numerical probability distributions, our formalism is used for
defining a single probability space, which is in par with
the standard practice in probabilistic programming.
As said earlier, the programs in our proposed formalism allow for recursion. As we show in the paper, the
semantics is captured by Markov chains that may be infinite. Related formalisms are those of the Probabilistic
Context-Free Grammar (PCFG) and the more general
Recursive Markov Chain (RMC) [17], where the probabilistic specification is by means of a finite set of transition graphs that can call one another (in the sense of
method call) in a possibly recursive fashion. In database
research, PCFGs and RMCs have been explored in the
context of probabilistic XML [8, 13]. Although these
formalisms do not involve numerical distributions, in
future work we plan to conduct a study of the relative
expressive power between them and restrictions of our
framework. Moreover, we plan to study whether and
how inference techniques on PCFGs and RMCs can be
adapted to our framework.
Organization. The remainder of the paper is organized as follows. In Section 2 we give basic definitions.
The syntax and semantics of generative Datalog is intro-

3

duced in Section 3, where we focus on the case where all
solutions are finite. In Section 4 we present our adaptation of the chase. The general case of generative Datalog, where solutions can be infinite, is presented in
Section 5. We complete our development in Section 6,
where generative Datalog is extended with constraints
(observations) to form Probabilistic-Programming Datalog (PPDL). Finally, we discuss extensions and future
directions in Section 7 and conclude in Section 8.

2.

and infinite, minimal solutions of I w.r.t. D is denoted
by min-solD (I), and the set of all finite minimal solutions is denoted by min-solfin
D (I). It is a well known fact
that, if D is a Datalog program (that is, without existential quantifiers), then every input instance I has a
unique minimal solution, which is finite, and therefore
min-solfin
D (I) = min-solD (I).
Probability spaces.
We separately consider discrete and continuous probability spaces. We initially
focus on the discrete case; there, a probability space is a
pair (Ω, π), where Ω is a finite or countably infinite set,
called
the sample space, and π : Ω → [0, 1] is such that
P
o∈Ω π(o) = 1. If (Ω, π) is a probability space, then
π is a probability distribution over Ω. We say that π is
a numerical probability distribution if Ω ⊆ R. In this
work we focus on discrete numerical distributions.
A parameterized probability distribution is a function δ : Ω × Rk → [0, 1], such that δ(·, p) : Ω → [0, 1]
is a probability distribution for all p ∈ Rk . We use
pardim(δ) to denote the number k, called the parameter dimensionality of δ. For presentation’s sake, we may
write δ(o|p) instead of δ(o, p). Moreover, we denote the
(non-parameterized) distribution δ(·|p) by δ[p]. Examples of (discrete) parameterized distributions follow.

PRELIMINARIES

In this section we give some preliminary definitions
that we will use throughout the paper.
Schemas and instances. A (relational ) schema is
a collection S of relation symbols, where each relation
symbol R is associated with an arity, denoted arity(R),
which is a natural number. An attribute of a relation
symbol R is any number in {1, . . . , arity(R)}. For simplicity, we consider here only databases over real numbers; our examples may involve strings, which we assume are translatable into real numbers. A fact over
a schema S is an expression of the form R(c1 , . . . , cn )
where R is an n-ary relation in S and c1 , . . . , cn ∈ R.
An instance I over S is a finite set of facts over S. We
will denote by RI the set of all tuples (c1 , . . . , cn ) such
that R(c1 , . . . , cn ) ∈ I is a fact of I.

• Flip(x|p): Ω is {0, 1}, and for a parameter p ∈ [0, 1]
we have Flip(1|p) = p and Flip(0|p) = 1 − p.
• Poisson(x|λ): Ω = N, and for a parameter λ ∈
(0, ∞) we have Poisson(x|λ) = λx e−λ /x!.
• Geo(x|p): Ω = N, and for a parameter p ∈ [0, 1]
we have Geo(x|p) = (1 − p)x p.

Datalog programs.
In this work we use Datalog with the option of having existential variables in
the head [12]. Formally, an existential Datalog program, or just Datalog∃ program for short, is a triple
D = (E, I, Θ) where: (1) E is a schema, called the extensional database (EDB) schema, (2) I is a schema,
called the intensional database (IDB) schema, and is
disjoint from E, and (3) Θ is a finite set of Datalog∃
rules, i.e.,, first-order formulas of the form


∀x ∃y(ψ(x, y)) ← ϕ(x)

In Section 7 we will discuss the extension of our
framework to models that have an unbounded number
of parameters, and to continuous distributions.

3. GENERATIVE DATALOG
A Datalog program without existential quantifiers
specifies how to obtain a solution from an input EDB
instance by producing the set of inferred IDB facts.
In this section we present generative Datalog programs,
which specify how to infer a distribution over possible
outcomes given an input EDB instance.

where ϕ(x) is a conjunction of atomic formulas over
E ∪I and ψ(x, y) is an atomic formula over I, such that
each variable in x occurs in at least one atomic formula
of ϕ. Here, by an atomic formula (or, atom) we mean
an expression of the form R(t1 , . . . , tn ) where R is an
n-ary relation and t1 , . . . , tn are either constants (i.e.,
real numbers) or variables. We usually omit the universal quantifiers for readability’s sake. Datalog is the
fragment of Datalog∃ where the conclusion (left-hand
side) of each rule is a single atomic formula without
existential quantifiers.
Let D = (E, I, Θ) be a Datalog∃ program. An input instance for D is an instance I over E. A solution
of I w.r.t. D is a possibly-infinite set F of facts over
E ∪ I, such that I ⊆ F and F satisfies all rules in Θ
(viewed as first-order sentences). A minimal solution
of I (w.r.t. D) is a solution F of I such that no proper
subset of F is a solution of I. The set of all, finite

3.1 Syntax
We first define the syntax of a generative Datalog
program, which we call a GDatalog[∆] program.
Definition 3.1 (GDatalog[∆]). Let ∆ be a finite set of parametrized numerical distributions.
1. A ∆-term is a term of the form δ[p1 , . . . , pk ]
where δ ∈ ∆ is a parametrized distribution with
pardim(δ) = k, and p1 , . . . , pk are variables and/or
constants.
2. A ∆-atom in a schema S is an atomic formula
R(t1 , . . . , tn ) with R ∈ S an n-ary relation, such
that exactly one term ti (1 ≤ i ≤ n) is a ∆-term,
4

1. Earthquake(c, Flip[0.01]) ← City(c, r)

1. ∃y EarthquakeFlip
2 (c, y, 0.01) ← City(c, r)

2. Unit(h, c) ← Home(h, c)

2. Unit(h, c) ← Home(h, c)

3. Unit(b, c) ← Business(b, c)

3. Unit(b, c) ← Business(b, c)

4. Burglary(x, c, Flip[r]) ← Unit(x, c) , City(c, r)

4. ∃y BurglaryFlip
3 (x, c, y, r) ← Unit(x, c) , City(c, r)

5. Trig(x, Flip[0.6]) ← Unit(x, c) , Earthquake(c, 1)

5. ∃y TrigFlip
2 (x, y, 0.6) ← Unit(x, c) , Earthquake(c, 1)

6. Trig(x, Flip[0.9]) ← Burglary(x, c, 1)

6. ∃y TrigFlip
2 (x, y, 0.9) ← Burglary(x, c, 1)

7. Alarm(x) ← Trig(x, 1)

7. Alarm(x) ← Trig(x, 1)
8. Earthquake(c, d) ← EarthquakeFlip
2 (c, d, p)

Figure 1: An example GDatalog[∆] program G

9. Burglary(x, y) ← BurglaryFlip
2 (x, y, p)
10. Trig(x, y) ← TrigFlip
2 (x, y, p)

and all other tj are constants and/or variables.
3. A GDatalog[∆] rule over a pair of disjoint schemas
E and I is a first-order sentence of the form
∀x(ψ(x) ← φ(x)) where φ(x) is a conjunction of
atoms in E ∪ I and ψ(x) is either an atom in I or
a ∆-atom in I.

Figure 2: The Datalog∃ program Gb for the
GDatalog[∆] program G of Figure 1
I ∆ (namely, those of I) are referred to as the ordinary
relation symbols. Intuitively, a fact in Riδ asserts the
existence of a tuple in R and a sequence of parameters,
such that the ith element of the tuple is sampled from
δ using the parameters.
The set Θ∆ contains three kinds of rules:
(i) All Datalog rules from Θ that contain no ∆-terms;

4. A GDatalog[∆] program is a triple G = (E, I, Θ),
where E and I are disjoint schemas and Θ is a
finite set of GDatalog[∆] rules over E and I.
Example 3.2. Our example is based on the burglar
example of Pearl [36] that has been frequently used for
illustrating probabilistic programming (e.g., [35]). Consider the EDB schema E consisting of the following relations: House(h, c) represents houses h and their location cities c, Business(b, c) represents businesses b and
their location cities c, City(c, r) represents cities c and
their associated burglary rates r, and AlarmOn(x) represents units (houses or businesses) x where the alarm
is on. Figure 3 shows an instance I over this schema.
Now consider the GDatalog[∆] program G = (E, I, Θ)
of Figure 1. Here, ∆ consists of only one distribution,
namely Flip. The first rule above, intuitively, states
that, for every fact of the form City(c, r), there must be
a fact Earthquake(c, y) where y is drawn from the Flip
(Bernoulli) distribution with the parameter 0.01.

(ii) The rule ∃yRiδ (t, y, t′ , p) ← φ(x) for every rule of
the form R(t, δ[p], t′ ) ← φ(x) in Θ, where i is the
position of δ[p] in R(t, δ[p], t′ );
(iii) The rule ∀x, p(R(x) ← Riδ (x, p)) for every distributional relation symbol Riδ ∈ I ∆ .
Note that in (ii), t and t′ are the terms that occur before
and after the ∆-term δ[p], respectively. A rule in (iii)
states that every fact in Riδ should be reflected in the
relation R.
Example 3.3. The GDatalog[∆] program G given in
Example 3.2 gives rise to the corresponding Datalog∃
program Gb of Figure 2. As an example of (ii), rule 6 of
Figure 1 is replaced with rule 6 of Figure 2. Rules 8–10
of Figure 2 are examples of (iii).

3.2 Possible Outcomes

A possible outcome is defined as follows.

To define the possible outcomes of a GDatalog[∆]
program, we associate to each GDatalog[∆] program
G = (E, I, Θ) a corresponding Datalog∃ program Gb =
(E, I ∆ , Θ∆ ). The possible outcomes of an input instance I w.r.t. G will then be minimal solutions of I
b Next, we describe I ∆ and Θ∆ .
w.r.t. G.
The schema I ∆ extends I with the following additional relation symbols: whenever a rule in Θ contains
a ∆-atom of the form R(. . . , δ[. . .], . . .), and i ≤ arity(R)
is the argument position at which the δ-term in question occurs, then we add to I ∆ a corresponding relation
symbol Riδ , whose arity is arity(R) + pardim(δ). These
relation symbols Riδ are called the distributional relation symbols of I ∆ , and the other relation symbols of

Definition 3.4 (Possible Outcome). Let I be
an input instance for a GDatalog[∆] program G. A possible outcome for I w.r.t. G is a minimal solution F of
b such that δ(b|p) > 0 for every distributional
I w.r.t. G,
fact Riδ (a, b, c, p) ∈ F with b in the ith position.
We denote the set of all possible outcomes of I w.r.t. G
by ΩG (I), and we denote the set of all finite possible
outcomes by Ωfin
G (I).
The following proposition provides an insight into
the possible outcomes of an instance, and will reappear later on in our study of the chase. For any distributional relation Riδ ∈ Θ∆ , the functional dependency associated to Riδ is the functional dependency
5

House
id
city
NP1
Napa
NP2
Napa
YC1 Yucaipa
City
name
burglaryrate
Napa
0.03
Yucaipa
0.01

EarthquakeFlip
2
city
draw param
Napa
1
0.01
Yucaipa
0
0.01

Business
id
city
NP3
Napa
YC1 Yucaipa

AlarmOn
unit
NP1
YC1
YC2

BurglaryFlip
3
city
draw param
Napa
1
0.03
0.03
Napa
0
0.03
Napa
1
Yucaipa
0
0.01

unit
NP1
NP2
NP3
YU1

Figure 3: EDB instance of the running example
unit
NP1
NP2
NP3
YU1

Riδ : ({1, . . . , arity(Riδ )} \ {i}) → i, expressing that the
i-th attribute is functionally determined by the rest.
Proposition 3.5. Let I be any input instance for a
GDatalog[∆] instance G. Then every possible outcome
in ΩG (I) satisfies all functional dependencies associated
to distributional relations.

unit
NP1
NP3
NP1
NP2
NP3

The proof of Proposition 3.5 is easy: if an instance J
violates the funtional dependency associated to a distributional relation Riδ , then one of the two facts involved
in the violation can be removed, showing that J is, in
b
fact, not a minimal solution w.r.t. G.

Burglary
city
draw
Napa
1
Napa
0
Napa
1
Yucaipa
0
TrigFlip
2
draw param
1
0.9
0
0.9
0.6
1
0.6
1
0.6
0

Earthquake
city
draw
Napa
1
Yucaipa
0

w(f )
0.01
0.99

w(f )
0.9
0.1
0.6
0.6
0.4

w(f )
0.03
0.97
0.03
0.99

id
NP1
NP2
NP3
YU1

Alarm
unit
NP1
NP2

Unit
city
Napa
Napa
Napa
Yucaipa
Trig
unit draw
NP1
1
NP3
0
NP1
1
NP2
1
NP3
0

Figure 4: A possible outcome for the input instance I in the running example

3.3 Finiteness and Weak Acyclicity
Our presentation first focuses on the case where all
the possible outcomes for the GDatalog[∆] program are
finite. Before we proceed to defining the semantics of
such a GDatalog[∆] program, we present the notion of
weak acyclicity for a GDatalog[∆] program, as a natural syntactic property that guarantees finiteness of all
possible outcomes. This draws on the notion of weak
acyclicity for Datalog∃ [18]. Consider any GDatalog[∆]
program G = (E, I, Θ). A position of I is a pair (R, i)
where R ∈ I and i is an attribute of R. The dependency
graph of G is the directed graph that has the attributes
of I as the nodes, and the following edges:
• A normal edge (R, i) → (S, j) whenever there is
a rule ψ(x) ← ϕ(x) and a variable x at position
(R, i) in ϕ(x), and at position (S, j) in ψ(x).

3.4 Probabilistic Semantics
Intuitively, the semantics of a GDatalog[∆] program
is a function that maps every input instance I to a probability distribution over ΩG (I). We now make this precise. Let G be a GDatalog[∆] program, let I be an
input for G. Again, we first consider the case where an
input instance I only has finite possible outcomes (i.e.,
ΩG (I) = Ωfin
G (I)). Observe that, when all possible outcomes of I are finite, the set ΩG (I) is countable, since
we assume that all of our numerical distributions are
discrete. In this case, we can define a discrete probability distribution over the possible outcomes of I w.r.t. G.
We denote this probability distribution by PrG,I .
For a distributional fact f = Riδ (a1 , . . . , an , p), we
define the weight of f (notation: weight(f )) to be
δ(ai |p). For an ordinary (non-distributional) fact f ,
we set weight(f ) = 1. For a finite set F of facts, we
denote by P(F ) the product of the weights of all the
facts in F .
Y
def
P(F ) =
weight(f )

• A special edge (R, i) →∗ (S, j) whenever there is a
rule of the form
S(t1 , . . . , tj−1 , δ[p], tj+1 , . . . , tn ) ← ϕ(x)
and an exported variable at position (R, i) in ϕ(x).
By an exported variable, we mean a variable that
appears in both the premise and the conclusion.
We say that G is weakly acyclic if no cycle in the
dependency graph of G contains a special edge.

f ∈F

The probability assigned to a possible outcome J ∈
Ωfin
P (I), denoted PrG,I (J), is simply P(J). If a possible outcome J does not contain any distributional facts,
then PrG,I (J) = 1 by definition.

Theorem 3.6. If a GDatalog[∆] program G is weakly
acyclic, then ΩG (I) = Ωfin
G (I) for all input instances I.

6

4. CHASING GENERATIVE PROGRAMS

Example 3.7. (continued) Let J be the instance
that consists of all of the relations in Figures 3 and 4.
Then J is a possible outcome of I w.r.t. G. For convenience, in the case of distributional relation symbols, we have added the weight of each fact to the
corresponding row as the rightmost attribute. This
weight is not part of our model (since it can be inferred from the rest of the attributes). For presentation’s sake, the sampled values are under the attribute
name draw (while attribute names are again external
to our formal model). PrG,I (J) is the product of all
of the numbers in the columns titled “w(f ),” that is,
0.01 × 0.99 × 0.03 × · · · × 0.4.

The chase [3,28] is a classic technique used for reasoning about tuple-generating dependencies and equalitygenerating dependencies. In the special case of full
tuple-generating dependencies, which are syntactically
isomorphic to Datalog rules, the chase is closely related
to (a tuple-at-a-time version of) the naive bottom-up
evaluation strategy for Datalog program (cf. [2]). In
this section, we present a suitable variant of the chase
for generative Datalog programs, and analyze some of
its properties. The goal of that is twofold. First, as we
will show, the chase provides an intuitive executional
counterpart of the declarative semantics in Section 3.
Second, we use the chase to prove Theorems 3.8 and 3.9.
We note that, although the notions and results could
arguably be phrased in terms of a probabilisitic extension of bottom-up Datalog evaluation strategy, the fact
that a GDatalog[∆] rule can create new values makes it
more convenient to phrase them in terms of a suitable
adaptation of the chase procedure.
To simplify the notation in this section, we fix
a GDatalog[∆] program G = (E, I, Θ). Let Gb =
(E, I ∆ , Θ∆ ) be the associated Datalog∃ program.
We define the notions of chase step and chase tree.

The following theorem states that PrG,I is indeed a
probability space over all the possible outcomes.
Theorem 3.8. Let G be a GDatalog[∆] program, and
I an input instance for G, such that ΩG (I) = Ωfin
G (I).
Then PrG,I is a discrete probability function over ΩG (I).
We prove Theorem 3.8 in Section 4. In Section 5 we
consider the general case, and in particular the generalization of Theorem 3.8, where not all possible outcomes
are guaranteed to be finite. There, if one considers only
the (countable set of all) finite possible outcomes, then
the sum of probabilities is not necessarily one. But still:

Chase step. Consider an instance J, a rule τ ∈ Θ∆
of the form ψ(x) ← ϕ(x), and a tuple a such that ϕ(a)
is satisfied in J but ψ(a) is not satisfied in J. If ψ(x) is
a distributional atom of the form ∃yRiδ (t, y, t′ , p), then
ψ being “not satisfied” is interpreted in the logical sense
(regardless of probabilities): there is no y such that the
tuple (t, y, t′ , p) is in Riδ . In that case, let J be the set
of all instances Jb obtained by extending J with ψ(a)
for a specific value b of the existential variable y, such
that δ(b|p) > 0. Furthermore, let π be the discrete
probability distribution over J that assigns to Jb the
probability mass δ(b|p). If ψ(x) is an ordinary atom
without existential quantifiers, J is simply defined as
{J ′ }, where J ′ extends J with the facts in ψ(a), and
π(J ′ ) = 1. Then, we say that

Theorem 3.9. Let G be a GDatalog[∆] program, and
I an input for G. Then ΣJ∈Ωfin
PrG,I (J) ≤ 1.
G (I)
We conclude this section with some comments. First,
we note that the restriction of a conclusion of a rule to
include a single ∆-term significantly simplifies the presentation, but does not reduce the expressive power. In
particular, we could simulate multiple ∆-terms in the
conclusion using a collection of predicates and rules.
For example, if one wishes to have conclusion where a
person gets both a random height and a random weight
(possibly with shared parameters), then she can do so
by deriving PersonHeight(p, h) and PersonWeight(p, w)
separately, and using the rule PersonHW(p, h, w) ←
PersonHeight(p, h), PersonWeight(p, w). We also highlight the fact that our framework can easily simulate
the probabilistic database model of independent tuples [41] with probabilities mentioned in the database,
using the Flip distribution, as follows. Suppose that
we have the EDB relation R(x, p) where p represents
the probability of every tuple. Then we can obtain
the corresponding probabilistic relation R′ using the
rules S(x, Flip[p]) ← R(x, p) and R′ (x) ← S(x, 1).
Finally, we note that a disjunctive Datalog rule [16],
where the conclusion can be a disjunction of atoms, can
be simulated by our model (with probabilities ignored):
If the conclusion has n disjuncts, then we construct a
distributional rule with a probability distribution over
{1, . . . , n}, and additional n deterministic rules corresponding to the atoms.

τ (a)

J −−−→ (J , π)
is a valid chase step.
Chase tree. Let I be an input instance for G. A
chase tree for I w.r.t. G is a possibly infinite tree, whose
nodes are labeled by instances over E ∪I and where each
edge is labeled by a real number r ∈ [0, 1] such that
1. The root is labeled by I;
2. For each non-leaf node labeled J, if J is the set of
labels of the children of the node, and if π is the
map assigning to each J ′ ∈ J the label of the edge
τ (a)

from J to J ′ , then J −−−→ (J , π) is a valid chase
step for some rule τ ∈ Θ∆ and tuple a.
3. For each leaf node labeled J, there does not ex7

τ (a)

5. INFINITE POSSIBLE OUTCOMES

ist a valid chase step of the form J −−−→ (J , π).
In other words, the tree cannot be extended to a
larger chase tree.
We denote by L(v) the label (instance) of the node v.
Each instance L(v) of a node of v of a chase tree is said
to be an intermediate instance w.r.t. that chase tree.
A chase tree is said to be injective if no intermediate
instance is the label of more than one node; that is, for
v1 6= v2 we have L(v1 ) 6= L(v2 ). As we will see shortly,
due to the specific construction of Θ∆ , every chase tree
turns out to be injective.

In the general case of a GDatalog[∆] program, possible oucomes may be infinite, and moreover, the space
of possible outcomes may be uncountable.
Example 5.1. We now discuss examples that show
what would happen if we straightforwardly extended
our current definition of the probability PrG,I (J) of possible outcomes J to infinite possible outcomes (where,
in the case where J is infinite, PrG,I (J) would be the
limit of an infinite product of weights).
Consider the GDatalog[∆] program defined by the
rule R(y, δ[y]) ← R(x, y) where δ is a probability distribution with one parameter p and such that δ(z|p)
is equal to 1 if z = 2p and 0 otherwise. Then,
I = {R(0, 1)} has no finite possible outcome. In fact, I
has exactly one infinite possible outcome: {R(0, 1)} ∪
{R2δ (2i , 2i+1 , 2i ) | i ≥ 0} ∪ {R(2i , 2i+1 ) | i ≥ 0}.
Now consider the previous program extended with
the rule R(0, Flip[0.5]) ← Q(x), and consider the input instance I ′ = {Q(0)}. Then, I ′ has one finite possible outcome J = {Q(0), R(0, 0), R2Flip(0, 0, 0.5)} with
PrG,I ′ (J) = 0.5, and another infinite possible outcome
J ′ = {R(0, 1), R2Flip(0, 1, 0.5)} ∪ {R2δ (2i , 2i+1 , 2i ) | i ≥
0} ∪ {R(2i , 2i+1 ) | i ≥ 0} with PrG,I ′ (J ′ ) = 0.5.
Next, consider the GDatalog[∆] program defined by
R(y, δ ′ [y]) ← R(x, y), where δ ′ is a probability distribution with one parameter p, and δ ′ (z|p) is equal to
0.5 if z ∈ {2p, 2p + 1} and 0 otherwise. Then, for
I = {R(0, 1)}, every possible outcome is infinite, and
would have the probability 0.
Now consider the previous program extended with
the rule R(0, Flip[0.5]) ← Q(x), and consider again
the input instance I ′ = {Q(0)}. Then I ′ would have
exactly one possible outcome J with PrG,I ′ (J) > 0,
′
namely J = {Q(0), R(0, 0), R2Flip(0, 0, .5), R2δ (0, 0, 0)}
where PrG,I ′ (J) = 0.25.

Properties of the chase. We now state some properties of our chase procedure.
Proposition 4.1. Let I be any input instance, and
consider any chase tree for I w.r.t. G. Then every intermediate instance satisfies all functional dependencies
associated to distributional relations.
Proposition 4.2. Every chase tree w.r.t. G is injective.
We denote by leaves(T ) the set of leaves of a
chase tree T , and we denote by L(leaves(T )) the set
{L(v) | v ∈ leaves(T )}.
Theorem 4.3. Let T be a chase tree for an input
instance I w.r.t. G. The following hold.
1. Every intermediate instance is a subset of some
possible outcome in ΩG (I).
2. If T does not have infinite directed paths, then
L(leaves(T )) = Ωfin
G (I).
This theorem is a special case of a more general result,
Theorem 5.3, which we prove later.

4.1 Proof of Theorems 3.8 and 3.9
By construction, for every node of a chase tree T ,
the weights of the edges that emanate from the node in
question sum up to one. We can associate to each intermediate instance L(v) a weight, namely the product
of the edge labels on the path from the root to v. This
weight is well defined, since T is injective. We can then
consider a random walk over the tree, where the probabilities are given by the edge labels. Then, for a node v,
the weight of L(v) is equal to the probability of visiting
v in this random world. From Theorem 4.3 we conclude
that, if all the possible outcomes are finite, then T does
not have any infinite paths, and moreover, the random
walk defines a probability distribution over the labels
of the leaves, which are the possible outcomes. This is
precisely the probability distribution of Theorem 3.8.
Moreover, in the general case, ΣJ∈Ωfin
PrG,I (J) is the
G (I)
probability that the random walk terminates (at a leaf),
and hence, Theorem 3.9 follows from the fact that this
probability (as is any probability) is a number between
zero and one.

5.1 Generalization of Probabilistic Semantics
To generalize our framework, we need to consider
probability spaces over uncountable domains; those are
defined by means of measure spaces, which are defined
as follows.
Let Ω be a set. A σ-algebra over Ω is a collection F of
subsets of Ω, such that F contains Ω and is closed under complement and countable unions. (Implied properties include that F contains the empty set, and that
F is closed under countable intersections.) If F ′ is a
nonempty collection of subsets of Ω, then the closure
of F ′ under complement and countable unions is a σalgebra, and it is said to be generated by F ′ .
A probability measure space is a triple (Ω, F , π),
where: (1) Ω is a set, called the sample space, (2)
F is a σ-algebra over Ω, and (3) π : F → [0, 1],
called a probability
P measure, is such that π(Ω) = 1,
and π(∪E) =
e∈E π(e) for every countable set E of
pairwise-disjoint measurable sets.
8

Let G be a GDatalog[∆] program, let I be an input for
G, and let T be a chase tree. We denote by paths(T ) the
set of all the maximal paths of T . (Note that paths(T )
may be uncountably infinite.) For P ∈ paths(T ), we
denote by ∪P the union of the (chain of) labels L(v)
along P . The following generalizes Theorem 4.3.

Let G be a GDatalog[∆] program, and let I be an
input for G. We say that a sequence f = (f1 , . . . , fn ) of
facts is a derivation (w.r.t. I) if for all i = 1, . . . , n, the
fact fi is the result of applying some rule of G that is
not satisfied in I ∪{f1 , . . . , fi−1 } (in the case of applying
a rule with a ∆-atom in the head, choosing a value
randomly). If f1 , . . . , fn is a derivation, then the set
{f1 , . . . , fn } is a derivation set. Hence, a finite set F
of facts is a derivation set if and only if I ∪ F is an
intermediate instance in some chase tree.
Let G be a GDatalog[∆] program, let I be an input
⊆
for G, and let F be a set of facts. We denote by ΩF
G (I)
the set of all the possible outcomes J ⊆ ΩG (I) such that
F ⊆ J. The following theorem states how we determine
the measure space defined by a GDatalog[∆] program.

Theorem 5.3. Let G be a GDatalog[∆] program, I
an input for G, and T a fair chase tree. The mapping
P → ∪P is a bijection between paths(T ) and ΩG (I).

5.3 Chase Measures
Let G be a GDatalog[∆] program, let I be an input
for G, and let T be a chase tree. Our goal is to define
a probability measure over ΩG (I). Given Theorem 5.3,
we can do that by defining a probability measure over
paths(T ). A random path in paths(T ) can be viewed
as a Markov chain that is defined by a random walk
over T , starting from the root. A measure space for
such a Markov chain is defined by means of cylinderification [6]. Let v be a node of T . The v-cylinder of T ,
denoted CvT , is the subset of paths(T ) that consists of all
the maximal paths that contain v. A cylinder of T is a
subset of paths(T ) that forms a v-cylinder for some node
v. We denote by C(T ) the set of all the cylinders of T .
Recall that L(v) is a finite set of facts, and observe
that P(L(v)) is the product of the weights along the
path from the root to v. The following theorem is a
special case of a classic result on Markov chains (cf. [6]).

Theorem 5.2. Let G be a GDatalog[∆] program, and
let I be an input for G. There exists a unique probability
measure space (Ω, F , π), denoted µG,I , that satisfies all
of the following.
(i) Ω = ΩG (I);
(ii) The σ-algebra (Ω, F ) is generated from the sets of
⊆
the form ΩF
G (I) where F is finite;
⊆
(iii) π(ΩF
G (I)) = P(F ) for every derivation set F .
Moreover, if J is a finite possible outcome, then π({J})
is equal to P(F ).

Observe that the items (i) and (ii) of Theorem 5.2
describe the unique properties of the probability measure space. The proof will be given in the next section.
The last part of the theorem states that our discrete and
continuous probability definitions coincide on finite possible outcomes; this is a simple consequence of item (ii),
since for a finite possible outcome J, the set F = J \ I
⊆
is such that ΩF
G (I) = {J}, and F is itself a derivation
set (e.g., due to Theorem 4.3).

Theorem 5.4. Let G be a GDatalog[∆] program, let
I be an input for G, and let T be a chase tree. There exists a unique probability measure (Ω, F , π) that satisfies
all of the following.
1. Ω = paths(T ).
2. (Ω, F ) is the σ-algebra generated from C(T ).

5.2 Measure Spaces by Infinite Chase

3. π(CvT ) = P(L(v)) for all nodes v of T .

We prove Theorem 5.2 by defining and investigating
measure spaces that are defined in terms of the chase.
Consider a GDatalog[∆] program G and an input I for
G. A maximal path of a chase tree T is a path P that
starts with the root, and either ends in a leaf or is infinite. Observe that the labels (instances) along a maximal path form a chain (w.r.t. the set-containment partial order). A maximal path P of a chase tree is fair if
whenever the premise of a rule is satisfied by some tuple
in some intermediate instance on P , then the conclusion
of the rule is satisfied for the same tuple in some intermediate instance on P . A chase tree T is fair (or has the
fairness property) if every maximal path is fair. Note
that every finite chase tree is fair. We will restrict attention to fair chase trees. Fairness is a classic notion in
the study of infinite computations; moreover, fair chase
trees can easily be constructed, for examples, by maintaining a queue of “active rule firings” (cf. any textbook
on term rewriting systems or lambda calculus).

Theorems 5.3 and 5.4 suggest the following definition.
Definition 5.5 (Chase Probability Measure).
Let G be a GDatalog[∆] program, let I be an input
for G, let T be a chase tree, and let (Ω, F , π) be the
probability measure of Theorem 5.4. The probability
measure µT over ΩG (I) is the one obtained from
(Ω, F , µ) by replacing every maximal path P with the
possible outcome ∪P .
Next, we prove that the probability measure space
represented by a chase tree is independent of the specific
chase tree of choice. For that, we need some notation
and a lemma. Let G be a GDatalog[∆] program, let I
be an input for G, let T be a chase tree, and let v be a
node of T . We denote by ∪CvT the set {∪P | P ∈ CvT }.
The following lemma is a consequence of Proposition 4.1
and Theorem 5.3.
9

Lemma 5.6. Let G be a GDatalog[∆] program, let I
be an input for G, and let T be a fair chase tree. Let v
⊆
be a node of T and F = L(v). Then ∪CvT = ΩF
G (I);
that is, ∪CvT is the set {J ∈ ΩG (I) | L(v) ⊆ J}.

To complete our framework, we define probabilisticprogramming Datalog, PPDL for short, wherein a program augments a generative Datalog program with constraints; these constraints unify the traditional integrity
constraints of databases and the traditional observations of probabilistic programming.

Using Lemma 5.6 we can prove the following theorem.

Definition 6.1 (PPDL[∆]). Let ∆ be a finite set
of parametrized numerical distributions. A PPDL[∆]
program is a quadruple (E, I, Θ, Φ), where (E, I, Θ) is
a GDatalog[∆] program and Φ is a finite set of logical
constraints over E ∪ I.1

Theorem 5.7. Let G be a GDatalog[∆] program, let
I be an input for G, and let T and T ′ be two fair chase
trees. Then µT = µT ′ .

5.4 Proof of Theorem 5.2
We can now prove Theorem 5.2. Let G be a
GDatalog[∆] program, let I be an input for G, and
let T be a fair chase tree for I w.r.t. G. Let µT =
(ΩG (I), FT , πT ) be the probability measure on ΩG (I)
associated to T , as defined in Definition 5.5.

Example 6.2. Consider again Example 3.2. Suppose that we have the EDB relations ReportHAlarm
and ReportBAlarm that represent reported home and
business alarms, respectively. We obtain from the program in the example a PPDL[∆]-program by adding the
following constraints.
1. ReportHAlarm(h) → Alarm(h)

Lemma 5.8. The σ-algebra (ΩG (I), FT ) is generated
⊆
by the sets of the form ΩF
G (I), where F is finite.

2. ReportBAlarm(b) → Alarm(b)
Note that we use right (in contrast to left) arrows to
distinguish constraints from ordinary Datalog rules.

Proof. Let (ΩG (I), F ) be the σ-algebra generated
⊆
F⊆
from the sets ΩF
G (I). We will show that every ΩG (I)
is in FT , and that every ∪CvT is in F . The second claim
is due to Lemma 5.6, so we will prove the first. So, let
⊆
F⊆
ΩF
G (I) be given. Due to Lemma 5.6, the set ΩG (I) is
T
the countable union ∪u∈U (∪Cu ) where U is the set of all
⊆
the nodes u such that F ⊆ u. Hence, ΩF
G (I) ∈ FT .

The semantics of a PPDL[∆] program is the posterior
distribution over the corresponding GDatalog[∆] program, conditioned on the satisfaction of the constraint.
A formal definition follows.
Let P = (E, I, Θ, Φ) be a PPDL[∆] program, and
let G be the GDatalog[∆] program (E, I, Θ). An input
instance for P is an input instance I for G. We say that
I is a legal input instance for P if {J ∈ ΩG (I) | J |= Φ}
is a measurable set in the probability space µG,I , and
moreover, its measure is nonzero. Intuitively, an input
instance I is legal if it is consistent with the observations
(i.e., with the conjunction of the constraints in Φ), given
G. The semantics of a PPDL[∆] program is defined as
follows.

Lemma 5.9. For every derivation set F we have
⊆
πT (ΩF
G (I)) = P(F ).
Proof. Let F be a derivation set. Due to Theorem 5.7, it suffices to prove that for some chase tree T ′
⊆
it is the case that πT ′ (ΩF
G (I)) = P(F ). But since F is
a derivation set, we can craft a chase tree T ′ that has a
⊆
node v with L(v) = F . Then we have that πT ′ (ΩF
G (I))
is the product of the weights along the path to v, which
is exactly P(F ).

Definition 6.3. Let P = (E, I, Θ, Φ) be a PPDL[∆]
program, and let G be the GDatalog[∆] program
(E, I, Θ). Let I be a legal input instance for P, and let
µG,I = (ΩG (I), FG , πG ). The probability space defined
by P and I, denoted µP,I , is the triple (ΩP (I), FP , πP )
where:
• ΩP (I) = {J ∈ ΩG (I) | J |= Φ}

Lemma 5.10. Let µ = (Ω, F , π) be any probability
space that satisfies (i)–(iii) of Theorem 5.2. Then
µ = µT .
Proof. Let µT = (ΩG (I), FT , πT ).
Due to
Lemma 5.8, we have that F = FT . So it is left to
prove that π = πT . Due to Lemmas 5.9 and 5.6, we
have that π agrees with πT on the cylinder sets of T .
Due to Theorems 5.3 and 5.4 we get that π must be
equal to πT due to the uniqueness of πT .

• FP = {S ∩ ΩP (I) | S ∈ FG }
• πP (S) = πG (S)/πG (ΩP (I)) for every S ∈ FP .
In other words, µP,I is µG,I conditioned on Φ.

The above lemmas show that µT = (ΩG (I), FT , πT ) is
a probability measure space that satisfies (i) and (ii) of
Theorem 5.2, and moreover, that no other probability
measure space satisfies (i) and (ii).

6.

Example 6.4. Continuing Example 6.2, the semantics of this program is the posterior probability distribution for the prior of Example 3.2, under the conditions that the alarm is on whenever it is reported.
1

The restriction of the language of constraints to a fragment
with tractability (or other goodness) properties is beyond
the scope of this paper.

PROBABILISTIC-PROGRAMMING
DATALOG
10

Then, one can ask various queries over the probability
space defined, for example, the probability of the fact
Earthquake(Napa, 1). Observe that, with negation, we
could also phrase the condition that an alarm is off unless reported.

that provides, for every English word wc , a distribution
over the possible misspelled words we ; hence, the fact
Cor(wc , we , q) means that wc is misspelled into we with
probability q. In our notation, this distribution will be
captured by the notation CatCor h2, 3; 1i(we ; wc ). Hence,
the following program contains, for each document, the
set of words that the document can contain by replacing
each word with a corresponding correction. The relation Doc(d, i, w) denotes that document d has the word
w as its ith token. The relation CDoc is the same as
Doc, except that each word is replaced with a random
correction.

We note that a traditional integrity constraint on the
input (e.g., there are no x, c1 and c2 such that both
Home(x, c1 ) and Business(x, c2 ) hold) can be viewed as
a constraint in Φ that holds with either probability 0
(and then the input is illegal) or with probability 1 (and
then the prior µG,I is the same as the posterior µP,I ).
An important direction for future work is to establish
tractable conditions that guarantee that a given input
is legal. Also, an interesting problem is to detect conditions under which the chase is a self conjugate [39],
that is, the probability space µP,I is captured by a chase
procedure without backtracking.

7.

CDoc(d, i, CatCor h2, 3; 1i(wc ; w)) ← Doc(d, i; w) (4)
The above specification for the categorical distribution is similar to the repair-key operation of the worldset algebra [4, 5]. In the general case, we define an Rdistribution to be one of the form δ R hd; gi(x; q), where
R is a relation symbol, d is a tuple of attributes of
R, representing the dynamic parameters (i.e., separate
parameters for every row), g is a tuple of grouping attributes, and q has the same length as g. We could also
add a tuple p of static parameters (i.e., ones that are
shared by all the tuples in the group).
Extending our semantics to support a program such
as (4) is straightforward, since the relation Cor that defines the distribution is an EDB relation. The only difference from our previous definitions is that, now, the
probability of a distributional fact is determined not
only by the fact itself, but also by the content of the
relation to which the fact refers to (e.g., Cor). When
the relation R that is used for defining the distribution
is an IDB, we need to be careful with the definition
of the chase, since when we wish to sample from an
R-distribution, it may be the case that some of the relevant facts of R have not been produced yet. We may
even be in a cyclic situation where the facts of R are
determined by facts derived (indirectly) from facts that
are produced using R-distributions. We plan to devise
a (testable) acyclicity condition that avoids such cycles, and then restrict the chase to behave accordingly;
R-distributions are sampled from only after R is complete. Of course, it would be interesting to explore the
semantics of programs without the acyclicity property.

EXTENSIONS AND FUTURE WORK

Our ultimate goal is to design a language for probabilistic programming that possesses the inherent declarative and logical nature of Datalog. To that end, extensions are required. In this section we discuss some of the
important future directions and challenges to pursue.
We focus on the semantic aspects of expressive power.
(An obvious aspect for future work is a practical implementation, e.g., corresponding sampling techniques.)

7.1 Unbounded Number of Parameters
It is often the case that the probability distributions
have a large number of parameters. A simple example
is the categorical distribution where a single member
of a finite domain of items is to be selected, each item
with its own probability. In that case, the domain can
be very large, and moreover, it can be determined dynamically from the database content and be unknown
to the static program. To support such distributions,
one can associate the distribution with a relation symbol in a schema, and here we illustrate it for the case of
a categorical distribution.
Let R be a relation symbol. A categorical distribution over R is associated with two attributes i and j
of R that determine dynamic parameters: i represents
a possible value, and j represents its probability. In
addition, the distribution is associated with a tuple g
of attributes of R that split R into groups with the semantics of SQL’s GROUP BY. We denote this distribution by CatR hi, j; gi(x; q), where g and q have the same
length. Given a relation RI over R and parameters q,
let RgI be the sub-relation of RI that have the values in
the attributes vector g are equal to q. Suppose that the
facts of RqI are f1 , . . . , fn . We assume that
Pn fk [j] ∈ [0, 1]
for all k = 1, . . . , n, and moreover, that k=1 fk [j] = 1.
Then we define CatR hi, j|gi(x|q) = s, where s is the
sum of fk [j] over all k ∈ {1, . . . , n} with fk [i] = x.
As an example, consider the relation Cor(wc , we , q)

7.2 Multivariate Distributions
A natural and important extension is to support multivariate distributions, which are distributions with a
support in Rk for k > 1. Examples of popular such distributions are multinomial, Dirichlet, and multivariate
Gaussian distribution. When k is fixed, one can replace
our single distributional term with multiple such terms.
But when k is unbounded, such a distribution should
be supported as an aggregate operation that implies in
a set of facts (rather than a single one).

7.3 Continuous Distributions
11

Acknowledgments

A natural extension of our framework is the support
of continuous probability distributions (e.g., continuous uniform, Pareto, Gaussian, Dirichlet, etc.). This is
a very important extension, as such distributions are
highly popular in defining statistical models. Syntactically, this extension is straightforward: we just need
to include these distributions in ∆. Likewise, extending
the probabilistic chase is also straightforward.
The challenge, though, is with the semantic analysis,
and in particular, with the definition of the probability
space implied by the chase. When a chase step involves
a continuous numeric distribution, such as U (0, 1) (the
uniform distribution between 0 and 1), then no chase
step is measurable, and hence, we can no longer talk
about the probability of a step or the probability of
a cylinder set (but we can talk about the density of
those). Note that our definition of the measure space
in Section 5 is inherently based on the assumption that
the set of possible outcomes that contains a given finite
set of facts is measurable. But to support continuous
distribution, the definition of measurable sets will need
to be based on sets of paths. We refer this to future
work, and we believe that our current framework will
naturally extend to continuous distributions.

8.

We are thankful to Molham Aref, Todd J. Green and
Emir Pasalic for insightful discussions and feedback on
this work. We also thank Michael Benedikt, Georg
Gottlob and Yannis Kassios for providing useful comments and suggestions. Finally, we are grateful to Kathleen Fisher and Suresh Jagannathan for including us in
DARPA’s PPAML initiative; this work came from our
efforts to design a principled approach to translating
probabilistic programs into statistical solvers.

9. REFERENCES
[1] S. Abiteboul, D. Deutch, and V. Vianu.
Deduction with contradictions in Datalog. In
ICDT, pages 143–154, 2014.
[2] S. Abiteboul, R. Hull, and V. Vianu. Foundations
of Databases. 1995.
[3] A. V. Aho, C. Beeri, and J. D. Ullman. The
theory of joins in relational databases. ACM
Trans. on Datab. Syst., (3):297–314, 1979.
[4] L. Antova, C. Koch, and D. Olteanu. From
complete to incomplete information and back. In
SIGMOD, pages 713–724, 2007.
[5] L. Antova, C. Koch, and D. Olteanu. Query
language support for incomplete information in
the MayBMS system. In VLDB, pages 1422–1425,
2007.
[6] R. B. Ash and C. Doleans-Dade. Probability &
Measure Theory. Harcourt Academic Press, 2000.
[7] C. Baral, M. Gelfond, and N. Rushton.
Probabilistic reasoning with answer sets. Theory
Pract. Log. Program., 9(1):57–144, 2009.
[8] M. Benedikt, E. Kharlamov, D. Olteanu, and
P. Senellart. Probabilistic XML via markov
chains. PVLDB, 3(1):770–781, 2010.
[9] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent
dirichlet allocation. J. of Machine Learning
Research, 3:993–1022, 2003.
[10] M. Bröcheler, L. Mihalkova, and L. Getoor.
Probabilistic similarity logic. In UAI, pages
73–82, 2010.
[11] Z. Cai, Z. Vagena, L. L. Perez, S. Arumugam,
P. J. Haas, and C. M. Jermaine. Simulation of
database-valued Markov chains using SimSQL. In
SIGMOD, pages 637–648, 2013.
[12] A. Calı̀, G. Gottlob, T. Lukasiewicz, B. Marnette,
and A. Pieris. Datalog+/-: A family of logical
knowledge representation and query languages for
new applications. In LICS, pages 228–242, 2010.
[13] S. Cohen and B. Kimelfeld. Querying parse trees
of stochastic context-free grammars. In Database
Theory - ICDT 2010, 13th International
Conference, Lausanne, Switzerland, March 23-25,
2010, Proceedings, ACM International Conference
Proceeding Series, pages 62–75. ACM, 2010.
[14] D. Deutch, C. Koch, and T. Milo. On

CONCLUDING REMARKS

We proposed and investigated a declarative framework for specifying statistical models in the context of
a database, based on an extension of Datalog with numerical distributions. The framework differs from traditional probabilistic programming languages not only
due to the tight integration with a database, but also
because of its fully declarative rule-based language:
the interpretation of a program is independent under
transformations (such as reordering or duplication of
rules) that preserve the first-order semantics. This was
achieved by treating a GDatalog[∆] program as a Datalog program with existentially quantified variables in
the conclusion, and using the minimal solutions as the
sample space of a (discrete or continuous) probability
distribution. Using a suitable notion of chase that we
introduced, we established that the resulting probability distributions are well-defined and robust.
This work is done as part of the effort to extend
the LogicBlox database [23], and its Datalog-based
data management language LogiQL [24], to support
the specification of statistical models. Through its
purely declarative rule-based syntax, such an extension
of LogiQL allows for natural specifications of statistical models. Moreover, there is a rich literature on (extensions of) Datalog, and we expect that, through our
framework, techniques and insights from this active research area can be put to use to advance the state of
the art in probabilistic programming.
12

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]
[25]

[26]

[27]

[28]

[29]

probabilistic fixpoint and Markov chain query
languages. In PODS, pages 215–226, 2010.
P. Domingos and D. Lowd. Markov Logic: An
Interface Layer for Artificial Intelligence.
Synthesis Lectures on AI and Machine Learning.
Morgan & Claypool Publishers, 2009.
T. Eiter, G. Gottlob, and H. Mannila. Disjunctive
datalog. ACM Trans. Database Syst.,
22(3):364–418, 1997.
K. Etessami and M. Yannakakis. Recursive
markov chains, stochastic grammars, and
monotone systems of nonlinear equations. J.
ACM, 56(1), 2009.
R. Fagin, P. G. Kolaitis, R. J. Miller, and
L. Popa. Data exchange: Semantics and query
answering. In ICDT, volume 2572 of LNCS, pages
207–224. Springer, 2003.
N. Fuhr. Probabilistic datalog: Implementing
logical information retrieval for advanced
applications. JASIS, 51(2):95–110, 2000.
A. Fuxman, P. G. Kolaitis, R. J. Miller, and
W. C. Tan. Peer data exchange. ACM Trans.
Datab. Syst., 31(4):1454–1498, 2006.
N. D. Goodman. The principles and practice of
probabilistic programming. In POPL, pages
399–402, 2013.
G. Gottlob, T. Lukasiewicz, M. Martinez, and
G. Simari. Query answering under probabilistic
uncertainty in Datalog+/ ontologies. Annals of
Math.& AI, 69(1):37–72, 2013.
T. J. Green, M. Aref, and G. Karvounarakis.
LogicBlox, platform and language: A tutorial. In
Int Conf on Datalog in Academia and Industry,
pages 1–8, 2012.
T. Halpin and S. Rugaber. LogiQL: A Query
Language for Smart Databases. CRC Press, 2014.
R. Jampani, F. Xu, M. Wu, L. L. Perez, C. M.
Jermaine, and P. J. Haas. MCDB: a monte carlo
approach to managing uncertain data. In
SIGMOD, pages 687–700, 2008.
B. Kimelfeld and P. Senellart. Probabilistic XML:
models and complexity. In Advances in
Probabilistic Databases for Uncertain Information
Management, volume 304 of Studies in Fuzziness
and Soft Computing, pages 39–66. 2013.
A. Kimmig, B. Demoen, L. De Raedt,
V. Santos Costa, and R. Rocha. On the
implementation of the probabilistic logic
programming language ProbLog. Theory and
Practice of Logic Programming, 11:235–262, 2011.
D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing
implications of data dependencies. ACM Trans.
on Datab. Syst., (4):455–469, 1979.
V. K. Mansinghka, D. Selsam, and Y. N. Perov.
Venture: a higher-order probabilistic
programming platform with programmable
inference. CoRR, abs/1404.0099, 2014.

[30] A. K. McCallum. Multi-label text classification
with a mixture model trained by EM. 1999.
[31] B. Milch and et al. BLOG: Probabilistic models
with unknown objects. In IJCAI, pages
1352–1359, 2005.
[32] K. Nigam, A. McCallum, S. Thrun, and T. M.
Mitchell. Text classification from labeled and
unlabeled documents using EM. Machine
Learning, pages 103–134, 2000.
[33] F. Niu, C. Ré, A. Doan, and J. W. Shavlik. Tuffy:
Scaling up statistical inference in markov logic
networks using an RDBMS. PVLDB,
4(6):373–384, 2011.
[34] F. Niu, C. Zhang, C. Re, and J. W. Shavlik.
DeepDive: Web-scale knowledge-base construction
using statistical learning and inference. In
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,
pages 25–28. CEUR-WS.org, 2012.
[35] A. V. Nori, C. Hur, S. K. Rajamani, and
S. Samuel. R2: an efficient MCMC sampler for
probabilistic programs. In AAAI, pages
2476–2482, 2014.
[36] J. Pearl. Probabilistic reasoning in intelligent
systems - networks of plausible inference. Morgan
Kaufmann, 1989.
[37] A. Pfeffer. Figaro: An object-oriented
probabilistic programming language. Technical
report, Charles River Analytics, 2009.
[38] D. Poole. The independent choice logic and
beyond. In Probabilistic Inductive Logic
Programming - Theory and Applications, pages
222–243, 2008.
[39] H. Raiffa and R. Schlaifer. Applied Statistical
Decision Theory. Harvard University Press,
Harvard, 1961.
[40] T. Sato and Y. Kameya. PRISM: A language for
symbolic-statistical modeling. In IJCAI, pages
1330–1339, 1997.
[41] D. Suciu, D. Olteanu, C. Ré, and C. Koch.
Probabilistic Databases. Synthesis Lectures on
Data Management. Morgan & Claypool
Publishers, 2011.
[42] J. Widom. Trio: a system for data, uncertainty,
and lineage. In C. Aggarwal, editor, Managing
and Mining Uncertain Data, chapter 5.
Springer-Verlag, 2008.
[43] www.probabilistic-programming.org. Repository
on probabilistic programming languages, 2014.

APPENDIX
A. ADDITIONAL PROOFS
A.1 Proof of Theorem 3.6
13

Theorem 3.6.If a GDatalog[∆] program G is weakly
acyclic, then ΩG (I) = Ωfin
G (I) for all input instances I.

Proof. We first prove that every ∪P is in ΩG (I).
Let P ∈ paths(T ) be given. We need to show that
∪P ∈ ΩG (I). By definition it is the case that every
distributional fact of ∪P has a nonzero probability. It
is also clear that ∪P is consistent, due to the fairness
property of T . Hence, it suffices to prove that ∪P is a
minimal solution, that is, no proper subset of ∪P is a
solution. So, let K be a strict subset of ∪P and suppose,
by way of contraction, that K is also a solution. Let
(J, J ′ ) be the first edge in P such that ∪P contains a
fact that is not in K. Now, consider the chase step that
leads from J to J ′ . Let f be the unique fact in J ′ \ J.
Then J ⊆ K and f ∈ J ′ \ K. The selected rule τ in
this step cannot be deterministic, or otherwise K must
contain f as well. Hence, it is a distributional rule, and
f has the form Riδ (a|p). But then, K satisfies this rule,
and hence, K must include a fact f ′ = Riδ (a′ |p), where
a′ differs from a only in the ith element. And since some
node in ∪P contains both f and f ′ , we get a violation
of the fd of Proposition 4.1. Hence, a contraction.
Next, we prove that every possible outcome J in
ΩG (I) is equal to ∪P for some P ∈ paths(T ). Let such
J be given. We build the path P inductively, as follows.
We start with the root, and upon every node v we select the next edge to be one that leads to a subset K
of J; note that K must exist since J resolves the rule
violated in L(v) by some fact, and that fact must be in
one of the children of v. Now, ∪P is consistent since T
is fair, and ∪P ⊆ J by construction. And since J is a
minimal solution, we get that ∪P is in fact equal to J.
Finally, we need to prove that if ∪P1 = ∪P2 then
P1 = P2 . We will prove the contrapositive statement.
Suppose that P1 , P2 ∈ paths(T ) are such that P1 6= P2 .
The two paths agree on the root. Let J be the first
node in the paths such that the two paths disagree on
the outgoing edge of J. Suppose that P1 has the edge
from J to J1 and P2 has an edge from J to J2 . Then
J1 ∪ J2 have a pair of facts that violate the functional
dependency of Proposition 4.1, and in particular, J1 6⊆
∪P2 . We conclude that ∪P1 = ∪P2 , as claimed.

Proof. It is easy to show that if G is weakly acyclic
in our sense, then Pb is weakly acyclic according to the
classic definition of weak ayclicity given in [18]. We then
apply the following result (restated here to match our
notation), which was established in [20]: if a Datalog∃
program D is weakly acyclic, then there is a polynomial
p(·) (depending only on D) such that for every input
instance I and for every solution J of I w.r.t. D, there is
a solution J ′ of I w.r.t. D with J ′ ⊆ J and |J ′ | ≤ p(|I|).
In particular, all J ∈ min-solD (I) are finite and have size
at most p(|I|).

A.2

Proof of Proposition 4.1

Proposition 4.1. Let I be any input instance, and
consider any chase tree for I w.r.t. G. Then every intermediate instance satisfies all functional dependencies
associated to distributional relations.
Proof. The proof proceeds by induction on the distance from the root of the chase tree. Suppose that in
τ (a)

a chase step J −−−→ (J , π), some J ′ ∈ J contains two
Riδ -facts that are identical except for the i-th attribute.
Then either J already contains both atoms, in which
case we can apply our induction hypothesis, or J ′ is
obtained by extending J with one of the two facts in
question, in which case, it is easy to see that the conclusion of τ was already satisfied for the tuple a, which
is not possible in case of a valid chase step.

A.3

Proof of Proposition 4.2

Proposition 4.2. Every chase tree w.r.t. G is injective.
Proof. For the sake of a contradiction, assume that
two nodes n1 and n2 in a chase tree are labeled by the
same instance J. Let n0 be the node that is the least
common ancestor of n1 and n2 in the tree, and let n′1
and n′2 be the children of n0 that are ancestors of n1 and
n2 , respectively. By construction, n′1 and n′2 are labeled
with distinct instances J1 6= J2 , respectively. Consider
the rule τ = ψ(x) ← ϕ(x) and tuple a constituting
the chase step applied at node n0 . Since n0 has more
than one child, ψ(x) must be a distributional atom, say
∃yRiδ (t, y, t′ , p). Then each Jk (k = 1, 2) contains an
Riδ -fact. Moreover, the two Riδ -facts in question differ in
the choice of value for the variable y, and are otherwise
identical. Due to the monotonic nature of the chase,
both atoms must belong J, and hence, J ′ violates the
functional dependency of Proposition 4.1. Hence, we
have reached a contradiction.

A.4

A.5 Proof of Theorem 5.7
Theorem 5.7. Let G be a GDatalog[∆] program, let
I be an input for G, and let T and T ′ be two fair chase
trees. Then µT = µT ′ .
Proof. Let µT = (Ω, F , π) and µT ′ = (Ω′ , F ′ , π ′ ).
We need to prove that Ω = Ω′ , F = F ′ and π = π ′ .
We have Ω = Ω′ due to Theorem 5.3. To prove that
F = F ′ , it suffices to prove that every ∪CvT is F ′ and
′
every ∪CvT′ is in F (since both σ-algebras are generated
by the cylinders). And due to symmetry, it suffices to
′
prove that CvT′ is in F . So, let v ′ be a node of T ′ . Recall
′
that L(v ) is a set of facts. Due to Lemma 5.6, we have
′
that ∪CvT′ is precisely the set of all possible outcomes
J in ΩG (I) such that L(v ′ ) ⊆ J. Let U be the set of
all the nodes of u of P with L(v ′ ) ⊆ L(u). Then, due

Proof of Theorem 5.3

Theorem 5.3. Let G be a GDatalog[∆] program, I
an input for G, and T a fair chase tree. The mapping
P → ∪P is a bijection between paths(T ) and ΩG (I).
14

′

to Theorem 5.3 we have that ∪CvT′ = ∪u∈U (∪CuT ). Observe that U is countable, since T has only a countable
number of nodes (as every node is identified by a finite
path from the root). Moreover, (Ω, F ) is a closed under
countable unions, and therefore, ∪u∈U (∪CuT ) is in F .
It remains to prove that π = π ′ . By now we know
that the σ-algebras (Ω, F ) and (Ω′ , F ′ ) are the same.
Due to Theorem 5.3, every measure space over (Ω, F )
can be translated into a measure space over the cylinder
algebra of T and T ′ . So, due to the uniqueness property
′
of Theorem 5.4, it suffices to prove that every ∪CvT′ has
′
the same probability in µT and µT ′ . That is, π(∪CvT′ ) =
′
′
P(L(v )). We do so next. We assume that v is not the
root of T ′ , or otherwise the claim is straightforward. Let
U be the set of all the nodes u in T with the property
that L(v ′ ) ⊆ L(u) but L(v ′ ) 6⊆ L(p) for the parent p of
u. Due to Lemma 5.6 we have the following:
X
′
π(∪CvT′ ) =
P(L(u))
(5)
u∈U

Let E be the set of all the edges (v1 , u1 ) of T , such
that L(u1 ) \ L(v1 ) consists of a node in v ′ . Let Q be
the set of all the paths from the root of T to nodes
in U . Due to Proposition 4.1, we have that every two
paths P1 and P2 in Q and edges (v1 , u1 ) and (v2 , u2 )
in P1 and P2 , respectively, if both edges are in E and
v1 = v2 , then u1 = u2 . Let T ′′ be the tree that is
obtained from T by considering every edge (v1 , u1 ) in
E, changing its weight to 1, and changing the weights
of remaining (v1 , u′1 ) emanating from v1 to 0. Then we
have the following for every node u ∈ U .
P(u) = wT ′′ (u) · P(L(v ′ ))

(6)

where wT ′′ (u) is the product of the weights along the
path from the root of T ′′ to u. Combining (5) and (6),
we get the following.
X
′
π(∪CvT′ ) = P(L(v ′ )) ·
wT ′′ (u)
P

u∈U

Let p = u∈U wT ′′ (u). We need to prove that p = 1.
Observe that p is the probability of visiting a node of
U in a random walk over T ′′ (with the probabilities
defined by the weights). Equivalently, p is the probability that random walk over T ′′ eventually sees all of
the facts in v ′ . But due to the construction of T ′′ , every rule violation that arises due to facts in both L(v ′ )
and any node of T ′′ is deterministically resolved exactly
as in L(v ′ ). Moreover, since L(v ′ ) is obtained from a
chase derivation (i.e., L(v ′ ) is a derivation set), solving
all such rules repeatedly results in the containment of
L(v ′ ). Finally, since T ′′ is fair (because T is fair), we
get that every random walk over T ′′ eventually sees all
of the facts in L(v ′ ). Hence, p = 1, as claimed.

15

