18134 LABEL:LastPageDec. 01, 2020Feb. 25, 2022

*Article version of the paper _Infinite Probabilistic Databases_ [GL20] presented at ICDT 2020

# Infinite Probabilistic Databases*

Martin Grohe  and  Peter Lindner  RWTH Aachen University, Ahornstraße 55,
52074 Aachen, Germany<EMAIL_ADDRESS>
###### Abstract.

Probabilistic databases (PDBs) model uncertainty in data in a quantitative
way. In the established formal framework, probabilistic (relational) databases
are finite probability spaces over relational database instances. This
finiteness can clash with intuitive query behavior (Ceylan et al., KR 2016),
and with application scenarios that are better modeled by continuous
probability distributions (Dalvi et al., CACM 2009).

We formally introduced infinite PDBs in (Grohe and Lindner, PODS 2019) with a
primary focus on countably infinite spaces. However, an extension beyond
countable probability spaces raises nontrivial foundational issues concerned
with the measurability of events and queries and ultimately with the question
whether queries have a well-defined semantics.

We argue that finite point processes are an appropriate model from probability
theory for dealing with general probabilistic databases. This allows us to
construct suitable (uncountable) probability spaces of database instances in a
systematic way. Our main technical results are measurability statements for
relational algebra queries as well as aggregate queries and Datalog queries.

###### Key words and phrases:

Probabilistic Databases, Possible Worlds Semantics, Query Measurability,
Relational Algebra, Aggregation, Infinite Probabilistic Databases

##  1\. Introduction

Probabilistic databases (PDBs) are used to model uncertainty in data. Such
uncertainty can have various reasons like, for example, noisy sensor data, the
presence of incomplete or inconsistent information, or information gathered
from unreliable sources [Agg09, SORK11]. In the standard formal framework,
probabilistic databases are finite probability spaces whose sample spaces
consist of database instances in the usual sense, referred to as “possible
worlds”. However, this framework has various shortcomings due to its inherent
_closed-world assumption_ [CDVdB16, CDVdB21], and the restriction to finite
domains. In particular, any event outside of the finite scope of such
probabilistic databases is treated as an impossible event. Yet, statistical
models of uncertain data, say, for example, for temperature measurements as in
Section 2, usually feature the use of continuous probability distributions in
appropriate error models. This (continuous attribute-level uncertainty) is not
expressible in the traditional PDB model. Finite PDBs also only have limited
support for tuple-level uncertainty: in finite PDBs, all possible worlds have
a fixed maximum number of tuples. Instead, in particular with respect to an
open-world assumption, we would like to be able to model probabilistic
databases without an a priori bound on the number of tuples per instance. It
is worth noting that there have been a number of approaches to PDB systems
that are supporting continuous probability distributions, and hence going
beyond finite probability spaces (see the related works section). These
models, however, lack a general (unifying) formal basis in terms of a possible
worlds semantics [DRS09]. While both open-world PDBs and continuous
probability distributions in PDBs have received some attention in the
literature, there is no systematic joint treatment of these issues with a
sound theoretical foundation. In [GL19], we introduced an extended model of
PDBs as arbitrary (possibly infinite) probability spaces over finite database
instances. However, the focus there was on countably infinite PDBs. An
extension to continuous PDBs, which is necessary to model probability
distributions appearing in many applications that involve real-valued
measurement data, raises new fundamental questions concerning the
measurability of events and queries.

In this paper, we lay the foundations of a systematic and sound treatment of
infinite, even uncountable, probabilistic databases. In particular, we prove
that queries expressed in standard query languages have a well-defined
semantics that is compatible with the existing theoretical point of view. Our
model is based on the mathematical theory of finite point processes [Moy62,
Mac75, DVJ03]. Adopting this theory to the context of relational databases, we
give a suitable construction of measurable spaces over which our probabilistic
databases can then be defined. The only (and mild) assumption we need is that
the domains of all attributes are Polish spaces. Intuitively, this requires
them to have nice topological properties. All typical domains one might
encounter in database theory, for example integers, strings, and reals,
satisfy this assumption.

For queries and views to have a well-defined open-world semantics, we need
them to be measurable mappings between probabilistic databases. Our main
technical result states that indeed all queries and views that can be
expressed in the relational algebra, even equipped with arbitrary aggregate
operators (satisfying some mild measurability conditions) are measurable
mappings. The result holds for both a bag-based and set-based relational
algebra and entails the measurability of Datalog queries.

Measurability of queries may seem like an obvious minimum requirement, but one
needs to be very careful. We give an example of a simple, innocent looking
“query” that is not measurable (see Example 3.2). The proofs of the
measurability results are not trivial, and to our knowledge not immediately
covered by standard results from point process theory. At their core, the
proofs are based on finding suitable “countable approximations” of the
queries. That such approximations can be obtained is guaranteed by our
topological requirements.

In the last section of this paper, we briefly discuss queries for
probabilistic databases that go beyond those that are just set-based versions
of traditional database queries. This also casts other natural PDB queries
into our framework. Examples of such a queries are probabilistic threshold
queries and rank queries. Note that these examples refer not only to the facts
in a database, but also to their probabilities, and hence are inherently
probabilistic.

This article is an extended version of the paper with the same title,
_Infinite Probabilistic Databases_ that was presented at the 23rd
International Conference on Database Theory (ICDT 2020) [GL20]. The
presentation of various proofs and arguments has been extensively reworked,
and the paper contains much more background information and new examples. The
overall accessibility of the paper has been additionally enhanced by many
notational and structural improvements.

### Related Work

Early models for probabilistic databases date back to the 1980s [Won82, GH86,
CP87] and 1990s [BGMP92, Pit94, DS96, FR97, Zim97]. Essentially, they are
special cases or variations of the now-acclaimed formal model of probabilistic
databases as a finite set of database instances (the “possible worlds”)
together with a probability distribution [Agg09, SORK11].

The work [Koc08] presents a formal definition of the probabilistic semantics
of relational algebra queries which is used in the MayBMS system [Koc09]. A
probabilistic semantics for Datalog has already been proposed in the mid-90s
[Fuh95]. More recently, a version of Datalog was considered in which rules may
fire probabilistically [DKM10]. Aggregate queries in probabilistic databases
were first treated systematically in [RSG05] and reappear in various works
concerning particular PDB systems [MIW11, FHO12].

The models of possible worlds semantics mentioned above are the mathematical
backbone of existing probabilistic database prototype systems such as MayBMS
[Koc09], Trio [Wid09] and MystiQ [BDM+05]. Various subsequent prototypes
feature uncountable domains as well, such as Orion [SMS+08], MCDB / SimSQL
[JXW+11, CVP+13], Trio [Wid09, AW09] and PIP [KK10]. The MCDB system in
particular allows programmers to specify probabilistic databases with
infinitely many possible worlds, and with database instances that can grow
arbitrarily large [JXW+11]. Its description does not feature a general formal,
measure theoretic account of its semantics though. In a spirit similar to our
work, the work [TPD+12] introduces a measure theoretic semantics for
probabilistic data stream systems with probability measures composed from
Gaussian mixture models but (to our knowledge) on a per tuple basis and
without the possibility of inter-tuple correlations. Continuous probabilistic
databases have already been considered earlier in the context of sensor
networks [FGB02, CKP03, DGM+04]. The first work to formally introduce
continuous possible worlds semantics (including aggregation) is [ACK+11] for
probabilistic XML. However, the framework has an implicit restriction bounding
the number of tuples in a PDB.

Models similar in expressivity to the one we present have also been suggested
in the context of probabilistic modeling languages and probabilistic
programming [MMR+05, Mil06, RD06, DRKNP16, Bel20, GHNR14]. In particular
notable are the measure theoretic treatments of Bayesian Logic (BLOG) [MMR+05]
in [WSH+18] and Markov Logic Networks (MLNs) [RD06] in [SD07]. While these
data models are relational, their suitability for general database
applications remains unclear. In particular, the investigation of typical
database queries is beyond the scope of the corresponding works. Recently,
point processes in particular have been abstractly investigated for
probabilistic programming [DS20].

Problems caused by the closed-world assumption [Rei81] in probabilistic
databases [ZP97] were initially discussed by Ceylan et al. in [CDVdB16] where
they suggest the model of OpenPDBs. In [BCL18], the authors make a more fine-
grained distinction between an _open-world_ and _open-domain assumption_ , the
latter of which does not assume the attribute values of the database schema to
come from a known finite domain. The semantics of OpenPDBs can be strengthened
towards an open-domain assumption by the means of ontologies [BCL17, BCL18,
BCL19].

There is a tight connection between the problem of computing the probability
of Boolean queries in (finite) probabilistic databases and _weighted first-
order model counting (WFOMC)_ [VdBS17]. For this connection, the _lineage_ of
the query in question is considered. Then probabilistic query evaluation in
finite PDBs boils down to weighted counting of the models of the lineage.
While weighted model counting it itself is restricted to discrete weight
functions, _weighted model integration (WMI)_ is an extension that also
supports uncountable domains [BPVDB15, MPS19]. However, a direct connection to
our infinite PDBs seems hard to obtain, as queries in infinite PDBs in general
do not have finite lineage expressions. In particular, our infinite PDBs may
have an unbounded number of random tuples, contrasting the setup of a fixed
number of variables in a WMI problem. Also, in this paper we introduce a
rather general notion of PDB queries, that covers, for example, parity tests
and various fixpoint queries.

Our classification of views towards the end of this paper is similar to
previous classifications of queries such as [CKP03, WvK15] in the sense that
it distinguishes the level on which information is aggregated. The work
[WvK15] suggests a distinction between “traditional” and “out-of-world
aggregation” similar to the one we present.

##  2\. Preliminaries

Throughout this paper, $\mathbb{N}$, $\mathbb{Q}$, and $\mathbb{R}$ denote the
sets of non-negative integers, rationals, and real numbers, respectively. With
$\mathbb{N}_{+}$, $\mathbb{Q}_{+}$, and $\mathbb{R}_{+}$ we denote their
restrictions to positive numbers.

### Sets and Bags

If $S$ is a set and $k\in\mathbb{N}$, then $\mathcal{P}_{k}(S)$ denotes the
set of all subsets of $S$ that have cardinality exactly $k$. The set of all
_finite_ subsets of $S$ is then given as
$\mathcal{P}_{\mathsf{fin}}(S)\coloneqq\bigcup_{i=0}^{\infty}\mathcal{P}_{k}(S)$.
The set of _all_ subsets of $S$ (that is, the _powerset_ of $S$) is denoted by
$\mathcal{P}(S)$.

A (finite) _bag_ (or _multiset_) $B$ over a set $S$ is a function from $S$ to
$\mathbb{N}$, assigning a _multiplicity_ to every element from $S$. We
interpret bags as collections of elements that may contain duplicates. For
$s\in S$ we let $\lvert B\rvert_{s}$ denote the multiplicity of $s$ in $B$. If
$\bm{S}\subseteq S$, we let $\lvert
B\rvert_{\bm{S}}\coloneqq\sum_{s\in\bm{S}}\lvert B\rvert_{s}$. The
_cardinality_ $\lvert B\rvert$ of the bag $B$ is the sum of all
multiplicities, i. e. $\lvert B\rvert\coloneqq\lvert B\rvert_{S}$.

Similar to the set notation, we use $\mathcal{B}_{k}(S)$ to denote the set of
all bags over $S$ that have cardinality exactly $k$. The set of all _finite_
bags over $S$ is given as
$\mathcal{B}_{\mathsf{fin}}(S)\coloneqq\bigcup_{i=0}^{\infty}\mathcal{B}_{k}(S)$.
Occasionally, we explicitly denote bags by the elements they contain. Then
$\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{k}\mathclose{}\middle\\}\right\\}$
denotes a bag of cardinality $k$ with elements $a_{1},\dots,a_{k}$ (possibly
including repetitions).

### Relational Databases

For the remainder of this paper, we fix two countably infinite sets
${\mathsf{Rel}}$ and ${\mathsf{Att}}$ with
${\mathsf{Rel}}\cap{\mathsf{Att}}=\emptyset$. The elements of ${\mathsf{Rel}}$
are called _relation symbols_ , and the elements of ${\mathsf{Att}}$ are
called _attribute names_.

A _database schema_ $\tau$ is a tuple
$(\mathcal{A},\mathcal{R},\operatorname{sort})$ such that $\mathcal{A}$ is a
finite subset of ${\mathsf{Att}}$, $\mathcal{R}$ is a finite subset of
${\mathsf{Rel}}$, and
$\operatorname{sort}\colon\mathcal{R}\to\bigcup_{k=0}^{\infty}{\mathcal{A}}^{k}$
is a function that maps every relation symbol $R\in\mathcal{R}$ to a tuple
$(A_{1},\dots,A_{k})$ of pairwise distinct attribute names
$A_{1},\dots,A_{k}\in\mathcal{A}$ for some $k\in\mathbb{N}$. For
$R\in\mathcal{R}$ we call $\operatorname{sort}(R)$ the _sort_ of $R$. If
$\operatorname{sort}(R)=(A_{1},\dots,A_{k})$, then $k$ is called the _arity_
of $R$, and denoted by $\operatorname{ar}(R)$. We abuse notation and write
$A\in\operatorname{sort}(R)$ if $A$ is an attribute name appearing in
$\operatorname{sort}(R)$. We also write $R\in\tau$ instead of
$R\in\mathcal{R}$ for relation symbols.

Let $\mathcal{A}$ be a subset of ${\mathsf{Att}}$. A _(sorted) universe_ with
sorts $\mathcal{A}$ is a pair $(\mathbb{U},\operatorname{dom})$ where
$\mathbb{U}$ is a non-empty set and
$\operatorname{dom}\colon\mathcal{A}\to\mathcal{P}(\mathbb{U})$. We abuse
notation and refer a sorted universe $(\mathbb{U},\operatorname{dom})$ just by
$\mathbb{U}$, and implicitly assume $\operatorname{dom}$ given. For
$A\in\mathcal{A}$, we call $\operatorname{dom}(A)\eqqcolon\mathbb{A}$ the
_(attribute) domain_ of $A$. If
$\tau=(\mathcal{A},\mathcal{R},\operatorname{sort})$ is a database schema and
$\mathbb{U}$ a universe with sorts $\mathcal{A}$ and $R\in\mathcal{R}$ with
$\operatorname{sort}(R)=(A_{1},\dots,A_{k})$, then

$\mathbb{T}_{[R,\mathbb{U}]}\coloneqq\mathbb{A}_{1}\times\dots\times\mathbb{A}_{k}$
(1)

is called the _domain_ of $R$. The elements of $\mathbb{T}_{[R,\mathbb{U}]}$
are called _$R$ -tuples_ (over $\mathbb{U}$). If $R$ is a relation of sort
$\operatorname{sort}(R)=(A_{1},\dots,A_{k})$, and $t=(a_{1},\dots,a_{k})$ is
an $R$-tuple, then

$t[A_{i_{1}},\dots,A_{i_{\ell}}]\coloneqq(a_{i_{1}},\dots,a_{i_{\ell}})$

denotes the restriction of $t$ to the attributes
$A_{i_{1}},\dots,A_{i_{\ell}}$ for all $1\leq i_{1}<\dots<i_{\ell}\leq k$ and
all $\ell=1,\dots,k$.

For $R\in\mathcal{R}$, an _$R$ -fact_ (over $\mathbb{U}$) is an expression of
the shape $R(t)$ where $t$ is an $R$-tuple over $\mathbb{U}$. If
$\bm{T}\subseteq\mathbb{T}_{[\tau,\mathbb{U}]}$ is a set of $R$-tuples over
$\mathbb{U}$, then

$R(\bm{T})\coloneqq\big{\\{}R(t)\colon t\in\bm{T}\big{\\}}\text{.}$

In particular, $R\big{(}\mathbb{T}_{[R,\mathbb{U}]}\big{)}$ is the set of all
$R$-facts over $\mathbb{U}$, which is formally given as

$\mathbb{F}_{[R,\mathbb{U}]}\coloneqq\\{R\\}\times\mathbb{T}_{[\tau,\mathbb{U}]}\text{.}$
(2)

The elements of

$\mathbb{F}_{[\tau,\mathbb{U}]}\coloneqq\bigcup_{R\in\tau}\mathbb{F}_{[R,\mathbb{U}]}$

are called _$\tau$ -facts_ (or just _facts_) over $\mathbb{U}$. We use
(variants of) the letter $f$ to denote facts.

A _database instance_ $D$ over $\tau$ and $\mathbb{U}$, or _$\tau$ -instance_
over $\mathbb{U}$ is a finite bag of $\tau$-facts over $\mathbb{U}$. Thus,

$\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}\coloneqq\mathcal{B}_{\mathsf{fin}}\big{(}\mathbb{F}_{[\tau,\mathbb{U}]}\big{)}$

is the set of all $\tau$-instances over $\mathbb{U}$. For $R\in\tau$ and
$D\in\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}$, we let $R(D)$ denote
the restriction of $D$ to $R$-facts. That is, the instance $R(D)$ is given by

$\lvert R(D)\rvert_{f}\coloneqq\begin{cases}\lvert D\rvert_{f}&\text{if
}f\in\mathbb{F}_{[R,\mathbb{U}]}\text{ and}\\\ 0&\text{if
}f\notin\mathbb{F}_{[R,\mathbb{U}]}\end{cases}$

for all $f\in\mathbb{F}_{[\tau,\mathbb{U}]}$.

From all of the notation we defined above, we omit the explicit mention of
$\tau$ and $\mathbb{U}$ if they are clear from the context, and just write
$\mathbb{T}$, $\mathbb{T}_{R}$, $\mathbb{F}$, $\mathbb{F}_{R}$ and
$\mathord{\mathbb{D}\mathbb{B}}$ instead of $\mathbb{T}_{[\tau,\mathbb{U}]}$,
$\mathbb{T}_{[R,\mathbb{U}]}$, $\mathbb{F}_{[\tau,\mathbb{U}]}$,
$\mathbb{F}_{[R,\mathbb{U}]}$ and
$\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}$. Table 1 recaps the
notation we just defined.

