TU Dortmund<EMAIL_ADDRESS>Dortmund
<EMAIL_ADDRESS>Dortmund
<EMAIL_ADDRESS>Jens Keppeler, Thomas
Schwentick, and Christopher Spinrath [300]Theory of computation Shared memory
algorithms [500]Theory of computation Database query processing and
optimization (theory) This paper – without the appendix – has been accepted
for publication in the proceedings of the 26th International Conference on
Database Theory (ICDT 2023). Floris Geerts and Brecht Vandevoort 2 26th
International Conference on Database Theory (ICDT 2023) ICDT 2023 ICDT 2023
March 28–31, 2023 Ioannina, Greece 255 16

# Work-Efficient Query Evaluation with PRAMs

Jens Keppeler  Thomas Schwentick  Christopher Spinrath

###### Abstract

The paper studies query evaluation in parallel constant time in the PRAM
model. While it is well-known that all relational algebra queries can be
evaluated in constant time on an appropriate CRCW-PRAM, this paper is
interested in the efficiency of evaluation algorithms, that is, in the number
of processors or, asymptotically equivalent, in the work. Naive evaluation in
the parallel setting results in huge (polynomial) bounds on the work of such
algorithms and in presentations of the result sets that can be extremely
scattered in memory. The paper first discusses some obstacles for constant
time PRAM query evaluation. It presents algorithms for relational operators
that are considerably more efficient than the naive approaches. Further it
explores three settings, in which efficient sequential query evaluation
algorithms exist: acyclic queries, semi-join algebra queries, and join queries
— the latter in the worst-case optimal framework. Under natural assumptions on
the representation of the database, the work of the given algorithms matches
the best sequential algorithms in the case of semi-join queries, and it comes
close in the other two settings. An important tool is the compaction technique
from Hagerup (1992).

###### keywords:

PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex
queries

###### category:

##  1 Introduction

Parallel query evaluation has been an active research area during the last 10+
years. Parallel evaluation algorithms have been thoroughly investigated,
mostly using the Massively Parallel Communication (MPC) model [7]. For surveys
we refer to [21, 17].

The MPC model is arguably very well-suited to study parallel query evaluation.
However, it is not the only model for parallel query evaluation. Indeed, there
is also the Parallel Random Access Machine (PRAM) model, a more “theoretical”
model which allows for a more fine-grained analysis of parallel algorithms,
particularly in non-distributed settings. It was shown by Immerman [18, 19]
that PRAMs with polynomially many processors can evaluate first-order formulas
and thus relational algebra queries in time $\operatorname{\mathcal{O}}(1)$.

In the study of PRAM algorithms it is considered very important that
algorithms perform well compared with sequential algorithms. The overall
number of computation steps in a PRAM-computation is called its _work_. An
important goal is to design parallel algorithms that are _work-optimal_ in the
sense that their work asymptotically matches the running time of the best
sequential algorithms.

Obviously, for $\operatorname{\mathcal{O}}(1)$-time PRAM algorithms the work
and the number of processors differ at most by a constant factor. Thus, the
result by Immerman shows that relational algebra queries can be evaluated with
polynomial work. Surprisingly, to the best of our knowledge, work-efficiency
of $\operatorname{\mathcal{O}}(1)$-time PRAM algorithms for query evaluation
has not been investigated in the literature. This paper is meant to lay some
groundwork in this direction.

The proof of the afore-mentioned result that each relational algebra query can
be evaluated in constant-time by a PRAM with polynomial work is scattered over
several papers. It consists basically of three steps, translating from queries
to first-order logic formulas [11], to bounded-depth circuits [6], and then to
PRAMs [18]. It was not meant as a “practical translation” of queries and does
not yield one. However, it is not hard to see directly that the operators of
the relational algebra can, in principle, be evaluated in constant time on a
PRAM. It is a bit less obvious, though, how the output of such an operation is
represented, and how it can be fed into the next operator.

######  Example 1.1.

Let us consider an example to illustrate some issues of constant-time query
evaluation on a PRAM. Let $q$ be the following conjunctive query, written in a
rule-based fashion, for readability.

$q(x,y,z)\leftarrow
E(x,x_{1}),E(x_{1},x_{2}),E(y,y_{1}),E(y_{1},y_{2}),E(z,z_{1}),E(z_{1},z_{2}),R(x_{2},y_{2},z_{2})$

A (very) naive evaluation algorithm can assign one processor to each
combination of six $E$-tuples and one $R$-tuple, resulting in work
$\operatorname{\mathcal{O}}(|E|^{6}|R|)$. Since the query is obviously
acyclic, it can be evaluated more efficiently in the spirit of Yannakakis’
algorithm. For simplicity, we ignore the semi-join step of the Yannakakis
algorithm. The join underlying the first two atoms $E(x,x_{1}),E(x_{1},x_{2})$
can be computed as a sub-query $q_{1}(x,x_{2})\leftarrow
E(x,x_{1}),E(x_{1},x_{2})$. This can be evaluated by $|E|^{2}$ many
processors, each getting a pair of tuples $E(a_{1},a_{2}),E(b_{1},b_{2})$ and
producing output tuple $(a_{1},b_{2})$ in case $a_{2}=b_{1}$. The output can
be written into a 2-dimensional table, indexed in both dimensions by the
tuples of $E$. In the next round, the output tuples can be joined with tuples
from $R$ to compute $q_{2}(x,y_{2},z_{2})\leftarrow
E(x,x_{1}),E(x_{1},x_{2}),R(x_{2},y_{2},z_{2})$. However, since it is not
clear in advance, which entries of the two-dimensional table carry
$q_{1}$-tuples, the required work is about $|E|^{2}\cdot|R|$. Output tuples of
$q_{2}$ can again be written into a 2-dimensional table, this time indexed by
one tuple from $E$ (for $x$) and one tuple from $R$ (for $y_{2}$ and $z_{2}$).
Proceeding in a similar fashion, $q$ can be evaluated with work
$\operatorname{\mathcal{O}}(|E|^{3}|R|)$. Other evaluation orders are possible
but result in similar work bounds. In terms of the input size of the database,
this amounts to $\operatorname{\mathcal{O}}(\textsf{IN}^{4})$, whereas
Yannakakis’ algorithm yields
$\operatorname{\mathcal{O}}(\textsf{IN}\cdot\textsf{OUT})$ in the sequential
setting, where IN denotes the number of tuples in the given relations and OUT
the size of the query result, respectively.

Let us take a look at the representation of the output of this algorithm. The
result tuples reside in a 3-dimensional table, each indexed by a tuple from
$E$. It is thus scattered over a space of size $|E|^{3}$, no matter the size
of the result. Furthermore, the same output tuple might occur several times
due to several valuations. To produce a table, in which each output tuples
occurs exactly once, a deduplication step is needed, which could yield
additional work in the order of $|E|^{6}$.

The example illustrates two challenges posed by the
$\operatorname{\mathcal{O}}(1)$-time PRAM setting, which will be discussed in
more detail in section 3.

  * •

It is, in general, not possible to represent the result of a query in a
compact form, say, as an array, contiguously filled with result tuples. This
obstacle results here in upper bounds in terms of the size of the input
database, but not in the size of the query result.

  * •

It might be necessary to deduplicate output (or intermediate) relations, but,
unfortunately, this cannot be done by sorting a relation, since sorting is not
possible in $\operatorname{\mathcal{O}}(1)$-time on a PRAM, either.

We will use compactification techniques for PRAMs from [16] to deal with the
first challenge. The second challenge is addressed by a suitable
representation of the relations. Besides the setting without any assumptions,
we consider the setting, where data items are mapped to an initial segment of
the natural numbers by a dictionary, and the setting where the relations are
represented by ordered arrays.

We show that, for each $\varepsilon>0$, there is a Yannakakis-based algorithms
for acyclic join queries in the dictionary setting with an upper work bound of
$\operatorname{\mathcal{O}}(\textsf{IN}\cdot\textsf{OUT})^{1+\varepsilon}$.
Two other results are work-optimal algorithms for queries of the semijoin
algebra and almost worst-case and work-optimal algorithms for join queries.

We emphasize that the stated result does not claim a fixed algorithm that has
an upper work bound $W$ such that, for every $\varepsilon>0$, it holds
$W\in\operatorname{\mathcal{O}}(\textsf{IN}\cdot\textsf{OUT})^{1+\varepsilon}$.
It rather means that there is a uniform algorithm that has $\varepsilon$ as a
parameter and has the stated work bound, for each fixed $\varepsilon>0$. The
linear factor hidden in the $\operatorname{\mathcal{O}}$-notation thus depends
on $\varepsilon$. This holds analogously for our other upper bounds of this
form.

This paper consists roughly of three parts, each of which has some
contributions to our knowledge on work-efficient constant-time PRAM query
evaluation.

The first part presents some preliminaries in section 2, discusses the
framework including some of our (typical) assumptions and data structures in
section 4, surveys lower bound results that pose challenges for
$\operatorname{\mathcal{O}}(1)$-time PRAM query evaluation in section 3, and
presents some basic operations that will be used in our query evaluation
algorithms in section 4.

The second part presents algorithms for these basic operations in section 5
and for relational operators in section 6.

After this preparation, the third part studies query evaluation in three
settings in which (arguably) efficient algorithms exist for sequential query
evaluation: the semi-join algebra (subsection 7.1), acyclic queries
(subsection 7.2), and worst-case optimal join evaluation (subsection 7.3).

##### Related work.

Due to space limitations, we only mention two other related papers. In a
recent paper, query evaluation by circuits has been studied [30]. Although
this is in principle closely related, the paper ignores polylogarithmic depth
factors and therefore does not study $\operatorname{\mathcal{O}}(1)$-time. The
work of $\operatorname{\mathcal{O}}(1)$-time PRAM algorithms has recently been
studied in the context of dynamic complexity, where the database can change
and the algorithms need to _maintain_ the query result [27].

##### Acknowledgements.

We are grateful to Uri Zwick for clarifications regarding results in [14] and
to Jonas Schmidt and Jennifer Todtenhoefer for careful proof reading.
Furthermore, we thank the reviewers of ICDT for many insightful suggestions.

##  2 Preliminaries

In this section, we fix some notation and recall some concepts from database
theory and PRAMs that are relevant for this paper. For a natural number $n$,
we write $[n]$ for $\\{1,\ldots,n\\}$.

A _database schema $\Sigma$_ is a finite set of relation symbols, where each
symbol $R$ is equipped with a finite set $\textnormal{{attr}}(R)$ of
attributes. A tuple $t=(a_{1},\ldots,a_{|X|})$ over a finite list
$X=(A_{1},\ldots,A_{k})$ of attributes has, for each $i$, a value $a_{i}$ for
attribute $A_{i}$. Unless we are interested in the lexicographic order of a
relation, induced by $X$, we can view $X$ as a set. An $R$-relation is a
finite set of tuples over $\textnormal{{attr}}(R)$. The arity of $R$ is
$|\textnormal{{attr}}(R)|$. For $Y\subseteq X$, we write $t[Y]$ for the
restriction of $t$ to $Y$. For $Y\subseteq\textnormal{{attr}}(R)$,
$R[Y]=\\{t[Y]\mid t\in R\\}$. A database $D$ over $\Sigma$ consists of an
$R$-relation $D(R)$, for each $R\in\Sigma$. We usually write $R$ instead of
$D(R)$ if $D$ is understood from the context. That is, we do not distinguish
between relations and relation symbols. The size $|R|$ of a relation $R$ is
the number of tuples in $R$. By $|D|$ we denote the number of tuple entries in
database $D$. For details on (the operators of) the relational algebra, we
refer to [3]. We always assume a fixed schema and therefore a fixed maximal
arity of tuples.

##### Parallel Random Access Machines (PRAMs).

A _parallel random access machine_ (PRAM) consists of a number of processors
that work in parallel and use a shared memory. The memory is comprised of
memory cells which can be accessed by a processor in
$\operatorname{\mathcal{O}}(1)$ time. Furthermore, we assume that the usual
arithmetic and bitwise operations can be done in
$\operatorname{\mathcal{O}}(1)$ time by a processor. In particular, since the
schema is considered fixed, a database tuple can be loaded, compared, etc. in
$\operatorname{\mathcal{O}}(1)$ time by one processor.

We mostly use the Concurrent-Read Concurrent-Write model (CRCW-PRAM), i.e.
processors are allowed to read and write concurrently from and to the same
memory location. More precisely, we mainly assume the _arbitrary_ PRAM model:
if multiple processors concurrently write to the same memory location, one of
them, “arbitrarily”, succeeds. For some algorithms the _common_ model would
suffice, where all processors need to write the same value into the same
location. We sometimes also use the weaker Exclusive-Read Exclusive-Write
model (EREW-PRAM), where concurrent access is forbidden and the CREW-PRAM,
where concurrent writing is forbidden. The work $w$ of a PRAM computation is
the sum of the number of all computation steps of all processors made during
the computation. We define the space $s$ required by a PRAM computation as the
maximal index of any memory cell accessed during the computation. We refer to
[20] for more details on PRAMs and to [28, Section 2.2.3] for a discussion of
alternative space measures.

In principle, we assume that relations are stored as sequences of tuples,
i.e., as arrays. Informally an array $\mathcal{A}$ is a sequence
$t_{1},\ldots,t_{N}$ and it represents a relation $R$, if each tuple from $R$
appears once as some $t_{i}$. In section 4, we describe more precisely, how
databases are represented for our PRAM algorithms.

##  3 Obstacles

We next discuss some obstacles that pose challenges for
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms for query evaluation.
They stem from various lower bound results from the literature.

The first obstacle, already mentioned in the introduction, is that we cannot
expect that query results can be stored in arrays in a compact fashion, that
is, as a sequence $t_{1},\ldots,t_{m}$ of tuples, for a result with $m$
tuples. This follows from the following lower bound on the _linear approximate
compaction problem_ , where the, somewhat relaxed, goal is to move $m$
scattered tuples into a target array of size $4m$.

######  Proposition 3.1 ([23, Theorem 4.1]).

Solving the linear approximate compaction problem on a randomized strong
priority CRCW-PRAM requires $\Omega(\log^{*}{n})$ expected time.

Since the PRAM model of that bound is stronger than the arbitrary CRCW model,
it applies to our setting.

The following theorem illustrates, how this lower bound restrains the ability
to compute query results in a compact form, even if the input relations are
given by compact arrays. Analogous results can be shown for simple projection
and selection queries.

######  Theorem 3.2.

Let $q$ be the conjunctive query defined by $q:H(x)\leftarrow R(x),S(x)$.
Every algorithm, which, upon input of arrays for relations $R$ and $S$,
computes an array of size $|q(D)|$ for $q(D)$ without empty cells, requires
$\omega(1)$ time. This holds even if the arrays for $R$ and $S$ are compact
and their entries are lexicographically ordered.

######  Proof 3.3 (Proof sketch).

Towards a contradiction, we assume that there is an algorithm on a PRAM which
computes in constant time, upon input of an input database $D$, an array of
size $|q(D)|$ for the query result $q(D)$. This can be used to solve the
linear approximate compaction problem in constant time as follows. Let
$\mathcal{A}$ be an instance for the linear approximate compaction problem
with $m$ non-empty cells. In the first step create an array $\mathcal{A}_{R}$
of size $n$ for the unary relation $R$ that consists of even numbers $2$ to
$2n$. This can be done in parallel in constant time with $n$ processors.

In the second step, store, for every $i\in\\{1,$…$,n\\}$, the value $2i$ in
the array $\mathcal{A}_{S}$ of size $n$ for relation $S$ if $\mathcal{A}[i]$
has a value (i.e. the $i$-th cell is not empty), and $2i+1$, otherwise. Hence,
the query result of $q$ exactly consists of even numbers $2i$ where $i$ is an
index such that $\mathcal{A}[i]$ has a value. From the array for the query
result a solution for the linear approximate compaction problem can be
obtained by replacing every value $2i$ in the result by $\mathcal{A}[i]$. The
size of the compact array is $m$.

All in all, the algorithm takes constant time to solve the linear approximate
compaction problem. This is a contradiction to 3.1. We note that by
construction, the arrays for the relations $R$ and $S$ are ordered and have no
empty cells.

