# Monads for Measurable Queries in Probabilistic Databases

Swaraj Dash Sam Staton University of Oxford
Oxford, United Kingdom<EMAIL_ADDRESS>
###### Abstract

We consider a bag (multiset) monad on the category of standard Borel spaces,
and show that it gives a free measurable commutative monoid. Firstly, we show
that a recent measurability result for probabilistic database queries (Grohe
and Lindner, ICDT 2020) follows quickly from the fact that queries can be
expressed in monad-based terms. We also extend this measurability result to a
fuller query language. Secondly, we discuss a distributive law between
probability and bag monads, and we illustrate that this is useful for
generating probabilistic databases.

##  1 Introduction

Probabilistic databases cater for uncertainty in data. There may be
uncertainty about whether rows should be in a database, or uncertainty about
what values certain attributes should have.

For example, consider a database of movies. We might have a table that assigns
the gross amount to each movie, which may be quite uncertain for older movies.
We might have a table that records which actors appeared in which movies, and
there may be uncertainty about whether a particular actor appeared in a given
movie. The uncertainty might come from incorrect text processing, for example
if the information was scraped off internet forums, or just noise in
measurement, e.g. if the gross amount is difficult to calculate precisely.
This is a simple example, but probabilistic databases have applications in
other areas of information extraction as well as in scientific data
management, medical records, and in data cleaning. See the textbook [29] for
further examples.

In this paper, we argue that the semantics of probabilistic databases lies in
combining a probability monad, $P$, with a bag monad $B$ (aka multiset). This
builds on the long-established tradition of using monads to structure
computational effects in functional programming [31, 5].

A good semantic analysis is important in view of the recent work of Grohe and
Lindner [12, 13] which builds on [19, 6]. This new line of work breaks with
the traditional approach of having a fixed finite support for the
probabilistic database, and argues that the support should be infinite,
possibly uncountable. For example, it may be that the gross takings from a
movie are approximated as a real number taken from a normal distribution, and
it may be that the number of actors appearing in a movie is unknown and
unbounded. This leads to semantic complications and introduces issues of
measurability.

###  1.1 Two monads

We argue that probabilistic databases are best understood as inhabitants of a
set, or space,

$P(B(X))\qquad\text{where:}$

  * •

$X$ is a space of all records (aka rows, tuples) that are allowed according to
the schema. For example, in the movie database above, we put
$X=\mathsf{MovieFact}$ where

$\mathsf{MovieFact}\ =\
\Big{(}\mathsf{cast}\colon(\mathsf{Actor}\times\mathsf{Movie})\ \uplus\
\mathsf{gross}\colon(\mathsf{Movie}\times\mathbb{R})\Big{)}$

since we can either record that an actor appeared in a movie, or that a movie
had a certain gross. (Here we are using a standard notation for tagged
disjoint unions.)

  * •

$B$ is a monad of bags (aka multisets). So $B(X)$ is the space of bags over
$X$, and these are the _deterministic_ databases for the given schema.

  * •

$P$ is a probability monad. So $P(B(X))$ is the space of probability
distributions (or measures) over the space of deterministic databases, and
these are the probabilistic databases for the given schema.

In the traditional case, studied in [29], the probability distributions have
finite support. In the general setting proposed by [13], the support of a
distribution is uncountable. This is formalized using measure theory, by
placing a $\sigma$-algebra on $X$, by deriving a $\sigma$-algebra on $B(X)$
and $P(B(X))$. We can regard this as moving from the category of sets to a
category of measurable spaces. As we will show (Theorem 3), the bag monad $B$
extends to a monad on the category of measurable spaces. We can then regard
$P$ as the Giry monad on the category of measurable spaces [9].

We clarify a subtle point. The support of the distributions in $P(B(X))$ might
be infinite, and this means that the set of records that have a chance of
appearing in the database can be infinite. But this is a different issue from
the sizes of the bags under consideration, which will always be finite. For
example, there are infinite possibilities as to what the gross from a movie
is, but the number of movies will always be finite. The number of actors in a
movie is unbounded, but there is never an infinite cast list for a particular
movie.

###  1.2 Measurable queries

In the deterministic setting, a query (aka view) translates a database from
one schema to another. For example, we might ask,

“Which actors appeared in films that grossed at least $200m?” (1)

This is a function $q:B(\mathsf{MovieFact})\to B(\mathsf{Actor})$. For
probabilistic databases, the usual approach is to consider queries on
deterministic databases, and then lift them to probabilistic databases.
Semantically, this can regarded as the functorial action of the monad $P$,
which gives a translation between probabilistic databases:

$P(q)\ :\ P(B(\mathsf{MovieFact}))\to P(B(\mathsf{Actor}))$

Notice that if there is uncertainty about whether an actor appeared in a
movie, or about what the gross of the movie was, then this will lead to
uncertainty about whether that actor should appear in this view.

This functorial action $P(q)$ amounts to pushing forward the probability
measure. But this is only legitimate if the query $q$ is measurable. In
Theorem 4, we show that all queries are measurable provided they are definable
in the standard BALG query language for bags [14].

Our proof of measurability is straightforward, because most of the BALG query
operations are directly definable from the monad structure of $B$ (Theorem 3).
The remaining operations are easily definable from an fold construction
(Theorem 1), which is connected to the fact that $B(X)$ is the free
commutative monoid on $X$.

Measurability of a fragment of BALG is perhaps the main technical result of
[13]. That work was groundbreaking, but here we have two additional
contributions:

  1. 1.

we show that the full language BALG is measurable, which allows us to also
treat aggregation queries within the same framework, and

  2. 2.

we demonstrate that the proof of measurability is almost immediate from the
categorical properties of the monad $B$.

We give the full details of BALG in Section 4. But for now we note that
another way to see that the particular query (1) is measurable is that it can
be written in the monad comprehension syntax as

$q(b)\ =\ \\{\\!\mid a~{}|~{}\mathsf{cast}(a,m)\leftarrow
b,\mathsf{gross}(m^{\prime},r)\leftarrow
b,m=m^{\prime},r>200\,000\,000\mid\\!\\}$

This comprehension syntax works for any strong monad (Section 2.2.1 and [31]),
indeed it is merely a convenient shorthand for

$b\mathrel{\scalebox{0.7}[1.0]{$>\\!\\!\\!>\\!=$}}\lambda
x.\,b\mathrel{\scalebox{0.7}[1.0]{$>\\!\\!\\!>\\!=$}}\lambda
y.\begin{cases}\mathsf{return}(a)&\text{if $x=\mathsf{cast}(a,m)$,
$y=\mathsf{gross}(m,r)$ and $r>200\,000\,000$}\\\
\varnothing&\text{otherwise}\end{cases}$

where $\mathrel{\scalebox{0.7}[1.0]{$>\\!\\!\\!>\\!=$}}$ is the monad bind
(Kleisli composition) and $\mathsf{return}$ is the monad unit. The predicates
($>$, $=$) are well-known to be measurable on the domains where they are used
here, and so the query must be measurable.

As an aside, we remark that much work in the database literature is on
computing the results of queries efficiently. In the probabilistic setting,
this is even more of a problem. But in this paper (as in [13]) we are focusing
on the semantic aspects.

###  1.3 Generating probabilistic databases

Having established the measurability of the query language, in Section 5 we
turn to investigate languages for generating probabilistic databases. For this
we turn to the composite of the monads, $P\circ B$, which we have already
shown to be a monad in [7] (see also [17, 20]). As we demonstrate, the
language for the monad $P\circ B$ appears to be ideal for generating
probabilistic databases, at least as an intermediate language.

The paradigm for using infinite support probabilistic databases is still under
debate, but typically one would begin from a deterministic database, and then
add some randomness. Very simple kinds of randomness include

  * •

adding noise to certain attributes, such as the movie gross, or blood pressure
in a medical database;

  * •

adding or deleting records at random, if there was uncertainty in the accuracy
of those records.