Table 1. Notation used for relational databases. Concept | Notation
---|---
Database schema |  $\tau=(\mathcal{A},\mathcal{R},\operatorname{sort})$ with $\mathcal{A}\subseteq{\mathsf{Att}}$, $\mathcal{R}\subseteq{\mathsf{Rel}}$
Attribute names | $A,A_{1},A_{2},\dots\in\mathcal{A}$
Relation names | $R,S,R_{1},R_{2},\dots\in\mathcal{R}$
Sort of a relation name $R\in\mathcal{R}$ | $\operatorname{sort}(R)\in\bigcup_{k\in\mathbb{N}}\mathcal{A}^{k}$
Arity of a relation name $R\in\mathcal{R}$ | $\operatorname{ar}(R)\in\mathbb{N}$
Underlying universe | $\mathbb{U}$
Space of all tuples over $(\tau,\mathbb{U})$ |  $\mathbb{T}_{[\tau,\mathbb{U}]}$, $\mathbb{T}$
Space of all $R$-tuples over $(\tau,\mathbb{U})$, $R\in\mathcal{R}$ |  $\mathbb{T}_{[R,\mathbb{U}]}$, $\mathbb{T}_{R}$
Tuples and restricted tuples |  $t,t_{1},t_{2},\dots$ and $t[A_{i_{1}},\dots,A_{i_{k}}]$
Space of all facts over $(\tau,\mathbb{U})$ |  $\mathbb{F}_{[\tau,\mathbb{U}]}$, $\mathbb{F}$
Space of all $R$-facts over $(\tau,\mathbb{U})$, $R\in\mathcal{R}$ |  $\mathbb{F}_{[R,\mathbb{U}]}$, $\mathbb{F}_{R}$
Facts | $f,f_{1},f_{2},\dots$
Space of database instances over $(\tau,\mathbb{U})$ |  $\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}$, $\mathord{\mathbb{D}\mathbb{B}}$

In [GL19], we used an example of temperature recordings to motivate infinite
probabilistic databases, to illustrate the setup, and to highlight some
observations. With some customization, we adopt this example to also serve as
a running example for this paper.

We consider a database that stores information about the rooms in an office
building. An example database instance is shown in Figure 1.

Office RoomNo | Person
---|---
4108 | Alice
4108a | Bob
4109 | Charlie

TempRec RoomNo | Date | Temp [°C]
---|---|---
4108 | 2021-07-12 | 20.5
4108a | 2021-07-12 | 21.0
4109 | 2021-07-12 | 21.1
4109 | 2021-07-13 | 20.8

Figure 1. A database instance $D$, storing temperature recordings in an office
building.

The database schema $\tau$ consists of

  * •

relation symbols $\mathcal{R}=\\{\text{Office},\text{TempRec}\\}$,

  * •

attribute names
$\mathcal{A}=\\{\text{RoomNo},\text{Person},\text{Date},\text{Temp}\\}$, and

  * •

sorts $\operatorname{sort}(\text{Office})=(\text{RoomNo},\text{Person})$ and
$\operatorname{sort}(\text{TempRec})=(\text{RoomNo},\text{Date},\text{Temp})$.

The sorted universe is given by $(\mathbb{U},\operatorname{dom})$ with
$\mathbb{U}=\Sigma^{*}\cup\mathbb{R}$ where $\Sigma$ is some alphabet, say,
the set of ASCII symbols, and (for simplicity)
$\operatorname{dom}(\text{RoomNo}),\operatorname{dom}(\text{Person}),\operatorname{dom}(\text{Date})\subseteq\Sigma^{*}$
and $\operatorname{dom}(\text{TempRec})=\mathbb{R}$.

For example facts $f_{1}=\text{Office}(\text{\small 4108},\text{\small Bob})$
and $f_{2}=\text{TempRec}(\text{\small 4108},\text{\small
2021-07-12},\text{\small 20.5})$ are both facts from
$\mathbb{F}_{[\tau,\mathbb{U}]}$, and it holds that $f_{1}\notin D$ and
$f_{2}\in D$ for the database instance $D$ from Figure 1.

### Measurable Spaces and Functions

In the following we recap the relevant background and foundations from
probability and measure theory that are needed throughout this paper. For a
general introduction to measure theory we point the reader to [Kle14, Chapter
1] or [Kal02, Chapter 1].

Let $\mathbb{X}\neq\emptyset$. A _$\sigma$ -algebra_ on $\mathbb{X}$ is a
family $\mathfrak{X}$ of subsets of $\mathbb{X}$ such that
$\mathbb{X}\in\mathfrak{X}$ and $\mathfrak{X}$ is closed under complements and
countable unions (an equivalent definition is obtained by replacing “countable
unions” with “countable intersections”).

Throughout the paper, we use double struck letters
($\mathbb{X},\mathbb{Y},\mathbb{Z},\mathbb{A},\mathbb{B},\dots$) to denote
underlying spaces of interest, and fraktur letters
($\mathfrak{X},\mathfrak{Y},\mathfrak{Z},\mathfrak{A},\mathfrak{B},\dots$) to
denote set families and $\sigma$-algebras over such spaces, in particular. We
usually denote subsets of the underlying spaces with bold italics letters
$(\bm{X},\bm{Y},\bm{Z},\bm{A},\bm{B},\dots)$.

Let $\mathfrak{G}$ (fraktur “$G$”) be a set of subsets of $\mathbb{X}$ (that
is, $\mathfrak{G}\subseteq\mathcal{P}(\mathbb{X})$). The _$\sigma$ -algebra
generated by $\mathfrak{G}$_ is the coarsest (i. e. smallest with respect to
set inclusion) $\sigma$-algebra $\mathbb{X}$ containing $\mathfrak{G}$. For
any $\mathfrak{G}\subseteq\mathcal{P}(\mathbb{X})$, the $\sigma$-algebra
generated by $\mathfrak{G}$ is unique. A _measurable space_ is a pair
$(\mathbb{X},\mathfrak{X})$ where $\mathbb{X}$ is an arbitrary set and
$\mathfrak{X}$ is a $\sigma$-algebra on $\mathbb{X}$. The sets in
$\mathfrak{X}$ are called _$\mathfrak{X}$ -measurable_ (or _measurable_ , if
$\mathfrak{X}$ is clear from the context). If $(\mathbb{Y},\mathfrak{Y})$ is
another measurable space, then a function
$\varphi\colon\mathbb{X}\to\mathbb{Y}$ is called
_$(\mathfrak{X},\mathfrak{Y})$ -measurable_ (or simply _measurable_ , if
$\mathfrak{X}$ and $\mathfrak{Y}$ are clear from the context), if for all
$\bm{Y}\in\mathfrak{Y}$ it holds that

$\varphi^{-1}(\bm{Y})=\big{\\{}X\in\mathbb{X}\colon\varphi(X)\in\bm{Y}\big{\\}}\in\mathfrak{X}\text{.}$

The following simple properties are needed throughout the paper.

######  Fact 1 (cf. [Kal02, Lemmas 1.4 and 1.7]).

Let $(\mathbb{X},\mathfrak{X})$, $(\mathbb{Y},\mathfrak{Y})$,
$(\mathbb{Z},\mathfrak{Z})$ be measurable spaces.

  1. (1)

Suppose $\mathfrak{Y}$ is generated by some
$\mathfrak{G}\subseteq\mathcal{P}(\mathbb{Y})$. If
$\varphi\colon\mathbb{X}\to\mathbb{Y}$ satisfies
$\varphi^{-1}(\bm{G})\in\mathfrak{X}$ for all $\bm{G}\in\mathfrak{G}$, then
$\varphi$ is measurable.

  2. (2)

Compositions of measurable functions are measurable. That is, if
$\varphi\colon\mathbb{X}\to\mathbb{Y}$ and $\psi\colon\mathbb{Y}\to\mathbb{Z}$
are measurable, then $\psi\circ\varphi\colon\mathbb{X}\to\mathbb{Z}$ is
$(\mathfrak{X},\mathfrak{Z})$-measurable. ∎

### Probability and Image Measures

A _probability measure_ on a measurable space $(\mathbb{X},\mathfrak{X})$ is a
countably additive function $P\colon\mathfrak{X}\to[0,1]$ with
$P(\mathbb{X})=1$. Then $(\mathbb{X},\mathfrak{X},P)$ is called a _probability
space_. Measurable sets in probability spaces are also called _events_. A
measurable function $\varphi$ from a probability space
$(\mathbb{X},\mathfrak{X},P)$ into a measurable space
$(\mathbb{Y},\mathfrak{Y})$ introduces a new probability measure $P^{\prime}$
on $(\mathbb{Y},\mathfrak{Y})$ by

$P^{\prime}(\bm{Y})=P\big{(}\varphi^{-1}(\bm{Y})\big{)}=P\big{(}\\{X\in\mathbb{X}\colon\varphi(X)\in\bm{Y}\\}\big{)}$

for all $\bm{Y}\in\mathfrak{Y}$. Then $P^{\prime}=P\circ\varphi^{-1}$ is
called the _image_ or _push-forward probability measure_ of $P$ under (or
along) $\varphi$. The measurability of $\varphi$ ensures that $P^{\prime}$ is
well-defined.

### Standard Constructions

Throughout this paper, we will encounter a variety of measurable spaces. The
most basic of these are either well-known measurable spaces like countable
spaces with the powerset $\sigma$-algebra or uncountable spaces like
$\mathbb{R}$ with its Borel $\sigma$-algebra. From these spaces, we then
construct more complicated measurable spaces with the use of the following
standard constructions.

  1. (1)

Product spaces. For $i=1,\dots,n$, let $(\mathbb{X}_{i},\mathfrak{X}_{i})$ be
a measurable space. The _product $\sigma$-algebra_

$\bigotimes_{i=1}^{n}\mathfrak{X}_{i}=\mathfrak{X}_{1}\otimes\dotsc\otimes\mathfrak{X}_{n}$

is the $\sigma$-algebra on $\prod_{i=1}^{n}\mathbb{X}_{i}$ that is generated
by the sets
$\\{\operatorname{proj}_{j}^{-1}(\bm{X})\colon\bm{X}\in\mathfrak{X}_{j}\\}$
with $j=1,\dots,n$ where $\operatorname{proj}_{j}$ is the canonical projection
$\operatorname{proj}_{j}\colon\prod_{i=1}^{n}\mathbb{X}_{i}\to\mathbb{X}_{j}$.
If $(\mathbb{X}_{i},\mathfrak{X}_{i})=(\mathbb{X},\mathfrak{X})$ for all
$i=1,\dots,n$, we also write $\mathfrak{X}^{\otimes n}$ instead of
$\bigotimes_{i=1}^{n}\mathfrak{X}$.

  2. (2)

Disjoint unions. If the spaces $\mathbb{X}_{i}$ are pairwise disjoint, then
the _disjoint union $\sigma$-algebra_ on $\bigcup_{i=1}^{n}\mathbb{X}_{i}$ is
given by

$\bigoplus_{i=1}^{n}\mathfrak{X}_{i}\coloneqq\big{\\{}\bm{X}\subseteq{\textstyle\bigcup_{i=1}^{n}}\mathbb{X}_{i}\colon\bm{X}\cap\mathbb{X}_{i}\in\mathfrak{X}_{i}\text{
for all }i=1,\dots,n\big{\\}}\text{.}$

It may be easily verified that this is a $\sigma$-algebra on
$\bigcup_{i=1}^{n}\mathbb{X}_{i}$.

  3. (3)

Subspaces. Let $(\mathbb{X},\mathfrak{X})$ be a measurable space and
$\bm{X}\in\mathfrak{X}$. Then

$\mathfrak{X}\rvert_{\bm{X}}\coloneqq\\{\bm{X}^{\prime}\cap\bm{X}\colon\bm{X}^{\prime}\in\mathfrak{X}\\}$

is a $\sigma$-algebra on $\bm{X}$.

### Polish Topological Spaces

There are deep connections between measure theory and general topology. In
fact, virtually everything we discuss and show in this paper relies on the
presence of certain topological properties. The central notion from topology
we need is that of _Polish spaces_ [Kec95, Chapter 3]. In the following, we
assume familiarity with the basic topological concepts. A small introduction
to the basic terms can be found in Appendix A. For a thorough introduction, we
refer to [Wil04].

A _Polish space_ is a topological space that is separable (i. e. there exists
a countable dense set), and completely metrizable (i. e. there is a complete
metric on the space generating its topology). Polish and (the later
introduced) standard Borel spaces are introduced and treated in detail in
[Kec95, Chapter 1 & 2] and [Sri98]. In this paper, we heavily exploit the
properties of Polish spaces. The existence of a countable dense set, together
with the existence of a complete metric generating the topology allows us to
approximate any point in the space by countable collections of open sets. More
specifically, for every point in the space, there exists a sequence over a
fixed _countable_ set that converges to the point.

The following fact lists a few natural classes of spaces that are Polish.

######  Fact 2.

All finite and countably infinite spaces (with the discrete topology) are
Polish [Kec95, p. 13]. The Euclidean space $\mathbb{R}^{n}$ is Polish for all
$n\in\mathbb{N}_{+}$ [Kec95, ibid.].

Countable sums and products of sequences of Polish spaces are Polish (subject
to the sum and product topologies) [Kec95, Proposition 3.3]. Moreover,
subspaces of a Polish space that are countable intersections of open sets are
Polish. This also implies that closed subspaces of Polish spaces are Polish,
cf. [Kec95, Proposition 3.7 and Theorem 3.11].

The above properties arguably capture all typical spaces of interest for
database theory. When we later work with Polish spaces, we always assume that
we have a fixed Polish metric at hand, that is, a complete metric generating
the Polish topology. With respect to said _compatible_ metric, we write
$B_{\varepsilon}(X)$ to denote the open ball of radius $\varepsilon>0$ around
the point $X\in\mathbb{X}$.

### Standard Borel Spaces

If $(\mathbb{X},\mathfrak{O})$ is a topological space, the _Borel
$\sigma$-algebra_ $\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{X})$ on
$\mathbb{X}$ is the $\sigma$-algebra generated by the open sets $\mathfrak{O}$
(the topology in use is usually clear from context; in our case, provided
there is one, we always use a Polish topology on $\mathbb{X}$). Sets in the
Borel $\sigma$-algebra are also called _Borel sets_. In the following, we
state some nice basic properties of standard Borel spaces.

######  Fact 3 (see [Kal02, Lemmas 1.5 & 1.10]).

Let $(\mathbb{X},\mathfrak{O}_{\mathbb{X}})$ and
$(\mathbb{Y},\mathfrak{O}_{\mathbb{Y}})$ be topological spaces.

  1. (1)

If $\varphi\colon\mathbb{X}\to\mathbb{Y}$ is continuous, then $\varphi$ is
$\big{(}\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{X}),\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{Y})\big{)}$-measurable.

  2. (2)

If $(\mathbb{Y},\mathfrak{O}_{\mathbb{Y}})$ is a metric topological space,
$(\varphi_{n})_{n\geq 0}$ is a sequence of
$\big{(}\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{X}),\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{Y})\big{)}$-measurable
functions $\varphi_{n}\colon\mathbb{X}\to\mathbb{Y}$ with
$\lim_{n\to\infty}\varphi_{n}=\varphi$, then $\varphi$ is measurable as well.
∎

A measurable space $(\mathbb{X},\mathfrak{X})$ is called a _standard Borel
space_ if there exists a Polish topology $\mathfrak{O}$ on $\mathbb{X}$ such
that $\mathfrak{X}$ is the (Borel) $\sigma$-algebra generated by
$\mathfrak{O}$.

######  Fact 4 (Lusin-Souslin, see [Kec95, Theorem 15.1]).

Let $(\mathbb{X},\mathfrak{X})$ and $(\mathbb{Y},\mathfrak{Y})$ be standard
Borel spaces, let $\bm{X}\in\mathfrak{X}$, and let
$\varphi\colon\mathbb{X}\to\mathbb{Y}$ be a continuous function such that
$\varphi\mathord{\upharpoonright}_{\bm{X}}$ (the restriction of $\varphi$ to
the set $\bm{X}$) is injective. Then $\varphi(\bm{X})\in\mathfrak{Y}$.∎

In other words, the above fact states that between standard Borel spaces, the
image of a measurable set $\bm{X}$ under a function is measurable itself,
provided that the function is continous, and injective on $\bm{X}$.

The following fact intuitively states that the property of measurable spaces
being standard Borel is closed under using the constructions introduced
before.

######  Fact 5 (see [Kec95, p. 75]).

Let $(\mathbb{X}_{i},\mathfrak{X}_{i})$ be a sequence of standard Borel
spaces.

  1. (1)

The product space
$\big{(}\prod_{i}\mathbb{X}_{i},\bigotimes_{i}\mathfrak{X}_{i}\big{)}$ is
standard Borel.

  2. (2)

If the spaces $\mathbb{X}_{i}$ are pairwise disjoint, then the disjoint sum
$\big{(}\sum_{i}\mathbb{X}_{i},\bigoplus_{i}\mathfrak{X}_{i}\big{)}$ is
standard Borel.

Moreover, if $(\mathbb{X},\mathfrak{X})$ is standard Borel, and
$\bm{X}\in\mathfrak{X}$, then $(\bm{X},\mathfrak{X}\rvert_{\bm{X}})$ is
standard Borel. ∎

### (Finite) Point Processes