As a consequence of Theorem 3.2, our main data structure to represent
relations are arrays that might contain _empty cells_ that do not correspond
to tuples in the relation.

As the example in the introduction illustrated, it is important that
intermediate results can be compacted to some extent. Indeed, processors can
be assigned to all cells of an array, but not so easily to only the non-empty
cells. We extensively use a classical technique by Hagerup [16] that yields
some (non-linear) compaction (see 5.1 for the statement of this result).
However, Hagerup’s compaction algorithm does not preserve the order of the
elements in the array, so ordered arrays with non-empty cells are transformed
into more compact but unordered arrays.

This brings us to another notorious obstacle for
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms: they can not sort
with polynomially many processors, even not in a (slightly) non-compact
fashion. The _padded sort problem_ asks to sort $n$ given items into an array
of length $n+o(n)$ with empty cells in spots without an item.

######  Proposition 3.4 ([23, Theorem 4.2]).

Solving the padded sort problem on a randomized strong priority CRCW-PRAM
requires $\Omega(\log^{*}{n})$ expected time.

Thus, we cannot rely on sorting as an intermediate operator, either.

Yet another weakness of $\operatorname{\mathcal{O}}(1)$-time parallel
algorithms is counting. It follows readily from the equivalence with
polynomial-size constant-depth circuits that (reasonable) CRCW-PRAMs cannot
tell whether the number of ones in a sequence of zeros and ones is even [13,
2], let alone count them. These obstacles apply in particular to the
evaluation of aggregate queries and for query evaluation under bag semantics
with explicit representation of multiplicities of tuples. However, we do not
study any of those in this paper.

##### Note.

It turned out at submission time of this paper that we had missed a paper by
Goldberg and Zwick [14], that contains two improvements to the above: it shows
that _ordered_ compaction and approximate counting, up to a factor of
$1+\frac{1}{(\log n)^{a}}$, for any $a>0$, are possible in constant time with
work $\operatorname{\mathcal{O}}(n^{1+\varepsilon})$. In fact both results
rely on the same technique for computing consistent approximate prefix sums.
We discuss this issue further in our conclusion.

##  4 Basics

Query evaluation algorithms often use additional data structures like index
structures. We consider two different kinds of such data structures for our
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms.

The first setting that we consider is that of dictionary-based compressed
databases, see, e.g., [10]. In a nutshell, the database has a dictionary that
maps data values to natural numbers and internally stores and manipulates
tuples over these numbers to improve performance. Such dictionaries are often
defined attribute-wise, but for the purpose of this paper this does not
matter. Query evaluation does not need to touch the actual dictionaries, it
only works with the numbers. In this paper, we write “in the presence of a
dictionary” or “in the dictionary setting” to indicate that we assume that
such a dictionary exists for the database $D$ at hand, and that it uses
numbers of size at most $\operatorname{\mathcal{O}}(|D|)$. In particular, the
database relations then only contain numbers of this size.

In the other _ordered_ setting, we assume that database relations are
represented by ordered arrays, for each order of its attributes. In
particular, we assume a linear order on the data values.

##### Arrays.

As mentioned before, we assume in this paper that relations are stored in
1-dimensional arrays, whose entries are tuples that might be augmented by
additional data.

More formally, an array $\mathcal{A}$ is a sequence of consecutive memory
cells. The number of cells is its _size_ $\left|\mathcal{A}\right|$. By
$\mathcal{A}[i]$ for $1\leq i\leq\left|\mathcal{A}\right|$ we refer to the
$i$-th cell of $\mathcal{A}$ and to the (current) content of that cell, and we
call $i$ its index. We assume that the size of an array is always available to
all processors (for instance, it might be stored in a ?hidden? cell with index
$0$). Given an index $i$, any processor can access cell $\mathcal{A}[i]$ in
$\operatorname{\mathcal{O}}(1)$ time with $\operatorname{\mathcal{O}}(1)$
work.

In this paper, a cell $\mathcal{A}[i]$ of an array always holds a
distinguished database tuple $t=\mathcal{A}[i].t$ (over some schema) and a
flag that indicates whether the cell is inhabited.111If a cell is not
inhabited, its data is basically ignored. There might be additional data,
e.g., further Boolean flags and links to other cells of (possibly) other
arrays.

We say that an array _represents_ a relation $R$ if some inhabited cell holds
tuple $t$, for each tuple $t$ of $R$, and no inhabited cells contain other
tuples. It represents $R$ _concisely_ , if each tuple occurs in exactly one
inhabited cell. To indicate that an array represents a relation $R$ we usually
denote it as $\mathcal{A}_{R}$, $\mathcal{A^{\prime}}_{R}$, etc.

An array $\mathcal{A}$ that represents a relation $R$ is _ordered_ if it is
lexicographically ordered with respect to some ordered list $X$ of the
attributes from $R$’s schema in the obvious sense. Its order is
$Y$-compatible, for a set $Y$ of attributes, if the attributes of $Y$ form a
prefix of $X$ (hence the order induces a partial order with respect to $Y$).

We often consider the _induced tuple sequence_
$t_{1},\ldots,t_{\left|\mathcal{A}\right|}$ of an array $\mathcal{A}$. Here,
$t_{i}=\mathcal{A}[i].t$ is a _proper_ tuple, if $\mathcal{A}[i]$ is
inhabited, or otherwise $t_{i}$ is the _empty tuple_ $\bot$.

######  Example 4.1.

The tuple sequence $[(1,5),\bot,(3,4),(8,3),(1,5),\bot,\bot,(7,3)]$ from an
array $\mathcal{A}$ of size eight has five proper tuples and three empty
tuples. It represents the relation $R=\\{(1,5),(3,4),(8,3),(7,3)\\}$, but
_not_ concisely. The sequence $[(1,5),(3,4),(7,3),\bot,(8,3)]$ represents $R$
concisely and ordered with respect to the canonical attribute order.

##### Operations and links.

Before we explain the basic operations used by our evaluation algorithms we
illustrate some aspects by an example.

######  Example 4.2.

We sketch how to evaluate the projection $\pi_{B}(R)$ given the array
$\mathcal{A}=[(1,5),(3,4),(7,3),\bot,(8,3)]$ from 4.1.

First, with the operation $\operatorname{\textnormal{{Map}}}$ the array
$\mathcal{A^{\prime}}[5,4,3,\bot,3]$ is computed and each tuple
$\mathcal{A}[i]$ is augmented by a link to $\mathcal{A^{\prime}}[i]$ and vice
versa. To achieve this, the tuples from $\mathcal{A}$ are loaded to processors
$1,\ldots,5$, each processor applies the necessary changes to its tuple, and
then writes the new tuple to the new array $\mathcal{A^{\prime}}$. We note
that it is not known in advance which cells of $\mathcal{A}$ are inhabited and
therefore, we need to assign one processor for each cell. Each processor only
applies a constant number of steps, so the overall work for the
$\operatorname{\textnormal{{Map}}}$-operation is
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$.

To get an array that represents $\pi_{B}(R)$ concisely, a second operation
eliminates duplicates. To this end, it creates a copy
$\mathcal{A^{\prime\prime}}$ of $\mathcal{A^{\prime}}$ and checks with one
processor for each pair $(i,j)$ of indices with $i<j$ in parallel, whether
$\mathcal{A^{\prime\prime}}[i]=\mathcal{A^{\prime\prime}}[j]$ holds. If
$\mathcal{A^{\prime\prime}}[i]=\mathcal{A^{\prime\prime}}[j]$ holds, then cell
$\mathcal{A^{\prime\prime}}[i]$ is made uninhabited. Lastly, the algorithm
creates links from every cell in $\mathcal{A^{\prime}}$ to the unique
inhabited cell in $\mathcal{A^{\prime\prime}}$ holding the same tuple. To do
this, it checks with one processor for each pair $(i,j)$ of indices with $i<j$
in parallel, whether $\mathcal{A^{\prime}}[i]=\mathcal{A^{\prime\prime}}[j]$
holds and $\mathcal{A^{\prime\prime}}[j]$ is inhabited. If this is the case,
the processor for $(i,j)$ augments the cell $\mathcal{A^{\prime}}[i]$ with a
link to $\mathcal{A^{\prime\prime}}[j]$ and vice versa. Note that multiple
processors might attempt to augment a cell $\mathcal{A^{\prime\prime}}[j]$
with a link to a cell of $\mathcal{A^{\prime}}$; but since this happens in
parallel only one processor will be successful. Overall, we get 2-step-links
from $\mathcal{A}$ to $\mathcal{A^{\prime\prime}}$ and 2-step-links from
$\mathcal{A^{\prime\prime}}$ to ?representatives? in $\mathcal{A}$.

The second operation has a work bound of
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{2})$ because it suffices
to assign one processor for each pair $(i,j)$ of indices and each processor
only applies a constant number of steps. We will show in section 5 that work
bounds $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{1+\varepsilon})$ can be
achieved for eliminating duplicates in the dictionary and ordered setting,
respectively (cf. 5.18).

Of course, one might skip the intermediate writing and reading of tuples of
$\mathcal{A^{\prime}}$. We will often blur the distinction whether tuples
reside in an array or within a sequence of processors.

##### Basic operations.

Next, we describe some basic operations which we will use as building blocks
in the remainder of this paper to query evaluation algorithms for PRAMs. We
will describe algorithms for them in the next section.

Just as in 4.2, the operations usually get arrays as input, produce arrays as
output, augment tuples and add links between tuples. In fact, each time a
tuple of a new array results from some tuple of an input array we silently
assume that (possibly mutual) links are added.

$\operatorname{\textnormal{{Concatenate}}}(\mathcal{A},\mathcal{B})$

computes a new array $\mathcal{C}$ of size
$\left|\mathcal{A}\right|+\left|\mathcal{B}\right|$ consisting of the tuples
from $\mathcal{A}$ followed by the tuples from $\mathcal{B}$ in the obvious
way. As usual, mutual links are added, in particular, the link from
$\mathcal{B}[1]$ indicates where the tuples from $\mathcal{B}$ start in
$\mathcal{C}$.

$\operatorname{\textnormal{{Map}}}(\mathcal{A},f)$

returns an array $\mathcal{B}$ with $\mathcal{B}[i]=f(\mathcal{A}[i])$, where
$f$ is a function that maps proper tuples in $\mathcal{A}$ to empty or proper
(possibly augmented) tuples and empty to empty tuples.

$\operatorname{\textnormal{{Partition}}}(\mathcal{A},n,g)$

yields $n$ arrays $\mathcal{A}_{1},\ldots,\mathcal{A}_{n}$ of size
$\left|\mathcal{A}\right|$ and adds links. Here, $g$ is a function that maps
proper tuples in $\mathcal{A}$ to numbers in $[n]$. For every
$i\in[\left|\mathcal{A}\right|]$ and every $j\in[n]$,
$\mathcal{A}_{j}[i]=\mathcal{A}[i]$, if $\mathcal{A}[i]$ is inhabited and
$g(\mathcal{A}[i])=j$, otherwise $\mathcal{A}_{j}[i]$ is uninhabited.

$\operatorname{\textnormal{{Compact}}}_{\varepsilon}(\mathcal{A})$

copies the proper tuples in $\mathcal{A}$ into distinct cells of an array
$\mathcal{B}$ of size at most $b^{i\varepsilon}$, where
$i\leq\frac{1}{\varepsilon}(1+\varepsilon)$ is a non-negative integer222In the
special case $n=0$, $i=0$ is required. such that $b^{i\varepsilon}\leq
n^{1+\varepsilon}b^{\varepsilon}$, and $b$ is $\left|\mathcal{A}\right|$ or an
upper bound for the (possibly unknown) number $n$ of proper tuples in
$\mathcal{A}$, given as an optional parameter. We refer to $i$ as the
?compaction parameter? and note that it can be inferred from the size of
$\mathcal{B}$. Mutual links are added as usual.

$\operatorname{\textnormal{{SearchRepresentatives}}}(\mathcal{A},\mathcal{B})$

links every inhabited cell $\mathcal{A}[i]$ to an inhabited representative
cell $\mathcal{B}[j]$, such that $\mathcal{B}[j].t=\mathcal{A}[i].t$ holds, if
such a cell exists. Furthermore, for every $i_{1},i_{2}$ with
$\mathcal{A}[i_{1}]=\mathcal{A}[i_{2}]\neq\bot$, both $\mathcal{A}[i_{1}]$ and
$\mathcal{A}[i_{2}]$ are linked to the same representative. If required a copy
of $\mathcal{B}$ might be produced in which representatives are marked. We
stress that $\mathcal{B}$ does not have to represent its relation concisely,
and, in fact, the operation is used to remove duplicates.

$\operatorname{\textnormal{{Deduplicate}}}(\mathcal{A})$ chooses one
representative tuple for each tuple-value, marks the remaining cells as
uninhabited and redirects incoming links from other arrays towards the
representatives, if possible.

##  5 Algorithmic Techniques and Algorithms for Basic Array Operations

In this section, we first describe some important algorithmic techniques and
present algorithms for the basic operations established in section 4,
afterwards.

##### Compaction.

To implement the operation
$\operatorname{\textnormal{{Compact}}}_{\varepsilon}$, we will utilise the
following classical result by Hagerup, whose formulation is slightly adapted
to our setting.

######  Proposition 5.1 ([16], Unnumbered theorem, p. 340).

For every $\varepsilon>0$, there is a $\operatorname{\mathcal{O}}(1)$-time
parallel algorithm that, given an array $\mathcal{A}$ and a number $k$, copies
the proper tuples in $\mathcal{A}$ to distinct cells of an array of size at
most $k^{1+\varepsilon}$ or detects that $\mathcal{A}$ contains more than $k$
proper tuples. The algorithm requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and space on an
arbitrary CRCW-PRAM.

The space bound is only implicit in [16]. To keep the paper self-contained, we
give a detailed account of the algorithm in Appendix A, including an analysis
of the space requirements.

##### Array hash tables.

In the presence of dictionaries we use _array hash tables_ which associate
each inhabited cell in $\mathcal{A}$ with a number from
$[\left|\mathcal{A}\right|]$, such that $\mathcal{A}[i],\mathcal{A}[j]$ get
the same number if and only if $\mathcal{A}[i].t=\mathcal{A}[j].t$ holds.
Array hash tables can be efficiently computed.

######  Lemma 5.2.

There is a $\operatorname{\mathcal{O}}(1)$-time parallel algorithm that, in
the presence of a dictionary, computes an array hash table for a given array
$\mathcal{A}$, and requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot|D|)$ space on an
arbitrary CRCW-PRAM.

We note that due to the “arbitrary” resolution of concurrent write, the result
of such a computation is not uniquely determined by the relations.

######  Proof 5.3 (Proof sketch).

Let $A_{1},\ldots,A_{\ell}$ be the attributes of the relation $R$ represented
by $\mathcal{A}$ in an arbitrary but fixed order and define
$X_{j}=\\{A_{1},\ldots,A_{j}\\}$ for all $j\in\\{1,$…$,\ell\\}$. The algorithm
inductively computes hash values for tuples in $R[X_{j}]$ for increasing $j$
from $1$ to $\ell$.

The idea is to assign, to each tuple $t\in R[X_{j}]$, a processor number in
the range $\\{1,$…$,\left|\mathcal{A}\right|\\}$ as hash value and augment
each cell of $\mathcal{A}$ containing a proper tuple $t^{\prime}$ with
$t^{\prime}[X]=t$ by this hash value. Since the same (projected) tuple $t\in
R[X_{j}]$ might occur in multiple, pairwise different, cells of $\mathcal{A}$,
it does not suffice to load all tuples in $\mathcal{A}$ to
$\left|\mathcal{A}\right|$ processors and let each processor augment the tuple
loaded to it by its processor number: multiple (different) numbers might get
assigned to the same tuple (in different cells of $\mathcal{A}$). To resolve
these conflicts, the algorithm utilizes the presence of a dictionary and the
hash values for tuples in $R[X_{j-1}]$.