We demonstrate how this can be done easily in the monad $P\circ B$. We also
investigate a more elaborate model based on a GDatalog program, which
translates very cleanly into the language of the $P\circ B$ monad.

###  1.4 Connection with other work on programming semantics

Our work discusses probabilistic databases in the context of monads and
functional programming, and so we bring the general ideas of probabilistic
databases to the language of functional probabilistic programming languages.
We have already prototyped our examples simply by implementing a bag monad in
Haskell and using a standard Haskell library for probabilistic inference. The
idea of applying ideas from probabilistic programming to databases already has
some momentum on the practical side, through languages such as BayesDB [28]
and PClean [21]. Slightly further afield are probabilistic logic languages
such as Blog [32] and ProbLog [8].

Probabilistic programming is a general approach for statistics. Within
statistics, inhabitants of $P(B(X))$ are well-known and important, and called
‘point processes’.

Further over to the semantic side, we note that the relevance of bags for
probability has recently been emphasised by Jacobs [17, 18]. Bags are a form
of non-determinism, and the problem for combining non-determinism and
probability is notoriously subtle, although there has been plenty of recent
progress [10, 20, 23, 24, 15, 30]. The particular combination we use here is
trouble-free.

###  1.5 Summary

In this paper we show the following.

  * •

The Bag monad extends to a strong monad on standard Borel spaces (Thm. 3).

  * •

The Bag monad gives a free commutative monoid, and has a ‘fold’ construction
(Thm. 2, Thm. 1).

  * •

The BALG language for database queries always yields functions that are
measurable (Thm. 4).

  * •

The composite monad $P\circ B$ combines probability and bags and is useful for
generating probabilistic databases.

##### Acknowledgements.

We are grateful to Peter Lindner for discussions. It has also been helpful to
discuss this work with Martin Grohe, Bart Jacobs, Sean Moss, and Philip
Saville. We acknowledge funding from Royal Society University Research
Fellowship, the ERC BLAST grant, and the Air Force Office of Scientific
Research under award number FA9550-21-1-0038. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the United States Air
Force.

##  2 Mathematical preliminaries

###  2.1 Measure theory

######  Definition 1.

The _Borel sets_ form the least collection $\Sigma_{\\_}\mathbb{R}$ of subsets
of $\mathbb{R}$ containing intervals $(a,b)\subseteq\mathbb{R}$ which is
closed under complementation and countable unions.

######  Definition 2.

A _$\sigma$ -algebra_ on a set $X$ is a nonempty family $\Sigma_{\\_}X$ of
subsets of $X$ that is closed under complements and countable unions. The pair
$(X,\Sigma_{\\_}X)$ is called a _measurable space_ (we just write $X$ when
$\Sigma_{\\_}X$ can be inferred from context).

Given $(X,\Sigma_{\\_}X)$, a _measure_ is a function
$\nu:\Sigma_{\\_}X\rightarrow\mathbb{R}^{\infty}_{\\_}+$ such that for all
countable collections of disjoint sets $A_{\\_}i\in\Sigma_{\\_}X$,
$\nu\left(\bigcup_{\\_}iA_{\\_}i\right)=\sum_{\\_}i\nu(A_{\\_}i).$ In
particular, $\nu(\varnothing)=0$. It is a _probability measure_ if $\nu(X)=1$.

######  Definition 3.

Let $(X,\Sigma_{\\_}X)$ and $(Y,\Sigma_{\\_}Y)$ be measurable spaces. A
measurable function $f:X\to Y$ is a function such that
$f^{-1}(U)\in\Sigma_{\\_}X$ when $U\in\Sigma_{\\_}Y$.

######  Definition 4.

A measurable space $(X,\Sigma_{\\_}X)$ is a _standard Borel space_ if it is
either measurably isomorphic to $(\mathbb{R},\Sigma_{\\_}\mathbb{R})$ or it is
countable and discrete.

(This is equivalent to the usual definition of standard Borel spaces, which
involves Polish spaces.)

Standard Borel spaces include the measurable spaces of real numbers and the
integers, as well as all finite discrete spaces such as the booleans. So all
the measurable spaces that arise in probabilistic databases are standard
Borel, and indeed the restriction to standard Borel spaces is also made in
Grohe and Lindner (see [13, Section 3.1]). Standard Borel spaces are closed
under countable products and countable coproducts. Moreover, the equality
predicate $X\times X\to\textsf{Bool}$ is measurable when $X$ is a standard
Borel space.

###  2.2 Monads

######  Definition 5.

A monad on a category is given by an object $TX$ for each object $X$, a
morphism $X\to TX$ for each object $X$, and for objects $X$ and $Y$ and
morphism $f:X\to TY$ a morphism
$f\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}:TX\to TY$ is given,
satisfying identity and associativity laws (see e.g. [25]).

A _strong_ monad on a category with products is equipped with a morphism
$X\times TY\to T(X\times Y)$ that respects the structure (see e.g. [25]).

The construction $\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}$ is
sometimes called bind or Kleisli composition.

####  2.2.1 Monad comprehension notation

For any strong monad we can use a comprehension notation, which is just
syntactic sugar for chaining together compositions of
$\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}$. The name comes from the
fact that this notation resembles set comprehension notation, and when $T$ is
the powerset monad on the category of sets, this is exactly set comprehension.
But it makes sense for any monad, and is often used with the list monad [31].
As we will see (Section 4), for the bag monad, it gives an alternative
notation for queries based on products, projection and selection (see also
[5]).

Given $f_{\\_}1:A\to TX_{\\_}1$, ${f_{\\_}2:A\times X_{\\_}1\to TX_{\\_}2}$,
$f_{\\_}3:A\times X_{\\_}1\times X_{\\_}2\to TX_{\\_}3$, $f_{\\_}n:A\times
X_{\\_}1\times\dots\times X_{\\_}{n-1}\to TX_{\\_}n$, and given $g:A\times
X_{\\_}1\times X_{\\_}2\times\dots\times X_{\\_}n\to Y$, we write

$a\ \mapsto\ \\{\\!\mid g(a,x_{\\_}1,\dots x_{\\_}n)~{}|~{}x_{\\_}1\leftarrow
f_{\\_}1(a),x_{\\_}2\leftarrow f_{\\_}2(a,x_{\\_}1),\dots,x_{\\_}n\leftarrow
f_{\\_}n(a,x_{\\_}1,\dots,x_{\\_}{n-1})\mid\\!\\}$

for the composite morphism

$A\xrightarrow{\bar{f_{\\_}1}}T(A\times
X_{\\_}1)\xrightarrow{\bar{f_{\\_}2}\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}}T(A\times
X_{\\_}1\times
X_{\\_}2)\to\dots\xrightarrow{\bar{f_{\\_}n}\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}}T(A\times
X_{\\_}1\times X_{\\_}2\times\dots\times X_{\\_}n)\xrightarrow{T(g)}T(Y)$

where

$\bar{f_{\\_}i}=A\times X_{\\_}1\times\dots
X_{\\_}{i-1}\xrightarrow{(\mathrm{id},f_{\\_}i)}A\times X_{\\_}1\times\dots
X_{\\_}{i-1}\times TX_{\\_}i\xrightarrow{\text{str}}T(A\times
X_{\\_}1\times\dots\times X_{\\_}i)\text{.}$

###  2.3 The Giry monad

The Giry monad [9] is a first key monad on measurable spaces. It also
restricts to standard Borel spaces. If $X$ is a measurable space, then $P(X)$
is the set of probability measures on $X$ equipped with the $\sigma$-algebra
generated by $A_{\\_}r^{U}=\\{p\in P(X)~{}|~{}p(U)\leq r\\}$. The unit is
given by the Dirac measures ($\eta(x)(U)=1$ if $x\in U$, otherwise $0$). The
bind is given by Lebesgue integration: if $f:X\to P(Y)$ then
$(f\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}p)(U)=\int
f(x)(U)\,p(\mathrm{d}x)$. The strength $s:X\times PY\to P(X\times Y)$ is given
by $s(x,p)(U)=p(\\{y~{}|~{}(x,y)\in U\\})$.