A _point process_ [DVJ03, DVJ08] is a probability space over countable sets of
points in some abstract “state space” such as the Euclidean space
$\mathbb{R}^{n}$. Point processes are a well-studied subject in probability
theory and they appear in a variety of applications such as particle physics,
ecology, geostatistics (cf. [DVJ03, Bad07] and target tracking [Deg17]. In
computer science, they have applications in queuing theory [Fra82] and machine
learning [KT12]. The individual outcomes (that is, point configurations) drawn
from a point process are called a _realization of the process_. A point
process is called _finite_ if all of its realizations are finite. In the
following, we recall the construction of a finite point process over a Polish
state space, following the classic constructions of [Moy62, Mac75].

Let $(\mathbb{X},\mathfrak{X})$ be a standard Borel space. Recall that
$(\mathbb{X}^{k},\mathfrak{X}^{\otimes k})$ is also standard Borel for all
$k\in\mathbb{N}_{+}$. For all
$(X_{1},\dots,X_{k}),(X_{1}^{\prime},\dots,X_{k}^{\prime})\in\mathbb{X}^{k}$,
we define

$(X_{1},\dots,X_{k})\sim_{k}(X_{1}^{\prime},\dots,X_{k}^{\prime})$

if and only if there exists a permutation $\pi$ of $\\{1,\dots,k\\}$ such that

$(X_{1},\dots,X_{k})=\big{(}X_{\pi(1)}^{\prime},\dots,X_{\pi(k)}^{\prime}\big{)}\text{.}$

Then $\sim_{k}$ is an equivalence relation on $\mathbb{X}^{k}$. Tuples in
$\mathbb{X}^{k}$ are equivalent under $\sim_{k}$ if and only if they contain
every individual element the exact same number of times. Thus, the quotient
space $\mathbb{X}^{k}\mkern-2.0mu/\mkern-1.0mu{\sim_{k}}$ can be identified
with the set $\mathcal{B}_{k}(\mathbb{X})$ of bags of cardinality exactly $k$
over $\mathbb{X}$. Note that in the case $k=0$,
$\mathbb{X}^{0}\mkern-2.0mu/\mkern-1.0mu{\sim_{0}}$ (by convention) consists
of a single distinguished point representing the empty realization. The space

$\bigcup_{k=0}^{\infty}\mathbb{X}^{k}\mkern-2.0mu/\mkern-1.0mu{\sim_{k}}=\bigcup_{k=0}^{\infty}\mathcal{B}_{k}(\mathbb{X})=\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$

is one of the canonical and equivalent choices for the sample space for a
finite point process on $\mathbb{X}$ [Mac75]. The original construction of
[Moy62] considers the _symmetrization_
$\operatorname{sym}\colon\bigcup_{k=0}^{\infty}\mathbb{X}^{k}\to\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$
where for all $(X_{1},\dots,X_{k})\in\mathbb{X}^{k}$ it holds that

$\operatorname{sym}(X_{1},\dots,X_{k})=[(X_{1},\dots,X_{k})]_{\sim_{k}}=\left\\{\middle\\{\mathopen{}X_{1},\dots,X_{k}\mathclose{}\middle\\}\right\\}\text{.}$

Then $\bigoplus_{k=1}^{\infty}\mathfrak{X}^{\otimes k}$ is the natural
$\sigma$-algebra on $\bigcup_{k\in\mathbb{N}}\mathbb{X}^{k}$. The
$\sigma$-algebra on $\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$ is then defined
as

$\big{\\{}\bm{B}\subseteq\mathcal{B}_{\mathsf{fin}}(\mathbb{X})\colon\operatorname{sym}^{-1}(\bm{B})\in{\textstyle\bigoplus_{k=0}^{\infty}}\mathfrak{X}^{\otimes
k}\big{\\}}\text{,}$ (3)

that is, as the $\sigma$-algebra on $\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$
induced by
$\operatorname{sym}\colon\bigcup_{k=0}^{\infty}\mathbb{X}^{k}\to\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$.
Note that this is indeed a $\sigma$-algebra on
$\mathcal{B}_{\mathsf{fin}}(\mathbb{X})$, cf. [Kal02, Lemma 1.3].

######  Remark 6 (cf. [Moy62, Section 2]).

A set $\bm{X}\in\mathfrak{X}^{\otimes k}$ is called _symmetric_ , if for all
$(X_{1},\dots,X_{k})\in\mathbb{X}^{k}$ it holds that
$(X_{1},\dots,X_{k})\in\bm{X}$ implies
$\big{(}X_{\pi(1)},\dots,X_{\pi(k)}\big{)}\in\bm{X}$ for all permutations
$\pi$ of $\\{1,\dots,k\\}$. The function
$\bm{X}\mapsto\operatorname{sym}(\bm{X})$ is a bijection between the symmetric
sets $\bm{X}$ in $\bigoplus_{k=0}^{\infty}\mathfrak{X}^{\otimes k}$ and the
sets of 3.

An equivalent, but technically more convenient construction is motivated by
interpreting point processes as _random counting measures_ [DVJ08]. For
$\bm{X}\in\mathfrak{X}$ and $n\in\mathbb{N}$, let

$\\#(\bm{X},n)\coloneqq\big{\\{}B\in\mathcal{B}_{\mathsf{fin}}(\mathbb{X})\colon\lvert
B\rvert_{\bm{X}}={\textstyle\sum_{X\in\bm{X}}}\lvert
B\rvert_{X}=n\big{\\}}\text{,}$

that is, $\\#(\bm{X},n)$ is the set of finite bags over $\mathbb{X}$
containing exactly $n$ elements from $\bm{X}$, counting multiplicities. The
sets $\\#(\bm{X},n)$ with $\bm{X}\in\mathfrak{X}$ and $n\in\mathbb{N}$ are
called _counting events_. The _counting $\sigma$-algebra_
$\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{X})$
on $\mathbb{X}$ is the $\sigma$-algebra generated by all counting events.

######  Fact 7 ([Moy62, Theorem 3.2]).

The $\sigma$-algebra from 3 coincides with
$\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{X})$.
∎

A _finite point process_ with standard Borel state space
$(\mathbb{X},\mathfrak{X})$ is a probability space
$\big{(}\mathcal{B}_{\mathsf{fin}}(\mathbb{X}),\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{X}),P\big{)}$.
A finite point process is _simple_ if
$P\big{(}\mathcal{P}_{\mathsf{fin}}(\mathbb{X})\big{)}=1$, that is, if its
realizations are almost surely sets.

##  3\. Probabilistic Databases

In this section, we introduce our framework for infinite probabilistic
databases and their query semantics. To begin with, we recall the conventional
formal definition of probabilistic databases as it is found in textbooks on
the subject [SORK11, VdBS17]:

[Finite Probabilistic Databases; adapted from [SORK11, Section 2.2]] Let
$\tau$ be a database schema and let $\mathbb{U}$ be a universe. A
_probabilistic database (PDB)_ $\mathcal{D}$ over $\tau$ and $\mathbb{U}$ is a
probability space
$\mathcal{D}=\big{(}\mathord{\mathbb{D}\mathbb{B}},\mathcal{P}(\mathord{\mathbb{D}\mathbb{B}}),P\big{)}$
where $\mathord{\mathbb{D}\mathbb{B}}$ is a finite set of database instances
over $\tau$ and $\mathbb{U}$.

From a probability theoretic point of view, Section 3 is a severe limitation
to the vast expressive power of stochastic models, only allowing probability
distributions over finitely many alternative database instances. As an
example, in a setting such as that of Section 2 (the database of temperature
measurements), we would typically model noise or uncertainty in the sensor
measurements by continuous distributions. This directly leads to (even
uncountably) infinite probability spaces that are not covered by the typical
textbook definition of probabilistic databases (Section 3). In [GL19], we
introduced the following general notion of probabilistic databases as
probability spaces of database instances:

[see [GL19, Definition 3.1]] Let $\tau$ be database schema and let
$\mathbb{U}$ be a universe. Suppose that $\mathfrak{F}$ is a $\sigma$-algebra
on the space $\mathbb{F}_{[\tau,\mathbb{U}]}$ of all
$(\tau,\mathbb{U})$-facts. A _probabilistic database (PDB)_ $\mathcal{D}$ over
$\tau$ and $\mathbb{U}$ is a probability space
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
where
$\mathord{\mathbb{D}\mathbb{B}}\subseteq\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}$
and $\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$ is a $\sigma$-algebra on
$\mathord{\mathbb{D}\mathbb{B}}$ satisfying

$\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{\bm{F}}>0\big{\\}}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

for all $\bm{F}\in\mathfrak{F}$.

Therein, the sample space $\mathord{\mathbb{D}\mathbb{B}}$ may be infinite,
even uncountable. While we only discussed set PDBs in [GL19], we broaden the
definition to support bag instances here. In any case, it was left open in
[GL19], how to construct such probability spaces, let alone how to obtain
suitable measurable spaces
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$.
This is no longer a trivial task once $\mathord{\mathbb{D}\mathbb{B}}$ is
uncountable. In this section, we provide a general construction for such
measurable spaces.

######  Remark 8.

At this point, we want to stress again the meaning of our terminology. In
general probabilistic databases there are lots of components, on different
levels of abstraction that could, in principle, be infinite spaces. The term
_infinite_ probabilistic databases is derived from the notion of an _infinite_
probability space, meaning that the sample space is of infinite size. Still,
in the PDBs we consider in this paper, database instances themselves (the
concrete outcomes, or realizations of a PDB) are always finite collections of
facts. The framework we discribe here is not suitable for discussing
probability spaces over infinite database instances in the sense of [AHV95,
Section 5.6], such as _constraint databases_ [KLP00].

###  3.1. Probabilistic Databases are Finite Point Processes

Our counstruction of measurable spaces of database instances stems from
interpreting a probabilistic database as a finite point process over the space
of possible facts.

_From now on, we only consider database schemas $\tau$ in combination with
sorted universes $\mathbb{U}$ where all attribute domains are Polish._

We first construct the measurable space of facts over $\tau$ and $\mathbb{U}$.
For all $A\in\mathcal{A}$, by assumption, the domain
$\mathbb{A}\coloneqq\operatorname{dom}(A)$ is Polish. Equipping it with its
Borel $\sigma$-algebra $\mathfrak{A}$ thus yields a standard Borel space
$(\mathbb{A},\mathfrak{A})$. Now let $R\in\tau$ be a relation symbol with
$\operatorname{sort}(R)=(A_{1},\dots,A_{k})$, so that the standard Borel
spaces belonging to the attribute names $A_{1},\dots,A_{k}$ are
$(\mathbb{A}_{1},\mathfrak{A}_{1}),\dots,(\mathbb{A}_{k},\mathfrak{A}_{k})$.
Recall from 1, that the set $\mathbb{T}_{R}$ of $R$-tuples is the product of
the attribute domains in $R$. Naturally, $\mathbb{T}_{R}$ is equipped with its
product $\sigma$-algebra

$\mathfrak{T}_{R}\coloneqq\bigotimes_{i=1}^{k}\mathfrak{A}_{i}\text{.}$ (4)

Likewise, the set $\mathbb{F}_{R}$ of $R$-facts is equipped with the
$\sigma$-algebra

$\mathfrak{F}_{R}\coloneqq\big{\\{}\emptyset,\\{R\\}\big{\\}}\otimes\mathfrak{T}_{R}$

(cf. 2). As the set $\mathbb{F}$ of all facts (over $\tau$ and $\mathbb{U}$)
is the disjoint union of all the $\mathbb{F}_{R}$, it is naturally equipped
with the disjoint union $\sigma$-algebra

$\mathfrak{F}\coloneqq\bigoplus_{R\in\tau}\mathfrak{F}_{R}\text{.}$

We reenact these definitions for our running example (Section 2). Recall that
the attribute names $A\in\\{\text{RoomNo},\text{Person},\text{Date}\\}$, have
domain $\Sigma^{*}$ for some (finite) alphabet $\Sigma$. As $\Sigma^{*}$ is
countably infinite, we equip this space with its powerset $\sigma$-algebra,
$\mathcal{P}(\Sigma^{*})$. For the attribute TempRec, we assume the measurable
space to be $(\mathbb{R},\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{R}))$,
where $\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{R})$ is the Borel
$\sigma$-algebra on $\mathbb{R}$. Given the sorts of the relation names Office
and TempRec, we have the tuple spaces
$\mathbb{T}_{\text{Office}}=\Sigma^{*}\times\Sigma^{*}$ and
$\mathbb{T}_{\text{TempRec}}=\Sigma^{*}\times\Sigma^{*}\times\mathbb{R}$.
Following (4), the corresponding $\sigma$-algebras are

$\mathfrak{T}_{\text{Office}}=\mathcal{P}(\Sigma^{*})\otimes\mathcal{P}(\Sigma^{*})$

and

$\mathfrak{T}_{\text{TempRec}}=\mathcal{P}(\Sigma^{*})\otimes\mathcal{P}(\Sigma^{*})\otimes\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{R})\text{.}$

That is, $\mathfrak{T}_{\text{Office}}$ is the $\sigma$-algebra generated by
all events of the shape $L_{1}\times L_{2}$ where
$L_{1},L_{2}\subseteq\Sigma^{*}$, and $\mathfrak{T}_{\text{TempRec}}$ is the
$\sigma$-algebra generated by all events of the shape $L_{1}\times L_{2}\times
B$ where $L_{1},L_{2}\subseteq\Sigma^{*}$ and $B$ is a Borel set in
$\mathbb{R}$. The spaces of Office\- and TempRec-facts are given by

$\mathbb{F}_{\text{Office}}=\text{Office}\big{(}\mathbb{T}_{\text{Office}}\big{)}=\big{\\{}\text{Office}(r,s)\colon
r,s\in\Sigma^{*}\big{\\}}$

and

$\mathbb{F}_{\text{TempRec}}=\text{TempRec}\big{(}\mathbb{T}_{\text{TempRec}}\big{)}=\big{\\{}\text{TempRec}(r,d,\theta)\colon
r,d\in\Sigma^{*}\text{ and }\theta\in\mathbb{R}\big{\\}}\text{.}$

For example, (assuming that the alphabet $\Sigma$ contains the respective
symbols), it holds that $\text{Office}(\text{\small 4108},\text{\small
Bob})\in\mathbb{F}_{\text{Office}}$, and $\text{TempRec}(\text{\small
4108},\text{\small 2021-07-12},\text{\small
20.5})\in\mathbb{F}_{\text{TempRec}}$. The $\sigma$-algebras on these spaces
of facts are directly obtained from the $\sigma$-algebras on the tuple spaces:
$\mathfrak{F}_{\text{Office}}=\mathcal{P}\big{(}\\{\text{Office}\\}\big{)}\otimes\mathfrak{T}_{\text{Office}}$
and
$\mathfrak{F}_{\text{TempRec}}=\mathcal{P}\big{(}\\{\text{TempRec}\\}\big{)}\otimes\mathfrak{T}_{\text{TempRec}}$.
Finally,

$\mathbb{F}=\mathbb{F}_{\text{Office}}\cup\mathbb{F}_{\text{TempRec}}$

is the space of all facts, with $\sigma$-algebra

$\mathfrak{F}=\mathfrak{F}_{\text{Office}}\oplus\mathfrak{F}_{\text{TempRec}}\text{.}$

For example, consider the sets

$\displaystyle\bm{F}_{1}$
$\displaystyle=\big{\\{}f\in\mathbb{F}_{\text{Office}}\colon
f=\text{Office}(\text{\small 4108},s)\text{ for some }s\in\Sigma^{*}\big{\\}}$
and $\displaystyle\bm{F}_{2}$
$\displaystyle=\big{\\{}f\in\mathbb{F}_{\text{TempRec}}\colon
f=\text{TempRec}(\text{\small 4108},d,\theta)\text{ for some
}d\in\Sigma^{*}\text{ and }\theta\in[21,23]\big{\\}}\text{.}$

Then $\bm{F}_{1}\in\mathfrak{F}_{\text{Office}}$ and
$\bm{F}_{2}\in\mathfrak{F}_{\text{TempRec}}$. Note that due to the real
interval, $\bm{F}_{2}$ contains uncountably many facts. As
$\bm{F}_{1}\in\mathfrak{F}_{\text{Office}}$ and
$\bm{F}_{2}\in\mathfrak{F}_{\text{TempRec}}$, it holds that
$\bm{F}_{1}\cup\bm{F}_{2}\in\mathfrak{F}$.

The constructions of the various measurable spaces above all started from
standard Borel measurable spaces for the attribute domains, and then used the
basic constructions of product and disjoint union measurable spaces.
Therefore, Fact 5 immediately yields the following statement.

######  Lemma 9.

The spaces $\big{(}\mathbb{T}_{R},\mathfrak{T}_{R}\big{)}_{R\in\tau}$,
$\big{(}\mathbb{F}_{R},\mathfrak{F}_{R}\big{)}_{R\in\tau}$, and
$(\mathbb{F},\mathfrak{F})$ are standard Borel spaces.

Recall that
$\mathord{\mathbb{D}\mathbb{B}}=\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}=\mathcal{B}_{\mathsf{fin}}(\mathbb{F})$.
We equip $\mathord{\mathbb{D}\mathbb{B}}$ with the $\sigma$-algebra
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}\coloneqq\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{F})$
from Section 2.

A _standard probabilistic database (standard PDB)_ over $\tau$ and
$\mathbb{U}$ is a probability space
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
with $\mathord{\mathbb{D}\mathbb{B}}=\mathcal{B}_{\mathsf{fin}}(\mathbb{F})$
and
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}=\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{F})$.

That is, a standard PDB is a finite point process over the state space
$(\mathbb{F},\mathfrak{F})$. Note that every standard PDB is a PDB in the
sense of Section 3. Standard PDBs that are simple are suitable for modeling
PDBs with set semantics.

We continue from Section 3.1. The space $\mathord{\mathbb{D}\mathbb{B}}$ of
database instances is exactly the space of finite bags over
$\mathbb{F}=\mathbb{F}_{\text{Office}}\cup\mathbb{F}_{\text{TempRec}}$ with
the counting $\sigma$-algebra
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}=\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{F})$.
This means, for example that the set

$\\#(\bm{F}_{2},3)=\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{\bm{F}_{2}}=3\big{\\}}$

is measurable (i. e., an event) in
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$.
This is the set of database instances over $\mathbb{F}$ that contain exactly
three facts of the shape $\text{TempRec}(\text{\small 4108},d,\theta)$ where
$d$ is an arbitrary string and $21\leq\theta\leq 23$. Note that these three
facts need not be distinct, as facts are allowed to be present with
multiplicities. A standard probabilistic database of the example schema is
just a probability space with underlying measurable space
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$.
In particular, in these PDBs, events such as $\\#(\bm{F}_{2},3)$ carry a
probability.

######  Lemma 10.

A standard PDB
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
is a standard Borel space itself.

######  Proof 3.1.

In [DVJ08, Proposition 9.1.IV], it is shown that the space of
$\mathbb{N}\cup\\{\infty\\}$-valued counting measures on a standard Borel
space (with the property of being finite on bounded sets) is a Polish space,
whose $\sigma$-algebra is generated by the functions that map a counting
measure $\mu$ to $\mu(\bm{F})\in\mathbb{N}\cup\\{\infty\\}$ for all
$\bm{F}\in\mathfrak{F}$. Restricting this space to integer-valued counting
measures, and equipping it with the corresponding subspace $\sigma$-algebra
yields a standard Borel space. This space is isomorphic to
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$
via the function that maps a counting measure $\mu$ to the database instance
whose multiplicity mapping is given by $\mu$.111Isomorphic here means that
this function is bijective and measurable both ways; bijectivity is clear, and
being measurable both ways stems from the fact that the generating events of
the $\sigma$-algebra of the space of integer-valued counting measures on
$(\mathbb{F},\mathfrak{F})$ are identified with the counting events in
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$,
i. e. the generating events of
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

_From now on, all PDBs we consider are standard PDBs._ When we speak of PDBs,
it is understood to refer to standard PDBs, unless explicitly stated
otherwise.

###  3.2. The Possible Worlds Semantics of Queries and Views

_Views_ are mappings between database instances. That is, a view $V$ is a
function
$V\colon\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]}\to\mathord{\mathbb{D}\mathbb{B}}_{[\tau^{\prime},\mathbb{U}^{\prime}]}$
for some database schemas $\tau$ and $\tau^{\prime}$ and universes
$\mathbb{U}$ and $\mathbb{U}^{\prime}$. We call $\tau$ the _input_ , and
$\tau^{\prime}$ the _output schema_ of the view $V$. If $\tau^{\prime}$
consists of a single relation symbol only, we call $V$ a _query_. Queries are
typically denoted by $Q$. Usually, queries and views are given as syntactic
expressions in some query language. As usual, we blur the distinction between
a query or view, and its syntactic representation. In the following, we let
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})=\big{(}\mathord{\mathbb{D}\mathbb{B}}_{[\tau,\mathbb{U}]},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{[\tau,\mathbb{U}]}\big{)}$,
and
$(\mathord{\mathbb{D}\mathbb{B}}_{V},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V})=\big{(}\mathord{\mathbb{D}\mathbb{B}}_{[\tau^{\prime},\mathbb{U}^{\prime}]},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{[\tau^{\prime},\mathbb{U}^{\prime}]}\big{)}$.

Let
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
be a PDB and let
$V\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{V}$
be a view. For $\bm{D}\subseteq\mathord{\mathbb{D}\mathbb{B}}$, the image of
$\bm{D}$ under $V$ is