For the base case $j=1$ the algorithm allocates an auxiliary array of size
$\operatorname{\mathcal{O}}(|D|)$ and loads the tuples in $\mathcal{A}$ to
processors $1$ to $\left|\mathcal{A}\right|$. To be more precise, for each
$i\in\\{1,$…$,\left|\mathcal{A}\right|\\}$, the tuple $t_{i}$ in cell
$\mathcal{A}[i]$ is loaded to processor $i$. Recall that, in the dictionary
setting, each value in the active domain is a number of size at most
$\operatorname{\mathcal{O}}(|D|)$. Thus, the projection $t[A_{1}]$ can be used
as index for the auxiliary array. Each processor $i$ with a proper tuple
writes its processor number $i$ into cell $t_{i}[A_{1}]$ of the auxiliary
array and then assigns to $t_{i}$ the value actually written at position
$t_{i}[A_{1}]$. Note that, for each value $a$, all processors $i$ with
$t_{i}[A_{1}]=a$ will assign the same value to their tuple $t_{i}$, since
precisely one processor among the processors with $t_{i}[A_{1}]=a$ succeeds in
writing its number to cell $t_{i}[A_{1}]$ on an arbitrary CRCW-PRAM. This can
be done with $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and
$\operatorname{\mathcal{O}}(|D|)$ space.

For $j>1$ the algorithm proceeds similarly but also takes, for a tuple $t$,
the hash value $h_{j-1}(t[X_{j-1}])$ for $t[X_{j-1}]$ into account, in
addition to $t[A_{j}]$. For this purpose, the algorithm first computes the
hash values for $R[X_{j-1}]$. It then allocates an auxiliary array of size
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot|D|)$ which is
interpreted as two-dimensional array and each processor $i$ writes its number
into cell $(h_{j-1}(t_{i}[X_{j-1}]),t_{i}[X_{j}])$ of the auxiliary array (if
$t_{i}$ is a proper tuple). The number in this cell is then the hash value for
$t_{i}[X_{j}]$.

Writing and reading back the processor numbers requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and the auxiliary
array requires $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot|D|)$
space. The same bounds hold for the recursive invocations of
$\operatorname{\textnormal{{ComputeHashvalues}}}$. Since the recursion depth
is $\ell$, the procedure requires
$\operatorname{\mathcal{O}}(\ell\cdot\left|\mathcal{A}\right|)=\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$
work and, because the space for the auxiliary arrays can be reused,
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot|D|)$ space in total.

Since most of our query evaluation algorithms rely on these two techniques, we
adopt the arbitrary CRCW-PRAM as our standard model and refer to it simply by
_CRCW-PRAM_.

##### Search in ordered arrays.

In sequential database processing, indexes implemented by search trees play an
important role, in particularly for the test whether a given tuple is in a
given relation. We use ordered arrays instead. Our search algorithm for
ordered arrays uses links from each cell to the next and previous inhabited
cell. We refer to those links as predecessor and successor links,
respectively, and say an array is _fully linked_ if it has predecessor and
successor links.

######  Proposition 5.4.

For every $\varepsilon>0$, there is a $\operatorname{\mathcal{O}}(1)$-time
parallel algorithm that computes, for an array $\mathcal{A}$, predecessor and
successor links with work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{1+\varepsilon})$ on a
common CRCW-PRAM.

######  Proof 5.5 (Proof sketch).

We describe the computation of predecessor links. Successor links can be
computed analogously. Let $n=\left|\mathcal{A}\right|$ and
$\delta=\frac{\varepsilon}{2}$. In the first round, the algorithm considers
subintervals of length $n^{\delta}$ and establishes predecessor links within
them. To this end, it uses, for each interval a
$n^{\delta}{\times}n^{\delta}$-table whose entries $(i,j)$ with $i<j$ are
initialised by $1$, if $\mathcal{A}[i]$ is inhabited and, otherwise, by $0$.
Next, for each triple $i,j,k$ of positions in the interval entry $(i,j)$ is
set to $0$ if $i<k<j$ and $\mathcal{A}[k]$ is inhabited. It is easy to see
that afterwards entry $(i,j)$ still carries a 1 if and only if $i$ is the
predecessor of $j$. And for all such pairs a link from $\mathcal{A}[j]$ to
$\mathcal{A}[i]$ is added. For every interval, $(n^{\delta})^{3}=n^{3\delta}$
processors suffice for this computation, i.e. one processor for each triple
$i,j,k$ of positions in the interval. Since there are
$\frac{n}{n^{\delta}}=n^{1-\delta}$ intervals, this yields an overall work of
$n^{1-\delta}\cdot n^{3\delta}=n^{1+2\delta}=n^{1+\varepsilon}$. In the next
round, intervals of length $n^{2\delta}$ are considered and each is viewed as
a sequence of $n^{\delta}$ smaller intervals of length $n^{\delta}$. The goal
in the second round is to establish predecessor links for the minimum cells of
each of the smaller intervals. This can be done similarly with the same
asymptotic work as round 1. After $\lceil\frac{1}{\delta}\rceil$ rounds, this
process has established predecessor links for all cells (besides for the
minimum cells without a predecessor).

In fully linked ordered arrays, tuples can be searched for efficiently.

######  Proposition 5.6.

For every $\varepsilon>0$, there is a $\operatorname{\mathcal{O}}(1)$-time
parallel algorithm that computes, for a given tuple $t$ and an ordered array
$\mathcal{A}$ with predecessor and successor links, the largest tuple
$t^{\prime}$ in $\mathcal{A}$ with $t^{\prime}\leq t$ with work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{\varepsilon})$ on an
CREW-PRAM.

######  Proof 5.7 (Proof sketch).

Let $n=\left|\mathcal{A}\right|$. In the first round, using $n^{\varepsilon}$
processors, the algorithm tests for all cells with positions
$k=in^{1-\varepsilon}$ whether $\mathcal{A}[k]$ is inhabited, or the
predecessor of $\mathcal{A}[k]$ contains a tuple $t^{\prime}\leq t$ and
whether this does not hold for position $(i+1)n^{1-\varepsilon}$ or its
successor. By a suitable process the search continues recursively in the thus
identified sub-interval. After $\lceil\frac{1}{\varepsilon}\rceil$ rounds it
terminates. Since, in each round, $n^{\varepsilon}$ processors are used, the
statement follows.

We note that analogously it is possible to search for $m$ tuples in parallel
with work
$\operatorname{\mathcal{O}}(m\left|\mathcal{A}\right|^{\varepsilon})$.

As an alternative to ordered arrays, bounded-depth search trees could be used.
They can be defined in the obvious way with degree about $n^{\varepsilon}$.
The work for a search is asymptotically the same as for fully linked ordered
arrays.

##### Algorithms for basic array operations.

In the remainder of this section we consider algorithms for basic array
operations. For the operations $\operatorname{\textnormal{{Concatenate}}}$,
$\operatorname{\textnormal{{Map}}}$, and
$\operatorname{\textnormal{{Partition}}}$, neither the algorithm nor the
analysis depends on the setting, i.e. they are the same in the dictionary
setting and the ordered setting. Furthermore, their implementation is
straightforward and only requires EREW-PRAMs, instead of CRCW-PRAMs.

######  Lemma 5.8.

There is a $\operatorname{\mathcal{O}}(1)$-time parallel algorithm for
$\operatorname{\textnormal{{Concatenate}}}$ that, given arrays $\mathcal{A}$
and $\mathcal{B}$, requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)$
work and space on an EREW-PRAM.

######  Proof 5.9 (Proof sketch).

The tuples in $\mathcal{A}$ are loaded to processors $1$ to
$\left|\mathcal{A}\right|$ and the tuples in $\mathcal{B}$ to processors
$\left|\mathcal{A}\right|+1$ to
$\left|\mathcal{A}\right|+\left|\mathcal{B}\right|$. The tuples are then
stored in the output array $\mathcal{C}$. Each processor can also augment its
tuple (between $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$) with mutual
links.

######  Lemma 5.10.

There is a $\operatorname{\mathcal{O}}(1)$-time parallel algorithm for
$\operatorname{\textnormal{{Map}}}$ that, given an array $\mathcal{A}$ and a
function $f$ that can be evaluated in $\operatorname{\mathcal{O}}(1)$-time
with work and space $\operatorname{\mathcal{O}}(1)$ on an EREW-PRAM, requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ space on an EREW-PRAM.
If $f$ is order-preserving and $\mathcal{A}$ is ordered, then the output array
is ordered, too.

######  Proof 5.11 (Proof sketch).

The algorithm loads the tuples in $\mathcal{A}$ to processors $1$ to
$\left|\mathcal{A}\right|$ and each processor computes the image $f(t)$ for
its tuple $t$.

Since $f(t)$ has to be computed for $\left|\mathcal{A}\right|$ tuples, the
bounds for work and space follow.

######  Lemma 5.12.

There is a $\operatorname{\mathcal{O}}(1)$-time parallel algorithm for
$\operatorname{\textnormal{{Partition}}}$ that, given an array $\mathcal{A}$,
an integer $n$, and a function $g$ that maps proper tuples in $\mathcal{A}$
into $\\{1,$…$,n\\}$ and can be evaluated in
$\operatorname{\mathcal{O}}(1)$-time with work and space
$\operatorname{\mathcal{O}}(1)$, requires
$\operatorname{\mathcal{O}}(n\cdot\left|\mathcal{A}\right|)$ work and
$\operatorname{\mathcal{O}}(n\cdot\left|\mathcal{A}\right|)$ space on an EREW-
PRAM.

######  Proof 5.13 (Proof sketch).

The algorithm first augments every proper tuple $t$ with the number $g(t)$
using $\operatorname{\textnormal{{Map}}}$. This requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ space, cf. 5.10.

Then the arrays $\mathcal{A}_{1},\ldots,\mathcal{A}_{n}$ of size
$\left|\mathcal{A}\right|$ are allocated (and initialised). This requires
$\operatorname{\mathcal{O}}(n\cdot\left|\mathcal{A}\right|)$ work and space.

For each $i\in\\{1,$…$,\left|\mathcal{A}\right|\\}$ in parallel, the tuple
$t_{i}$ in cell $\mathcal{A}[i]$ is then – if it is a proper tuple – copied
into cell $\mathcal{A}_{j}[i]$ where $j=g(t_{i})$. This requires
$\operatorname{\mathcal{O}}(\mathcal{A})$ work.

Let us point out that the upper bound for the work stated in 5.12 can be
reduced to $\operatorname{\mathcal{O}}(n+\left|\mathcal{A}\right|)$ by
adapting the classical _lazy array initialisation technique_ for (sequential)
RAMs to PRAMs.333In a nutshell, this requires replacing a global counter by
one counter per processor and maintaining back-references to initialised cells
per processor (processors can still read counters and back-references of other
processors). It turned out, however, that this is not necessary for our
results, since $n$ is either a constant or the work is dominated by other
operations in our algorithms.

The algorithm for $\operatorname{\textnormal{{Compact}}}_{\varepsilon}$ does
not depend on the setting either. It is implicitly proved in the proof of 5.1
in [16] for a fixed choice of $b$. The idea is to try several, but constantly
many, compaction parameters.

######  Lemma 5.14 ([16], implicit in proof).

For every $\varepsilon>0$, there is a $\operatorname{\mathcal{O}}(1)$-time
parallel algorithm for $\operatorname{\textnormal{{Compact}}}_{\varepsilon}$
that, given an array $\mathcal{A}$ and an upper bound $b$ for the number of
proper tuples in $\mathcal{A}$, requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work and space on a
CRCW-PRAM.

######  Proof 5.15 (Proof sketch).

Let $n$ denote the number of proper tuples in the given array $\mathcal{A}$.

We assume $n\geq 1$ in the following444The algorithm yields $i=0$, if $n=0$
holds, as required. and set $k=\lceil\frac{1}{\varepsilon}\rceil$. The
algorithm invokes the algorithm guaranteed by 5.1 with
$k_{i}=b^{\frac{i\varepsilon}{1+\varepsilon}}$ for every $0\leq i\leq\lceil
k(1+\varepsilon)\rceil$ in ascending order until it is successful (or the
current $k_{i}$ is larger than $\left|\mathcal{A}\right|$ in which case the
procedure can just return $\mathcal{A}$). Each of the (constantly many)
invocations requires $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$
work and space.

If the algorithm is successful for $i=0$, the requirements are trivially met.

Otherwise, let $i$ be such that the compaction for $i+1$ was successful but
the compaction for $i$ was not (note that for $j=\lceil
k(1+\varepsilon)\rceil$ the compaction will always succeed, since $k_{j}$ is
an upper bound for the number of proper tuples in $\mathcal{A}$). Then the
resulting array has size

$k_{i+1}^{1+\varepsilon}=\Big{(}b^{\frac{(i+1)\varepsilon}{1+\varepsilon}}\Big{)}^{1+\varepsilon}=b^{(i+1)\varepsilon}=b^{i\varepsilon}\cdot
b^{\varepsilon}.$

Moreover, since the compaction algorithm was not successful for $i$, we also
have that $k_{i}=b^{\frac{i\varepsilon}{1+\varepsilon}}<n$ and, thus,
$b^{i\varepsilon}<n^{1+\varepsilon}$.

All in all, the array $\mathcal{B}$ has size $b^{(i+1)\varepsilon}\leq
n^{1+\varepsilon}\cdot b^{\varepsilon}$.

For
$\operatorname{\textnormal{{SearchRepresentatives}}}(\mathcal{A},\mathcal{B})$
we present four algorithms, depending on the setting and, in the ordered
setting, whether $\mathcal{A}$ or $\mathcal{B}$ is suitably ordered. This
operation is crucial for deduplication, semi-join and join and the upper
bounds impact the bounds for those operations as well.

######  Lemma 5.16.

For every $\varepsilon>0$, there are $\operatorname{\mathcal{O}}(1)$-time
parallel algorithms for SearchRepresentatives that, given arrays $\mathcal{A}$
and $\mathcal{B}$, have the following bounds on a CRCW-PRAM.

  1. (a)

Work
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)\cdot\left|\mathcal{B}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|))$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)\cdot|D|)$
in the presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot\left|\mathcal{B}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|))$,
if $\mathcal{B}$ is ordered and fully linked;

  4. (d)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{B}\right|\cdot\left|\mathcal{A}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|))$,
if $\mathcal{A}$ is ordered and fully linked and $\mathcal{B}$ is concise.

######  Proof 5.17 (Proof sketch).

For (a), the naive algorithm can be used. In a first phase, it uses one
processor per pair $(i,j)$ of indices for the cells of $\mathcal{B}$ to mark
duplicates in $\mathcal{B}$: if $i<j$ and $\mathcal{B}[i].t=\mathcal{B}[j].t$,
then $\mathcal{B}[j]$ is marked as duplicate. On the second phase, it uses one
processor per pair $(i,j)$ of indices for the cells of $\mathcal{A}$ and
$\mathcal{B}$ and links $\mathcal{A}[i]$ to $\mathcal{B}[j]$ if
$\mathcal{B}[i].t=\mathcal{B}[j].t$ and $\mathcal{B}[j]$ is not marked as
duplicate.

For (b), first an array hash table for (the concatenation of) $\mathcal{A}$
and $\mathcal{B}$ is computed with
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)$
work and
$\operatorname{\mathcal{O}}((\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)\cdot|D|)$
space, thanks to 5.2 and 5.8. For a proper tuple $t$, let $h(t)$ denote the
hash value in the range
$\\{1,$…$,\left|\mathcal{A}\right|+\left|\mathcal{B}\right|\\}$ assigned to
$t$. The algorithm then allocates an auxiliary array of size
$\left|\mathcal{A}\right|+\left|\mathcal{B}\right|$ and, for each proper tuple
$s_{i}$ in $\mathcal{B}$, it writes, in parallel, $i$ into cell $h(s_{i})$ of
the auxiliary array. Here $s_{i}$ denotes the $i$-tuple from $\mathcal{B}$.
Other processors might attempt to write an index to cell $h(s_{i})$ but only
one will succeed. This requires
$\operatorname{\mathcal{O}}(\left|\mathcal{B}\right|)$ work to write the
indices and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|+\left|\mathcal{B}\right|)$
space for the auxiliary array.