##  3 The bag monoid and monad on measurable spaces

Let $X$ be a set. A bag, aka multiset, is a finite unordered list of elements
of $X$, or more formally an equivalence class of lists under permutation.
Equivalently, a bag is a function $b:X\to\mathbb{N}$ such that
$\\{x~{}|~{}b(x)\neq 0\\}$ is finite, or more formally it is an integer valued
finite measure.

In this section we will focus on bags in the category of standard Borel
spaces. We will show that the bags form a free commutative monoid, and support
a ‘fold’ operation. We will also show that the bag construction forms a strong
monad.

We begin by defining the measurable space of bags on some measurable space.

######  Definition 6.

Let $X$ be a measurable space. Let $BX$ be the set of bags on the set
underlying $X$. Equip $BX$ with the least $\sigma$-algebra $\Sigma_{\\_}{BX}$
containing the generating sets $A^{U}_{\\_}k=\\{b\in BX\mid\text{$b$ contains
exactly}$ $\text{$k$ elements in $U$}\\}$.

$\Sigma_{\\_}{BX}=\sigma(\\{A^{U}_{\\_}k\mid
U\in\Sigma_{\\_}X,k\in\mathbb{N}\\})$

Then $(BX,\Sigma_{\\_}{BX})$ is the measurable space of bags of $X$.

Some observations about the space of bags $BX$ are helpful in what follows.
First we note that for any measurable space $X$ we can decompose the set $BX$
of bags of $X$ into a disjoint union of the set of bags $B_{\\_}nX$ of size
$n$ for all $n\in\mathbb{N}$. We can equip each $B_{\\_}nX$ with the
sub-$\sigma$-algebra. Then,

$BX=\biguplus_{\\_}{n\in\mathbb{N}}B_{\\_}nX.$

Second we record the following lemma.

######  Lemma 1.

Let $X$ be a non-empty standard Borel space. The quotient function $X^{n}\to
B_{\\_}nX$, which takes a tuple $(x_{\\_}1,\dots,x_{\\_}n)$ to the bag
$\\{\\!\mid x_{\\_}1\dots x_{\\_}n\mid\\!\\}$, is measurable, and has a
measurable section $B_{\\_}nX\to X^{n}$.

###### Proof.

The idea is that we can regard $B_{\\_}nX$ as a space of sorted lists in
$X^{n}$, as is common in practice in databases. Any standard Borel space is
either isomorphic to the reals or countable and discrete. All of these spaces
have a measurable total order $(<)\subseteq X\times X$. There may or may not
be a canonical choice for a particular $X$, but it doesn’t matter for the sake
of this proof.

We can then use this within the language of measurable functions to write a
measurable sorting function $i:X^{n}\to X^{n}$ that takes a list and returns
the sorted version of it. (For example, if $n=2$, let $i(x,y)=(x,y)$ if $x<y$
and otherwise $(y,x)$.)

As a set-theoretic function, this sorting function $i:X^{n}\to X^{n}$ factors
through the quotient map,

$i\ =\ X^{n}\xrightarrow{q}B_{\\_}nX\xrightarrow{s}X^{n}\text{.}$

It remains to show that these two functions are measurable. That $q$ is
measurable is well-known, and in fact the $\sigma$-algebra on $B_{\\_}nX$ can
be characterized as
$\Sigma_{\\_}{B_{\\_}nX}=\\{U~{}|~{}q^{-1}(U)\in\Sigma_{\\_}{X^{n}}\\}$ [22,
26]. Finally, to see that $s$ is measurable, suppose
$U\in\Sigma_{\\_}{X^{n}}$, then we must show that
$s^{-1}(U)\in\Sigma_{\\_}{B_{\\_}nX}$, i.e. that
$q^{-1}(s^{-1}(U))\in\Sigma_{\\_}{X^{n}}$. Since $sq=i$, and $i$ is
measurable, we are done. ∎

######  Proposition 1.

The space $(BX,\Sigma_{\\_}{BX})$ is standard Borel when $X$ is standard
Borel.

###### Proof.

If $X$ is standard Borel, then so is $X^{n}$, since any countable product of
standard Borel spaces is standard Borel. So each $B_{\\_}n(X)$ is standard
Borel, since any retract of a standard Borel space is standard Borel. So
$B(X)$ is a countable union of standard Borel spaces, hence also standard
Borel. ∎

Note. Since all the spaces involved in probabilistic databases are standard
Borel, in the remainder of this paper we only consider standard Borel spaces.

###  3.1 Measurable structural recursion on bags

All the computations we were interested in relied on a form of structural
recursion over bags, which we now introduce. This is reminiscent of the fold
construction from functional programming. For example, given a list of
integers, it is possible to compute the sum of its elements by extracting
elements starting at the head and calculating a running sum until we reach the
tail. In this way the function sum can be defined as
$\textsf{fold}(\textsf{plus},0)$ where
$\textsf{plus}:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ plays the role of the
accumulating function and $0$ is the initial argument provided to plus along
with the head of the list. If the list being considered is empty, the result
of the fold is simply the initial argument provided, which in this case is
$0$. The same approach works for bags too, provided that our accumulating
function will need to be such that the order in which it receives its
arguments does not matter. This leads us to the definition of commutative
functions. In the rest of this Section we define what it means to _measurably_
fold a bag.

######  Definition 7.

A function $f:X\times Y\to Y$ is _commutative_ if

$\forall x_{\\_}1,x_{\\_}2\in X,y\in Y.\
f(x_{\\_}1,f(x_{\\_}2,y))=f(x_{\\_}2,f(x_{\\_}1,y)).$

######  Definition 8.

Let $f:X\times Y\to Y$ be a measurable commutative function. Then define
$\mathsf{fold}_{\\_}f:Y\times BX\to Y$ to be the function which applies the
accumulating function $f$ with initial value $y\in Y$ to each element of $b\in
BX$ one-by-one. Note that the order of selection of elements does not matter
as $f$ is commutative. We first define $\mathsf{fold}^{n}_{\\_}f$ for bags of
size $n$. When $n=0$, $\mathsf{fold}^{0}_{\\_}f(y,\varnothing)=y$. For non-
zero $n$,

$\displaystyle\mathsf{fold}^{n}_{\\_}f:Y\times B_{\\_}nX\to Y$
$\displaystyle\mathsf{fold}^{n}_{\\_}f(y,\\{\\!\mid
x_{\\_}1,\dots,x_{\\_}n\mid\\!\\})=f(x_{\\_}1,f(x_{\\_}2,\dots
f(x_{\\_}n,y)\dots)).$

From this, we obtain fold as the unique function coming out of the coproduct
of each of the $\mathsf{fold}^{n}_{\\_}f$’s above, giving us

$\mathsf{fold}_{\\_}f:Y\times BX\to Y.$

######  Theorem 1.

$\mathsf{fold}_{\\_}f$ is measurable for commutative measurable $f:X\times
Y\to Y$.

###### Proof.

We use Lemma 1. First we define fold on lists:

$\displaystyle\mathsf{ofold}^{n}_{\\_}f:Y\times X^{n}\to Y$
$\displaystyle\mathsf{ofold}^{n}_{\\_}f(y,(x_{\\_}1,\dots,x_{\\_}n))=f(x_{\\_}1,f(x_{\\_}2,\dots
f(x_{\\_}n,y)\dots)).$

This is clearly measurable, because it is just built from composition of
measurable functions and product operations. Next we note that for any section
$B_{\\_}nX\to X^{n}$ of the quotient map,

$\mathsf{fold}^{n}_{\\_}f\ =\ Y\times B_{\\_}nX\xrightarrow{Y\times s}Y\times
X^{n}\xrightarrow{\mathsf{ofold^{n}_{\\_}f}}Y$