$V(\bm{D})\coloneqq\\{V(D)\colon
D\in\bm{D}\\}\subseteq\mathord{\mathbb{D}\mathbb{B}}_{V}\text{.}$

If the function $V$ is
$(\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V})$-measurable,
then $V$ introduces a push-forward measure $P_{V}$ on
$(\mathord{\mathbb{D}\mathbb{B}}_{V},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V})$
via

$P_{V}(\bm{D})\coloneqq
P\big{(}V^{-1}(\bm{D})\big{)}=P\big{(}\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon
V(D)\in\bm{D}\\}\big{)}$ (5)

for all $\bm{D}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V}$. In this
case

$V(\mathcal{D})\coloneqq\big{(}\mathord{\mathbb{D}\mathbb{B}}_{V},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V},P_{V}\big{)}$

is a PDB.

######  Remark 11.

The kind of semantics we introduce here is the natural generalization of a
standard choice for semantics on probabilistic databases. Conceptually, we
consider queries and views that have well-defined semantics on traditional
database instances. That is, they get as input a database instance, and as
output, produce a new database instance. Such a semantics is lifted to
probabilistic databases by applying the query or view on every possible world,
and weighting it according to the probability measure of the input PDB. This
notion of semantics is commonly called the _possible answer sets semantics_ of
probabilistic databases [SORK11, Section 2.3.1]. It (or, to be more precise,
its discrete version) has previously been also called _possible worlds
semantics (of queries)_ [DS07], which is the term we prefer to use in this
work, as we deem it the natural choice on how to define query (or view)
semantics on PDBs that are modelled as a collection of possible worlds with a
probability distribution, matching the standard definition of output
probabilities of a (measurable) function on a probability space (cf. [Gre09]).
Note that strictly speaking, this overloads the term “possible worlds
semantics”: in reference to PDBs, “possible worlds semantics” means the
definition of PDBs as probability spaces over database instances, whereas in
reference to queries or views, it means the definition of the output of a
query with respect to an application per possible world, as in (5).

For queries, another semantics has been discussed in literature, wich was
later dubbed the _possible answers semantics_ [SORK11, Section 2.3.2]. Under
this semantics, the output of a query is the collection of tuples that may
appear as an answer to the query (i. e. the tuples that appear in the output
possible worlds under the possible worlds semantics), together with their
marginal probability. For finite PDBs, this notion makes sense, because the
result will be much smaller than a description of the whole output probability
under possible worlds semantics. For uncountable infinite PDBs, however, this
is not of much use. As soon as continuous probability distributions are
involved, we naturally encounter PDBs where the marginal probability of every
particular fact (or tuple in the output) may be zero.

We note that to the best of our knowledge, there has been no formal
description of these semantics when duplicates are allowed. Note that for
_Boolean queries_ with set semantics, i. e., queries whose output is either
$\\{()\\}$ (true) or $\emptyset$ (false), both of the above semantics are
essentially equivalent: the only possible answer tuple is the empty tuple
$()$, and the only possible worlds of the answer are $\emptyset$ and
$\\{()\\}$.

Note that if $V$ fails to be measurable, then 5 is not well-defined. In this
case, $V$ has no meaningful semantics on probabilistic databases! Thus,
discussing the measurability of views and queries is an issue that requires
attention. The following example shows that there are inconspicuous, seemingly
simple queries that are not measurable.

Consider $\mathbb{U}=\mathbb{U}^{\prime}=\mathbb{R}$, together with the
database schemas $\tau=\tau^{\prime}$ consisting of the single, unary relation
symbol $R$ with domain $\mathbb{T}_{R}=\mathbb{R}$ (equipped with the Borel
$\sigma$-algebra). Let
$\bm{B}\in\mathfrak{B\mkern-1.0muo\mkern-0.2mur}(\mathbb{R}^{2})$. We define a
function
$Q_{\bm{B}}\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}^{\prime}$
(where
$\mathord{\mathbb{D}\mathbb{B}}^{\prime}=\mathord{\mathbb{D}\mathbb{B}}_{[\tau^{\prime},\mathbb{U}^{\prime}]}$)
as follows.

$Q_{\bm{B}}(D)\coloneqq\begin{cases}D&\text{if }D\text{ is a singleton
}\left\\{\middle\\{\mathopen{}R(x)\mathclose{}\middle\\}\right\\}\text{ and
there exists a }y\in\mathbb{R}\text{ s.\,t. }(x,y)\in\bm{B}\text{ and}\\\
\emptyset&\text{otherwise.}\end{cases}$

Observe that
$Q_{B}^{-1}\big{(}\mathord{\mathbb{D}\mathbb{B}}^{\prime}\big{)}=\big{\\{}\left\\{\middle\\{\mathopen{}R(x)\mathclose{}\middle\\}\right\\}\colon
x\in\operatorname{proj}_{1}(\bm{B})\big{\\}}$, where

$\operatorname{proj}_{1}(\bm{B})=\\{x\in\mathbb{R}\colon\text{ there is
}y\in\mathbb{R}\text{ s.\,t. }(x,y)\in B\\}\text{.}$

It is well known that there are Borel sets $\bm{B}\subseteq\mathbb{R}^{2}$
with the property that $\operatorname{proj}_{1}(\bm{B})$ is _not_ Borel in
$\mathbb{R}$ [Kec95, Theorem 14.2 (Souslin) and Exercise 14.3]. In this case,
$Q_{\bm{B}}$ is not measurable even though $\bm{B}$ is Borel.

###  3.3. Assembling Views from Queries

A view $V$ with output relations $R_{1},\dots,R_{k}$ can be identified with a
set of queries $Q_{1},\dots,Q_{k}$, one per output relation symbol, such that
for all $D\in\mathord{\mathbb{D}\mathbb{B}}$ it holds that

$V(D)=\bigcup_{i=1}^{k}Q_{i}(D)\text{.}$

Let $(\mathbb{F}_{V},\mathfrak{F}_{V})$ be the measurable space of facts
belonging to
$(\mathord{\mathbb{D}\mathbb{B}}_{V},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{V})$
and let $(\mathbb{F}_{Q_{i}},\mathfrak{F}_{Q_{i}})$ be the measurable space of
facts belonging to
$(\mathord{\mathbb{D}\mathbb{B}}_{Q_{i}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q_{i}})$.
From the above equality, we get that for all
$D\in\mathord{\mathbb{D}\mathbb{B}}$, all $\bm{F}\in\mathfrak{F}_{V}$, and all
$n\in\mathbb{N}$ it holds that $\lvert V(D)\rvert_{\bm{F}}=n$ if and only if
there exist non-negative integers $n_{1},\dots,n_{k}$ with
$n_{1}+\dots+n_{k}=n$ and the property that $\lvert
Q_{i}(D)\rvert_{\bm{F}\cap\mathbb{F}_{Q_{i}}}=n_{i}$ for all $i=1,\dots,k$.
Note that this condition corresponds to an event given by a countable union of
counting events. Thus, we obtain the following.

######  Lemma 12.

The view $V$ is measurable if and only if $Q_{i}$ is measurable for all
$i=1,\dots,k$.

By the merit of Lemma 12, we only need to discuss the measurability of
queries.

##  4\. General Measurability Criteria

In the remainder of the paper we establish measurability results for various
types of queries as they typically appear in database applications. In this
section, we set out the general setup of said investigation and introduce some
general measurability results that are not yet tailored to specific query
languages.

###  4.1. Setup

Henceforth, we adhere to the following notational conventions when discussing
the measurability of a query $Q$.

[Inputs] The input schema of $Q$ is
$\tau=(\mathcal{A},\mathcal{R},\operatorname{sort})$. We consider input
instances over $\tau$, and the sorted universe $\mathbb{U}$ (with all
attribute domains Polish).

The associated fact space is denoted as $(\mathbb{F},\mathfrak{F})$, with
subspaces $(\mathbb{F}_{R},\mathfrak{F}_{R})$ for all $R\in\tau$. The space of
$R$-tuples is given as $(\mathbb{T}_{R},\mathfrak{T}_{R})$. For all
$R\in\tau$, we fix a compatible Polish metric $d_{R}$ on $\mathbb{T}_{R}$ and
let $\mathbb{T}_{R}^{*}$ be a countable, dense set in $\mathbb{T}_{R}$. With
abuse of notation, we denote the corresponding metric on $\mathbb{F}_{R}$ by
$d_{R}$ as well. Note that $\mathbb{F}^{*}_{R}\coloneqq\mathbb{T}_{R}^{*}$ is
a countable dense set in $\mathbb{F}_{R}$.

We denote the input (standard) PDB under consideration by
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$,
where $\mathord{\mathbb{D}\mathbb{B}}=\mathcal{B}_{\mathsf{fin}}(\mathbb{F})$
and
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}=\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{F})$.

[Outputs] The output schema of $Q$ is
$\tau_{Q}=(\mathcal{A}_{Q},\mathcal{R}_{Q},\operatorname{sort}_{Q})$ where
$R_{Q}$ is the only relation symbol in $\mathcal{R}_{Q}$. We consider output
instances over $\tau_{Q}$, and sorted universe $\mathbb{U}_{Q}$ (with all
attribute domains Polish). The associated fact space is denoted as
$(\mathbb{F}_{Q},\mathfrak{F}_{Q})$. The space of $R_{Q}$-tuples is given as
$(\mathbb{T}_{Q},\mathfrak{T}_{Q})$. We fix a compatible Polish metric $d_{Q}$
on $\mathbb{T}_{Q}$, and a countable dense set $\mathbb{T}_{Q}^{*}$ in
$\mathbb{T}_{Q}$. Again $d_{Q}$ will also denote the corresponding metric on
$\mathbb{F}_{Q}$, and the set $\mathbb{F}_{Q}^{*}$ is countable and dense in
$\mathbb{F}_{Q}$.

The output measurable space is denoted by
$(\mathord{\mathbb{D}\mathbb{B}}_{Q},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q})$,
were
$\mathord{\mathbb{D}\mathbb{B}}_{Q}=\mathcal{B}_{\mathsf{fin}}(\mathbb{F}_{Q})$
and
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q}=\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{F}_{Q})$.

Thus, our goal is to show that a given function
$Q\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{Q}$
is
$(\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q})$-measurable.

######  Remark 13.

We have some straightforward measurability criteria from the general
properties of measurable functions and the used $\sigma$-algebras.

  1. (1)

By Fact 11, to show the measurability of a query $Q$, it suffices to show that

$\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\\}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

for all $\bm{F}\in\mathfrak{F}_{Q}$ and all $n\in\mathbb{N}$, as the counting
events generate the $\sigma$-algebra
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q}$. This remains true, if we
replace “$=n$” with “$\geq n$” or only require $n\in\mathbb{N}_{+}$.

  2. (2)

By Fact 12, compositions of measurable functions are measurable. That is, for
query languages whose semantics are defined inductively over the structure of
their syntactic expression, it suffices to show measurability for the basic
building blocks.

  3. (3)

By Fact 32, limits of measurable queries are measurable.

###  4.2. The Mapping Theorem

The following is a partial restatement of what is known as the _mapping
theorem_ of point processes. The original theorem from point process theory
also involves the transfer of certain properties to the image space [LP17,
Theorem 5.1] which is, however, of less importance for the remainder of the
paper. Moreover, we allow partial transformations as long as their domain is
measurable (and this does not invalidate the measurability statement from the
mapping theorem).

######  Theorem 14 (cf. [LP17, Theorem 5.1]).

Let $\bm{F}_{q}\in\mathfrak{F}$. If $q\colon\bm{F}_{q}\to\mathbb{F}_{Q}$ is
$(\mathfrak{F},\mathfrak{F}_{Q})$-measurable, then the function
$Q\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{Q}$
with

$\lvert Q(D)\rvert_{f}\coloneqq\begin{cases}\lvert
D\rvert_{q^{-1}(f)}&\text{if }q^{-1}(f)\neq\emptyset\text{ and}\\\
0&\text{otherwise,}\end{cases}$

for all $D\in\mathord{\mathbb{D}\mathbb{B}}$ is a measurable query. ∎

In this (restricted) form, the theorem is straightforward to verify.

######  Proof 4.1.

Let $\bm{F}_{q}\in\mathfrak{F}$ and $q\colon\bm{F}_{q}\to\mathbb{F}_{Q}$ be
measurable. Now let $\bm{F}\in\mathfrak{F}_{Q}$ and $n\in\mathbb{N}$. Then

$\lvert Q(D)\rvert_{\bm{F}}=n\iff\lvert D\rvert_{q^{-1}(\bm{F})}=n\text{.}$

Since $q^{-1}(\bm{F})\in\mathfrak{F}$, the claim follows.

Intuitively, the theorem states that whenever we have a measurable
transformation of the fact space of a a PDB, then we obtain a measurable query
when we just apply this transformation to all facts in the database
instances.222Functions of the shape of $Q$ in Theorem 14 are a special case of
“mapping constructs” (applying a function to every element of a bag) that can
be found in previously considered bag query languages [GM96, LW97].

We continue our running example. Recall that $\mathbb{F}_{\text{TempRec}}$ is
the space of facts $\text{TempRec}(r,d,\theta)$ where $r$ and $d$ are strings
and $\theta$ is a real number. Consider the function
$q\colon\mathbb{F}_{\text{TempRec}}\to\mathbb{F}_{\text{TempRec}}$ that
increases the temperature by $2$ °C, i. e. with

$q\big{(}\text{TempRec}(r,d,\theta)\big{)}=\text{TempRec}(r,d,\theta+2)\text{.}$

Then $q$ is
$(\mathfrak{F}_{\text{TempRec}},\mathfrak{F}_{\text{TempRec}})$-measurable.
This follows, since the addition of $2$ is a continuous function on
$\mathbb{R}$ and by the construction of the measurable spaces.

Thus, by Theorem 14, the query that, given an instance $D$, applies $q$ to
every fact in $D$ (i. e. increasing temperatures by $2$) is measurable.

While Theorem 14 is a nice statement, it fails to cover most queries of
interest, as database queries often consider and manipulate multiple tuples at
once. Such transformations are not captured by Theorem 14. We therefore need
measurability statements beyond Theorem 14.

###  4.3. Continuous One-to-One Decompositions

In this subsection we introduce a new criterion for query measurability that
overcomes the aforementioned limitation of Theorem 14.

######  Lemma 15.

Let
$Q\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{Q}$.
Then $Q$ is measurable if there exists some $k\in\mathbb{N}_{+}$, pairwise
distinct $R_{1},\dots,R_{k}\in\tau$ and functions
$q_{i}\colon\mathbb{F}_{Q}\to\mathbb{F}_{R_{i}}$ for $i=1,\dots,k$ with the
following properties:

  1. (1)

For all $n\in\mathbb{N}_{+}$ there is a set
$N_{Q}(n)\in\mathbb{N}^{k}\setminus\\{(0,\dots,0)\\}$ with

$\lvert Q(D)\rvert_{f}=n\iff\big{(}\lvert D\rvert_{q_{1}(f)},\dotsc,\lvert
D\rvert_{q_{k}(f)}\big{)}\in N_{Q}(n)$

for all $D\in\mathord{\mathbb{D}\mathbb{B}}$ and all $f\in\mathbb{F}_{Q}$.

  2. (2)

For all $i=1,\dots,k$, the function $q_{i}$ is injective and continuous.

Think of the functions $q_{i}$ as providing a decomposition of $R_{Q}$-facts
into the $R_{i}$-facts of the input instance they originated from under the
query. The set $N_{Q}(n)$ provides the recipe, how the number of occurrences
of a fact in the output is determined by the counts of its decompositions in
the input. That is, requirement 1 stipulates the query semantics. The
topological requirement 2 ensures measurability.

A simple example application that we ask the reader to have in mind is that of
a difference operator on bag instances (this is in fact, one of our later
applications, where it is made precise). Intuitively, if $Q$ is the difference
of relations $R$ and $S$, then the number of times a tuple $t$ occurs in the
output is given by the number of times it appears in $R$, minus the number of
times it appears in $S$. This fits the pattern of Lemma 15 with functions
$q_{1},q_{2}$ being the identity $t\mapsto t$, and $N_{Q}(n)$ being the set of
pairs $(n_{1},n_{2})$ with $\max(0,n_{1}-n_{2})=n$. Lemma 15 provides a
generalization of this setup, allowing for much more general functions
$q_{i}$, and sets $N_{Q}(n)$.

######  Remark 16.

This is vaguely related to the notion of _(why- and how-)provenance_ of a
tuple in the output of a view [GKT07], with the functions $q_{i}$ providing
the “why-information”, and the set $N_{Q}(n)$ providing the “how”. Lemma 15
now only applies to queries inducing a very particular provenance structure
(as governed by the $q_{i}$ and $N_{Q}(n)$).

######  Proof 4.2 (Proof of Lemma 15).

Let
$Q\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{Q}$,
let $k\in\mathbb{N}_{+}$. Let $R_{1},\dots,R_{k}$ be distinct relation symbols
in $\tau$. In the following, we write $(\mathbb{F}_{i},\mathfrak{F}_{i})$
instead of $(\mathbb{F}_{R_{i}},\mathfrak{F}_{R_{i}})$ for all $i=1,\dots,k$.
As required, let $q_{i}\colon\mathbb{F}_{Q}\to\mathbb{F}_{i}$ for all
$i=1,\dots,k$ and assume that 1 and 2 hold. We have to show that $Q$ is
measurable, which is settled, in particular, by showing that
$\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert Q(D)\rvert_{\bm{F}}\geq
n\\}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$ for all
$\bm{F}\in\mathfrak{F}_{Q}$ and all $n\in\mathbb{N}_{+}$.

Let $d$ be a fixed Polish metric on $\mathbb{F}_{Q}$ generating
$\mathfrak{F}_{Q}$ and let $\mathbb{F}_{Q}^{*}\subseteq\mathbb{F}_{Q}$ be
countable and dense in $\mathbb{F}_{Q}$. Let $\bm{F}\in\mathfrak{F}_{Q}$ and
$n\in\mathbb{N}_{+}$. We show that for all
$D\in\mathord{\mathbb{D}\mathbb{B}}$, it holds that $\lvert
Q(D)\rvert_{\bm{F}}\geq n$ is equivalent to the following condition.

######  Condition 17.

For some $\ell\in\mathbb{N}_{+}$ there exist
$n_{1},\dots,n_{\ell}\in\mathbb{N}$ with $n_{1}+n_{2}+\dots+n_{\ell}\geq n$,
and $(n_{ij})_{i=1,\dots,k\text{;}~{}j=1,\dots,\ell}$ with

$\big{(}n_{1j},\dots,n_{kj}\big{)}\in N_{Q}(n_{j})$ (6)

for all $j=1,\dots,\ell$; and there exists $\varepsilon_{0}>0$ such that for
all positive $\varepsilon<\frac{\varepsilon_{0}}{4}$ there are
$f_{1,\varepsilon}^{*},\dots,f_{\ell,\varepsilon}^{*}\in\mathbb{F}_{Q}^{*}$
with the following properties:

  1. (1)