For each proper tuple $t$ in $\mathcal{A}$ it is then checked in parallel, if
cell $h(t)$ contains an index $i$. If yes, then $t$ is marked and augmented
with a pointer to cell $\mathcal{B}[i]$, since $\mathcal{B}[i].t=t$. If not,
then $t$ has no partner tuple in $\mathcal{B}$, thus $t$ is not augmented by a
link.

Towards (c), the algorithm identifies, for each proper tuple $t$ in
$\mathcal{A}$, the smallest proper tuple $s$ in $\mathcal{B}$ such that $t\leq
s$. If $t=s$ holds, $t$’s cell is marked and a link to the cell of $s$ is
added. For each tuple, this can be done with work
$\left|\mathcal{B}\right|^{\varepsilon}$, thanks to 5.6 and these searches can
be done in parallel by assigning $\left|\mathcal{B}\right|^{\varepsilon}$
processors per tuple of $\mathcal{A}$.

For (d), the algorithm searches, for each proper tuple $s$ in $\mathcal{B}$,
the smallest tuple $t$ in $\mathcal{A}$ with $t\geq s$. If $t=s$ then the cell
of $t$ is marked and a link to the cell of $s$ is added. If $\mathcal{A}$ is
guaranteed to be concise, that’s all. Otherwise, for each proper tuple $t$ in
$\mathcal{A}$ the smallest inhabited cell $\mathcal{A}[i]$ with
$\mathcal{A}[i].t=t$ is searched. If it is marked then $t$ is marked as well
and a link to the cell in $\mathcal{B}$ to which $\mathcal{A}[i]$ links is
added.

######  Lemma 5.18.

For every $\varepsilon>0$, there are $\operatorname{\mathcal{O}}(1)$-time
parallel algorithms for $\operatorname{\textnormal{{Deduplicate}}}$ that,
given an array $\mathcal{A}$ have the following bounds on an arbitrary CRCW-
PRAM.

  1. (a)

Work $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{2})$ and space
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$, without any
assumptions;

  2. (b)

Work $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ and space
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|\cdot|D|)$ in the presence
of a dictionary;

  3. (c)

Work $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|^{1+\varepsilon})$
and space $\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$, if
$\mathcal{A}$ is ordered.

######  Proof 5.19 (Proof sketch).

In all three cases,
$\operatorname{\textnormal{{SearchRepresentatives}}}(\mathcal{A},\mathcal{A})$
is invoked and afterwards all inhabited cells with tuples that received a link
to a different tuple are made uninhabited, leaving only the other tuples as
representatives. For (c), it might be necessary to compute full links
according to 5.4. The bounds then follow with 5.16.

##  6 Algorithms for Database Operations

In this section, we present $\operatorname{\mathcal{O}}(1)$-time parallel
algorithms for the operators of the relational algebra and analyse their
complexity with respect to work and space.

We formulate the results for relations rather than arrays. We always assume
that a relation $R$ is represented concisely by an array $\mathcal{A}_{R}$,
but we make no assumptions about the compactness of the representation. All
algorithms produce output arrays which represent the result relation
concisely.

With the notable exception of the join operator, for most operators the
algorithms are simple combinations of the algorithms of section 5. The
respective proofs are given in Appendix B. The algorithms for the join
operator are more involved and are presented at the end of the section.

We note that the relational algebra has an additional rename operator, which,
of course, does not require a parallel algorithm.

######  Proposition 6.1.

There is a $\operatorname{\mathcal{O}}(1)$-time parallel algorithm that
receives as input a relation $R$ and an attribute $X$ in $R$, and an element
$a$ in the domain or an attribute $Y$, and computes the selection
$\sigma_{X=a}(R)$ (if $a$ is given) or $\sigma_{X=Y}(R)$ (if $Y$ is given).
The algorithm requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|)$ work and space on
an EREW-PRAM. The output array is of size at most
$\left|\mathcal{A}_{R}\right|$. If $\mathcal{A}_{R}$ is ordered, then the
output is ordered, too.

The algorithm is a simple application of the operation
$\operatorname{\textnormal{{Map}}}$.

######  Proposition 6.2.

For every $\varepsilon>0$, there are $\operatorname{\mathcal{O}}(1)$-time
parallel algorithms for CRCW-PRAMs that compute upon input of two relations
$R$ and $S$ the semijoin $R\ltimes S$ with the following bounds. Here, $X$
denotes the joint attributes of $R$ and $S$.

  1. (a)

Work
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot|D|)$
in the presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|\cdot\left|\mathcal{A}_{S}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
if $\mathcal{A}_{S}$ is $X$-compatibly ordered and fully linked;

  4. (d)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|\cdot\left|\mathcal{A}_{R}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
if $\mathcal{A}_{R}$ is $X$-compatibly ordered and fully linked and
$\mathcal{A}_{S}$ is concise.

The output array is of size $\left|\mathcal{A}_{R}\right|$. If
$\mathcal{A}_{R}$ is ordered, then the output is ordered, too. Moreover, each
$t\in R\ltimes S$ in the output of $R\ltimes S$ gets augmented by a link to a
corresponding tuple in $S$.

######  Proposition 6.3.

For every $\varepsilon>0$, there are CRCW-PRAM
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms that compute upon
input of two relations $R$ and $S$ the difference $R\setminus S$ with the
following bounds.

  1. (a)

Work
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot|D|)$
in the presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|\cdot\left|\mathcal{A}_{S}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
if $\mathcal{A}_{S}$ is ordered and fully linked;

  4. (d)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|\cdot\left|\mathcal{A}_{R}\right|^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
if $\mathcal{A}_{R}$ is ordered and fully linked and $\mathcal{A}_{S}$ is
concise.

The output array is of size $\left|\mathcal{A}_{R}\right|$. If
$\mathcal{A}_{R}$ is ordered, then the output is ordered, too.

The algorithms for 6.2 and 6.3 combine the appropriate algorithm for
$\operatorname{\textnormal{{SearchRepresentatives}}}$ with suitable
applications of $\operatorname{\textnormal{{Map}}}$.

######  Proposition 6.4.

For every $\varepsilon>0$, there are CRCW-PRAM
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms that receive as input
a relation $R$ and a list $X$ of attributes from $R$, and evaluate the
projection $\pi_{X}(R)$ with the following bounds.

  1. (a)

Work $\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|^{2})$ and space
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|)$, without any
assumptions;

  2. (b)

Work $\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|)$ and space
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|\cdot|D|)$ in the
presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|^{1+\varepsilon})$ and
space $\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|)$, if
$\mathcal{A}_{R}$ is $X$-compatibly ordered.

The output array is of size $\left|\mathcal{A}_{R}\right|$. If
$\mathcal{A}_{R}$ is ordered then the output is ordered, too.

The algorithms combine $\operatorname{\textnormal{{Deduplicate}}}$ with
$\operatorname{\textnormal{{Map}}}$ in a straightforward manner. We note that
we do not require in (c) that $\mathcal{A}_{R}$ is fully linked, since the
work bound allows to compute links.

######  Proposition 6.5.

For every $\varepsilon>0$, there are CRCW-PRAM
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms that compute upon
input of two relations $R$ and $S$ the union $R\cup S$ with the following
bounds.

  1. (a)

Work
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\cdot|D|)$
in the presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|\cdot\left|\mathcal{A}_{S}\right|^{\varepsilon}+\left|\mathcal{A}_{S}\right|)$
and space
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|))$,
if $\mathcal{A}_{S}$ is ordered and fully linked.

The output array is of size
$\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|$.

The algorithms basically concatenate $R\setminus S$ and $S$. We note that
thanks to the symmetry of union, the algorithm of (c) can also be applied if
$\mathcal{A}_{R}$ is ordered.

######  Proposition 6.6.

For every $\varepsilon>0$, there are CRCW-PRAM
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms that compute upon
input of two relations $R$ and $S$ the join $R\bowtie S$ with the following
bounds. Here, $X$ denotes the joint attributes of $R$ and $S$.

  1. (a)

Work
$\operatorname{\mathcal{O}}((\left|\mathcal{A}_{S}\right|^{2}+\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon})+(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)\left|\mathcal{A}_{S}\right|+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$
and
space
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon}+\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon}+(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$
and
space
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon}+(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)|D|+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$
in the presence of a dictionary;

  3. (c)

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|^{1+\varepsilon}+\left|\mathcal{A}_{R}\right|\cdot\left|\mathcal{A}_{S}\right|^{\varepsilon}+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$
and
space
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|+\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon})$,
if $\mathcal{A}_{S}$ is $X$-compatibly ordered and fully linked.

The output array is of size $\left|R\bowtie
S\right|\left|\mathcal{A}_{R}\right|^{2\varepsilon}\left|\mathcal{A}_{S}\right|^{2\varepsilon}$.

######  Proof 6.7 (Proof idea).

The algorithms proceed in three phases, the grouping phase, the pairing phase
and the joining phase. For (a) and (b), the tuples of $S$ are grouped with
respect to their $X$-attributes in the grouping phase. Each group is compacted
into an array of some size $\left|\mathcal{A}_{S}\right|^{\ell\varepsilon}$.
Likewise the projection $\pi_{X}(S)$, containing the ?index tuples?, is
compacted. In the pairing phase, a semijoin reduction is performed and the
remaining $R$-tuples are partitioned with respect to the size of their
corresponding “$X$-group” from $S$. Finally, during the joining phase, output
tuples are produced, by combining tuples from $R$ with the tuples from their
“$X$-group” from $S$. The work bounds for the three phases can be seen as the
three main summands in the statement of the proposition.

If $S$ is represented by an array that is $X$-compatibly ordered and fully
linked, the grouping phase can be performed more efficiently. In that case,
$\mathcal{A}_{S}$ itself can be viewed as the concatenation of all
?$X$-groups?. Thus, this steps is for free and, furthermore, the compaction of
the ?$X$-groups? can be done in-place and therefore only requires work
$\left|\mathcal{A}_{S}\right|$ in total. The pairing phase and the joining
phase are basically as for (a) and (b), but the work bounds for the pairing
phase differ, due to the more efficient semijoin algorithm in the ordered
setting.

##  7 Query Evaluation

After studying algorithms for basic operations and operators of the relational
algebra, we are now prepared to investigate the complexity of
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms for query evaluation.

Although every query of the relational algebra can be evaluated by a
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms with polynomial work,
the polynomials can be arbitrarily bad. In fact, that a graph has a $k$-clique
can be expressed by a conjunctive query with $k$ variables and it follows from
Rossman’s $\omega(n^{k/4})$ lower bound for the size of bounded-depth circuit
families for $k$-Clique [26] that any $\operatorname{\mathcal{O}}(1)$-time
parallel algorithm that evaluates this query needs work $\omega(n^{k/4})$.

We therefore concentrate in this section on restricted query evaluation
settings. We study two restrictions of query languages which allow efficient
sequential algorithms, the semijoin algebra and free-connex and/or acylic
conjunctive queries. Furthermore, we present a
$\operatorname{\mathcal{O}}(1)$-time parallel version of worst-case optimal
join algorithms.

In the following, IN always denotes the maximum number of tuples in any
relation of the underlying database that is addressed by the given query.
Furthermore, we always assume that the database relations are represented
concisely by _compact_ arrays without any uninhabited cells.

###  7.1 Semi-Join Algebra

The semijoin algebra is the fragment of the relational algebra that uses only
selection, projection, rename, union, set difference and, not least, semijoin.
It is well-known that semijoin queries produce only query results of size
$\operatorname{\mathcal{O}}(|D|)$ and can be evaluated in time
$\operatorname{\mathcal{O}}(|D|)$ [22, Theorem 7]. From the results of section
6 we can easily conclude the following.

######  Proposition 7.1.

For each query $q$ of the semijoin algebra and for every $\varepsilon>0$ there
are CRCW-PRAM $\operatorname{\mathcal{O}}(1)$-time parallel algorithms that,
given a database $D$, evaluate $q(D)$ with the following bounds.

  1. (a)

Work $\operatorname{\mathcal{O}}(\textsf{IN}^{2+\varepsilon})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN}^{2+\varepsilon})$, without any
assumptions;

  2. (b)

Work $\operatorname{\mathcal{O}}(\textsf{IN})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN}\cdot|D|)$ in the presence of a
dictionary.

######  Proof 7.2 (Proof sketch).

Towards (a), the operators of the query are evaluated with the naive
algorithms from section 6 (stated as (a)). After each evaluation the result
array is compacted by $\operatorname{\textnormal{{Compact}}}_{\varepsilon/2}$.
Statement (b) follows by using the (b)-algorithms from section 6.

Altogether, semijoin queries can be evaluated work-optimally by a
$\operatorname{\mathcal{O}}(1)$-time parallel algorithm. We plan to address
ordered setting in a journal version of this paper. We expect that the results
of [14] enable almost work-optimal $\operatorname{\mathcal{O}}(1)$-time
parallel algorithms with a
$\operatorname{\mathcal{O}}(\textsf{IN}^{1+\varepsilon})$ work bound, if the
relations are represented by suitably ordered arrays. We discuss this further
in our conclusion.

###  7.2 Evaluation of Conjunctive Queries

In this section we give algorithms to evaluate subclasses of conjunctive
queries in parallel. More precisely, we consider acyclic join queries, acyclic
conjunctive queries, free-connex acyclic conjuntive queries and arbitrary
free-connex conjunctive queries.

Conjunctive queries are conjunctions of relation atoms. We write a
_conjunctive query_ (_CQ_ for short) $q$ as a rule of the form
$q:\mathsf{A}\leftarrow\mathsf{A}_{1},\dots,\mathsf{A}_{m}$, where
$\mathsf{A},\mathsf{A}_{1},\dots,\mathsf{A}_{m}$ are atoms and $m\geq 1$. A
conjunctive query $q$ is _acyclic_ , if it has a join tree $T_{q}$, i.e. an
undirected tree $(V(T),E(T))$ where $V(T)$ consists of the atoms in $q$ and
for each variable $v$ in $T_{q}$ the set $\\{\alpha\in V(T)|\alpha\text{
contains }v\\}$ induces a connected subtree of $T_{q}$. It is _free-connex
acyclic_ if $q$ is acyclic and the Boolean query whose body consists of the
body atoms _and_ the head atom of $q$ is acyclic as well [5, 9]. A _join
query_ is a conjunctive query with no quantified variable, i.e. every variable
in a join query is free. For more background on (acyclic) conjunctive queries
we refer to [1, 3].

Our algorithms rely on the well-known Yannakakis algorithm [31]. Yannakakis’
algorithm receives as input an acyclic conjunctive query $q$, the join tree
$T_{q}$ and a database $D$. With each node $v$ in $T_{q}$ a relation $S_{v}$
is associated. Initially, $S_{v}=R_{v}(D)$, where $R_{v}$ is the relation that
is labelled in $v$. The algorithm is divided into three steps.

  * (1)

bottom-up semijoin reduction: All nodes are visited in bottom-up traversal
order of $T$. When a node $v$ is visited, $S_{v}$ is updated to $S_{v}\ltimes
S_{c}$ for every child $c$ of $v$ in $T$.

  * (2)

top-down semijoin reduction: All nodes are visited in top-down traversal order
of $T$. When a node $v$ is visited, the relation $S_{c}$ is updated to
$S_{c}\ltimes S_{v}$ for every child $c$ of $v$ in $T$.

  * (3)

All nodes are visited in bottom-up traversal order in $T$. When a node $v$ is
visited, the algorithm updates, for every child $c$ of $v$, the relation
$S_{v}$ to $\pi_{\mathsf{free}(q)\cup\textnormal{{attr}}(S_{v})}(S_{v}\bowtie
S_{c})$, where $\mathsf{free}(q)$ denotes the attributes that are associated
with the free variables of $q$.

6.2 immediately yields the following lemma.

######  Lemma 7.3.

There are CRCW-PRAM $\operatorname{\mathcal{O}}(1)$-time parallel algorithms
for phase (1) and (2) of the Yannakakis algorithm with the following bounds.

  1. (a)

Work $\operatorname{\mathcal{O}}(\textsf{IN}^{2})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN})$, without any assumptions;

  2. (b)