The commutativity of $f$ means that the choice of section $s$ does not matter.
This again is a composition of measurable functions and so
$\mathsf{fold}^{n}_{\\_}f$ is measurable. The full function
$\mathsf{fold}_{\\_}f:Y\times BX\to Y$ is a copairing of measurable functions,
and so it is measurable too. ∎

###  3.2 The space of bags as the free commutative monoid

In order to define a monoidal structure on the space of bags we first consider
the function $\mathsf{add}:X\times BX\to BX$ which adds a single element to a
bag, incrementing its multiplicity by one. It is clear that add is
commutative.

######  Proposition 2.

$\mathsf{add}:X\times BX\to BX$ is measurable.

###### Proof.

Consider a measurable set $A^{U}_{\\_}k\in\Sigma_{\\_}{BX}$. This is the set
of bags with exactly $k$ elements belonging to $U$. Then
$\textsf{add}^{-1}(A^{U}_{\\_}k)$ is the set of pairs $(x,b)$ such that
$\textsf{add}(x,b)\in A^{U}_{\\_}k$. In other words, each bag in
$A^{U}_{\\_}k$ is decomposed into a set of pairs consisting of an element from
the bag and the remaining bag. We consider the cases when $k=0$ and when
$k>0$. In both these cases the inverse image map is in $\Sigma_{\\_}{X\times
BX}$.

  * •

$k=0$: Here we consider the set of bags such that no element belongs to $U$.
Then it is guaranteed that any element removed from the bag will be in
$\overline{U}$ and the remaining bag still in $A^{U}_{\\_}0$, resulting in the
inverse map being $\overline{U}\times A^{U}_{\\_}0$, which is in
$\Sigma_{\\_}{X\times BX}$.

  * •

$k>0$: Here each bag in the set has a non-zero number of elements in $U$ and
as a result we have two further cases depending on whether or not the element
extracted from the bag is in $U$. If it is not in $U$, the pair consisting of
the element and the remaining bag belongs to $\overline{U}\times
A^{U}_{\\_}k$. If it belongs to $U$, the pair is an element of $U\times
A^{U}_{\\_}{k-1}$. And so the inverse image of $A^{U}_{\\_}k$ under add is the
union of these two sets. Each of these sets is an element of
$\Sigma_{\\_}{X\times BX}$; consequently so too is their union.

∎

With add as an accumulating function we can define the disjoint union of two
bags as a measurable function by considering the fold of add where one bag
provides all the new elements to be added to the other bag, which acts as the
base case.

$\displaystyle\uplus$ $\displaystyle:BX\times BX\to BX$ $\displaystyle\uplus$
$\displaystyle\
\\!(b_{\\_}1,b_{\\_}2)=\textsf{fold}_{\\_}\textsf{add}(b_{\\_}1,b_{\\_}2)$

######  Theorem 2.

For any standard Borel space $X$, $(BX,\uplus,\varnothing)$ is a free
commutative monoid.

###### Proof.

First note that $(BX,\uplus,\varnothing)$ is a commutative monoid. Given any
commutative monoid $(Y,+_{\\_}Y,e_{\\_}Y)$ and a map $f:X\to Y$ we can define
$g=\textsf{fold}_{\\_}\textsf{monAcc}:Y\times BX\to Y$ where monAcc is the
composite

$\textsf{monAcc}=X\times Y\xrightarrow{f\times Y}Y\times
Y\xrightarrow{+_{\\_}Y}Y.$

From this we obtain the unique commutative monoid homomorphism
$f^{\ast}(b)=g(e_{\\_}Y,b):BX\to Y$. ∎

As an aside, we remark that a fold-like operation is sometimes regarded as
immediate from the free (commutative) monoid property. For example, in a
cartesian closed category with list objects $X^{*}$, the space ${Y\to Y}$ is a
monoid (under composition), and hence any map $X\to(Y\to Y)$ induces a
canonical monoid homomorphism $X^{*}\to(Y\to Y)$, which is a curried form of
fold. However, the category of measurable spaces is _not_ cartesian closed [2,
16], and so we have recorded the existence of fold as a separate fact to the
free commutative monoid property.

###  3.3 The bag monad

We now use this universal property to describe the structure of the bag monad
on standard Borel spaces.

  * •

The unit $\eta:X\to B(X)$ is given by the singleton bag: $\eta(x)=\\{\\!\mid
x\mid\\!\\}$. This is measurable because $\eta^{-1}(A^{U}_{\\_}k)$ is
$\overline{U}$ if $k=0$, $U$ if $k=1$, and $\varnothing$ otherwise.

  * •

The bind is given as follows. Informally, for $f:X\to B(Y)$, let
$f\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}:B(X)\to B(Y)$,

$f\mathrel{\scalebox{0.7}[1.0]{$=\\!<\\!\\!\\!<$}}\\{\\!\mid x_{\\_}1\dots
x_{\\_}n\mid\\!\\}=\biguplus_{\\_}{i=1}^{n}f(x_{\\_}i)$

Formally, we apply fold to the composite measurable function

$X\times B(Y)\xrightarrow{f\times B(Y)}B(Y)\times
B(Y)\xrightarrow{\uplus}B(Y)$

to get a measurable function $B(X)\times B(Y)\to B(Y)$, and then pass in the
empty set as the initial argument. Equivalently, the monad multiplication can
be given by applying fold to the function

$\uplus:B(X)\times B(X)\to B(X)$

to get a measurable function $\mu:B(B(X))\to B(X)$, by passing in
$\varnothing$ as the initial argument.

  * •

The strength $X\times B(Y)\to B(X\times Y)$ is given by applying fold to the
function

$(\mathsf{add},\pi_{\\_}2):B(X\times Y)\times X\times Y\to B(X\times Y)\times
X$

to get a measurable function $B(X\times Y)\times X\times B(Y)\to B(X\times
Y)\times X$, and passing in the empty set as the initial argument and
projecting the first result.

As an aside we note that in the statistics literature, it is quite common to
regard $B(X)$ as a space of integer valued measures on $X$. With this
perspective, regarding $B$ as a monad of measures, the strong monad structure
on $B$ is entirely analogous to the monad structure of the Giry monad $P$.

######  Theorem 3.

$(B,\eta,\mu)$ is a strong monad on the category of standard Borel spaces.

##  4 Measurable query operations on bags

In the standard theory of database modelling, relations are assumed to be
sets, disallowing the existence of duplicates. Most database software,
however, relax this restriction, often to save the cost of duplicate
elimination. BALG (“bag algebra”), an algebra for manipulating bags, was first
introduced in [14]. In that paper BALG was presented as an extension of the
nested relation algebra (RALG), with a focus on the study of its expressive
power and relative complexity to RALG. The authors showed that BALG as a query
language was more expressive than RALG.

In this Section we will consider the entire BALG query language and show that
it extends to measurable functions on bags.

For now we briefly review the query language BALG; we discuss these queries
and their semantics in more detail later in this Section. The singleton
operation returns a singleton bag consisting of the input. Restructuring rows
of tables is possible using the $\textsc{map}_{\\_}f$ query, which applies the
function $f$ to every row in the table. The queries product, dunion,
difference, union, and intersect compute the product, disjoint union,
difference, union, and intersection of the input tables respectively. The
project query projects out user-specified columns. flatten transforms a bag of
bags to a bag consisting of the disjoint unions of all the internal bags.
Duplicate elimination, or deduplication, is possible using the dedup query.
Finally, we can compute the bag of sub-bags of any bag using powerbag, and the
bag of subsets of any bag using powerset.

Given the expressiveness of the BALG query language it comes as no surprise
that many operations can be defined in terms of each other. For example, the
powerset of a bag is simply the deduplicated version of the powerbag. It is
also known that the union and intersection of bags can be defined using the
disjoint union and difference operators. To this end we will only consider the
following minimal subset of BALG queries, in terms of which all other queries
can be defined: {singleton, flatten, map, product, project, select, dunion,
difference, powerbag, dedup}.