For all $j,j^{\prime}=1,\dots,\ell$ with $j\neq j^{\prime}$ it holds that
$d_{Q}(f_{j,\varepsilon}^{*},f_{j^{\prime},\varepsilon}^{*})>\frac{\varepsilon_{0}}{2}$.

  2. (2)

For all $i=1,\dots,k$ and all $j=1,\dots,\ell$ it holds that $\lvert
D\rvert_{q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))}=n_{ij}$

An illustration of the situation of Condition 17 can be found in Figure 2. We
now prove both directions of the claimed equivalence.

$\Rightarrow$:

First assume that $\lvert Q(D)\rvert_{\bm{F}}\geq n>0$ and suppose that
$f_{1},\dots,f_{\ell}$ are (pairwise distinct) facts from $\bm{F}$ with the
property $\lvert D\rvert_{q_{i}(f_{j})}>0$ for at least one $i=1,\dots,k$ for
all $j=1,\dots,\ell$. Such $f_{1},\dots,f_{\ell}$, with
$\ell\in\mathbb{N}_{+}$, exist by requirement 1. Let $n_{j}\coloneqq\lvert
Q(D)\rvert_{f_{i}}$ for all $j=1,\dots,\ell$. Then $\sum_{j=1}^{\ell}n_{j}\geq
n$, and, according to 1, $\big{(}n_{1j},\dots,n_{kj}\big{)}\in N_{Q}(n_{j})$,
where $n_{ij}\coloneqq\lvert D\rvert_{q_{i}(f_{j})}$ for all $i=1,\dots,k$ and
$j=1,\dots,\ell$. We choose $\varepsilon_{0}>0$ such that

$\varepsilon_{0}<\min\big{\\{}d_{Q}(f_{j},f)\colon j=1,\dots,\ell,f\neq
f_{j},f\in Q(D)\big{\\}}$

and let $0<\varepsilon<\frac{\varepsilon_{0}}{4}$. Because
$\mathbb{F}_{Q}^{*}$ is dense in $\mathbb{F}_{Q}$, we can choose
$f_{1,\varepsilon}^{*},\dots,f_{\ell,\varepsilon}^{*}\in\mathbb{F}_{Q}$ such
that
$d_{Q}(f_{j},f_{j,\varepsilon}^{*})<\varepsilon<\frac{\varepsilon_{0}}{4}$ for
all $j=1,\dots,\ell$. Then from the triangle inequality it follows that

$d_{Q}(f_{j,\varepsilon}^{*},f_{j^{\prime},\varepsilon}^{*})\geq
d_{Q}\big{(}f_{j},f_{j^{\prime}}\big{)}-d_{Q}\big{(}f_{j,\varepsilon}^{*},f_{j}\big{)}-d_{Q}\big{(}f_{j^{\prime}},f_{j^{\prime},\varepsilon}^{*}\big{)}>\varepsilon_{0}-2\tfrac{\varepsilon_{0}}{4}=\tfrac{\varepsilon_{0}}{2}\text{.}$

In particular, since $\varepsilon<\tfrac{\varepsilon}{4}$, the balls
$B_{\varepsilon}(f_{j,\varepsilon}^{*})$ are pairwise disjoint and $f_{j}\in
B_{\varepsilon}(f_{j,\varepsilon}^{*})$ for all $j=1,\dots,\ell$. Moreover, by
the choice of $\varepsilon_{0}$, no fact $f$ from $Q(D)$ other than
$f_{1},\dots,f_{\ell}$ appears in the balls
$B_{\varepsilon}(f_{1,\varepsilon}^{*}),\dots
B_{\varepsilon}(f_{j,\varepsilon}^{*})$. Because $q_{i}$ is injective, it
follows that $q_{i}(f)\notin q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))$
for all $f\neq f_{j}$ appearing in $Q(D)$, and all $i=1,\dots,k$. This means
that for all $i=1,\dots,k$ and $j=1,\dots,\ell$ it holds that

$\lvert D\rvert_{q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))}=\lvert
D\rvert_{q_{i}(f_{j})}=n_{ij}\text{.}$

Thus, Condition 17 holds.

$\Leftarrow$:

Suppose that Condition 17 holds and let $\ell\in\mathbb{N}_{+}$,
$n_{1}+\dots+n_{\ell}\geq n$ and $n_{ij}$ for $i=1,\dots,k$ and
$j=1,\dots,\ell$, and $\varepsilon_{0}$ be given accordingly. Note that for
all $\varepsilon<\frac{\varepsilon_{0}}{4}$, the balls
$B_{\varepsilon}(f_{j,\varepsilon}^{*})$ are pairwise disjoint by condition 1.
Since $q_{i}$ is injective, the sets
$q_{i}\big{(}B_{\varepsilon}(f_{j,\varepsilon}^{*}))\big{)}$ are disjoint as
well. By 2, for all $i=1,\dots,k$, and all $j=1,\dots,\ell$ it holds that

$\lvert D\rvert_{q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))}=n_{ij}\text{.}$

If $\varepsilon$ is small enough, then for all $n_{ij}$ with $n_{ij}>0$ it
holds that there exists a single fact $f_{i,j,\varepsilon}\in
q_{i}(\bm{F})\cap q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))$ with the
property that $\lvert D\rvert_{f_{i,j,\varepsilon}}=n_{ij}$. To see this, note
that if the fact count $n_{ij}$ were distributed over multiple facts, then by
the injectivity of the functions $q_{i}$, these facts have pairwise different
preimages under $q_{i}$. For small enough $\varepsilon$, however,
$B_{\varepsilon}(f_{j,\varepsilon}^{*})$ can only contain one of these facts,
yielding a contradiction with 2. We now fix $\varepsilon$ small enough such
that the above holds, as well as an index $j=1,\dots,\ell$. Moreover, we pick
some $i(j)\in\\{1,\dots,k\\}$ with $n_{i(j),j}>0$ and define $f_{j}\coloneqq
q_{i(j)}^{-1}(f_{i(j),j,\varepsilon})$. As $q_{i(j)}$ is injective, it follows
that $f_{j}\in\bm{F}\cap B_{\varepsilon}(f_{j,\varepsilon}^{*})$. Without loss
of generality, we assume that $f_{j}\in
B_{\varepsilon^{\prime}}(f_{j,\varepsilon^{\prime}}^{*})$ for all
$0<\varepsilon^{\prime}<\varepsilon$.333Generally, it could happen that $j$
switches roles with some $j^{\prime}$ where
$(n_{1j^{\prime}},\dots,n_{kj^{\prime}})=(n_{1j},\dots,n_{kj})$. If there are
exactly $m$ indices $j$ for which the sequences $(n_{1j},\dots,n_{kj})$
coincide, the corresponding balls $B_{\varepsilon}(f_{j,\varepsilon}^{*})$ for
these indices have (at least) $m$ distinct accumulation points. This means
that
$\bigcap_{0<\varepsilon^{\prime}<\varepsilon}B_{\varepsilon^{\prime}}(f_{j,\varepsilon^{\prime}}^{*})=\\{f_{j}\\}$.

We claim that for all $i=1,\dots,k$ it then holds that

$\lvert D\rvert_{q_{i}(f_{j})}=n_{ij}\text{.}$

By choice, this already holds for $i=i(j)$. Suppose $i$ is an index with
$n_{ij}=0$. As $\lvert D\rvert_{q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))}=n_{ij}=0$ and $f_{j}\in
B_{\varepsilon}(f_{j,\varepsilon}^{*})$, it follows that $\lvert
D\rvert_{q_{i}(f_{j})}=0$. Now let $i$ be an index different from $i(j)$ such
that $n_{ij}>0$. We have argued before that then there exists a single fact
$f_{i,j,\varepsilon}\in q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))=n_{ij}$. Assume that
$f_{i,j,\varepsilon}\neq q_{i}(f_{j})$. Then
$q_{i}^{-1}(f_{i,j,\varepsilon})\neq f_{j}$ and therefore, there is
$\varepsilon^{\prime}<\varepsilon$ such that
$q_{i}^{-1}(f_{i,j,\varepsilon^{\prime}})\notin
B_{\varepsilon}(f_{j,\varepsilon^{\prime}}^{*})$, leading to a contradiction
with 2. Thus, $f_{i,j,\varepsilon}=q_{i}(f_{j})$ and $\lvert
D\rvert_{q_{i}(f_{j})}=\lvert D\rvert_{f_{i,j,\varepsilon}}=n_{ij}$. From
property 1, it follows that $\lvert Q(D)\rvert_{f_{j}}=n_{j}$. Thus, since
$n_{1}+\dots+n_{\ell}\geq n$ and since the facts $f_{j}\in\bm{F}$ are pairwise
distinct, it follows that $\lvert Q(D)\rvert_{\bm{F}}\geq n$.

To conclude the proof, we argue that Condition 17 can be used to express
$\lvert Q(D)\rvert_{\bm{F}}\geq n$ as a countable combination of counting
events. Note that because $\mathbb{Q}_{+}$ is dense in $\mathbb{R}_{+}$, the
equivalence of $\lvert Q(D)\rvert_{\bm{F}}\geq n$ and Condition 17 still
holds, if the numbers $\varepsilon_{0}$ and $\varepsilon$ are additionally
required to be rational. Also, the fact sets in 2 are measurable in
$\mathfrak{F}_{i}$: the open balls are certainly measurable, and as $q_{i}$ is
injective and continuous, $q_{i}$ maps measurable sets to measurable sets by
Fact 4. Then the set of database instances
$D\in\mathord{\mathbb{D}\mathbb{B}}$ with Condition 17 is of the shape

$\bigcup_{\ell,(n_{i}),(n_{ij})}\bigcup_{\varepsilon_{0}}\bigcap_{\varepsilon}\bigcup_{(f_{j,\varepsilon}^{*})}\bigcap_{i,j}\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{q_{i}(\bm{F})\cap
q_{i}(B_{\varepsilon}(f_{j,\varepsilon}^{*}))}=n_{ij}\big{\\}}\text{,}$

with the indices ranging as in Condition 17 and $\varepsilon$,
$\varepsilon_{0}$ additionally restricted to $\mathbb{Q}$.

$\mathbb{F}_{Q}$$\mathbb{F}_{R_{1}}$$\mathbb{F}_{R_{2}}$$\bm{F}$$f_{j}$$f_{j,\varepsilon}^{*}$$B_{\varepsilon}(f_{j,\varepsilon}^{*})$$f_{j^{\prime}}$$f_{j^{\prime},\varepsilon}^{*}$$q_{1}(\bm{F})$$q_{2}(\bm{F})$$q_{1}$$q_{2}$
Figure 2. Illustration of Condition 17 in the case $k=2$. Note that
$f_{j,\varepsilon}^{*}$ itself need not necessarily lie in $\bm{F}$. The
dashed arrows indicate the intended convergence of $f_{j,\varepsilon}^{*}$ to
the fact $f_{j}$ as $\varepsilon\to 0$.

Incidentally, Theorem 14 is a special case of Lemma 15 for $k=1$ and with
$N_{Q}(n)\coloneqq\\{n\\}$ for all $n\in\mathbb{N}_{+}$.

###  4.4. Coarse Preimages

For $D\in\mathord{\mathbb{D}\mathbb{B}}$, and every relation symbol
$R\in\tau$, we let

$\bm{T}_{R}(D)\coloneqq\big{\\{}t\in\mathbb{T}_{R}\colon\lvert
D\rvert_{R(t)}>0\big{\\}}$

denote the set of $R$-tuples in $D$. Moreover, we let

$d_{R}(D)\coloneqq\begin{cases}\min\\{d_{R}(t,t^{\prime})\colon
t,t^{\prime}\in\bm{T}_{R}(D)\text{ with }t\neq t^{\prime}\\}&\text{if
}\big{\lvert}\bm{T}_{R}(D)\big{\rvert}\geq 2\text{ and}\\\
\infty&\text{otherwise.}\end{cases}$

That is, $d_{R}(D)$ is the smallest distance between any two $R$-tuples of $D$
(or $\infty$, if $D$ contains at most one $R$-fact).

Let $\varepsilon>0$. An instance $D\in\mathord{\mathbb{D}\mathbb{B}}$ is
called _$\varepsilon$ -coarse_ if for all $R\in\tau$ it holds that
$d_{R}(D)>\varepsilon$. We denote the set of $\varepsilon$-coarse instances by
$\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$.

Unfolding the definition, all instances in
$\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$ have the property that
their tuples (per relation) are sufficiently far apart with respect to the
metric on the respective space of tuples.

Consider our example of temperature recordings, but for simplicity (in order
for not having to discuss the metric on the product space), assume that there
is only one relation, with a single attribute for (real-valued) temperature
recordings. Then a database instance is $\varepsilon$-coarse precisely if the
temperatures occuring in its instances differ by more than $\varepsilon$
between distinct facts.

The following lemma states that the set of $\varepsilon$-coarse instances is
measurable for any $\varepsilon>0$.

######  Lemma 18.

It holds that
$\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$
for all $\varepsilon>0$.

######  Proof 4.3.

An instance $D\in\mathord{\mathbb{D}\mathbb{B}}$ is _not_
$\varepsilon$-coarse, if for some $R\in\tau$, there exist
$t_{1},t_{2}\in\bm{T}_{R}(D)$ such that $t_{1}\neq t_{2}$ and
$d_{R}(t_{1},t_{2})\leq\varepsilon$. We claim that this is the case if and
only if $D$ satisfies the following condition.

######  Condition 19.

There are $k_{1},k_{2}\in\mathbb{N}_{+}$ and $\varepsilon_{0}>0$ such that for
all $r\in\big{(}0,\varepsilon_{0}\big{)}$ there are
$t_{1,r}^{*},t_{2,r}^{*}\in\mathbb{T}_{R}^{*}$ with
$\varepsilon_{0}<d_{R}(t_{1,r}^{*},t_{2,r}^{*})<\varepsilon+2r$ such that

  1. (1)

$\lvert D\rvert_{R(B_{r}(t_{1,r}^{*}))}=k_{1}$ and

  2. (2)

$\lvert D\rvert_{R(B_{r}(t_{2,r}^{*}))}=k_{2}$.

The condition basically states that we can find approximations $t_{1,r}^{*}$
and $t_{2,r}^{*}$ of two tuples $t_{1}$ and $t_{2}$ in $\bm{T}_{R}(D)$ that
witness that $d_{R}(t_{1},t_{2})$ is too small. In particular, the role of
$\varepsilon_{0}$ in Condition 19 is to guarantee that $t_{1,r}^{*}$ and
$t_{2,r}^{*}$ do not end up approximating the same tuple. We proceed to show
the following equivalence:

$\text{there are }t_{1},t_{2}\in\bm{T}_{R}(D),t_{1}\neq t_{2}\text{ with
}d_{R}(t_{1},t_{2})\leq\varepsilon\quad\Leftrightarrow\quad D\text{ satisfies
\lx@cref{creftype~refnum}{cond:coarseequiv}}\text{.}$

To simplify notation, we let $d\coloneqq d_{R}$ denote our metric on
$\mathbb{T}_{R}$, and $d(D)\coloneqq d_{R}(D)$.

$\Rightarrow$:

Let $t_{1},t_{2}$ be two distinct tuples in $\bm{T}_{R}(D)$ of minimal
distance, in particular satisfying $0<d(t_{1},t_{2})\leq\varepsilon$. Let
$k_{1}\coloneqq\lvert D\rvert_{R(t_{1})}$ and $k_{2}\coloneqq\lvert
D\rvert_{R(t_{2})}$. We fix some $\varepsilon_{0}>0$ that satisfies
$\varepsilon_{0}<\tfrac{1}{3}d(t_{1},t_{2})$. Since $\mathbb{T}_{R}^{*}$ is
dense in $\mathbb{T}_{R}$, for every $r>0$ (in particular for
$r<\varepsilon_{0}$) there exist
$t_{1,r}^{*},t_{2,r}^{*}\in\mathbb{T}_{R}^{*}$ with
$d(t_{1,r}^{*},t_{1}),d(t_{2,r}^{*},t_{2})<r$. Since
$d(t_{1},t_{2})>3\varepsilon_{0}$ and $r<\varepsilon_{0}$, $r>0$, using the
triangle inquality, it follows that

$d(t_{1,r}^{*},t_{2})\geq
d(t_{1},t_{2})-d(t_{1},t_{1,r}^{*})>3\varepsilon_{0}-r>\varepsilon_{0}>r$

and similarly that $d(t_{2,r}^{*},t_{1})>\varepsilon_{0}>r$. Because $t_{1}$
and $t_{2}$ were chosen with minimal distance, this entails $\lvert
D\rvert_{R(B_{r}(t_{1,r}^{*}))}=\lvert D\rvert_{R(t_{1})}=k_{1}$ and $\lvert
D\rvert_{R(B_{r}(t_{2,r}^{*}))}=\lvert D\rvert_{R(t_{2})}=k_{2}$. Note that,
again using the triangle inequality, it holds that

$d(t_{1,r}^{*},t_{2,r}^{*})\leq
d(t_{1,r}^{*},t_{1})+d(t_{1},t_{2})+d(t_{2},t_{2,r}^{*})<\varepsilon+2r$

and, moreover,

$d(t_{1,r}^{*},t_{2,r}^{*})\geq
d(t_{1},t_{2})-d(t_{1},t_{1}^{*})-d(t_{2},t_{2,r}^{*})>\varepsilon_{0}\text{.}$

Together, $D$ satisfies Condition 19.

$\Leftarrow$:

Now suppose Condition 19 holds for some $k_{1},k_{2}\in\mathbb{N}_{+}$, and
some $\varepsilon_{0}>0$. By Condition 19, for all positive
$r<\varepsilon_{0}$ there exist $t_{1,r}^{*},t_{2,r}^{*}\in\mathbb{T}_{R}^{*}$
with $\varepsilon_{0}<d(t_{1,r}^{*},t_{2,r}^{*})<\varepsilon+2r$ such that
$\lvert D\rvert_{R(B_{r}(t_{1,r}^{*}))}=k_{1}>0$ and $\lvert
D\rvert_{R(B_{r}(t_{2,r}^{*}))}=k_{2}>0$. Note that this implies
$\varepsilon_{0}<\varepsilon$.

Now for all $r<\tfrac{1}{3}\min\big{\\{}d_{R}(D),\varepsilon_{0}\big{\\}}$,
the balls $B_{r}(t_{1,r}^{*})$ and $B_{r}(t_{2,r}^{*})$ are disjoint, and
contain at exactly one tuple from $\bm{T}_{R}(D)$ each, say $\bm{T}_{R}(D)\cap
B_{r}(t_{1,r}^{*})=\\{t_{1}\\}$ and $\bm{T}_{R}(D)\cap
B_{r}(t_{2,r}^{*})=\\{t_{2}\\}$. Thus, $\lvert D\rvert_{R(t_{1})}=\lvert
D\rvert_{R(B_{r}(t_{1,r}^{*}))}=k_{1}>0$ and $\lvert D\rvert_{R(t_{2})}=\lvert
D\rvert_{R(B_{r}(t_{2,r}^{*}))}=k_{2}>0$. Moreover,