Work $\operatorname{\mathcal{O}}(\textsf{IN})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN}\cdot|D|)$ in the presence of a
dictionary.

By combining Yannakakis’ algorithm with the algorithms from section 6 we
obtain the following results.

######  Proposition 7.4.

For every $\varepsilon>0$ and every acyclic join query $q$, there are CRCW-
PRAM $\operatorname{\mathcal{O}}(1)$-time parallel algorithms that compute
$q(D)$, given a database $D$, with the following bounds.

  1. (a)

Work
$\operatorname{\mathcal{O}}(\textsf{IN}^{2}+\textsf{OUT}^{2+\varepsilon}\textsf{IN}^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}(\textsf{IN}+\textsf{OUT}^{2+\varepsilon}\textsf{IN}^{\varepsilon})$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\textsf{IN}^{1+\varepsilon}\cdot\textsf{OUT}^{1+\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\textsf{IN}\cdot\textsf{OUT})^{1+\varepsilon}\left|D\right|)$,
in the presence of a dictionary.

To perform phase (3) of the Yannakakis algorithm the parallel algorithms first
shrink every array $\mathcal{A}_{R_{v}}$ to the size
$\left|S_{v}\right|^{1+\varepsilon^{\prime}}\left|R_{v}(D)\right|^{\varepsilon^{\prime}}$
using $\operatorname{\textnormal{{Compact}}}_{\varepsilon^{\prime}}(S_{v})$,
for some very small $\varepsilon^{\prime}$, depending (only) on the size of
the join tree. Likewise, by calling the join algorithm with a suitable
parameter, it strongly compacts each intermediate join result. That the stated
bounds are met can be established by a straightforward, but tedious
calculation, given in Appendix C.

######  Proposition 7.5.

For every $\varepsilon>0$, and every acyclic conjunctive query $q$, there are
CRCW-PRAM $\operatorname{\mathcal{O}}(1)$-time parallel algorithms that
compute $q(D)$, given a database $D$, with the following bounds.

  1. (a)

Work
$\operatorname{\mathcal{O}}(\textsf{IN}^{2}+\textsf{OUT}^{2+\varepsilon}\textsf{IN}^{2+\varepsilon})$
and space
$\operatorname{\mathcal{O}}(\textsf{IN}+\textsf{IN}^{2+\varepsilon}\cdot\textsf{OUT}^{1+\varepsilon})$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\textsf{OUT}^{1+\varepsilon}\textsf{IN}^{2+2\varepsilon})$
and space
$\operatorname{\mathcal{O}}(\textsf{OUT}^{1+\varepsilon}\textsf{IN}^{2+\varepsilon}\left|D\right|)$,
in the presence of a dictionary.

The algorithms are obtained from the algorithms for 7.4 by a suitable
adaptation of phase (3). A proof sketch for 7.5 is given in Appendix C.

It turns out that the bounds for acyclic join queries carry over to free-
connex acyclic conjunctive queries. We use the reduction from free-connex
acyclic queries to join queries given in [8]. We adapt it for
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms.

######  Lemma 7.6.

For every free-connex acyclic query $q$ and every database $D$ there exists an
acyclic join query $\tilde{q}$ and a database $\widetilde{D}$ such that
$q(D)=\widetilde{q}(\widetilde{D})$. Here, $\tilde{q}$ only depends on $q$.

Furthermore, there are CRCW-PRAM $\operatorname{\mathcal{O}}(1)$-time parallel
algorithms that compute upon input of a free-connex acyclic query $q$ and a
database $D$ the corresponding join query $\widetilde{q}$ and database
$\widetilde{D}$ with the following bounds.

  1. (a)

Work $\operatorname{\mathcal{O}}(\textsf{IN}^{2})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN})$, without any assumptions;

  2. (b)

Work $\operatorname{\mathcal{O}}(\textsf{IN})$ and space
$\operatorname{\mathcal{O}}(\textsf{IN}\cdot|D|)$ in the presence of a
dictionary;

A proof sketch is given in Appendix C.

By combining 7.6 and 7.4 we obtain the following result.

######  Corollary 7.7.

There are CRCW-PRAM $\operatorname{\mathcal{O}}(1)$-time parallel algorithms
that receives as input a free-connex acyclic conjunctive query $q$ and a
database $D$ and computes the result $q(D)$, with the following bounds.

  1. (a)

Work
$\operatorname{\mathcal{O}}(\textsf{IN}^{2}+\textsf{OUT}^{2+\varepsilon}\textsf{IN}^{\varepsilon})$
and space
$\operatorname{\mathcal{O}}(\textsf{IN}+\textsf{OUT}^{2+\varepsilon}\textsf{IN}^{\varepsilon})$,
without any assumptions;

  2. (b)

Work
$\operatorname{\mathcal{O}}(\textsf{IN}^{1+\varepsilon}\cdot\textsf{OUT}^{1+\varepsilon})$
and space
$\operatorname{\mathcal{O}}((\textsf{IN}\cdot\textsf{OUT})^{1+\varepsilon}\left|D\right|)$,
in the presence of a dictionary.

In [5, Definition 36] and [8, Definition 3.2], a definition of free-connex,
not necessarily acyclic, conjunctive queries is given. For the sake of
completeness, the definition is also given in Appendix C. 7.7 can be extended
to that class of queries along the lines of [8, Lemma 4.4].

We plan to give a more detailed account in a journal version of this paper.

###  7.3 Weakly Worst-Case Optimal Work for Natural Joins

This section is concerned with the evaluation of _natural join queries_
$q=R_{1}\Join\ldots\Join R_{m}$ over some schema
$\Sigma=\\{R_{1},\ldots,R_{m}\\}$ with attributes
$\textnormal{{attr}}(q)=\bigcup_{i=1}^{m}\textnormal{{attr}}(R_{i})$. It was
shown in [4] that $|q(D)|\leq\prod_{i=1}^{m}|R_{i}|^{x_{i}}$ holds for every
database $D$ and that this bound is tight for infinitely many databases $D$
(this is also known as the AGM bound). Here $x_{1},\ldots,x_{m}$ is a
fractional edge cover of $q$ defined as a solution of the following linear
program.

$\textnormal{minimize }\textnormal{$\sum_{i=1}^{m}x_{i}$}\textnormal{ subject
to}\sum_{i:A\in\textnormal{{attr}}(R_{i})}x_{i}\geq 1\textnormal{ for all
}A\in\textnormal{{attr}}(q)\\\ \textnormal{ and }x_{i}\geq 0\textnormal{ for
all }1\leq i\leq m$

We say that a natural join query $q$ has _weakly worst-case optimal_
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms, if, for every
$\varepsilon>0$, there is a $\operatorname{\mathcal{O}}(1)$-time parallel
algorithm that evaluates $q$ with work
$(\prod_{i=1}^{m}|R_{i}|^{x_{i}}+\textsf{IN})^{1+\varepsilon}$. For
comparison, in the sequential setting, algorithms are considered worst-case
optimal if they have a time bound
$O(\prod_{i=1}^{m}|R_{i}|^{x_{i}}+\textsf{IN})$ [24]. In this subsection, we
show that natural join queries indeed have weakly worst-case optimal
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms.

######  Theorem 7.8.

For every $\varepsilon>0$ and natural join query $q=R_{1}\Join\ldots\Join
R_{m}$ with attributes $X=(A_{1},\ldots,A_{k})$, there is a
$\operatorname{\mathcal{O}}(1)$-time parallel algorithm that, given arrays
$\mathcal{A}_{R_{1}},\ldots,\mathcal{A}_{R_{m}}$ ordered w.r.t. $X$, computes
$q(D)$ and requires
$\operatorname{\mathcal{O}}\big{(}\big{(}(\prod_{i=1}^{m}|R_{i}|^{x_{i}})+\textsf{IN}\big{)}\cdot\textsf{IN}^{\varepsilon}\big{)}$
work and space on a CRCW-PRAM where $(x_{1},\ldots,x_{m})$ is a fractional
edge cover of $q$.

######  Proof 7.9 (Proof idea).

A $\operatorname{\mathcal{O}}(1)$-time parallel algorithm can proceed, from a
high-level perspective, similarly to the sequential attribute elimination join
algorithm, see e.g. [3, Algorithm 10].

In a nutshell, the algorithm computes iteratively, for increasing $j$ from $1$
to $k$ relations $L_{j}$ defined as follows: $L_{1}=\bigcap_{1\leq i\leq
m,A_{1}\in\textnormal{{attr}}(R_{i})}\pi_{A_{1}}(R_{i})$ and, for $j>1$,
$L_{j}$ is the union of all relations $V_{t}=\\{t\\}\times\bigcap_{1\leq i\leq
m,A_{j}\in\textnormal{{attr}}(R_{i})}\pi_{A_{j}}(R_{i}\ltimes\\{t\\})$ for
each $t\in L_{j-1}$. $L_{k}$ is then the query result $q(D)$. Note that each
$L_{j}$ contains tuples over attributes $X_{j}=(A_{1},\ldots,A_{j})$.

To achieve the desired running time in the sequential setting, it is essential
that each relation $V_{t}$ for $t\in L_{j-1}$ is computed in time
$\tilde{}\operatorname{\mathcal{O}}(\min_{1\leq i\leq
m}|R_{i}\ltimes\\{t\\}|)$, where $\tilde{\operatorname{\mathcal{O}}}$ hides a
logarithmic factor; for instance with the Leapfrog algorithm, see e.g. [29],
[3, Proposition 27.10].

In the parallel setting each relation $V_{t}$ is computed with work
$\operatorname{\mathcal{O}}(\min_{1\leq i\leq
m}|R_{i}\ltimes\\{t\\}|\cdot\textsf{IN}^{\frac{1}{2}\varepsilon})$ – for all
tuples $t\in L_{i-1}$ in parallel. Note that the work bound is _not_ uniform,
i.e. the work bound for a tuple $t$ depends on how many ?matching? tuples
there are in each of the input relations. This makes assigning processors
challenging.

Utilizing that the input relations are ordered w.r.t. $X_{j}$, our algorithm
groups the tuples in the relations $\pi_{X_{j}}(R_{i})$ w.r.t. $X_{j-1}$ and
identifies, for each $t\in L_{j-1}$, the corresponding group in
$\pi_{X_{j}}(R_{i})$. These groups are compacted using
$\operatorname{\textnormal{{Compact}}}_{\delta}$ for
$\delta=\frac{\varepsilon}{4}$ which allows to approximate the size of
$R_{i}\ltimes\\{t\\}$ up to a factor of $\textsf{IN}^{\frac{1}{2}\varepsilon}$
for each $i$, and, thus, $\min_{1\leq i\leq m}|R_{i}\ltimes\\{t\\}|$ for each
tuple $t$.

The tuples in $L_{j-1}$ are then partitioned w.r.t. (the approximation of)
$\min_{1\leq i\leq m}|R_{i}\ltimes\\{t\\}|$ into sets $S_{j,\ell}$. Each tuple
in a set $S_{j,\ell}$ can then be assigned the same number of processors,
determined by the size of the array for the smallest group, similarly as in
the Leapfrog algorithm. This is feasible because the number of sets
$S_{j,\ell}$ in the partition is bounded by a constant due to the guarantees
of $\operatorname{\textnormal{{Compact}}}_{\varepsilon}$.

The full proof is given in Appendix D.

We plan to address the evaluation of natural join queries in the dictionary
setting in a journal version of this paper. We expect that almost the same
work bound holds, with an additional summand
$\operatorname{\mathcal{O}}(\max_{1\leq i\leq m}|R_{i}|^{2})$, accounting for
the grouping of each $\pi_{X_{j}}(R_{i})$ with respect to
$\pi_{X_{j-1}}(R_{i})$.

##  8 Conclusion

This paper is meant as a first study on work-efficient
$\operatorname{\mathcal{O}}(1)$-time parallel algorithms for query evaluation
and many questions remain open. The results are very encouraging as they show
that quite work-efficient $\operatorname{\mathcal{O}}(1)$-time parallel
algorithms for query evaluation are possible. In fact, the results give a hint
at what could be a good notion of _work-efficiency_ in the context of
constant-time parallel query evaluation. Our impression is that work-
optimality is very hard to achieve in constant time and that query evaluation
should be considered as work-efficient for a query language, if there are
constant-time parallel algorithms with
$\operatorname{\mathcal{O}}(T^{1+\varepsilon})$ work, for every
$\varepsilon>0$, where $T$ is the best sequential time of an evaluation
algorithm. Of course, it would be nice if this impression could be
substantiated by lower bound results, but that seems to be quite challenging.

We have not given results for all combinations of query languages and
settings, e.g., subsection 7.1 and subsection 7.2 do not yet cover the ordered
setting and subsection 7.3 not the dictionary setting.

As mentioned in section 3, when finding the results of this paper we were
unaware of the fact that [14] provides algorithms for _ordered_ compaction
with constant time and work $\operatorname{\mathcal{O}}(n^{1+\varepsilon})$.
Naturally, these algorithms can be useful for the ordered setting and we
expect them to yield a $\operatorname{\mathcal{O}}(n^{1+\varepsilon})$ work
bound for the semi-join algebra (subsection 7.1). We do not expect them to
improve the bounds for natural joins (subsection 7.3) or for general acyclic
queries (subsection 7.2). We plan to fully explore the consequences in a
journal version of this paper, but we decided against incorporating them into
the final version of this paper, due to the lack of peer-review. In that
journal version we will also address some of the reviewer’s suggestions that
could not be incorporated yet.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.  URL: http://webdam.inria.fr/Alice/.
  * [2] Miklós Ajtai.  $\Sigma_{1}^{1}$ formulae on finite structures.  Ann. of Pure and Applied Logic, 24:1–48, 1983.  doi:10.1016/0168-0072(83)90038-6.
  * [3] Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris.  Database Theory.  Open source at https://github.com/pdm-book/community, 2021.  Preliminary Version, August 19, 2022.
  * [4] Albert Atserias, Martin Grohe, and Dániel Marx.  Size bounds and query plans for relational joins.  SIAM J. Comput., 42(4):1737–1767, 2013.  doi:10.1137/110859440.
  * [5] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208–222. Springer, 2007.  doi:10.1007/978-3-540-74915-8\\_18.
  * [6] David A. Mix Barrington, Neil Immerman, and Howard Straubing.  On uniformity within NC1.  J. Comput. Syst. Sci., 41(3):274–306, 1990.  doi:10.1016/0022-0000(90)90022-D.
  * [7] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  J. ACM, 64(6):40:1–40:58, 2017.  doi:10.1145/3125644.
  * [8] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.  doi:10.1145/3385634.3385636.
  * [9] Johann Brault-Baron.  De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre.  Theses, Université de Caen, April 2013.  URL: https://hal.archives-ouvertes.fr/tel-01081392.
  * [10] Zhiyuan Chen, Johannes Gehrke, and Flip Korn.  Query optimization in compressed database systems.  In Sharad Mehrotra and Timos K. Sellis, editors, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001, pages 271–282. ACM, 2001.  doi:10.1145/375663.375692.
  * [11] E. F. Codd.  Relational completeness of data base sublanguages.  In R. Rustin, editor, Database Systems, pages 33–64. Prentice-Hall, 1972.
  * [12] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with 0(1) worst case access time.  J. ACM, 31(3):538–544, 1984.  doi:10.1145/828.1884.
  * [13] Merrick L. Furst, James B. Saxe, and Michael Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Mathematical Systems Theory, 17(1):13–27, 1984.  doi:10.1007/BF01744431.
  * [14] Tal Goldberg and Uri Zwick.  Optimal deterministic approximate parallel prefix sums and their applications.  In Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings, pages 220–228. IEEE Computer Society, 1995.  doi:10.1109/ISTCS.1995.377028.
  * [15] Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello.  Hypertree decompositions: Questions and answers.  In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 57–74. ACM, 2016.  doi:10.1145/2902251.2902309.
  * [16] Torben Hagerup.  On a compaction theorem of Ragde.  Inf. Process. Lett., 43(6):335–340, 1992.  doi:10.1016/0020-0190(92)90121-B.
  * [17] Xiao Hu and Ke Yi.  Massively parallel join algorithms.  SIGMOD Rec., 49(3):6–17, 2020.  doi:10.1145/3444831.3444833.
  * [18] Neil Immerman.  Expressibility and parallel complexity.  SIAM J. Comput., 18(3):625–638, 1989.  doi:10.1137/0218043.
  * [19] Neil Immerman.  Descriptive Complexity.  Graduate texts in computer science. Springer, 1999.  doi:10.1007/978-1-4612-0539-5.
  * [20] Joseph F. JáJá.  An Introduction to Parallel Algorithms.  Addison-Wesley, 1992.
  * [21] Paraschos Koutris, Semih Salihoglu, and Dan Suciu.  Algorithmic aspects of parallel data processing.  Found. Trends Databases, 8(4):239–370, 2018.  doi:10.1561/1900000055.
  * [22] Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz, and Jan Van den Bussche.  The semijoin algebra and the guarded fragment.  Journal of Logic, Language and Information, 14(3):331–343, 2005\.  doi:10.1007/s10849-005-5789-8.
  * [23] Philip D. MacKenzie.  Load balancing requires omega($\log^{*}$_n_) expected time.  In Greg N. Frederickson, editor, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA, pages 94–99. ACM/SIAM, 1992.  URL: http://dl.acm.org/citation.cfm?id=139404.139425.
  * [24] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms.  J. ACM, 65(3):16:1–16:40, 2018.  doi:10.1145/3180143.
  * [25] Prabhakar Ragde.  The parallel simplicity of compaction and chaining.  In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 744–751. Springer, 1990.  doi:10.1007/BFb0032071.
  * [26] Benjamin Rossman.  On the constant-depth complexity of k-clique.  In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 721–730, 2008.  doi:10.1145/1374376.1374480.
  * [27] Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, and Thomas Zeume.  Work-sensitive dynamic complexity of formal languages.  In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021, volume 12650 of Lecture Notes in Computer Science, pages 490–509. Springer, 2021.  doi:10.1007/978-3-030-71995-1_25.
  * [28] Peter van Emde Boas.  Machine models and simulation.  In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 1–66. Elsevier and MIT Press, 1990.
  * [29] Todd L. Veldhuizen.  Triejoin: A simple, worst-case optimal join algorithm.  In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96–106. OpenProceedings.org, 2014.  doi:10.5441/002/icdt.2014.13.
  * [30] Yilei Wang and Ke Yi.  Query evaluation by circuits.  In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 67–78. ACM, 2022.  doi:10.1145/3517804.3524142.
  * [31] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 82–94. IEEE Computer Society, 1981.