Previous work: In their work, Grohe and Lindner [12] considered BALG1111It is
called BALG1, with superscript 1., a subset of BALG restricted to bags of
nesting level 1. That is, the queries of BALG1 are defined on bags of type
$BX$ where $X$ cannot have another type $BY$ in its definition. The minimal
set of queries for BALG1 is the same set we consider here minus flatten and
powerbag since they operate on bags of bags. In their work Grohe and Lindner
showed that BALG1 queries extend to measurable functions on bags. We
generalise their results and show, using our monadic and monoidal structure on
bags, that all of BALG extends to measurable functions on bags, and give a
clearer picture of how it comes together. Furthermore, we discuss the actions
of grouping and aggregation as measurable queries in BALG.

###  4.1 Measurability of BALG queries

We provide a semantics to BALG queries by mapping each query to a measurable
function on bags. The measurability of the semantics of the singleton,
flatten, map, product, project, and select queries is guaranteed by defining
their semantics as monad comprehensions. The measurability of the semantics of
the remaining queries, dunion, difference, powerbag, and dedup, is obtained by
defining their semantics using our fold construction introduced in Section 3.
Note that commutativity holds for all the measurable accumulating functions in
the fold-based definitions to follow. The condition of commutativity is easy
to check.

##### Bagging and flattening

The semantics for the singleton and flatten queries are given by the unit
$\eta^{B}$ and multiplication $\mu^{B}$ maps for the bag monad $B$. The
measurability of these maps is proved in Theorem 3.

$\displaystyle\llbracket\textsc{singleton}\rrbracket:X\to
BX\qquad\qquad\qquad\qquad\llbracket\textsc{flatten}\rrbracket:B^{2}X\to BX$
$\displaystyle\llbracket\textsc{singleton}\rrbracket(x)=\eta^{B}_{\\_}X(x)=\\{\\!\mid
x\mid\\!\\}\qquad\qquad\llbracket\textsc{flatten}\rrbracket(b)=\mu^{B}_{\\_}X(b)\
$ $\displaystyle\llbracket\textsc{map}_{\\_}f\rrbracket:BX\to
BY\qquad\llbracket\textsc{map}_{\\_}f\rrbracket(b)=B(f)(b)$ This can be neatly
written using monad comprehension notation:
$\llbracket\textsc{map}_{\\_}f\rrbracket(b)=\\{\\!\mid f(x)\mid x\leftarrow
b\mid\\!\\}$.
$\displaystyle\llbracket\textsc{product}\rrbracket:B(X_{\\_}1\times\dots\times
X_{\\_}m)\times B(Y_{\\_}1\times\dots\times Y_{\\_}n)\to
B(X_{\\_}1\times\dots\times X_{\\_}m\times Y_{\\_}1\times\dots\times
Y_{\\_}n)$
$\displaystyle\llbracket\textsc{product}\rrbracket(b_{\\_}1,b_{\\_}2)=\\{\\!\mid(x_{\\_}1,\dots,x_{\\_}m,y_{\\_}1,\dots,y_{\\_}n)\mid(x_{\\_}1,\dots,x_{\\_}m)\leftarrow
b_{\\_}1,\ (y_{\\_}1,\dots,y_{\\_}n)\leftarrow b_{\\_}2\mid\\!\\}$ A similar
treatment can be given to the project${}_{\\_}{i_{\\_}1,\dots,i_{\\_}k}$ query
which projects out the $i_{\\_}1,\dots,i_{\\_}k$ indices of the input schema.
$\displaystyle\llbracket\textsc{project}_{\\_}{i_{\\_}1,\dots,i_{\\_}k}\rrbracket:B(X_{\\_}1\times\dots\times
X_{\\_}n)\to B(X_{\\_}{i_{\\_}1}\times\dots\times X_{\\_}{i_{\\_}k})$
$\displaystyle\llbracket\textsc{project}_{\\_}{i_{\\_}1,\dots,i_{\\_}k}\rrbracket(b)=\\{\\!\mid(x_{\\_}{i_{\\_}1},\dots,x_{\\_}{i_{\\_}k})\mid(x_{\\_}1,\dots,x_{\\_}n)\leftarrow
b\mid\\!\\}$ $\displaystyle\llbracket\textsc{select}_{\\_}\psi\rrbracket:BX\to
BX\qquad\llbracket\textsc{select}_{\\_}\psi\rrbracket(b)=\textsf{filter}_{\\_}\psi(b)=\\{\\!\mid
x\mid x\leftarrow b,\ \star\leftarrow\hat{\psi}(x)\mid\\!\\}$

In monad comprehension syntax, for a monad with a given zero element (e.g.
$\varnothing\in BX$), a shorthand notation $\\{\\!\mid x\mid x\leftarrow b,\
\psi(x)\mid\\!\\}$ is often used.

##### Disjoint union

dunion simply computes the disjoint union of its arguments. In Section 3.2 we
defined the measurable disjoint union $\uplus:BX\times BX\to BX$ as
$\textsf{fold}_{\\_}\textsf{add}$.

$\displaystyle\llbracket\textsc{dunion}\rrbracket:BX\times BX\to
BX\qquad\llbracket\textsc{dunion}\rrbracket(b_{\\_}1,b_{\\_}2)=b_{\\_}1\uplus
b_{\\_}2=\textsf{fold}_{\\_}\textsf{add}(b_{\\_}1,b_{\\_}2)$

##### Bag difference

Bag difference is the first operation we consider that is not quite immediate
from the monad and monoid structure. The idea is that, for instance,
$\llbracket\textsc{difference}\rrbracket(\\{\\!\mid 1,1,2\mid\\!\\},\\{\\!\mid
1,2,3\mid\\!\\})=\\{\\!\mid 1\mid\\!\\}$. Defining bag difference as a fold
requires a little care. To this end, we first define the measurable function
remove which takes an element and a bag as input and returns either the same
bag if that element did not belong to the bag, or a modified bag with one
fewer instance of the given element. remove is defined as a fold over the
accumulating function remAcc, which maintains a triple as an accumulator:

  * •

the value $x_{\\_}\textsf{rem}\in X$ to be removed,

  * •

a Boolean value indicating whether or not $x_{\\_}\textsf{rem}$ has already
been removed (in order to prevent us from removing $x_{\\_}\textsf{rem}$ more
than once),

  * •

and the resulting bag (which is initially empty) to which elements are added.

Each of the three cases has been defined by combining tupling and add, both of
which are measurable functions. From this it follows that remAcc is
measurable.

$\displaystyle\textsf{remAcc}:X\times((X\times\textsf{Bool})\times
BX)\to(X\times\textsf{Bool})\times BX$
$\displaystyle\textsf{remAcc}(x,((x_{\\_}\textsf{rem},c),b))=\begin{cases}((x_{\\_}\textsf{rem},\textsf{True}),\textsf{add}(x,b))&\text{if
}c=\textsf{True}\\\ ((x_{\\_}\textsf{rem},\textsf{True}),b)&\text{if
}x=x_{\\_}\textsf{rem}\\\
((x_{\\_}\textsf{rem},\textsf{False}),\textsf{add}(x,b))&\text{otherwise}\end{cases}$
To get the final bag after removal we project out the second element of the
pair returned by remAcc. $\displaystyle\textsf{remove}:X\times BX\to
BX\qquad\textsf{remove}(x_{\\_}\textsf{rem},b)=\pi_{\\_}2\left(\textsf{fold}_{\\_}\textsf{remAcc}(((x_{\\_}\textsf{rem},\textsf{False}),\varnothing),b)\right)$
Using remove we define the bag difference of $b_{\\_}1$ and $b_{\\_}2$ by
letting $b_{\\_}1$ be the initial input and from it remove-ing each element in
$b_{\\_}2$ one-by-one. The measurability of bag difference follows from the
commutativity and measurability of remove.
$\displaystyle\llbracket\textsc{difference}\rrbracket:BX\times BX\to
BX\qquad\llbracket\textsc{difference}\rrbracket(b_{\\_}1,b_{\\_}2)=\textsf{fold}_{\\_}\textsf{remove}(b_{\\_}1,b_{\\_}2)$
$\displaystyle\begin{array}[]{@{}l@{\qquad}l}\textsf{powerAcc}:X\times
B^{2}X\to B^{2}X&\llbracket\textsc{powerbag}\rrbracket:BX\to B^{2}X\\\
\textsf{powerAcc}(x,b_{\\_}0)=b_{\\_}0\uplus
B(\textsf{add}_{\\_}x)(b_{\\_}0)&\llbracket\textsc{powerbag}\rrbracket(b)=\textsf{fold}_{\\_}\textsf{powerAcc}(\\{\\!\mid\varnothing\mid\\!\\},b)\end{array}$
$\displaystyle\begin{array}[]{@{}l@{\qquad}l}\textsf{dedupAcc}:X\times BX\to
BX&\llbracket\textsc{dedup}\rrbracket:BX\to BX\\\
\textsf{dedupAcc}(x,b)=\textsf{add}(x,\textsf{filter}_{\\_}{\not=x}(b))&\llbracket\textsc{dedup}\rrbracket(b)=\textsf{fold}_{\\_}\textsf{dedupAcc}(\varnothing,b)\end{array}$