$d(t_{1},t_{2})\leq
d(t_{1},t_{1,r}^{*})+d(t_{1,r}^{*},t_{2,r}^{*})+d(t_{2,r}^{*},t_{2})<\varepsilon+4r\text{.}$
(7)

In particular, Condition 19 implies that for all $r>0$ there exist distinct
$t_{1},t_{2}\in\bm{T}_{R}(D)$ with $d(t_{1},t_{2})<\varepsilon+4r$. As $D$ is
finite, letting $r\to 0$ implies that there exist distinct
$t_{1},t_{2}\in\bm{T}_{R}(D)$ with $d(t_{1},t_{2})\leq\varepsilon$.

Because $\mathbb{Q}$ is dense in $\mathbb{R}$, the equivalence still holds, if
the numbers $\varepsilon_{0}$ and $r$ are restricted to $\mathbb{Q}$. Then,

$\big{(}\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\big{)}^{c}=\bigcup_{R}\bigcup_{\varepsilon_{0}}\bigcap_{r}\bigcup_{t_{1,r}^{*},t_{2,r}^{*}}\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{R(B_{r}(t_{1,r}^{*}))}=k_{1}\text{ and }\lvert
D\rvert_{R(B_{r}(t_{2,r}^{*}))}=k_{2}\big{\\}}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

(with the indices ranging as in our equivalence, numbers being restricted to
rationals). Thus,
$\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

Note that for every database instance $D$, there exists an $\varepsilon>0$,
small enough, such that
$D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$, because $D$ is
finite. This means that
$\bigcup_{\varepsilon>0}\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$
covers $\mathord{\mathbb{D}\mathbb{B}}$ (even if the union is taken only over
rational $\varepsilon$).

######  Corollary 20.

If for all $\varepsilon>0$, all $\bm{F}\in\mathfrak{F}_{Q}$, and all
$n\in\mathbb{N}$ it holds that

$\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\big{\\}}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}\text{,}$

then $Q$ is measurable.

######  Proof 4.4.

This follows directly from

$\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\big{\\}}=\bigcup\nolimits_{\varepsilon\in\mathbb{Q}_{+}}\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\big{\\}}.$

Corollary 20 can be used to leverage the finiteness of our instances. In an
$\varepsilon$-coarse instance, we can approximate sets of facts by simpler
sets of facts as long as these approximations are sufficiently fine. For
example, in the context of Section 4.4, in order to prove measurability of a
query, it suffices to prove the measurability with respect to preimages where
the temperature recordings are “far apart”.

##  5\. Relational Algebra

As motivated in Section 3.2, we investigate the measurability of relational
algebra queries in our model. The concrete relational algebra for bags that we
use here is basically the (unnested version of the) algebra that was
introduced in [DGK82] and investigated, respectively extended, and surveyed in
[Alb91, GM96, GLMW96]. It is called $\mathsf{BALG^{1}}$ (with superscript $1$)
in [GM96].

We do not introduce nesting as it would yield yet another layer of abstraction
and complexity to the spaces we investigate, although by the properties that
such spaces exhibit, we have strong reason to believe that there is no
technical obstruction in allowing spaces of finite bags as attribute domains.
It is unclear however, whether this extends to PDBs with unbounded nesting
depth.

The operations we consider are shown in the Table 2 below. As seen in [Alb91,
GM96, GLMW96], there is some redundancy within this set of operations that
will be addressed later. A particular motivation for choosing this particular
algebra is that possible worlds semantics are usually built on top of set
semantics and these operations naturally extend the common behavior of
relation algebra queries to bags. This is quite similar to the original
motivation of [DGK82] and [Alb91] regarding their choice of operations.

Table 2. The operators of $\mathsf{BALG}^{1}$ considered in this paper. Base Queries | Constructors |  $Q=\left\\{\middle\\{\mathopen{}\mathclose{}\middle\\}\right\\}$ and $Q=\left\\{\middle\\{\mathopen{}R(t_{0})\mathclose{}\middle\\}\right\\}$
---|---|---
| Extractors | $Q=R$
| Renaming | $Q=\rho_{#1}\lparen R\rparen$
Basic Bag Operations | Additive Union | $Q=R\uplus S$
| Max Union | $Q=R\cup S$
| Intersection | $Q=R\cap S$
| Difference | $Q=R-S$
| Deduplication | $Q=\delta\lparen R\rparen$
SPJ-Operations | Selection | $Q=\sigma_{#1}\lparen R\rparen$
| Projection | $Q=\pi_{#1}\lparen R\rparen$
| Cross Product | $Q=R\times S$

Since compositions of measurable functions are measurable, it suffices to show
the measurability of the operators from Table 2, and the measurability of
compound queries follows by structural induction.

Therefore, by investigating the measurability of the operators from Table 2 we
will show the following main result of this section.

######  Theorem 21.

All queries expressible in the bag algebra $\mathsf{BALG^{1}}$ are measurable.

###  5.1. Base Queries

The base queries (Table 3) are easily seen to be measurable.

Table 3. Base Queries. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t\in\mathbb{T}_{Q}$)
---|---
$Q=\left\\{\middle\\{\mathopen{}\mathclose{}\middle\\}\right\\}$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq 0$
$Q=\left\\{\middle\\{\mathopen{}R_{Q}(t_{0})\mathclose{}\middle\\}\right\\}$ |  $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq 1$ if $t=t_{0}$, and $0$ otherwise
$Q=R$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\lvert D\rvert_{R(t)}$

######  Lemma 22.

The following queries are measurable:

  1. (1)

$Q=\left\\{\middle\\{\mathopen{}\mathclose{}\middle\\}\right\\}$,

  2. (2)

$Q=\left\\{\middle\\{\mathopen{}f\mathclose{}\middle\\}\right\\}$ for all
$f\in\mathbb{F}_{Q}$, and

  3. (3)

$Q=R$ for all $R\in\tau$.

######  Proof 5.1.

  1. (1)

Let $\bm{D}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}_{Q}$. If
$\left\\{\middle\\{\mathopen{}\mathclose{}\middle\\}\right\\}\in\bm{D}$, then
$Q^{-1}(\bm{D})=\mathord{\mathbb{D}\mathbb{B}}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.
Otherwise, if
$\left\\{\middle\\{\mathopen{}\mathclose{}\middle\\}\right\\}\notin\bm{D}$,
then
$Q^{-1}(\bm{D})=\emptyset\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

  2. (2)

This can be shown the same way.

  3. (3)

Let $Q=R$, let $R_{Q}(\bm{T})\in\mathfrak{F}_{Q}$ and let $n\in\mathbb{N}$.
Then $R(\bm{T})\in\mathfrak{F}_{R}\subseteq\mathfrak{F}$. For all
$D\in\mathord{\mathbb{D}\mathbb{B}}$, it holds that

$\lvert Q(D)\rvert_{R_{Q}(\bm{T})}=n\iff\lvert D\rvert_{R(\bm{T})}=n\text{,}$

and the latter is measurable in
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$. Thus, $Q$ is measurable.

Note that there is nothing to show for the renaming query because it leaves
all tuples themselves untouched. In the subsequent subsections, we deal with
the remainder of Table 2.

###  5.2. Basic Bag Operations

We now treat the basic bag operations (Table 4). Assume that $R,S\in\tau$ are
relation symbols of the same sort. From now on, we will only consider the case
where $R$ and $S$ are distinct, as for the case $R=S$, measurability is
trivial.

Table 4. Basic Bag Operations. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t\in\mathbb{T}_{Q}$)
---|---
$Q=R\uplus S$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\lvert D\rvert_{R(t)}+\lvert D\rvert_{S(t)}$
$Q=R-S$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\max\big{\\{}0,\lvert D\rvert_{R(t)}-\lvert D\rvert_{S(t)}\big{\\}}$
$Q=R\cup S$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\max\big{\\{}\lvert D\rvert_{R(t)},\lvert D\rvert_{S(t)}\big{\\}}$
$Q=R\cap S$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\min\big{\\{}\lvert D\rvert_{R(t)},\lvert D\rvert_{S(t)}\big{\\}}$

######  Lemma 23.

The following queries are measurable:

  1. (1)

$Q=R\uplus S$.

  2. (2)

$Q=R-S$.

  3. (3)

$Q=R\cup S$.

  4. (4)

$Q=R\cap S$.

######  Proof 5.2.

As $\cup$ and $\cap$ can be expressed by compositions of $\uplus$ and $-$
[Alb91], it suffices to show 1 and 2.

  1. (1)

Consider the functions $g\colon\mathbb{F}_{Q}\to\mathbb{F}_{R}$ and
$h\colon\mathbb{F}_{Q}\to\mathbb{F}_{S}$ with

$g\big{(}R_{Q}(t)\big{)}=R(t)\qquad\text{and}\qquad
h\big{(}R_{Q}(t)\big{)}=S(t)$

for all $t\in\mathbb{T}_{Q}=\mathbb{T}_{R}=\mathbb{T}_{S}$. Clearly, both
functions are injective and continuous. For all $k\in\mathbb{N}$ we define

$N_{Q}(n)\coloneqq\\{(n_{1},n_{2})\in\mathbb{N}^{2}\colon
n_{1}+n_{2}=n\\}\text{.}$

Then $\lvert Q(D)\rvert_{f}=n$ if and only if $\big{(}\lvert
D\rvert_{g(f)},\lvert D\rvert_{h(f)}\big{)}\in N_{Q}(n)$. Thus, $Q$ is
measurable by Lemma 15.

  2. (2)

This works analogously to part 1, with

$N_{Q}(n)\coloneqq\\{(n_{1},n_{2})\in\mathbb{N}^{2}\colon\max\\{n_{1}-n_{2},0\\}=n\\}\text{.}$

###  5.3. Set Semantics

The deduplication operator (Table 5) maps bag instances to their underlying
set instances.

Table 5. Deduplication. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t\in\mathbb{T}_{Q}$)
---|---
$Q=\delta\lparen R\rparen$ |  $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq 1$ if $\lvert D\rvert_{R(t)}>0$, and $0$ otherwise

######  Lemma 24.

The deduplication query $Q=\delta\lparen R\rparen$ is measurable for all
$R\in\tau$.

######  Proof 5.3.

We apply Lemma 15 for $r=1$ and the function
$q_{1}=q\colon\mathbb{F}_{Q}\to\mathbb{F}_{R}$ defined by $q(R_{Q}(x))=R(x)$.
Then for all $D\in\mathord{\mathbb{D}\mathbb{B}}$ and all
$f\in\mathbb{F}_{Q}$, it holds that

$\lvert Q(D)\rvert_{f}=\lvert D\rvert_{q(f)}\text{.}$

Thus, we let $N_{Q}(k)=\\{0\\}$ if $k=0$ and
$N_{Q}(k)=\mathbb{N}\setminus\\{0\\}$ otherwise. Then $r$, $q$ and $N_{Q}$
satisfy the requirements of Lemma 15, so $Q$ is measurable.

Having the deduplication query measurable means that standard PDBs support set
semantics.

######  Remark 25.

The function associated with the deduplication query is countable-to-one
(preimage of a single instance in the result is a countable collection of
instances) and measurable by the lemma above. This can be used to infer that
the space of set instances is standard Borel using [Sri98, Theorem 4.12.4].
This means that we could also completely restrict our setting to set instances
without introducing new measurability problems. In general however, it can
still be mathematically more conventient to use the full measurable space that
was defined in Section 3.1, even in a set semantics setting. The point
processes defining PDBs should then just be “simple” in the sense of Section
2, i. e. have the probability $0$ of containing duplicate facts.

###  5.4. Selection and Projection

In this section, we investigate the selection and projection operators Table
6. First, we note that reordering the attributes in the sort of a relation
yields a measurable query.

######  Lemma 26.

Let $\operatorname{sort}(R)=(A_{1},\dots,A_{r})$ and let $\beta$ be a
permutation of $\\{1,\dots,r\\}$. For $f=R(a_{1},\dots,a_{r})$ let
$\beta(f)=R_{Q}(a_{\beta(1)},\dots,a_{\beta(r)})$, and let
$Q(D)\coloneqq\\{\beta(f)\colon f\in D\\}$. Then $Q$ is measurable.

######  Proof 5.4.

This directly follows from the mapping theorem (Theorem 14), because
$\beta\colon\mathbb{F}_{R}\to\mathbb{F}_{Q}$ is measurable.

Lemma 26 is helpful for restructuring relations into a more convenient shape
to work with later. Semantically, it is a special case of a projection query.

Let $R\in\tau$ be a relation symbol with $\operatorname{ar}(R)=r$, and let
$A_{1},\dots,A_{k}$ be pairwise distinct attributes appearing in
$\operatorname{sort}(R)$ where $0<k\leq r$. By Lemma 26, wlog. we assume that
$\operatorname{sort}(R)=(A_{1},\dots,A_{r})$.