##  Appendix A Revisiting the Compaction Algorithm of Hagerup

In this section we discuss several aspects of Hagerup’s compaction algorithm,
cf. 5.1:

  1. 1.

We discuss how it can be detected that the compaction failed because the input
array $\mathcal{A}$ contained more than $k$ proper tuples (we note that the
compaction may still succeed if $\mathcal{A}$ contains at most
$k^{1+\varepsilon}$ proper tuples, but this is not guaranteed).

  2. 2.

We discuss how proper tuples in the input array can be mutually linked with
their counterparts in the resulting array.

  3. 3.

We will outline Hagerup’s algorithm (and the compaction algorithm from Ragde
[25] Hagerup’s algorithm is based on) to analyse its space requirements.

###  A.1 Detecting Compaction Failure

Let us point out that the compaction algorithm presented in [16] can indeed
detect whether the operation fails because the given $k$ is too small, itself,
although this might not be obvious from the results’ statement in [16]. This
is even used by Hagerup’s algorithm itself.

We will, however, discuss a ?black-box? test instead (that works for any
compaction algorithm), to keep things as simple as possible (and be able to
ignore this when analysing the space requirements of Hagerup’s algorithm).

The black-box test can be performed as follows. First, augment every proper
tuple in the input array $\mathcal{A}$ by its index. That is, if cell $i$ of
$\mathcal{A}$ contains a proper tuple $t$, augment $t$ by $i$. Obviously, this
does not affect the number of proper tuples in $\mathcal{A}$ and, thus, does
not affect whether the compaction algorithm succeeds (or not). Then the
compaction algorithm is called with input $\mathcal{A}$ and $k$. After the
algorithm terminates (or got terminated after it exceeded its constant time
budget), it can be checked whether it was successful (or not) as follows. Let
$\mathcal{B}$ be the resulting array of size $k^{1+\varepsilon}$. For each
proper tuple $t$ in $\mathcal{A}_{B}$, in parallel, mark the cell at index $i$
in the original array $\mathcal{B}$ where $i$ is the index $t$ was augmented
by in the first step. Lastly, test, again in parallel, whether each proper
tuple in $\mathcal{A}$ has been marked. The algorithm was successful if, and
only if, the test is successful. This additional test requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}\right|)$ work, since we can
assume that $k^{1+\varepsilon}\leq\left|\mathcal{A}\right|$ holds (otherwise
the algorithm can just return $\mathcal{A}$ itself).

###  A.2 Establishing Mutual Links between Proper Tuples in Input and Output
Array

######  Remark A.1.

Recall that, as discussed in section 3, Hagerup’s algorithm does not preserve
the order of tuples. It is, however, possible to mutually link proper tuples
in the input array $\mathcal{A}$ with their counterparts in the resulting
array $\mathcal{B}$ of size $k^{1+\varepsilon}$.

This can be achieved similarly to the ?black-box? test for checking whether
the compaction has been successful. Each proper tuple in $\mathcal{A}$ is
augmented by its index in $\mathcal{A}$ prior to the compaction. The
compaction preserves these augmentations and, thus, each proper tuple in
$\mathcal{B}$ is linked to its cell in $\mathcal{A}$ by its augmented index.
To establish links in the other direction, for each proper tuple $t_{j}$ in
$\mathcal{B}$ with augmentation $i$ in parallel, the cell $\mathcal{A}[i]$ can
be augmented by a link to $t_{j}$.

###  A.3 Space Bound for Hagerup’s Algorithm

In the remainder, we revisit (parts of) the proof for 5.1 from [16] to analyse
the space requirements of Hagerup’s compaction algorithm. For that purpose, we
will also revisit the compaction algorithm of Ragde [25], since Hagerup’s
algorithm is based on and invokes it.

We will proceed analogously to [16]: First, we will introduce some (more)
terminology for hash functions and discuss a result from [12] which is used by
Ragde’s as well as Hagerup’s algorithm to compute hash functions in constant
time. Then we will analyse the space requirements of Ragde’s algorithm before
we finally revisit Hagerup’s algorithm.

Note that we will also (partially) use the notation and terminology from [16]
in the following. In particular, we will say that a cell of an array is
_empty_ if it is not inhabited. And if it is inhabited, the cell is non-empty.

#### Computing Hash Functions in Constant Time

A _hash function_ , for our purposes, is a function of the form
$h:\\{1,\ldots,m\\}\to\\{1,\ldots,n\\}$ for natural numbers $m,n$ where,
usually, $m>>n$ holds. It is _perfect_ on a subset
$X\subseteq\\{1,\ldots,m\\}$ if $h$ restricted to $X$ is injective.

######  Definition A.2 ([16], collision number).

Let $h:\\{1,\ldots,m\\}\to\\{1,\ldots,n\\}$ be a hash function and
$X\subseteq\\{1,\ldots,m\\}$ be a subset of its domain. The _collision number_
of $h$ on $X$ is

$|\\{x\in X\mid\text{there is a }y\in X\text{ such that }y\neq x\text{ and
}h(y)=h(x)\\}|.$

In other words, the collision number of $h$ on $X$ is the number of elements
in $X$ whose image under $h$ is not unique (among the elements in $X$). Note
that a hash function $h$ is perfect (on $X$) if and only if the collision
number of $h$ (on $X$) is $0$.

In [16] and [25] the computation of suitable hash functions is based on the
following result.

######  Proposition A.3 ([16, Lemma 1], [12, Lemma 1]).

Let $m,k,s\in\mathbb{N}$ and let $p>m$ be a prime. Then for every subset $X$
of $\\{1,\ldots,m\\}$ with $|X|=k$ and $k\leq s$, there is an integer
$a\in\\{1,$…$,p\\}$ such that the collision number on $X$ of the function
$x\mapsto(ax\mod p)\mod s$ is at most $2\lfloor\frac{k(k-1)}{s}\rfloor$.

A.3 is implied by (the proof of) [12, Lemma 1]. We emphasise, however, that
[12, Lemma 1] makes no statement on the collision number but, instead, on a
(related) magnitude: For a hash function of the form $x\mapsto(ax\mod p)\mod
s$ and $j\in\\{1,$…$,s\\}$, let $B(s,X,a,j)=|\\{x\in X\mid h(x)=j\\}|$, i.e.
the number of elements in $X$ mapped to $j$. [12, Lemma 1] states that there
is an $a$ such that

$\sum_{j=1}^{s}\binom{B(s,X,a,j)}{2}<\frac{k^{2}}{s}$

holds. We briefly discuss, how A.3 is implied. First, we observe that at the
end of the proof of [12, Lemma 1] (last sentence) the inequality
$\binom{k}{2}<\frac{k^{2}}{2}$ is used. Replacing this inequality with
$\binom{k}{2}\leq\frac{k(k-1)}{2}$ and observing that the sum on the left hand
side is an integer yields that

$\sum_{j=1}^{s}\binom{B(s,X,a,j)}{2}\leq\Big{\lfloor}\frac{k(k-1)}{s}\Big{\rfloor}$

holds. Let $h$ denote the hash function $x\mapsto(ax\mod p)\mod s$. We can
then bound the collision number for $h$ on $X$ as follows.

$\displaystyle|\\{x\in X\mid\text{there is a }y\in X\text{ such that }y\neq
x\text{ and }h(y)=h(x)\\}|$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle|\\{(x,y)\in X^{2}\mid y\neq x\text{ and }h(y)=h(x)\\}|$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2\cdot|\\{\\{x,y\\}\subseteq X\mid y\neq x\text{ and }h(y)=h(x)\\}|$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
2\cdot\sum_{j=1}^{s}|\\{\\{x,y\\}\subseteq X\mid y\neq x\text{ and
}h(y)=h(x)=j\\}|$ $\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
2\cdot\sum_{j=1}^{s}\binom{B(h,X,j)}{2}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2\cdot\Big{\lfloor}\frac{k(k-1)}{s}\Big{\rfloor}$

Further on, we observe that A.3 guarantees, for $s=k^{2}$, the existence of an
$a\in\\{1,$…$,p\\}$ such that $h:X\to\\{1,\ldots,k^{2}\\},x\mapsto(ax\mod
p)\mod k^{2}$ is a perfect hash function, for any prime $p>m$, since the
collision number is bounded by $0$ for these functions. This gives rise to the
following result.

######  Lemma A.4.

There is an algorithm that, upon input of $m,k\in\mathbb{N}$, and
$X\subseteq\\{1,\ldots,m\\}$ with $|X|=k$, computes a prime number $p>m$ and
an $a\in\\{1,$…$,p\\}$ such that

$h:X\to\\{1,\ldots,k^{2}\\},x\mapsto(ax\mod p)\mod k^{2}$

is a perfect hash function (on $X$) in constant time. The algorithm requires
$\operatorname{\mathcal{O}}(m^{2})$ work and
$\operatorname{\mathcal{O}}(m^{2})$ space if the elements of $X$ are initially
distributed evenly among $k$ processors.

######  Proof A.5 (Proof sketch).

Since there is a prime number between $m$ and $2m$ if $m>1$, the prime $p$ can
be computed with $\operatorname{\mathcal{O}}(m^{2})$ processors: for each
candidate $p$ allocate $2m$ processors and check in parallel whether $p$ is
divisible by a smaller number. The case $m=1$ is trivial. Since each processor
requires only a constant amount of space, this first step can be done in
$\operatorname{\mathcal{O}}(m^{2})$ space in total.

The number $a\in\\{1,$…$,p\\}$ is determined by brute-force (in parallel). For
each $a\in\\{1,$…$,p\\}$, let $h_{a}$ denote the hash function
$x\mapsto(ax\mod p)\mod s$ associated with $a$. Whether, for a single number
$a$, the function $h_{a}$ is perfect, can be determined as follows: Allocate
an array of size $k^{2}$, and, for each $x\in X$ in parallel, compute
$h_{a}(x)=(ax\mod p)\mod s$ and write $x$ to the $h_{a}(x)$-th cell of the
array. Each process then reads the content of the cell it had written to again
and verifies that it contains the value the process had written.

Performing this check in parallel for all $a\in\\{1,$…$,p\\}$ requires
$\big{(}m^{2})$ processors and $\operatorname{\mathcal{O}}(m^{2})$ space,
because we can assume that $k^{2}\leq m$ holds (otherwise an array of size
$p\leq 2m$ suffices).

###  A.4 Ragde’s Compaction Algorithm

######  Definition A.6 ([16], p. 335).

For $n,s,k\in\mathbb{N}$, the $(n,k,s)$-compaction problem is defined as
follows: Given $k$ and an array $\mathcal{A}$ of size at most $n$ with at most
$k$ non-empty cells, copy the values in the non-empty cells to distinct cells
in an array of size at most $s$.

As in [16] we will, for convenience and readability, often omit rounding
operators and allow $n$ and $s$ in a triplet $(n,k,s)$ to be (positive) real
numbers.

Note that Hagerup’s result (stated as 5.1) is that $(n,k,s)$-compaction
problems can be solved with $\operatorname{\mathcal{O}}(n)$ work and space in
constant time for every $\varepsilon>0$.

We note that A.4 already gives rise to a simple compaction algorithm solving
$(n,k,k^{2})$-compaction problems with $\operatorname{\mathcal{O}}(n^{2})$
work and space: let $X\subseteq\\{1,\ldots,n\\}$ be the indices of the input
array referring to non-empty cells. Then A.4 allows the computation of a
perfect hash function that can be utilised to copy the contents of all non-
empty cells of the input array to distinct non-empty cells of an array of size
$k^{2}$.

In the following we revisit the compaction algorithm of Ragde, which solves
$(n,k,k^{4})$-compaction problems with $\operatorname{\mathcal{O}}(n)$ work
and space – thus, effectively trading a larger size of the target array for
better upper bounds for the required work and space.

A common approach in the considered compaction algorithms (of both, Ragde and
Hagerup) is to divide an array $\mathcal{A}$ of size $r\sqrt{n}$ into
$\operatorname{\mathcal{O}}(\sqrt{n})$ subarrays and interpret each subarray
as a ?cell? of an array $\mathcal{A}_{\sqrt{n}}$ of size
$\operatorname{\mathcal{O}}(\sqrt{n})$. For convenience and readability, we
introduce the following terminology: For $r\geq 1$, a _$r$ -block array of
size $n$_ is an array $\mathcal{A}_{rn}$ of size $rn$ interpreted as an array
$\mathcal{A}_{n}$ of size $n$ where an index $i\in\\{1,$…$,n\\}$ refers to the
subarray consisting of the (underlying) cells $\mathcal{A}_{rn}[r(i-1)]$ to
$\mathcal{A}_{rn}[ri-1]$. A cell of an $r$-block array is considered empty if
and only if all cells of the corresponding subarray are empty. Moreover, if
the ?normal? array $\mathcal{A}_{rn}$ contains at most $k$ non-empty cells,
then so does the $r$-block array $\mathcal{A}_{n}$. Which cells of a $r$-block
array are empty can easily be determined with $\operatorname{\mathcal{O}}(n)$
work in parallel and cached in an array of size $n$, i.e. cell $i$ of the
cache array contains $1$ if and only if cell $i$ of the $r$-block array is
empty. Beware that copying the contents of a single cell of a $r$-block array
requires work $\operatorname{\mathcal{O}}(r)$ in contrast to
$\operatorname{\mathcal{O}}(1)$ for a ?normal? array.

The following lemma is proven as part of the proof of [25, Theorem 1] and
stated as [16, Lemma 2].

######  Lemma A.7 ([25, 16]).

For every $k\in N$, $n,r\geq 1$ with
$r\in\operatorname{\mathcal{O}}(\sqrt{n})$, $(r\sqrt{n},k,k^{2}r)$-compaction
problems can be solved in constant time with $\operatorname{\mathcal{O}}(n)$
processors and $\operatorname{\mathcal{O}}(n)$ space.