The function $\not=\\!\\!x:X\to\textsf{Bool}$ is measurable since
$\not=\\!\\!x^{-1}(\\{\textsf{True}\\})=X\setminus\\{x\\}$ and
$\not=\\!\\!x^{-1}(\\{\textsf{False}\\})=\\{x\\}$, both of which are
measurable sets (due to $X$ being standard Borel).

######  Theorem 4.

BALG queries yield measurable functions on bags.

###  4.2 Grouping and aggregation

Consider, for example, the table
$\textsf{cast}:\textsf{Actor}\times\textsf{Movie}$ from the database MovieFact
introduced at the start of this paper. A natural query that one may want to
compute is, _“How many movies has each actor appeared in?”_ In order to
calculate the answer to this we first need to be able to group actors with the
bag of all the movies they appeared in. To this resultant table we can map a
size function to the second column to get the numbers we need. Here we
introduce a group query to BALG and show that it is a measurable operation on
bags.

######  Definition 9.

The $\textsc{group}_{\\_}{p_{\\_}1,p_{\\_}2}$ query acts on tables of schema
$X_{\\_}1\times\dots\times X_{\\_}k$ and is parametrized by two projection
functions $p_{\\_}1:X_{\\_}1\times\dots\times X_{\\_}k\to
X_{\\_}{i_{\\_}1}\times\dots\times X_{\\_}{i_{\\_}m}$ and
$p_{\\_}2:X_{\\_}1\times\dots\times X_{\\_}k\to
X_{\\_}{j_{\\_}1}\times\dots\times X_{\\_}{j_{\\_}n}$. The result of this
query is a table with schema $(X_{\\_}{i_{\\_}1}\times\dots
X_{\\_}{i_{\\_}m})\times B(X_{\\_}{j_{\\_}1}\times\dots\times
X_{\\_}{j_{\\_}n})$ where the elements of the first column are paired with the
bag of elements they were related to in the input table. In other words, we
group the rows of the table by the elements in the $p_{\\_}1$-projection of
the table.

The measurable bag-semantics for $\textsc{group}_{\\_}{p_{\\_}1,p_{\\_}2}$ is
given by

$\displaystyle\llbracket\textsc{group}_{\\_}{p_{\\_}1,p_{\\_}2}\rrbracket:B(X_{\\_}1\times\dots\times
X_{\\_}k)\to B((X_{\\_}{i_{\\_}1}\times\dots X_{\\_}{i_{\\_}m})\times
B(X_{\\_}{j_{\\_}1}\times\dots\times X_{\\_}{j_{\\_}n}))$
$\displaystyle\llbracket\textsc{group}_{\\_}{p_{\\_}1,p_{\\_}2}\rrbracket(b)=\\{\\!\mid(i,B(p_{\\_}2)(\textsf{filter}_{\\_}{\lambda
x.p_{\\_}1(x)\equiv i}(b)))\mid
i\leftarrow\llbracket\textsc{dedup}\rrbracket(B(p_{\\_}1)(b))\mid\\!\\}$
$\displaystyle\phantom{\llbracket\textsc{group}_{\\_}{p_{\\_}1,p_{\\_}2}\rrbracket(b)}=\\{\\!\mid(i,\\{\\!\mid
p_{\\_}2(x)~{}|~{}x\leftarrow
b,p_{\\_}1(x)=i\mid\\!\\})~{}|~{}i\leftarrow\llbracket\textsc{dedup}\rrbracket(\\{\\!\mid
p_{\\_}1(x)~{}|~{}x\leftarrow b\mid\\!\\})\mid\\!\\}$

In the monad comprehension we first project out the columns of interest using
$p_{\\_}1$ and deduplicate the resultant bag. From this bag we extract out the
rows indices by which we index the rows of the input bag. For each index $i$
we return the pair consisting of $i$ along with the $p_{\\_}2$-projection of
the input where the $p_{\\_}1$-projection of the rows is equal to $i$. We can
conclude that this query is measurable by defining it as a monad comprehension
composed of other measurable functions.

Recall the actor grouping example suggested earlier. Given an input bag from
$B(\textsf{Actor}\times\textsf{Movie})$ we can apply
$\textsc{group}_{\\_}{\pi_{\\_}1,\pi_{\\_}2}$ to create a table of rows
relating actors to the bag of movies they appeared in. To this table we can
apply $\textsc{map}_{\\_}{\lambda(x,y).(x,\textsf{size}(y))}$ to arrive at the
final result. The function $\textsf{size}:B\ \\!\textsf{Movie}\to\mathbb{N}$
can be measurably defined as a fold, for example.

A second option for defining an group/aggregation query comes from an
extension to monad comprehensions in Haskell where the syntax has been
extended with the keywords group by [27]. This extension works for any strong
monad, but the user needs to provide a grouping function which, in our case,
needs to map a bag on $X$ to a bag of bags on $X$ where each sub-bag contains
the same element. This can be written in BALG as

$\displaystyle\textsc{group'}(b)$ $\displaystyle=\textsc{map}_{\\_}{\lambda
i.\textsc{select}_{\\_}{\lambda x.x\equiv i}(b)}(\textsc{dedup}(b))$