Table 6. Selection and Projection. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t\in\mathbb{T}_{Q}$)
---|---
$Q=\sigma_{#1}\lparen R\rparen$ |  $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\lvert D\rvert_{R(t)}$ if $t[A_{1},\dots,A_{k}]\in\bm{B}$, and $0$ otherwise
$Q=\pi_{#1}\lparen R\rparen$ | $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\sum_{t^{\prime}\colon t^{\prime}[A_{1},\dots,A_{k}]=t}\lvert D\rvert_{R(t^{\prime})}$

######  Lemma 27.

Let $\bm{B}\in\bigotimes_{i=1}^{k}\mathfrak{A}_{i}$. Then the query
$Q=\sigma_{#1}\lparen R\rparen$ is measurable.

######  Proof 5.5.

Fix $\bm{F}\in\mathfrak{F}_{Q}$, say $\bm{F}=R_{Q}(\bm{T})$ with
$\bm{T}\in\bigotimes_{i=1}^{k}\mathfrak{A}_{i}$, and let $n\in\mathbb{N}$.
Define

$\bm{F}^{-1}\coloneqq R(\bm{T})\cap
R(\bm{B}\times\mathbb{A}_{k+1}\times\dotsc\times\mathbb{A}_{r}\big{)}$ (8)

Then $\bm{F}^{-1}\in\mathfrak{F}_{R}\subseteq\mathfrak{F}$. It holds that

$\lvert Q(D)\rvert_{\bm{F}}=n\iff\lvert D\rvert_{\bm{F}^{-1}}=n\text{.}$

Thus, $Q$ is measurable.

Suppose $A_{1},A_{2}\in\operatorname{sort}(R)$ with
$\mathbb{A}_{1}=\mathbb{A}_{2}=\mathbb{R}$. The sets

$\displaystyle\bm{T}_{=}\coloneqq\\{(x,y)\in\mathbb{R}^{2}\colon x=y\\}$ and
$\displaystyle\bm{T}_{<}\coloneqq\\{(x,y)\in\mathbb{R}^{2}\colon x<y\\}$ are
Borel in $\mathbb{R}^{2}$. Thus, the queries $\displaystyle\sigma_{#1}\lparen
R\rparen\coloneqq\sigma_{#1}\lparen R\rparen$ and
$\displaystyle\sigma_{#1}\lparen R\rparen\coloneqq\sigma_{#1}\lparen R\rparen$

are measurable by Lemma 27. In particular, in the context of our running
example, we can do selections based on comparing temperatures.

######  Lemma 28.

The query $Q=\pi_{#1}\lparen R\rparen$ is measurable.

######  Proof 5.6.

Fix $\bm{F}\in\mathfrak{F}_{Q}$, say $\bm{F}=R_{Q}(\bm{T})$ with
$\bm{T}\in\bigotimes_{i=1}^{k}\mathfrak{A}_{i}$, and let $n\in\mathbb{N}$.
Again, define

$\bm{F}^{-1}\coloneqq
R\big{(}\bm{T}\times\mathbb{A}_{k+1}\times\dotsc\times\mathbb{A}_{r}\big{)}\text{.}$
(9)

Then $\bm{F}^{-1}\in\mathfrak{F}_{R}$ and it holds that

$\lvert Q(D)\rvert_{\bm{F}}=n\iff\lvert D\rvert_{\bm{F}^{-1}}=n\text{,}$

and, hence, $Q$ is measurable.

######  Remark 29.

Above, we provided direct proofs of Lemma 27 and Lemma 28. Alternatively, they
follow from Theorem 14 using the function

$\displaystyle q\colon\big{\\{}R(t)\in\mathbb{F}_{R}\colon
t[A_{1},\dots,A_{k}]\in\bm{B}\big{\\}}\to\mathbb{F}_{Q}$ with $\displaystyle
q\big{(}R(t)\big{)}$ $\displaystyle=R_{Q}(t)$ for selection and the function
$\displaystyle q\colon\mathbb{F}_{R}\to\mathbb{F}_{Q}$ with $\displaystyle
q\big{(}R(t)\big{)}$ $\displaystyle=R_{Q}\big{(}t[A_{1},\dots,A_{k}]\big{)}$

for projection. A closer look reveals that the sets $\bm{F}^{-1}$ of 8 and 9
are really the preimages of the respective function $q$ that we know from
Theorem 14.

###  5.5. Products

Let $R,S\in\tau$ be relation symbols. In this section, we treat the cross
product $Q=R\times S$ (Table 7). (For the discussions here, it does not matter
whether $R=S$.)

Table 7. Cross Products. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t\in\mathbb{T}_{R}$, $t^{\prime}\in\mathbb{T}_{S}$)
---|---
$Q=R\times S$ | $\lvert Q(D)\rvert_{R_{Q}(t,t^{\prime})}\coloneqq\lvert D\rvert_{R(t)}\cdot\lvert D\rvert_{S(t^{\prime})}$

######  Lemma 30.

Let $\bm{F}\in\mathfrak{F}_{Q}$ such that
$\bm{F}=R_{Q}(\bm{T}_{R}\times\bm{T}_{S})$ with
$\bm{T}_{R}\in\mathfrak{T}_{R}$ and $\bm{T}_{S}\in\mathfrak{T}_{S}$. Then

$\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\\}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

for all $n\in\mathbb{N}$.

######  Proof 5.7.

Let $\bm{F}\in\mathfrak{F}_{Q}$, say $\bm{F}=R_{Q}(\bm{T})$ with
$\bm{T}\in\mathbb{T}_{Q}$. If $\bm{T}=\bm{T}_{R}\times\bm{T}_{S}$ for some
$\bm{T}_{R}\in\mathbb{T}_{R}$ and $\bm{T}_{S}\in\mathbb{T}_{S}$, then for all
$D\in\mathbb{D}$, it holds that

$\lvert Q(D)\rvert_{\bm{F}}=\lvert D\rvert_{\bm{F}_{R}}\cdot\lvert
D\rvert_{\bm{F}_{S}}\text{,}$ (10)

where $\bm{F}_{R}=R(\bm{T}_{R})$ and $\bm{F}_{S}=S(\bm{T}_{S})$. Thus,

$\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\\}=\bigcup_{n_{R}\cdot
n_{S}=n}\big{\\{}D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{\bm{F}_{R}}=n_{R}\text{ and }\lvert
D\rvert_{\bm{F}_{S}}=n_{S}\big{\\}}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}\text{.}$

######  Remark 31.

Note that we proceeded similar to Lemma 15. Unfortunately, not every set
$\bm{T}\in\mathbb{T}_{Q}$ can be decomposed into a product of measurable sets
$\bm{T}_{R}$ and $\bm{T}_{S}$ as used above. The sets $\bm{T}_{R}$ and
$\bm{T}_{S}$ are the projections of $\mathbb{T}_{Q}$ to $\mathbb{T}_{R}$ and
$\mathbb{T}_{S}$. Recall that we already encountered a similar situation in
Section 3.2. In general, such projections of measurable sets from products of
standard Borel spaces to their factors yield the _analytic_ sets (cf. [Kec95,
Exercise 14.3]). A fundamental theorem in descriptive set theory states that
every uncountable standard Borel space has analytic, non-(Borel-)measurable
subsets [Kec95, Theorem 14.2]. Thus, with suitably chosen attribute domains,
there are sets $\bm{T}\in\mathfrak{T}_{Q}$ such that, for instance, the
projection of $\bm{T}$ to $\mathbb{T}_{R}$ is not in $\mathfrak{T}_{R}$.
Therefore, the approach from 10 doesn’t help us resolve the measurability of
$Q$, even though it appeared promisingly similar to the arguments from the
previous section. In particular, for the given query we cannot establish
criterion 2 from Lemma 15.

For $t\in\mathbb{T}_{Q}$, we let $t_{R}\in\mathbb{T}_{R}$ and
$t_{S}\in\mathbb{T}_{S}$ denote the projections of $t$ to its $R$\- and
$S$-part. Then for all $r>0$, $\bm{W}_{r}(t)\coloneqq B_{r}(t_{R})\times
B_{r}(t_{S})\subseteq\mathbb{T}_{Q}$ is a _measurable rectangle_ containing
$t$ with $B_{r}(t_{R})\subseteq\mathbb{T}_{R}$ and
$B_{r}(t_{S})\subseteq\mathbb{T}_{S}$. Note that $B_{r}(t_{R})$ is a ball with
respect to the (Polish) metric on $\mathbb{T}_{R}$, and $B_{r}(t_{S})$ is a
ball with respect to the (Polish) metric on $\mathbb{T}_{S}$.

######  Remark 32.

Let us briefly comment on the intuition of the setup. The sets $\bm{W}_{r}(t)$
should be thought of as a small _windows_ that we can use to make our
considerations local around $t=(t_{R},t_{S})$. We use these windows to show
query measurability by exploiting the finiteness of our database instances:
since every $D$ is finite, $D$ is $\varepsilon$-coarse for $\varepsilon>0$
small enough (see Section 4.4). Then for small enough radius $r$, the balls
$B_{r}(t_{R})$ and $B_{r}(t_{S})$ both contain at most one $R$\- or $S$-tuple
from $D$, respectively. Thus, the image of $D$ under the cross product query
also contains at most one tuple in $\bm{W}_{r}(t)=B_{r}(t_{R})\times
B_{r}(t_{S})$. Then, as $\bm{W}_{r}(t)$ has the appropriate shape, Lemma 30
can be used again.

Recall that for all $\varepsilon>0$,
$\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$ is the set of
$\varepsilon$-coarse instances in $\mathord{\mathbb{D}\mathbb{B}}$. Let
$\bm{F}\in\mathfrak{F}_{Q}$ and $n\in\mathbb{N}$. For all $\varepsilon>0$, we
let

$\bm{D}_{\bm{F},n,\varepsilon}\coloneqq\\{D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\colon\lvert
Q(D)\rvert_{\bm{F}}=n\\}\text{.}$

Then $\bm{D}_{\bm{F},n,\varepsilon}$ is the $\varepsilon$-coarse preimage of
the event $\\{D_{Q}\in\mathord{\mathbb{D}\mathbb{B}}_{Q}\colon\lvert
D\rvert_{\bm{F}}=n\\}$ from $\mathord{\mathbb{D}\mathbb{B}}_{Q}$.

######  Lemma 33.

For all $\bm{F}\in\mathfrak{F}_{Q}$, $n\in\mathbb{N}$, $t\in\mathbb{T}_{Q}$
and all $\varepsilon,r>0$, with $r<\tfrac{\varepsilon}{3}$ it holds that
$\bm{D}_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

######  Proof 5.8.

We prove the lemma as follows. Let

$\mathfrak{F}_{\varepsilon}\coloneqq\big{\\{}\bm{F}\in\mathfrak{F}_{Q}\colon\bm{D}_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}\text{
for all }t\in\mathbb{T}_{Q}\text{,}~{}n\in\mathbb{N}\text{, and
}r<\tfrac{\varepsilon}{3}\big{\\}}\text{.}$ (11)

Intuitively, this is the set of measurable sets $\bm{F}$ with the property
that all sufficiently fine “window approximations” of the $\varepsilon$-coarse
preimages of $\\{D_{Q}\in\mathord{\mathbb{D}\mathbb{B}}_{Q}\colon\lvert
D_{Q}\rvert_{\bm{F}}=n\\}$ are measurable in
$\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

It then suffices to show for all $\varepsilon>0$ that

  1. (1)

for every set $\bm{F}=R_{Q}(\bm{T})$ with
$\bm{T}=\bm{T}_{R}\times\bm{T}_{S}\in\mathfrak{T}_{R}\times\mathfrak{T}_{S}\subseteq\mathfrak{T}_{Q}$
it holds that $\bm{F}\in\mathfrak{F}_{\varepsilon}$, and

  2. (2)

the family $\mathfrak{F}_{\varepsilon}$ is a $\sigma$-algebra on
$\mathbb{F}_{Q}$.

From these two it follows that $\mathfrak{F}_{\varepsilon}=\mathfrak{F}_{Q}$.
That is, indeed every measurable set $\bm{F}\in\mathfrak{F}_{Q}$ satisfies the
property from 11. This line of argument is occasionally referred to as the
_good sets principle_ [Ash72, p. 5].

We fix $\varepsilon>0$ arbitrary and show 1 and 2.

  1. (1)

Suppose $\bm{F}=R_{Q}(\bm{T})$ for some
$\bm{T}\in\mathfrak{T}_{R}\times\mathfrak{T}_{S}$, say
$\bm{T}=\bm{T}_{R}\times\bm{T}_{S}$. Let $t\in\mathbb{T}_{Q}$,
$n\in\mathbb{N}$, and $r<\frac{\varepsilon}{3}$ be arbitary. With
$t_{R}\in\mathbb{T}_{R}$ and $t_{S}\in\mathbb{T}_{S}$, we denote the $R$\- and
the $S$-part of $t$, respectively. Then

$\displaystyle\bm{F}\cap R_{Q}\big{(}\bm{W}_{r}(t)\big{)}$
$\displaystyle=R_{Q}(\bm{T}_{R}\times\bm{T}_{S})\cap R_{Q}(B_{r}(t_{R})\times
B_{r}(t_{S}))$ $\displaystyle=R_{Q}\big{(}(\bm{T}_{R}\cap
B_{r}(t_{R}))\times(\bm{T}_{S}\cap B_{r}(t_{S}))\big{)}\text{.}$

By Lemma 30, it follows that
$\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert Q(D)\rvert_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t))}=n\\}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.
With Lemma 18 this entails that

$\bm{D}_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}=\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}\cap\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
Q(D)\rvert_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t))}=n\\}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}\text{.}$

As $t$, $n$ and $r$ were arbitrary, it follows that
$\bm{F}\in\mathfrak{F}_{\varepsilon}$.

  2. (2)

We show that $\mathfrak{F}_{\varepsilon}$ is a $\sigma$-algebra on
$\mathbb{F}_{Q}$ by showing $\mathbb{F}_{Q}\in\mathfrak{F}_{\varepsilon}$, and
that it is closed under complements and countable intersections.

First note that $\mathbb{F}_{Q}\in\mathfrak{F}_{\varepsilon}$ follows from
Lemma 30 because $\mathbb{F}_{Q}=R_{Q}(\mathbb{T}_{R}\times\mathbb{T}_{S})$.
Now let $t\in\mathbb{T}_{Q}$, $n\in\mathbb{N}$, and $r<\tfrac{\varepsilon}{3}$
be arbitrary but fixed, and let
$D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$. Figure 3 provides
visualizations for the remaining cases.

$\bm{F}$$\bm{F}^{c}$$B_{r}(t_{R})$ $B_{r}(t_{S})$
$t$$R_{Q}\big{(}\bm{W}_{r}(t)\big{)}$ (a) Depiction of $\bm{F}^{c}\cap
R_{Q}\big{(}\bm{W}_{r}(t)\big{)}$.

$\bm{F}_{2}$$\bm{F}_{1}$$B_{r}(t_{R})$ $B_{r}(t_{S})$
$t$$R_{Q}\big{(}\bm{W}_{r}(t)\big{)}$ (b) Depiction of
$\bm{F}_{1}\cap\bm{F}_{2}\cap R_{Q}\big{(}\bm{W}_{r}(t)\big{)}$.

Figure 3. Illustrations for the proof of Lemma 33. The indications of
$B_{r}(t_{R})$ and $B_{r}(t_{S})$ are only to convey the intuition behind the
construction of $\bm{W}_{r}(t)$.

    1. (a)

Let $\bm{F}\in\mathfrak{F}_{\varepsilon}$. Then it holds that

$\displaystyle D\in\bm{D}_{\bm{F}^{c}\cap R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}$
$\displaystyle\iff\lvert Q(D)\rvert_{\bm{F}^{c}\cap R_{Q}(\bm{W}_{r}(t))}=n$
$\displaystyle\iff\lvert Q(D)\rvert_{R_{Q}(\bm{W}_{r}(t))}-\lvert
Q(D)\rvert_{\bm{F}\cap R_{Q}(\bm{W}_{r}(t))}=n$

Recall that $D$ is $\varepsilon$-coarse. In particular, as
$r<\frac{\varepsilon}{3}$, the ball $B_{r}(t_{R})$ contains at most one
$R$-tuple from $D$ and the ball $B_{r}(t_{S})$ contains at most one $S$-tuple
from $D$. Hence, $\bm{W}_{r}(t)=B_{r}(t_{R})\times B_{r}(t_{S})$ contains at
most one $R_{Q}$-tuple from $Q(D)$. Thus, $D\in\bm{D}_{\bm{F}^{c}\cap
R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}$ if and only if

$\lvert Q(D)\rvert_{R_{Q}(\bm{W}_{r}(t))}=n\text{ and }\lvert
Q(D)\rvert_{\bm{F}\cap R_{Q}(\bm{W}_{r}(t))}=0\text{.}$

From 1 and the assumption $\bm{F}\in\mathfrak{F}_{\varepsilon}$, it thus
follows that $\bm{F}^{c}\in\mathfrak{F}_{\varepsilon}$.

    2. (b)

Now let $\big{(}\bm{F}_{i}\big{)}_{i=1,2,\dots}$ be a sequence of sets
$\bm{F}_{i}\in\mathfrak{F}_{\varepsilon}$ and let
$\bm{F}=\bigcap_{i=1}^{\infty}\bm{F}_{i}$. Then it holds that

$\displaystyle D\in\bm{D}_{\bm{F}\cap R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}$
$\displaystyle\iff\lvert Q(D)\rvert_{\bm{F}\cap R_{Q}(\bm{W}_{r}(t))}=n$
$\displaystyle\iff\lvert Q(D)\rvert_{\bigcap_{i=1}^{\infty}(\bm{F}_{i}\cap
R_{Q}(\bm{W}_{r}(t)))}=n\text{.}$

As in the previous case, because $D$ is $\varepsilon$-coarse, the set
$\bm{W}_{r}(t)$ contains at most one $R_{Q}$-tuple from $Q(D)$. Thus,
$D\in\bm{D}_{\bm{F}\cap R_{Q}(\bm{W}_{r}(t)),n,\varepsilon}$ if and only if

$\lvert Q(D)\rvert_{\bm{F}_{i}\cap R_{Q}(\bm{W}_{r}(t))}=n\text{ for all
}i=1,2,\dots\text{.}$

Thus, $\bigcap_{i=1}^{\infty}\bm{F}_{i}\in\mathfrak{F}_{\varepsilon}$ using
the assumption.

Together, $\mathfrak{F}_{\varepsilon}$ is indeed a $\sigma$-algebra on
$\mathbb{F}_{Q}$.

From 1 and 2 it follows that $\mathfrak{F}_{\varepsilon}=\mathfrak{F}_{Q}$ for
all $\varepsilon>0$.

######  Lemma 34.

For all $\bm{F}\in\mathfrak{F}_{Q}$, all $n\in\mathbb{N}$, and all
$\varepsilon>0$, it holds that
$\bm{D}_{\bm{F},n,\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$.

######  Proof 5.9.

Let $\bm{F}\in\mathfrak{F}_{Q}$, $n\in\mathbb{N}$, and $\varepsilon>0$. It
suffices to show that

$\bm{D}_{\bm{F},\geq n,\varepsilon}\coloneqq\bigcup_{m\geq
n}\bm{D}_{\bm{F},m,\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

where we may assume $n>0$. We show that $D\in\bm{D}_{\bm{F},\geq
n,\varepsilon}$ is equivalent to $D$ satisfying the following condition.

######  Condition 35.

The instance $D$ is $\varepsilon$-coarse and for some $\ell\in\mathbb{N}_{+}$
there are $k_{1},\dots,k_{\ell}\in\mathbb{N}_{+}$ with
$k_{1}+\dots+k_{\ell}\geq n$ such that for all
$r\in\big{(}0,\frac{\varepsilon}{3}\big{)}$ there are
$t_{1,r}^{*},\dots,t_{\ell,r}^{*}\in\mathbb{T}_{R}^{*}\times\mathbb{T}_{S}^{*}$
such that

  1. (1)

for all $i\neq j$ it holds that
$d_{R}(t_{i,r,R}^{*},t_{j,r,R}^{*})>\frac{\varepsilon}{3}$ or
$d_{S}(t_{i,r,S}^{*},t_{j,r,S}^{*})>\frac{\varepsilon}{3}$ and

  2. (2)

for all $i=1,\dots,\ell$ it holds that $D\in\bm{D}_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t_{i,r}^{*})),k_{i},\varepsilon}$.

We start with the easy direction ($\Leftarrow$).

$\Leftarrow$:

Suppose $D$ satisfies Condition 35. Then
$D\in\mathord{\mathbb{D}\mathbb{B}}\rvert_{\varepsilon}$ and it remains to
show $\lvert Q(D)\rvert_{\bm{F}}\geq n$. Note that it suffices to show that if
$r$ is small enough in Condition 35, then the sets $\bm{W}_{r}(t_{i,r}^{*})$
are pairwise disjoint. In this case, the claim follows from 2.

By 1, for all $i,j=1,\dots,n$ with $i\neq j$ it holds that at least one of
$d_{R}(t_{i,R}^{*},t_{j,R}^{*})$ or $d_{R}(t_{i,S}^{*},t_{j,S}^{*})$ is larger
than $\frac{\varepsilon}{3}$. Thus, for $r<\frac{\varepsilon}{6}$ it follows
that at least one of $d_{R}(t_{i,R}^{*},t_{j,R}^{*})$ or
$d_{S}(t_{i,S}^{*},t_{j,S}^{*})$ is larger than $2r$. Therefore,
$\bm{W}_{r}(t_{i,r}^{*})\cap\bm{W}_{r}(t_{j,r}^{*})=\emptyset$.

$\Rightarrow$:

Suppose that $D\in\bm{D}_{\bm{F},\geq n,\varepsilon}$. Then $D$ is
$\varepsilon$-coarse and $\lvert Q(D)\rvert_{\bm{F}}\geq n$. Thus, there exist
pairwise distinct $t_{1},\dots,t_{\ell}\in Q(D)$ with $R_{Q}(t_{i})\in\bm{F}$
for all $i=1,\dots,n$ such that

$\lvert Q(D)\rvert_{R_{Q}(t_{1})}+\dots+\lvert
Q(D)\rvert_{R_{Q}(t_{\ell})}\geq n\text{.}$

Let $r\in\big{(}0,\frac{\varepsilon}{3}\big{)}$. Since $\mathbb{T}_{R}^{*}$ is
dense in $\mathbb{T}_{R}$ and $\mathbb{T}_{S}^{*}$ is dense in
$\mathbb{T}_{S}$, for all $i=1,\dots,n$ we can choose
$t_{i,r}^{*}=(t_{i,r,R}^{*},t_{i,r,S}^{*})\in\mathbb{T}_{R}^{*}\times\mathbb{T}_{S}^{*}$
such that

$d_{R}(t_{i,r,R}^{*},t_{i,R})<r\qquad\text{and}\qquad
d_{S}(t_{i,r,S}^{*},t_{i,S})<r\text{.}$

Thus, $t_{i}\in\bm{W}_{r}(t_{i,r}^{*})$. Now let $t\in Q(D)$ with $t\neq
t_{i}$. Because $D$ is $\varepsilon$-coarse, it holds that

$d_{R}(t_{i,R},t_{R})>\varepsilon\qquad\text{or}\qquad
d_{S}(t_{i,S},t_{S})>\varepsilon\text{.}$

For the rest of the proof we assume $d_{R}(t_{i,R},t_{R})>\varepsilon$ (the
other case is completely symmetric). Recall that $r<\frac{\varepsilon}{3}$.
Then it follows that

$d_{R}(t_{i,r,R}^{*},t_{R})\geq
d_{R}(t_{i,R},t_{R})-d_{R}(t_{i,R},t_{i,r,R}^{*})>\varepsilon-r>r\text{.}$

Thus, $t\notin\bm{W}_{r}(t_{i,r}^{*})$, so every $\bm{W}_{r}(t_{i,r}^{*})$
contains no tuple from $Q(D)$ other than $t_{i}$. Thus, $\lvert
Q(D)\rvert_{R_{Q}(t_{i})}=\lvert Q(D)\rvert_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t_{i,r}^{*}))}$, and 2 follows.

Also for all $j\neq i$, we have that

$d_{R}(t_{i,r,R}^{*},t_{j,r,R}^{*})\geq
d_{R}(t_{i,R},t_{j,R})-d_{R}(t_{i,R},t_{i,r,R}^{*})-d_{R}(t_{j,R},t_{j,r,R}^{*})>\varepsilon-2r>\tfrac{\varepsilon}{3},$

establishing 1.

The equivalence still holds, if $r$ is additionally required to be rational.
That is,