######  Proof A.8 (Proof sketch).

The input array of size $r\sqrt{n}$ is interpreted as a $r$-block array
$\mathcal{A}_{\sqrt{n}}$ of size $\operatorname{\mathcal{O}}(\sqrt{n})$ with
subarrays of size at most $r$. Recall that $\mathcal{A}_{\sqrt{n}}$ contains
at most $k$ non-empty cells.

Then, using A.4 with $m=\sqrt{n}$, a perfect hash function $h$ for the set of
all indices $i\in\\{1,$…$,\sqrt{n}\\}$ where the cell
$\mathcal{A}_{\sqrt{n}}[i]$ is non-empty is computed. Finally, a $r$-block
array $\mathcal{A}_{k^{2}}$ of size $k^{2}$ is allocated, and, for every
$i\in\\{1,$…$,\sqrt{n}\\}$ the contents of $\mathcal{A}_{\sqrt{n}}$ (i.e. the
subarray) is copied to $\mathcal{A}_{k^{2}}[h(i)]$ if it is non-empty.

The array $\mathcal{A}_{k^{2}}$ then has the desired size and contains all
values in non-empty cells of the input array in distinct cells. Computing the
hash function requires
$\operatorname{\mathcal{O}}(\sqrt{n}^{2})=\operatorname{\mathcal{O}}(n)$ space
and work. Copying the $\operatorname{\mathcal{O}}(\sqrt{n})$ many subarrays of
size $r$ each also requires $\operatorname{\mathcal{O}}(r\sqrt{n})$ work and
the resulting array has size $k^{2}r$ which is in
$\operatorname{\mathcal{O}}(n)$ under the assumption that $k^{2}\leq n$
(otherwise, the input array can just be returned).

Ragde’s algorithm then results from two applications of A.7 with different
values for $r$. This reduces the work and space requirements to
$\operatorname{\mathcal{O}}(n)$ work and $\operatorname{\mathcal{O}}(n)$ space
while increasing the size of the target array from $k^{2}$ to $k^{4}$.

######  Proposition A.9 ([25, Theorem 1]).

For every $k\in N$, and $n\geq 1$, $(n,k,k^{4})$-compaction problems can be
solved in constant time with $\operatorname{\mathcal{O}}(n)$ processors and
$\operatorname{\mathcal{O}}(n)$ space.

######  Proof A.10 (Proof sketch).

First, note that we can assume that $k<n^{\frac{1}{4}}$ holds, because,
otherwise, the input array already has the desired size. The desired array can
be computed by applying A.7 twice with different values for $r$.

Using A.7 with $r=\sqrt{n}$ to solve the
$(\sqrt{n}\cdot\sqrt{n},k,k^{2}\sqrt{n})$-compaction problem, yields an array
of size $k^{2}\sqrt{n}$. Another application of A.7, this time with $r=k^{2}$,
to solve the $(k^{2}\sqrt{n},k,k^{4})$-compaction problem, then yields the
desired result of size $k^{4}$. Note that $k^{2}<n^{\frac{2}{4}}=\sqrt{n}$
holds by assumption and, thus, $r=k^{2}$ satisfies the conditions of A.7.

The upper bounds for the required work and space are inherited from A.7.

###  A.5 Hagerup’s Compaction Algorithm

Hagerup’s algorithm is build upon Ragde’s algorithm and can solve
$(n,k,k^{1+\varepsilon})$-compaction problems for every fixed
$\varepsilon\in\mathbb{R}_{>0}$. In a nutshell, it is shown in [16] that, if
$(n,k,k^{1+\varepsilon})$-compaction problems are solvable for some
$\varepsilon>0$ in constant time, then $(n,k,k^{1+\mu})$-compaction problems
are solvable in constant time for _any_ $0<\mu\leq\varepsilon$, too. Since
$(n,k,k^{1+\varepsilon})$-compaction problems are solvable in constant time
for $\varepsilon=3$ due to A.9, this implies that $(n,k,k^{1+\mu})$-compaction
problems are solvable in constant time for every fixed
$\mu\in\mathbb{R}_{>0}$.

The proof involves two major ingredients used to improve Ragde’s algorithm
under the assumption that $(n,k,k^{1+\varepsilon})$-compaction problems are
solvable for some $\varepsilon>0$:

  1. 1.

The indices (of the subarrays) are hashed with a non-perfect hash functions.
If the number of collisions is small enough, the colliding indices can be be
compacted with the algorithm given by the assumption.

  2. 2.

The subarrays are compacted recursively. The recursion depth will only depend
on the desired $\mu$, and is, thus, constant.

Ingredient 1 is formalised in the following lemma which is an analogue to A.7.

######  Lemma A.11 ([16, Lemma 3]).

Let $\varepsilon\in\mathbb{R}_{>0}$ and
$\mu=\frac{\varepsilon}{2+\varepsilon}$. The following holds: If
$(n,k,k^{1+\varepsilon})$-compaction problems can be solved in constant time
with $\operatorname{\mathcal{O}}(n)$ work and $\operatorname{\mathcal{O}}(n)$
space for all $k\in\mathbb{N}$ and $n\geq 1$, then
$(r\sqrt{n},k,k^{1+\mu}r)$-compaction problems can be solved in constant time
with $\operatorname{\mathcal{O}}(n)$ work and $\operatorname{\mathcal{O}}(n)$
space for all $k\in\mathbb{N}$, $n\geq 1$, and $r\geq 3$ with
$r\in\operatorname{\mathcal{O}}(\sqrt{n})$.

In difference to the proof of A.7, the proof of A.11 relies on hash functions
which are not perfect, i.e. their collision number is greater than $0$. As a
consequence, we cannot use (an analogue of) A.4 to compute a hash function
because, essentially, we cannot count the number of collisions for non-perfect
hash functions to select a suitable hash function with ?few? collisions.
Instead, the algorithm operates – similar to the algorithm presented in the
proof of A.4 – on all candidates for hash functions in parallel and tries to
compact colliding indices for each of them. If the compaction of the colliding
indices is successful for a hash function $h$, the number of collisions for
$h$ is small enough, and $h$ can be chosen.

######  Proof A.12 (Proof sketch for A.11).

Assume that $(n^{\prime},k,k^{1+\varepsilon})$-compaction problems can be
solved with $\operatorname{\mathcal{O}}(n^{\prime})$ work and space. We show
that then $(r\sqrt{n},k,k^{1+\mu}r)$-compaction problems where
$\mu=\frac{\varepsilon}{2+\varepsilon}$ and
$r\in\operatorname{\mathcal{O}}(\sqrt{n})$ can be solved with
$\operatorname{\mathcal{O}}(n)$ work and space.

The input array of size $r\sqrt{n}$ is interpreted as $\frac{r}{3}$-block
array $\mathcal{A}_{\sqrt{n}}$ of size $\operatorname{\mathcal{O}}(\sqrt{n})$
with subarrays of size at most $\frac{r}{3}$. Recall that there are at most
$k$ non-empty subarrays.

Next, a prime number $p$ between $\sqrt{n}$ and $2\sqrt{n}$ suitable for A.3
with $m=\sqrt{n}$ is computed using $\operatorname{\mathcal{O}}(n)$ work and
$\operatorname{\mathcal{O}}(n)$ space.

For every $a\in\\{1,$…$,p\\}$, let $h_{a}$ denote the hash function
$x\mapsto(ax\mod p)\mod s$ where $s=\lfloor 2k^{1+\mu}\rfloor$. The algorithm
tries to compact into an array of size $3k^{1+\mu}$ for all hash function
$h_{a},a\in\\{1,$…$,p\\}$ in parallel. We describe the procedure for a single,
fixed $a\in\\{1,$…$,p\\}$, in the following.

An array $\mathcal{A}_{a}$ of size $s=\lfloor 2k^{1+\mu}\rfloor$ is allocated,
and, for each index $i\in\\{1,$…$,\sqrt{n}\\}$ in parallel, a processor is
allocated which writes $i$ into the $h_{a}(i)$-cell of $\mathcal{A}_{a}$ if
$\mathcal{A}_{\sqrt{n}}[i]$ is non-empty (otherwise, it does nothing). Then
for each $i\in\\{1,$…$,\sqrt{n}\\}$ in parallel, the processor for $i$ checks
whether $\mathcal{A}_{\sqrt{n}}[h_{a}(i)]$ contains the value $i$. If not and
$\mathcal{A}_{\sqrt{n}}[i]$ is non-empty, $h(i)=h(j)$ holds for some
$j\in\\{1,$…$,p\\},j\neq i$, i.e. there is a collision. In that case,
$\mathcal{A}_{\sqrt{n}}[i]$ is marked as colliding. To avoid conflicts, the
marks can be stored in arrays $\mathcal{A}_{a,\texttt{coll}}$ of size
$\operatorname{\mathcal{O}}(\sqrt{n})$ for each $a\in\\{1,$…$,p\\}$.

It is then attempted to solve the $(\sqrt{n},k^{1-\mu},k^{1+\mu})$-compaction
problem for $\mathcal{A}_{\sqrt{n}}$ where only the cells marked as colliding
are interpreted as non-empty and the content of each non-empty cell is
considered to be its index.555Since each cell actually represents a subarray,
copying these subarrays into a new array, for all $a$ in parallel, would
require more work than desired. Thus, the indices are used as ?fake? values;
note that, whether the compaction algorithm is successful or not, does not
depend on the values, only on the number of non-empty cells. If the compaction
succeeds, $h_{a}$ considered suitable to compact $\mathcal{A}_{\sqrt{n}}$.

Note that due to A.3 there is at least one $a\in\\{1,$…$,p\\}$ such that there
are at most $\frac{2k(k-1)}{s}=\frac{2k(k-1)}{2k^{1+\mu}}\leq
k^{2-(1+\mu)}=k^{1-\mu}$ collisions for $h_{a}$ and that
$\big{(}k^{1-\mu}\big{)}^{1+\varepsilon}=k^{(1-\mu)(1+\varepsilon)}=k^{1+\mu}$.
That is, the $(\sqrt{n},k^{1-\mu},k^{1+\mu})$-compaction problems can be
solved due to the assumption that $(n,k,k^{1+\varepsilon})$-compaction
problems can be solved and the compaction is successful for at least one $a$.

Finally, a suitable function $h_{a}$ is picked and used to copy the values in
the non-colliding, non-empty cells of $\mathcal{A}_{\sqrt{n}}$ to distinct
cells of a $\frac{r}{3}$-block array of size $2k^{1+\mu}$ and the colliding,
non-empty cells of $\mathcal{A}_{\sqrt{n}}$ are compacted into a
$\frac{r}{3}$-block array of size $k^{1+\mu}$ using the algorithm guaranteed
by the assumption. All in all, all values in non-empty cells of
$\mathcal{A}_{\sqrt{n}}$ have been copied into distinct cells of a
$\frac{r}{3}$-block array of size $3k^{1+\mu}$. Since each cell actually
represents a subarray of size at most $\frac{r}{3}$, the ?real? size of the
final array is $k^{1+\mu}r$, as desired.

The prime number $p$ can be computed with $\operatorname{\mathcal{O}}(n)$ work
and space (cf. the proof of A.4). For each $a\in\\{1,$…$,p\\}$, the collision
check for $h_{a}$ requires work $\operatorname{\mathcal{O}}(\sqrt{n})$ and
space $\operatorname{\mathcal{O}}(\sqrt{n})$, because it allocates two arrays
of size $\operatorname{\mathcal{O}}(\sqrt{n})$ (if $k^{1+\mu}$ is larger than
$\sqrt{n}$ there is nothing to do) and, for each index
$i\in\\{1,$…$,\sqrt{n}\\}$, a processor is allocated and performs constantly
many operations. The $(\sqrt{n},k^{1-\mu},k^{1+\mu})$-compaction problem can
be solved with $\operatorname{\mathcal{O}}(\sqrt{n})$ work and space by
assumption (since the input array uses ?fake? values and is a normal array of
size $\sqrt{n}$). Since $p\in\operatorname{\mathcal{O}}(\sqrt{n})$, checking
all functions $h_{a}$ in parallel, thus, requires
$\operatorname{\mathcal{O}}(n)$ work and space. Lastly, copying
$\operatorname{\mathcal{O}}(\sqrt{n})$ subarrays of size at most $\frac{r}{3}$
requires $\operatorname{\mathcal{O}}(n)$ work and space, since
$r\in\operatorname{\mathcal{O}}(\sqrt{n})$, and solving the
$(\sqrt{n},k^{1-\mu},k^{1+\mu})$-compaction problem with input
$\mathcal{A}_{\sqrt{n}}$ requires
$\operatorname{\mathcal{O}}(\frac{r}{3}\sqrt{n})=\operatorname{\mathcal{O}}(n)$
work and space, since copying cell contents of $\mathcal{A}_{\sqrt{n}}$
requires $\operatorname{\mathcal{O}}(\frac{r}{3})$ work.

Therefore, the procedure requires $\operatorname{\mathcal{O}}(n)$ work and
space in total.

Towards the second ingredient, Hagerup defines a function
$g:\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ which has, among others, the property
that $g(\varepsilon)<\varepsilon$ for all $\varepsilon\in\mathbb{R}_{>0}$
holds, cf. [16, p. 337]. Therefore, the sequence
$g(3),g(g(3)),g(g(g(3))),\ldots$ is strictly decreasing and the limit is $0$.
Moreover, it is shown by induction that, for all
$\varepsilon\in(0,\frac{13}{4})$ and $\beta\in\mathbb{R}$ the following holds:
If $(n,k,k^{1+\varepsilon})$-compaction problems are solvable with
$\operatorname{\mathcal{O}}(n)$ work, then
$(n,k,k^{1+g^{(i)}(\varepsilon)+\beta})$-compaction problems are solvable with
$\operatorname{\mathcal{O}}(n)$ work (here $g^{(i)}$ is the $i$-fold
application of $g$). This implies 5.1 since for $\varepsilon=3$ the premise is
satisfied due to A.9.

We refer to [16] for the (very) technical details and, instead, just analyse
the space complexity of the algorithm for the recursion/induction step
formalized in the following result.

######  Lemma A.13 ([16, Lemma 7]).

Let $\varepsilon\in(0,\frac{13}{4})$ and $\beta\in\mathbb{R}_{>0}$. The
following holds: If $(n,k,k^{1+\varepsilon})$-compaction problems can be
solved in constant time with $\operatorname{\mathcal{O}}(n)$ work and
$\operatorname{\mathcal{O}}(n)$ space for all $k\in\mathbb{N}$ and $n\geq 1$,
then $(n,k,c_{\varepsilon,\beta}k^{1+g(\varepsilon)+\beta})$-compaction
problems can be solved in constant time with $\operatorname{\mathcal{O}}(n)$
work and $\operatorname{\mathcal{O}}(n)$ space for all $k\in\mathbb{N}$ and
$n\geq 1$ where $c_{\varepsilon,\beta}$ is a constant (depending on
$\varepsilon$ and $\beta$).

######  Proof A.14 (Proof sketch).

We assume that $(n,k,k^{1+\varepsilon})$-compaction problems can be solved in
constant time with $\operatorname{\mathcal{O}}(n)$ work and
$\operatorname{\mathcal{O}}(n)$ space for all $k\in\mathbb{N}$ and $n\geq 1$.
For convenience, we define $\gamma=g(\varepsilon)+\beta$ and
$\alpha=\frac{1}{1+\varepsilon}$. In the following we describe an algorithm to
solve $(n,k,c_{\gamma}k^{1+\gamma})$-compaction problems for some constant
$c_{\gamma}$ depending only on $\gamma$ (and, thus, $\varepsilon$ and
$\beta$).

We can assume that $\varepsilon$, $\beta$, $\gamma$, and $\alpha$ are rational
due to continuity. Hence, a PRAM can perform computations with these
quantities. The input array of size $n$ with at most $k$ non-empty cells is
divided into at most $3\sqrt{n}$ subarrays of size at most $\sqrt{n}$. The
algorithm operates in two steps. In the first step, each (non-empty) subarray
is ?compacted as good as possible? using (a constant number of) applications
of the assumption and the subarrays are grouped by how ?good? they could be
compacted. In the second step, each group is further compacted using
(multiple) applications of A.11.