So $\llbracket\textsc{group'}\rrbracket:BX\to B^{2}X$, with:

$\displaystyle\llbracket\textsc{group'}(b)\rrbracket$
$\displaystyle=\\{\\!\mid\\{\\!\mid x~{}|~{}x\leftarrow
b,x=i\mid\\!\\}~{}|~{}i\leftarrow\textsc{dedup}(b)\mid\\!\\}$

The entire actor query can now be concisely written in the notation of [27] as

$\\{\\!\mid(\textsf{the}\ a,\textsf{size}\
m)\mid(a,m)\leftarrow\textsf{actorMovieTable},\ \texttt{group by}\
a\mid\\!\\}.$

This modified comprehension syntax of [27] works by implicitly changing the
types of $a$ and $m$ from Actor and Movie in the right half of the
comprehension to $a\in B\ \\!\textsf{Actor}$ and $m\in B\ \\!\textsf{Movie}$
on the left half. This allows us to apply the measurable aggregation function
$\mathsf{size}:BX\to\mathbb{N}$ to $m$. The aggregation function used on $a$
is $\mathsf{the}:B\ \\!\textsf{Actor}\to\textsf{Actor}$, which is some
measurable function such that $\mathsf{the}(b)=x$ when $b$ is a bag that only
contains copies of $x$. (For example, we could sort $b$ and return the first
element.)

##  5 Generating probabilistic databases

The main focus of this paper has been measurable query languages (Theorem 4).
We now turn to the question of where probabilistic databases come from in the
first place, particularly in the setting where they have infinite support. A
good language for generating infinite probabilistic databases remains a topic
of active research, but we now illustrate that the monads for probability $P$
and bags $B$ could be the basis of a good intermediate language.

###  5.1 A distributive law

We recall the distributive law $\mathsf{distr}$ between the monads $P$ and $B$
that we provided in an earlier paper [7] (see also [17, 20, 33]):

$\mathsf{distr}:B(P(X))\to P(B(X))$

Using our fold technology (Thm. 1) we can define the distributive law as
$\mathsf{distr}=\mathsf{fold}_{\\_}{\mathsf{distrAcc}}$, where

$\displaystyle\mathsf{distrAcc}:P(X)\times P(B(X))\to P(B(X))$
$\displaystyle\mathsf{distrAcc}\ =\ P(X)\times
P(B(X))\xrightarrow{\text{double strength}}P(X\times
B(X))\xrightarrow{P(\mathsf{add})}P(B(X))$

As usual, this distributive law determines a monad structure on $P\circ B$
[3].

###  5.2 Randomizing attributes

For a first example of a probabilistic database, suppose we are given a
deterministic database of (movie,gross) pairs. We may then decide that the
gross figure is inaccurate and should be subject to a noise from a normal
distribution, yielding a probabilistic database. This can be done
categorically by the following map:

$B(\mathsf{Movie}\times{\mathbb{R}})\xrightarrow{B(\mathsf{Movie}\times\mathit{normal})}B(\mathsf{Movie}\times
P({\mathbb{R}}))\xrightarrow{\text{strength}}B(P(\mathsf{Movie}\times{\mathbb{R}}))\xrightarrow{\text{distr}}P(B(\mathsf{Movie}\times{\mathbb{R}}))$

Since $PB$ is a monad, we can use comprehension notation for it, and
equivalently write the above generation method
$\mathit{addNoise}:B(\mathsf{Movie}\times{\mathbb{R}})\to
P(B(\mathsf{Movie}\times{\mathbb{R}}))$ as

$\mathit{addNoise}(b)=\\{\\!\mid(m,r^{\prime})~{}|~{}(m,r)\leftarrow
b,r^{\prime}\leftarrow\mathit{normal}(r,100000)\mid\\!\\}$

Here we are implictly casting $b\in B(X)$ to $b\in P(B(X))$ and
$\mathit{normal}(r,100000)\in P({\mathbb{R}})$ to $P(B({\mathbb{R}}))$,
implicitly using the units $\eta_{\\_}PB:B(X)\to P(B(X))$ and
$P\eta_{\\_}B:P(X)\to P(B(X))$.

Another use-case for random attributes, studied in [13], is to deal with null
attributes by drawing them randomly from a vague prior distribution. This
would also be easy to express using the $PB$ monad.

###  5.3 Adding random records

We can also add and remove random records straightforwardly. We note a few
helpful facts.

  * •

The disjoint union operation $\uplus:B(X)\times B(X)\to B(X)$ lifts to
$\uplus:P(B(X))\times P(B(X))\to P(B(X))$ by composing with the strength of
$P$. In this way the composite monad $PB$ has a commutative monoid structure.

  * •

Since $B(1)\cong\mathbb{N}$, we can regard the Poisson distribution as a map
in ${\mathbb{R}}\to P(B(1))$, parameterized by rate.

Now supposing we also have reasonably uniform distributions
$\mathit{r\text{-}actor}:P(\mathsf{Actor})$ and
$\mathit{r\text{-}movie}:P(\mathsf{Movie})$, we can delete some credits and
generate random additional actors for movies, modelling the fact that some
actors are unlisted:

$\displaystyle\mathit{addRemove}(b)=\quad$
$\displaystyle\\{\\!\mid(a,m)~{}|~{}(a,m)\leftarrow
b,1\leftarrow\mathit{bernoulli}(0.9)\mid\\!\\}$ $\displaystyle\ \uplus\ $
$\displaystyle\\{\\!\mid(a,m)~{}|~{}n\leftarrow\mathit{poisson}(3),a\leftarrow\mathit{r\text{-}actor},m\leftarrow\mathit{r\text{-}movie}\mid\\!\\}$

The first line deletes random rows with probability $0.1$, and the second line
adds in some extra actors (on average, 3 extra actors). Of course, a more
sophisticated model could take into account other prior information such as
relationships and ages between actors.

###  5.4 Towards GDatalog

The GDatalog language has recently been proposed as a generative language for
probabilistic databases [4, 11]. The language combines datalog-style features
with continuous probability distributions.

In general, GDatalog is recursive. We have not treated recursion in this
paper, so we focus on the non-recursive fragment. This can easily be
translated into the $PB$ monad. For example, consider the following GDatalog
program taken from [11]. The idea is to simulate possibly faulty burglar
alarms which either go off because of a burglary or because of an earthquake.

$\displaystyle\mathsf{earthquake}(c,\mathit{bernoulli}(0.1))\leftarrow\mathsf{crimechance}(c,r)$
$\displaystyle\mathsf{burglary}(x,\mathit{bernoulli}(r))\leftarrow\mathsf{address}(x,c),\mathsf{crimechance}(c,r)$
$\displaystyle\mathsf{trigger}(x,\mathit{bernoulli}(0.6))\leftarrow\mathsf{address}(x,c),\mathsf{earthquake}(c,1)$
$\displaystyle\mathsf{trigger}(x,\mathit{bernoulli}(0.9))\leftarrow\mathsf{burglary}(x,1)$
$\displaystyle\mathsf{alarm}(x)\leftarrow\mathsf{trigger}(x,1)$

We will regard this as transforming a deterministic database into a
probabilistic one, $B(X)\to P(B(X))$ where

$\begin{array}[]{rll}X\ =&&(\mathsf{earthquake}:\mathsf{City}\times
2)\uplus(\mathsf{crimechance}:\mathsf{City}\times[0,1])\uplus(\mathsf{address}:\mathsf{House}\times\mathsf{City})\\\
&\uplus&(\mathsf{burglary}:\mathsf{House}\times
2)\uplus(\mathsf{trigger}:\mathsf{House}\times
2)\uplus(\mathsf{alarm}:\mathsf{House})\end{array}$

The GDatalog program can be translated almost verbatim as a sequence of
definitions of a probabilistic database in $PB(X)$ using monad comprehensions,
starting from $b\in B(X)$, as follows.

$\begin{array}[]{rl@{}l}b_{\\_}1&=b&\uplus\
\\{\\!\mid\mathsf{earthquake}(c,z)~{}|~{}\mathsf{crimechance}(c,r)\leftarrow
b,z\leftarrow\mathit{bernoulli}(0.1)\mid\\!\\}\\\ b_{\\_}2&=b_{\\_}1&\uplus\
\\{\\!\mid\mathsf{burglary}(x,z)~{}|~{}\mathsf{crimechance}(c,r)\leftarrow
b_{\\_}1,\mathsf{address}(x,c^{\prime})\leftarrow
b_{\\_}1,c=c^{\prime},z\leftarrow\mathit{bernoulli}(r)\mid\\!\\}\\\
b_{\\_}3&=b_{\\_}2&\uplus\
\\{\\!\mid\mathsf{trigger}(x,z)~{}|~{}\mathsf{address}(x,c)\leftarrow
b_{\\_}2,\mathsf{earthquake}(c^{\prime},1)\leftarrow
b_{\\_}2,c=c^{\prime},z\leftarrow\mathit{bernoulli}(0.6)\mid\\!\\}\\\
b_{\\_}4&=b_{\\_}3&\uplus\
\\{\\!\mid\mathsf{trigger}(x,z)~{}|~{}\mathsf{burglary}(x,1)\leftarrow
b_{\\_}3,z\leftarrow\mathit{bernoulli}(0.9)\mid\\!\\}\\\
b_{\\_}5&=b_{\\_}4&\uplus\
\\{\\!\mid\mathsf{alarm}(x)~{}|~{}\mathsf{trigger}(x,1)\leftarrow
b_{\\_}4\mid\\!\\}\end{array}$

One of the main results of [11] is that GDatalog programs yield proper
probabilistic databases, that is, that all the constructions are measurable.
For examples such as this, in the non-recursive fragment, this measurability
is immediate from the fact that we are programming in the $PB$ monad, where
everything is measurable.

##  6 Summary and outlook

We have shown that the bag monad on standard Borel spaces is strong (Thm. 3)
and supports a fold operation (Thm. 1) which is connected to its
characterization as the free commutative monoid. We have used this to show
straightforwardly that all the bag query operations of BALG yield measurable
queries (Thm. 4), and so they are all safe to use in defining queries of
probabilistic databases. This affirms the results in [12], generalizing them
to the full BALG language and clarifying the measurability arguments by
factoring them through the measurability of the bag monad. Finally, in Section
5 we have argued by illustrations that the combination of the bag and
probability monads gives a powerful intermediate language for processes that
generate probabilistic databases.

## References

  * [1]
  * [2] R. J. Aumann (1961): _Borel structures for function spaces_.  Illinois Journal of Mathematics 5, pp. 614–630, 10.1215/ijm/1255631584.
  * [3] Jon Beck (1969): _Distributive laws_.  In B. Eckmann, editor: Seminar on Triples and Categorical Homology Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 119–140, 10.1007/BFb0083084.
  * [4] Vince Bárány, Balder ten Cate, Benny Kimelfeld, Dan Olteanu & Zografoula Vagena (2017): _Declarative Probabilistic Programming with Datalog_.  ACM Transactions on Database Systems (TODS) 42(4), 10.1017/S1471068409003767.
  * [5] Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen & Limsoon Wong (1994): _Comprehension Syntax_.  SIGMOD Rec. 23(1), pp. 87–96, 10.1145/153850.153853.
  * [6] I I Ceylan, A Darwiche & Guy Van den Broeck (2016): _Open-World Probabilistic Databases_.  In: Proc. KR 2016, 10.1016/j.artint.2021.103474.
  * [7] S. Dash & S. Staton (2020): _A monad for probabilistic point processes_.  In: Proc. ACT 2020, 10.4204/EPTCS.333.2.
  * [8] L De Raedt & A Kimmig (2015): _Probabilistic (logic) programming concepts_.  Machine Learning 100(1), pp. 5–47, 10.1007/s10994-015-5494-z.
  * [9] Michèle Giry (1982): _A categorical approach to probability theory_.  In: Categorical aspects of topology and analysis (Ottawa, Ont., 1980), Lecture Notes in Mathematics 915, Springer, Berlin, pp. 68–85, 10.1007/BFb0092872.
  * [10] Alexandre Goy & Daniela Petrisan (2020): _Combining probabilistic and non-deterministic choice via weak distributive laws_.  In: Proc. LICS 2020, 10.1145/3373718.3394795.
  * [11] Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen & Peter Lindner: _Generative Datalog with Continuous Distributions_.  In: Proc. PODS 2020, pp. 347–360, 10.1145/3375395.3387659.
  * [12] Martin Grohe & Peter Lindner (2019): _Probabilistic Databases with an Infinite Open-World Assumption_.  In: Proc. PODS 2019, pp. 17–31, 10.1145/3294052.3319681.
  * [13] Martin Grohe & Peter Lindner (2020): _Infinite Probabilistic Databases_.  In: Proc. ICDT 2020, 10.4230/LIPIcs.ICDT.2020.16.
  * [14] Stephane Grumbach, Leonid Libkin, Tova Milo & Limsoon Wong (1996): _Query languages for bags: expressive power and complexity_.  SIGACT News (Database Theory Column), pp. 30–37, 10.1145/153850.153853.
  * [15] Gerco van Heerdt, Justin Hsu, Joel Ouaknine & Alexandra Silva (2018): _Convex Language Semantics for Nondeterministic Probabilistic Automata_.  In: Proc. ICTAC 2018, 10.1007/3-540-45319-91.
  * [16] C. Heunen, O. Kammar, S. Staton & H. Yang (2017): _A convenient category for higher-order probability theory_.  In: Proc. LICS 2017, IEEE Press, 10.1109/LICS.2017.8005137.
  * [17] Bart Jacobs (2021): _From Multisets over Distributions to Distributions over Multisets_.  In: Proc. LICS 2021, 10.1109/LICS52264.2021.9470678.
  * [18] Bart Jacobs (2021): _Multinomial and Hypergeometric distributions in Markov Categories_.  In: Proc. MFPS 2021.
  * [19] Ravi Jampani, Fei Xu, Mingxi Wu, Luis Leopoldo Perez, Christopher Jermaine & Peter J. Haas (2008): _MCDB: A Monte Carlo Approach to Managing Uncertain Data_.  In: Sigmod 2008, 10.1145/1376616.1376686.
  * [20] Klaus Keimel & Gordon Plotkin: _Mixed powerdomains for probability and nondeterminism_.  arXiv:1612.01005, 10.23638/LMCS-13(1:2)2017.
  * [21] A K Lew, M Agrawal, D Sontag & V K Mansinghka (2021): _PClean: Bayesian Data Cleaning at Scale with Domain-Specific Probabilistic Programming_.  In: Proc. AISTATS 2021.
  * [22] Odile Macchi (1975): _The Coincidence Approach to Stochastic Point Processes_.  Advances in Applied Probability 7, pp. 83–122, 10.2307/1425855.
  * [23] Matteo Mio & Valeria Vignudelli (2020): _Monads and quantitative equational theories for nondeterminism and probabilities_.  In: Proc. CONCUR 2020, 10.4230/LIPIcs.CONCUR.2020.28.
  * [24] Michael W. Mislove, Joël Ouaknine & James Worrell (2003): _Axioms for Probability and Nondeterminism_.  In: Proc. EXPRESS 2003, 10.1016/j.entcs.2004.04.019.
  * [25] Eugenio Moggi (1991): _Notions of Computation and Monads_.  Inf. Comput. 93(1), p. 55–92, 10.1016/0890-5401(91)90052-4.
  * [26] Jose Enrique Moyal (1962): _The General Theory of Stochastic Population Processes_.  Acta Mathematica 108, 10.1007/BF02545761.
  * [27] Simon Peyton Jones & Philip Wadler (2007): _Comprehensive comprehensions_.  In Gabriele Keller, editor: Proceedings of the ACM SIGPLAN Workshop on Haskell, Haskell 2007, Freiburg, Germany, September 30, 2007, ACM, pp. 61–72, 10.1145/1291201.1291209.
  * [28] F. Saad & V. Mansinghka (2016): _A Probabilistic Programming Approach To Probabilistic Data Analysis_.  In: NeurIPS.
  * [29] Dan Suciu, Dan Olteanu, Christopher Ré & Christoph Koch (2011): _Probabilistic Databases_.  Morgan and Claypool, 10.1016/S0304-3975(96)00129-6.
  * [30] D Varacca & G Winskel (2006): _Distributing probability over non-determinism_.  Mathematical structures in computer science 16, pp. 87–113, 10.1017/S0960129505005074.
  * [31] P Wadler (1992): _Comprehending monads_.  Mathematical Structures in Computer Science 2, pp. 461–493, 10.1016/0304-3975(75)90017-1.
  * [32] Yi Wu, Siddharth Srivastava, Nicholas Hay, Simon Du & Stuart J. Russell (2018): _Discrete-Continuous Mixtures in Probabilistic Programming: Generalized Semantics and Inference Algorithms_.  In: Proc. ICML 2018, pp. 5339–5348.
  * [33] Maaike Zwart & Dan Marsden (2019): _No-Go Theorems for Distributive Laws_.  In: Proc. LICS 2019, 10.1109/LICS.2019.8785707.