$\bm{D}_{\bm{F},\geq
n,\varepsilon}=\bigcup_{\ell}\bigcup_{k_{1},\dots,k_{\ell}}\bigcap_{r}\bigcup_{t_{1,r}^{*},\dots,t_{\ell,r}^{*}}\bm{D}_{\bm{F}\cap
R_{Q}(\bm{W}_{r}(t_{i,r}^{*})),k_{i},\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$

using Lemma 33 (with the indices ranging as in our equivalence, and numbers
being restricted to rationals).

Finally, the measurability of $Q=R\times S$ is a direct consequence of Lemmas
34 and 20.

######  Lemma 36.

The query $Q=R\times S$ is measurable. ∎

Altogether, Lemmas 22, 23, 24, 27, 28 and 36 now prove the main result—the
measurability of $\mathsf{BALG}^{1}$-queries—of this section (Theorem 21).

As a consequence, we also obtain the measurability of all kinds of derived
operators, including the typical join operators. Note that it also follows
from Theorem 21, that we can use finite Boolean combinations of predicates for
selection queries.

##  6\. Aggregation

There are practically relevant queries that are not already covered by our
treatment in the previous section. For example, in our running example of
temperature recordings, we might be interested in returning the _average_ (or
_minimum_ or _maximum_) temperature per room, taken over all temperature
records for this particular room.

In this section, we formalize aggregate operators and aggregate queries,
possibly with grouping in the standard PDB framework in a possible worlds
semantics style (cf. Section 3.2). In particular, we show that these queries
are measurable in the standard PDB framework.

######  Remark 37.

Often, when a separate treatment of aggregate queries over purely algebraic
ones is motivated, it is mentioned that the correspondence of relational
algebra and relational calculus limits expressive power to that of first-order
logic. However, bag query languages based on relational algebra _do_ allow
expressing various kinds of aggregation based on exploiting the presence of
multiplicities. For example, counting in a unary fashion is possible in
$\mathsf{BALG^{1}}$ [GM96]. Here, we follow a more general approach in
allowing basically any measurable function over finite bags to be used for
aggregation. This goes beyond the integer aggregation of $\mathsf{BALG}$
[GLMW96].

Let $(\mathbb{A},\mathfrak{A})$ and $(\mathbb{B},\mathfrak{B})$ be standard
Borel spaces. An _aggregate operator_ (or _aggregator_) from $\mathbb{A}$ to
$\mathbb{B}$ is a function
$\Phi\colon\mathcal{B}_{\mathsf{fin}}(\mathbb{A})\to\mathbb{B}$, that is, a
function mapping (finite) bags of elements of $\mathbb{A}$ to elements of
$\mathbb{B}$. If $\mathbb{T}_{R}=\mathbb{A}$, then every such aggregator
$\Phi$ induces an _aggregation query_ $Q=\varpi_{#1}\lparen R\rparen$ with
$\mathbb{T}_{Q}=\mathbb{B}$ as follows:

$\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq\begin{cases}1&\text{if
}t=\Phi\big{(}R(D)\big{)}\text{, and}\\\ 0&\text{otherwise,}\end{cases}$

for all $D\in\mathord{\mathbb{D}\mathbb{B}}$.444Formally, $R(D)$ has been
defined as the bag of _$R$ -facts_ in $D$ wheras $\Phi$ should take bags of
_$R$ -tuples_. This small type mismatch is of no significance whatsoever. In
essence, its output on a single instance $D$ is the instance containing only
the single “tuple” corresponding to the value of the aggregation over the
relation $R$ in $D$. Examples of common attribute operators $\Phi$ are shown
in Table 8.

######  Proposition 38.

If $\Phi$ is a
$\big{(}\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{T}_{R}),\mathfrak{T}_{Q}\big{)}$-measurable
aggregator, then $\varpi_{#1}\lparen R\rparen$ is a measurable query.

######  Proof 6.1.

Let $\bm{F}=R_{Q}(\bm{T})$ where $\bm{T}\in\mathfrak{T}_{Q}$. Without loss of
generality, we assume that $R$ is the only relation in $\tau$. Then for all
$D\in\mathord{\mathbb{D}\mathbb{B}}$, it holds that

$\lvert Q(D)\rvert_{\bm{F}}=1\iff R(D)\in\Phi^{-1}(\bm{T})\iff D\in
R\big{(}\Phi^{-1}(\bm{T})\big{)}$

(and $\lvert Q(D)\rvert_{\bm{F}}=0$ otherwise). Since $\Phi$ is
$\big{(}\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{T}_{R}),\mathfrak{T}_{Q}\big{)}$-measurable,
the claim follows.

Table 8. Common aggregate operators. (We assume that $\bm{\mathsf{MIN}}$, $\bm{\mathsf{MAX}}$ and $\bm{\mathsf{AVG}}$ have a suitable definition on empty bags, so that their semantics are well-defined.) Name | Definition
---|---
Count | $\bm{\mathsf{CNT}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq m$
Distinct Count | $\bm{\mathsf{CNTd}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq\lvert\\{a_{1},\dots,a_{m}\\}\rvert$
Sum | $\bm{\mathsf{SUM}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq a_{1}+\dotsc+a_{m}$
Minimum | $\bm{\mathsf{MIN}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq\min\\{a_{1},\dots,a_{m}\\}$
Maximum | $\bm{\mathsf{MAX}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq\max\\{a_{1},\dots,a_{m}\\}$
Average | $\bm{\mathsf{AVG}}(\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\})\coloneqq\frac{a_{1}+\dots+a_{m}}{m}$

For $m\in\mathbb{N}$, we call a function
$\varphi\colon\mathbb{T}_{R}^{m}\to\mathbb{T}_{Q}$ _symmetric_ if
$\varphi(t)=\varphi(t^{\prime})$ for all $t\in\mathbb{T}_{R}^{m}$ and all
permutations $t^{\prime}$ of $t$.

######  Lemma 39.

For all $m\in\mathbb{N}$, let
$\varphi_{m}\colon\mathbb{T}_{R}^{m}\to\mathbb{T}_{Q}$ be a symmetric,
measurable function. Then the aggregator
$\Phi\colon\mathcal{B}_{\mathsf{fin}}(\mathfrak{T}_{R})\to\mathbb{T}_{Q}$ with

$\Phi\big{(}\left\\{\middle\\{\mathopen{}a_{1},\dots,a_{m}\mathclose{}\middle\\}\right\\}\big{)}\coloneqq\varphi_{m}(a_{1},\dots,a_{m})$

is
$\big{(}\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{T}_{R}),\mathfrak{T}_{Q})$-measurable.

######  Proof 6.2.

It suffices to show that the restriction $\Phi_{m}$ of $\Phi$ to
$\mathcal{B}_{m}(\mathbb{T}_{R})$, the bags of cardinality $m$ over
$\mathbb{T}_{R}$, is measurable for all $m\in\mathbb{N}$. Note that
$\mathcal{B}_{0}(\mathbb{T}_{R})$ only contains the empty bag, and
$\mathbb{T}_{R}^{0}$ only contains the empty tuple. That is, the statement is
trivial for $m=0$. Thus, let $m\in\mathbb{N}_{+}$. Since $\varphi_{m}$ is
$(\mathfrak{T}_{R}^{\otimes m},\mathfrak{T}_{Q})$-measurable and symmetric,
for all $\bm{T}\in\mathfrak{T}_{Q}$ it holds that $\varphi_{m}^{-1}(\bm{T})$
is a symmetric set in $\mathfrak{T}_{R}^{\otimes
m}\subseteq\bigoplus_{m=0}^{\infty}\mathfrak{T}_{R}^{\otimes m}$. From Remarks
6 and 7 it follows that
$\Phi_{m}^{-1}(\bm{T})\in\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{T}_{R})$.

All the aggregators in Table 8 yield measurable aggregation queries. The
associated functions $\varphi_{m}$ are all continuous under suitable choices
of attribute domains. That is, for example, if $+$ in the definition of
$\bm{\mathsf{SUM}}$ is the addition of real numbers.

What we have introduced so far is only sufficient to express the aggregation
over all tuples of a relation at once. Usually, we want to perform aggregation
separately for parts of the data, as in our motivating example of returning
the average temperature per room. For this, we need to _group_ tuples before
aggregating values. Suppose we want to group a relation $R$ by attributes
$A_{1},\dots,A_{k}$ and perform the aggregation over attribute $A$, separately
for every occurring value of the attributes $A_{1},\dots,A_{k}$. Without loss
of generality, we assume that $\operatorname{sort}(R)=(A_{1},\dots,A_{k},A)$.
Then what we described is an _group-by aggregate query_ $\varpi_{#1}\lparen
R\rparen$ and is defined by

$\lvert
Q(D)\rvert_{R_{Q}(a_{1},\dots,a_{k},b)}\coloneqq\begin{cases}1&\text{if
}b=\Phi(\bm{A}_{a_{1},\dots,a_{k}}(D))\text{ and}\\\
0&\text{otherwise.}\end{cases}$ (12)

for all $D\in\mathord{\mathbb{D}\mathbb{B}}$ where $\bm{A}(D)$ is the bag of
values $a$ such that $R(a_{1},\dots,a_{k},a)\in D$ with

$\lvert\bm{A}_{a_{1},\dots,a_{k}}(D)\rvert_{a}=\lvert
D\rvert_{R(a_{1},\dots,a_{k},a)}\text{.}$

Essentially, $\bm{A}_{a_{1},\dots,a_{k}}(D)$ is obtained by selecting those
tuples where the first $k$ attributes have values $a_{1},\dots,a_{k}$, and
then projecting to the last attribute. Both kinds of aggregate queries
(without, and with grouping) are shown in Table 9.

Table 9. Aggregate Queries. Query |  Semantics (for all $D\in\mathord{\mathbb{D}\mathbb{B}}$, $t,(a_{1},\dots,a_{k},b)\in\mathbb{T}_{Q}$)
---|---
$Q=\varpi_{#1}\lparen R\rparen$ |  $\lvert Q(D)\rvert_{R_{Q}(t)}\coloneqq 1$ if $t=\Phi\big{(}R(D)\big{)}$, and $0$ otherwise
$Q=\varpi_{#1}\lparen R\rparen$ | $\lvert Q(D)\rvert_{R_{Q}(a_{1},\dots,a_{k},b)}\coloneqq 1\text{ if }b=\Phi(\bm{A}_{a_{1},\dots,a_{k}}(D))\text{ and }0\text{ otherwise}$

######  Theorem 40.

If $\Phi\colon\mathcal{B}_{\mathsf{fin}}(\mathbb{A})\to\mathbb{B}$ is a
$(\mathfrak{C\mkern-0.2muo\mkern-0.5muu\mkern-0.4mun\mkern-0.5mut}(\mathbb{A}),\mathfrak{B})$-measurable
aggregator, then the query $\varpi_{#1}\lparen R\rparen$ is a measurable
query.

######  Proof 6.3.

Let $\mathbb{T}_{\mathsf{grp}}=\prod_{i=1}^{k}\mathbb{A}_{i}$. In the
following, we fix a compatible Polish metric $d_{\mathsf{grp}}$ on
$\mathbb{T}_{\mathsf{grp}}$, and a countable dense set
$\mathbb{T}_{\mathsf{grp}}^{*}$ in $\mathbb{T}_{\mathsf{grp}}$. For all
$t\in\mathbb{T}_{\mathsf{grp}}$ and all $r>0$ define

$Q_{t,r}=\pi_{#1}\big{\lparen}\sigma_{#1}\lparen
R\rparen\big{\rparen}\times\varpi_{#1}\big{\lparen}\pi_{#1}\big{\lparen}\sigma_{#1}\lparen
R\rparen\big{\rparen}\big{\rparen}\text{.}$

Note that $Q_{t,r}$ is measurable by Theorem 21 for all particular choices of
$t$ and $r$. Let $\widetilde{Q}=\pi_{#1}\lparen R\rparen$ and

$\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}\coloneqq\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\widetilde{Q}(D)\text{
is $\varepsilon$-coarse}\\}$

Then
$\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}\in\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}}$,
as
$\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}=\widetilde{Q}^{-1}\big{(}\mathord{\mathbb{D}\mathbb{B}}^{\prime}\rvert_{\varepsilon}\big{)}$
using Lemmas 28 and 18 where $\mathord{\mathbb{D}\mathbb{B}}^{\prime}$ is the
output instance space of $\widetilde{Q}$. Intuitively,
$\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}$ are the
instances that are $\varepsilon$-coarse in the $(A_{1},\dots,A_{k})$
attributes of $R$. Similar to Corollary 20 it suffices to show that
$\\{D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}\colon\lvert
Q(D)\rvert_{\bm{F}}\geq n\\}$ is measurable for all positive $\varepsilon$,
$\bm{F}\in\mathfrak{F}_{Q}$ and $n\in\mathbb{N}_{+}$.

We show that for all
$D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}$, all
$\bm{F}\in\mathfrak{F}_{Q}$, and all $n\in\mathbb{N}_{+}$ it holds that
$\lvert Q(D)\rvert_{\bm{F}}\geq n$ is equivalent to $D$ satisfying the
following condition.

######  Condition 41.

For all positive $r<\tfrac{\varepsilon}{3}$ there exist
$t_{1,r}^{*},\dots,t_{n,r}^{*}\in\mathbb{T}_{\mathsf{grp}}^{*}$ with
$d_{\mathsf{grp}}(t_{i,r}^{*},t_{j,r}^{*})>\tfrac{\varepsilon}{3}$ such that
$\lvert Q_{t_{i,r}^{*},r}(D)\rvert_{\bm{F}}\geq 1$ for all $i=1,\dots,n$.

$\Rightarrow$:

Let $D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}$ such
that $\lvert Q(D)\rvert_{\bm{F}}\geq n$. Then there exist
$R_{Q}(t_{1},b_{1}),\dots,R_{Q}(t_{n},b_{n})\in\bm{F}$ with $\lvert
Q(D)\rvert_{R_{Q}(t_{i},b_{i})}=1$ for all $i=1,\dots,n$ such that
$d_{\mathsf{grp}}(t_{i},t_{j})>\varepsilon$ for all $i\neq j$. Since
$\mathbb{T}_{\mathsf{grp}}^{*}$ is dense in $\mathbb{T}_{\mathsf{grp}}$, for
all positive $r$ (in particular $r<\tfrac{\varepsilon}{3}$) there exist
$t_{i,r}^{*}$ with $d_{\mathsf{grp}}(t_{i},t_{i,r}^{*})<r$ for all
$i=1,\dots,n$. Since $d_{\mathsf{grp}}(t_{i},t_{j})>\varepsilon$, it follows
that $d_{\mathsf{grp}}(t_{i,r}^{*},t_{j,r}^{*})>\tfrac{\varepsilon}{3}$. In
particular, every $B_{r}(t_{i,r}^{*})$ contains no tuple among
$t_{1},\dots,t_{n}$ other than $t_{i}$. Thus,

$\lvert Q_{t_{i,r}^{*},r}(D)\rvert_{R_{Q}(t_{i},b_{i})}=1\text{,}$

i. e. $\lvert Q_{t_{i,r}^{*},r}(D)\rvert_{\bm{F}}\geq 1$ for all
$i=1,\dots,n$.

$\Leftarrow$:

Suppose Condition 41 holds. Since $D$ is finite, the tuples $t_{i,r}^{*}$ in
Condition 41 converge to tuples $t_{i}$ with

$\lvert Q_{t_{i,r}^{*},r}(D)\rvert_{R_{Q}(t_{i},b_{i})}\geq 1$ (13)

for some $b_{i}\in\mathbb{A}$ where $R_{Q}(t_{i},b_{i})\in\bm{F}$. Because
$D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}$, and
$d_{\mathsf{grp}}(t_{i,r}^{*},t_{j,r}^{*})>\tfrac{\varepsilon}{3}$, the tuples
$t_{1},\dots,t_{n}$ are pairwise distinct. Thus, 13 implies $\lvert
Q(D)\rvert_{\bm{F}}\geq\sum_{i=1}^{n}\lvert
Q_{t_{i,r}^{*},r}(D)\rvert_{\bm{F}}\geq n$.

The equivalence still holds, when $r$ is additionally required to be rational.
Thus,

$\\{D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}\colon\lvert
Q(D)\rvert_{\bm{F}}\geq
n\\}=\bigcap_{r}\bigcup_{t_{1,r}^{*},\dots,t_{n,r}^{*}}\bigcap_{i}\\{D\in\widetilde{\mathord{\mathbb{D}\mathbb{B}}}\rvert_{\varepsilon}\colon\lvert
Q_{t_{i,r}^{*},r}(D)\rvert_{\bm{F}}\geq 1\\}\text{.}$

with the indices ranging as in Condition 41 (and $r$ rational).

By the observation of Section 6, Theorem 40 applies to the operators from
Table 8.

######  Corollary 42.

The query $\varpi_{#1}\lparen R\rparen$ is measurable for all the aggregate
operators
$\Phi\in\\{\bm{\mathsf{CNT}},\bm{\mathsf{CNTd}},\bm{\mathsf{SUM}},\bm{\mathsf{MIN}},\bm{\mathsf{MAX}},\bm{\mathsf{AVG}}\\}$.
∎

##  7\. Datalog

The measurability results of the previous sections also allow us to say
something about fixpoint queries. The key observation is the following lemma,
which follows from Fact 32.

######  Lemma 43.

Let $(Q_{i})_{i\in\mathbb{N}}$ be a family of measurable queries such that
$Q(D)\coloneqq\bigcup_{i=0}^{\infty}Q_{i}(D)$ is finite for all
$D\in\mathbb{D}$. Then $Q$ is a measurable query.

######  Proof 7.1.

For all $n\in\mathbb{N}$, let $Q^{(n)}\coloneqq\bigcup_{i=0}^{n}Q_{i}$. As a
finite (maximum-)union of measurable queries, $Q^{(n)}$ is measurable. As
$Q(D)$ is finite for all $D$, it holds that
$Q(D)=\lim_{n\to\infty}Q^{(n)}(D)$, and $Q$ is the pointwise limit of the
functions $Q^{(n)}$. Thus, $Q=\lim_{n\to\infty}Q^{(n)}$ is measurable as well.

We omit the definition of Datalog and related query languages. For simplicity,
we consider set PDBs, and Datalog with sets semantics. Recall that if $Q$ is a
Datalog query, then $Q$ can be written as a countable union of conjunctive
queries [AHV95].555We note that a similar statement can be made for the
bounded fixpoints semantics over bags featured in [CL97]. Thus, combining our
measurability results with the above lemma, we obtain the following.

######  Corollary 44.

Every Datalog query is measurable. ∎

In fact, our argumentation can be applied to all types of queries with
operators that are based on countable iterative (or inductive, inflationary,
or fixed-point) processes. All we need is that the iterative mechanism forms a
converging sequence of measurable queries. For partial Datalog / fixed-point
logic, we cannot directly use Corollary 44, but a slightly more complicated
argument still based on countable limits works there as well.

##  8\. Beyond Possible Worlds Semantics

In Section 3.2, we introduced the notion of queries or views on probabilistic
databases solely based on the existing notion of queries and views for
traditional databases, which we referred to as the _possible worlds semantics_
of queries or views. As the title of this section suggests, we explicitly
leave this setup.666Note that we _do not_ abandon our definition of PDBs as
probability spaces over possible worlds. It is only that we broaden the notion