For the first step, the algorithm uses a constant $\delta\in(0,1)$ which has
the following properties: (1) it depends only on $\varepsilon$ and $\beta$,
(2) $\frac{1}{4}$ is a multiple of $4$, and (3) is sufficiently
small.666$\delta$ will occur in the exponent of the size of an intermediate
result and has to be small enough such that A.11 can be applied with the
desired $r$. It is shown in [16] that such a $\delta$ can always be chosen by
the algorithm. For each subarray in parallel, the algorithm then tries to
compact the subarray into arrays of size $n^{i\delta}$ for
$i\in\\{1,\ldots,i_{\texttt{max}}\\}$ where
$i_{\texttt{max}}=\frac{1}{2\delta}-1$ (note that $2\delta-1\geq 1$ since
$\frac{1}{\delta}$ is a multiple of $4$). We note that $n^{i\delta}<\sqrt{n}$
for all $i$. This can be done by attempting to solve
$(\sqrt{n},n^{i\delta\alpha},n^{i\delta})$-compaction problems which is
possible due to the assumption (note that
$\big{(}n^{i\delta\alpha}\big{)}^{1+\varepsilon}=n^{i\delta}$ since
$\alpha=\frac{1}{1+\varepsilon}$ and that each subarray has size at most
$\sqrt{n}$). Since $i_{\texttt{max}}$ does not depend on $n$ or $k$, this can
be with $\operatorname{\mathcal{O}}(\sqrt{n})$ work and space for a single
subarray, and, hence, with $\operatorname{\mathcal{O}}(n)$ work and space in
total.

The subarrays are then grouped as follows: A subarray is assigned to group $i$
if the compaction into an array of size $n^{(i+1)\delta}$ succeeded but the
compaction into an array of size $n^{i\delta}$ did not. It is assigned to
group $0$ if the compaction into an array of size $n^{\delta}$, i.e. for $i=1$
was successful and to group $i_{\texttt{max}}$ if none of the compaction
attempts was successful. Note that every subarray in group $i$ contains at
least $n^{i\delta\alpha}$ non-empty cells.

In the second step, the algorithm compacts, for each group, every value in any
subarray of the group into an array of size $3k^{1+\gamma}$. Overall, this
yields the desired array of size $c_{\gamma}k^{1+\gamma}$ where
$c_{\gamma}=3(i_{\texttt{max}}+1)$ is three times the number of groups. We
describe the procedure for a single, fixed group
$i\in\\{0,\ldots,i_{\texttt{max}}\\}$.

First, all (compacted) subarrays of group $i$ are copied into an
$n^{(i+1)\delta}$-block array $\mathcal{A}_{i}$ of size $3\sqrt{n}$. Note
that, since the original array had $k$ non-empty cells, and each subarray in
group $i$ contains at least $n^{i\delta\alpha}$ non-empty cells,
$\mathcal{A}_{i}$ has at most
$\frac{k}{n^{i\delta\alpha}}=kn^{-i\delta\alpha}$ non-empty cells. Using A.11
with $r=3$ (and interpreting $\mathcal{A}_{i}$ as ?normal? array of size
$3\sqrt{n}$), $\mathcal{A}_{i}$ can be compacted into an
$n^{(i+1)\delta}$-block array of size $3(kn^{-i\delta\alpha})^{1+\mu}$ for
$\mu=\frac{\varepsilon}{2+\varepsilon}$. That is, every value occurring in
(distinct cells of) any of the subarrays of group $i$ has been copied to
distinct cells of an array of size $3k^{1+\mu}n^{\delta(i+1-i\alpha(1+\mu))}$.
It is shown in [16] that this either has size (smaller or equal to)
$3k^{1+\gamma}$ or that it can be compacted into an array of the desired size
by up to two more applications of A.11 with $r=3$ and/or $r\leq\sqrt{n}$.

Since there are only constantly many groups, the second step can thus be done
with $\operatorname{\mathcal{O}}(n)$ work and space due to A.11. For the
correctness, we refer to the proof of [16, Lemma 7].

##  Appendix B Missing Proofs for section 6

######  Proof B.1 (Proof sketch for 6.1).

If an element $a$ is given, let $f$ be the function where $f(t)=t$, if
$t[X]=a$, and $f(t)=\bot$ otherwise. If an attribute $Y$ is given, let $f$ be
the function where $f(t)=t$, if $t[X]=t[Y]$, and $f(t)=\bot$ otherwise.

The algorithm uses the operation $\operatorname{\textnormal{{Map}}}$ with
input $\mathcal{A}_{R}$ and $f$ and returns its result. The evaluation of the
operation $\operatorname{\textnormal{{Map}}}$ takes
$\operatorname{\mathcal{O}}(|\mathcal{A}_{R}|)$ work and space (5.10).

Obviously, $f$ is order-preserving and therefore, thanks to 5.10, the output
$\operatorname{\textnormal{{Map}}}(\mathcal{A}_{R},f)$ is ordered, if
$\mathcal{A}_{R}$ is ordered.

######  Proof B.2 (Proof sketch for 6.2).

Let $f_{X}$ be a function that maps every tuple t to $t[X]$. In the beginning,
the algorithm uses $\operatorname{\textnormal{{Map}}}(R,f)$ and
$\operatorname{\textnormal{{Map}}}(S,f)$ to compute $R^{\prime}=\pi_{X}(R)$
and $S^{\prime}=\pi_{X}(S)$. It follows from 5.10 that
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)$
work and space to compute $\mathcal{A}_{R^{\prime}}$ and
$\mathcal{A}_{S^{\prime}}$. Note, that in particular, every tuple in
$\mathcal{A}_{R}$ (and $\mathcal{A}_{S}$) is augmented by a link to the
corresponding tuple in $\mathcal{A}_{R^{\prime}}$ (in
$\mathcal{A}_{S^{\prime}}$). If $\mathcal{A}_{S}$ is $X$-compatibly ordered
then this also holds for $\mathcal{A}_{S^{\prime}}$. The algorithm then uses
$\operatorname{\textnormal{{SearchRepresentatives}}}(\mathcal{A}_{R^{\prime}},\mathcal{A}_{S^{\prime}})$
to augment every tuple in $\mathcal{A}_{R^{\prime}}$ by a link, if there is a
corresponding tuple in $\mathcal{A}_{S^{\prime}}$. Let $g$ be a function that
maps a tuple $t$ in $R$, if $t\in R\ltimes S$ and to $\bot$, otherwise. To
compute $g(t)$ from $t$, the algorithm follows the link in $t$ to a tuple
$t^{\prime}\in R^{\prime}$ and if it has a link to a tuple in $S^{\prime}$,
the value is $t$. If $t^{\prime}$ has no link to a tuple in $S^{\prime}$, the
value is $\bot$. Hence, the algorithm returns
$\operatorname{\textnormal{{Map}}}(R,g)$ to obtain an array that represents
$R\ltimes S$. We note, that in every case, the work and space for the
$\operatorname{\textnormal{{SearchRepresentatives}}}$ operation dominate the
overall work and space and the bounds therefore follow from 5.16.

######  Proof B.3 (Proof sketch for 6.3).

The algorithm uses $\operatorname{\textnormal{{SearchRepresentatives}}}(R,S)$
to augment every tuple that also appears in $S$. The tuples that did not get
augmented by this operation belongs to the difference $R\setminus S$. Thus,
let $f$ be a function that maps $t$ to itself, if is not augmented by
$\operatorname{\textnormal{{SearchRepresentatives}}}$, and maps $t$ to $\bot$
otherwise, and the algorithm returns $\operatorname{\textnormal{{Map}}}(R,f)$
to obtain the result.

As for the semi-join, the work and space for the
$\operatorname{\textnormal{{SearchRepresentatives}}}$ operation dominate the
overall work and space and the bounds.

In both cases, the applied functions are order-preserving. Thanks to 5.10, it
therefore follows that if $\mathcal{A}_{R}$ is ordered, then the output is
ordered, too.

######  Proof B.4 (Proof sketch for 6.4).

Let $f_{X}$ be a function that maps every tuple $t$ to $t[X$. The algorithm
uses $\operatorname{\textnormal{{Map}}}(R,f)$ to compute
$R^{\prime}=\pi_{X}(R)$. It follows from 5.10 that
$\operatorname{\mathcal{O}}(\mathcal{A}_{R})$ work and space suffice to
compute $R^{\prime}$. The algorithm uses
$\operatorname{\textnormal{{Deduplicate}}}(R^{\prime})$ to remove multiple
appearances of a tuple in $\mathcal{A}_{R^{\prime}}$ and returns its output.
The work and space bounds are dominated by the latter part, therefore the
bounds follow from 5.18. In the ordered case it is crucial that the order of
$\mathcal{A}_{R}$ is $X$-compatible.

######  Proof B.5 (Proof sketch for 6.5).

The algorithms use 6.3 to compute the difference $R^{\prime}=R\setminus S$,
concatenate $R^{\prime}$ with $S$ and return the result. The output represents
$(R\setminus S)\cup S$ concisely, if $R$ and $S$ are represented concisely.

Thanks to 5.8 the $\operatorname{\textnormal{{Concatenate}}}$ operation
requires
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{R}\right|+\left|\mathcal{A}_{S}\right|)$
work and space. In any case, the required work and space is dominated by the
set difference.

######  Proof B.6 (Proof sketch for 6.6).

Let $k=\frac{1}{\varepsilon}$ We first describe the algorithm for (a) and (b).
It yields two different algorithms for the two settings, due to different
implementations of some operations. The algorithm is divided into three
phases, the grouping phase, the pairing phase and the joining phase.

In the grouping phase, the algorithm groups the tuples of $S$ into arrays, one
array $\mathcal{G}_{t}$, for each tuple $t$ from array $\mathcal{B}$, which
represents $\pi_{X}(S)$. To save space (and work, later on), it compacts
$\pi_{X}(S)$ and each group $\mathcal{G}_{t}$. Further it defines function $f$
that maps each tuple to the compaction parameter $j$ of its compacted group
array. The grouping phase is spelled out in steps 1-7 of algorithm 1.

In the pairing phase, the algorithm first computes $R^{\prime}:=R\ltimes
S^{\prime}$ to filter out tuples from $R$ without partner tuples in $S$. Then
it partitions the tuples $t\in R^{\prime}$ by $f(t[X])$ yielding $k$ arrays
$\mathcal{B}_{1},\ldots,\mathcal{B}_{k}$, where each array $\mathcal{B}_{j}$
represents the relation $R_{j}$ of all tuples $t\in R^{\prime}$, for which the
group $\mathcal{G}_{t[X]}$ has size
$\left|\mathcal{A}_{S}\right|^{j\varepsilon}$.

In the joining phase, it remains to join each tuple $t$ in some $R_{j}$ with
all tuples in $S_{t[X]}$ which is represented by an array of size
$\left|\mathcal{A}_{S}\right|^{j\varepsilon}$. This correspondence allows to
assign an appropriate, but not too large number of processors, for each $j$.
To save space and work, the arrays representing the relations $R_{j}$ are
first compacted. Then the join is done, for each $j$ and the result arrays are
concatenated. For simplicity of presentation, the algorithm uses 2-dimensional
arrays $\mathcal{C}_{j}$ for the join, which are transformed into
1-dimensional arrays in the obvious way.

// Phase 1: the grouping phase

$S^{\prime}\leftarrow\pi_{X}(S)$ ;

// Use 6.4

$\mathcal{B}\leftarrow\operatorname{\textnormal{{Compact}}}_{\varepsilon}(\mathcal{A}_{S^{\prime}})$
;

// Use 5.14

// Let $g$ map each tuple in $S$ to the index of its projection in
$\mathcal{B}$

$(\mathcal{G}_{t})_{t\in\mathcal{B}}\leftarrow\operatorname{\textnormal{{Partition}}}(S,\left|\mathcal{B}\right|,g)$
;

// Use 5.12

1 for  _$t\in\mathcal{B}$ _ do in parallel

$\mathcal{G}_{t}\leftarrow\operatorname{\textnormal{{Compact}}}_{\varepsilon}(\mathcal{G}_{t})$
;

// Use 5.14

2 Augment $t$ by a link to $\mathcal{G}_{t}$ and let $f(t)=j$ be such that
$\left|\mathcal{G}_{t}\right|=\left|\mathcal{A}_{S}\right|^{j\varepsilon}$ ;

3

4 end forpar

// Phase 2: the pairing phase

$R^{\prime}\leftarrow R\ltimes S^{\prime}$ ;

// Use 6.2

// Note, that the algorithm in 6.2 links every tuple in $R^{\prime}$ to the
corresponding tuple in $S^{\prime}$

// Let $f^{\prime}$ map every tuple $t\in R^{\prime}$ to $f(s^{\prime})$ for
the tuple $s^{\prime}\in S^{\prime}$ to which $t$ is linked (note that
$s^{\prime}=t[X]$ holds)

$(\mathcal{B}_{1},\ldots,\mathcal{B}_{k})\leftarrow\operatorname{\textnormal{{Partition}}}(\mathcal{A}_{R^{\prime}},k,f^{\prime})$;

// Use 5.12

// Phase 3: the joining phase

Let $\mathcal{C}$ be an empty array. // At the end, this will represent the
result

5 foreach  _$j\leq k$_ do

$\mathcal{A}_{j}\leftarrow\operatorname{\textnormal{{Compact}}}_{\varepsilon}(\mathcal{A}_{R_{j}})$
;

// Use 5.14

6 Initialize 2-dimensional array $\mathcal{C}_{j}$ of size
$\left|\mathcal{A}_{j}\right|\cdot\left|\mathcal{A}_{S}\right|^{j\varepsilon}$
;

// The following for-block computes $\mathcal{R}_{j}\bowtie S$ and stores the
result in $\mathcal{C}_{j}$

7 for
_$(\ell,\ell^{\prime})\in[\left|\mathcal{A}_{j}\right|]\times[\left|\mathcal{A}_{S}\right|^{j\varepsilon}]$_
do in parallel

// The for-loop considers every tuple $t\in\mathcal{R}_{j}$ and every tuple in
the corresponding group of $\mathcal{S}_{t}$

8 if  _$\mathcal{A}_{j}[\ell]\neq\bot$_ then

9 $t\leftarrow\mathcal{A}_{j}[\ell].t$ ;

10 if  _$\mathcal{G}_{t}[\ell^{\prime}]\neq\bot$_ then

11 $\mathcal{C}_{j}\left[\ell,\ell^{\prime}\right]\leftarrow
t\Join\mathcal{G}_{t}[\ell^{\prime}]$ ;

12

13 end if

14

15 end if

16

17 end forpar

$\mathcal{C}\leftarrow\operatorname{\textnormal{{Concatenate}}}(\mathcal{C},\mathcal{C}_{j})$
;

// Here, $\mathcal{C}_{j}$ is implicitly flattened into a 1-dimensional array

18

19 end foreach

return $\mathcal{C}$

Algorithm 1 Algorithm for $R\bowtie S$ for (a) and (b)

Each step in the algorithm takes constant time. Let us now analyse the
required work and space for the grouping phase. Thanks to 6.4, algorithm 1
requires $\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|^{2})$ work
without any assumptions and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|)$ work in the
presence of a dictionary and
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|^{1+\varepsilon})$ if
$S$ is ordered. The work as well as the space of the remainder of the grouping
phase can be bounded by
$\operatorname{\mathcal{O}}(\left|\mathcal{B}\right|\cdot\left|\mathcal{A}_{S}\right|)$
which can be bounded by
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon})$,
thanks to compaction. Altogether, we get the following bounds for the grouping
phase.

  * •

Work
$\operatorname{\mathcal{O}}(\left|\mathcal{A}_{S}\right|^{2}+\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon})$
and space
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon})$
without any assumptions;

  * •

Work and space
$\operatorname{\mathcal{O}}(\left|\pi_{X}(S)\right|^{1+\varepsilon}\left|\mathcal{A}_{S}\right|^{1+\varepsilon})$
in the presence of a dictionary.

In the pairing phase, the work and space bounds for the semijoin operation