††thanks: Big thanks to the anonymous reviewers who read the firsts versions
of that paper. Special thanks to Luc Segoufin and Sophie Dramé-Maigné for
helping me with their thoughtful comments

# Dynamic Query Evaluation Over Structures With Low Degree

Alexandre Vigny  Universität Bremen, Germany<EMAIL_ADDRESS>
###### Abstract

We consider the evaluation of first-order queries over classes of databases
that have _bounded degree_ and _low degree_. More precisely, given a query and
a database, we want to efficiently test whether there is a solution, count how
many solutions there are, or be able to enumerate the set of all solutions.

Bounded and low degree are rather natural notions and both yield efficient
algorithms. For example, Berkholz, Keppeler, and Schweikardt showed in 2017
that over databases of bounded degree, not only any first order query can
efficiently be tested, counted and enumerated, but the data structure used can
be updated when the database itself is updated.

This paper extends existing results in two directions. First, we show that
over classes of databases with low degree, there is a data structure that
enables us to test, count and enumerate the solutions of first order queries.
This data structure can also be efficiently recomputed when the database is
updated. Secondly, for classes of databases with bounded degree we show that,
without increasing the preprocessing time, we can compute a data structure
that does not depend on the query but only on its quantifier rank. We can
therefore perform a single preprocessing that can later be used for many
queries.

###### keywords:

dynamic databases, first-order queries, enumeration, bounded degree, low
degree

##  1 Introduction

Query evaluation is one of the most central tasks of a database system and a
vast amount of literature is devoted to the complexity of this problem. Given
a database $\mathcal{D}$ and a query $\varphi$, the goal is to compute the set
$\varphi(\mathcal{D})$ of all solutions for $\varphi$ over $\mathcal{D}$.
Unfortunately, the set $\varphi(\mathcal{D})$ might be much bigger than the
database itself, as the number of solutions may be exponential in the arity of
the query. It can therefore be insufficient to measure the complexity of
answering $\varphi$ on $\mathcal{D}$ only in terms of the total time needed to
compute the complete result set $\varphi(\mathcal{D})$. Many other algorithmic
tasks have been studied to overcome this situation. We can for instance only
compute the number of solutions or simply test whether there exists a
solution.

In addition, we consider evaluation of queries in a “dynamic setting”, where
the databases may be updated by inserting or deleting tuples. In this setting,
given a database $\mathcal{D}$ and a query $\varphi$, the goal is to compute a
_data structure_ that represents the result of evaluating $\varphi$ on
$\mathcal{D}$. After every database update, the data structure must be adapted
so that it represents the result of evaluating $\varphi$ on
$\mathcal{D}^{\prime}$, the new database.

Since we do not wish to compute the entire set of solutions, we want the data
structure to enable us to efficiently perform the following tasks:

  * •

_Model check:_ Decide whether $\varphi(\mathcal{D})=\emptyset$.

  * •

_Enumerate:_ Enumerate the set $\varphi(\mathcal{D})$ i.e. to output one by
one all elements of $\varphi(\mathcal{D})$.

  * •

_Test:_ Given a tuple $\overline{a}$, decide whether it is in
$\varphi(\mathcal{D})$.

  * •

_Count:_ Compute the number $\\#\varphi(\mathcal{D})$ of solutions.

The time needed to solve these problems is split between three sub-processes.
The first one is the _preprocessing_ , i.e. the process that computes the data
structure. The second one is the _update_ , i.e. the process that adapts the
data structure when the database is updated. The third and final process is
the _answering_ , or _enumeration_. For the enumeration problem, the delay is
the maximum time between the outputs of any two consecutive solutions.

We want to perform these processes as efficiently as possible. For the
answering or enumeration process, the best we can hope for is to perform it in
constant time (or with constant delay): depending only on the query and
independent from the size of the database. For the preprocessing, an ideal
time would be linear time: linear in the size of the database with a constant
factor depending on the query. The ideal update time depends on what kind of
updates are allowed. If we only allow _local updates_ that only affect a fixed
number of tuples, one can hope for update procedures working in constant or
almost constant time.

###  1.1 The need of restrictions

Efficient algorithmic procedures for these problems cannot be achieved for all
queries over all databases. Even without updates the model checking of first-
order (FO) queries over arbitrary relational structure is, by definition,
AW[$*$]-complete [12, Definition 8.29]. But for restricted classes of queries
and databases, several evaluation algorithms with linear time preprocessing
have been obtained, first without updates.

This is the case for arbitrary databases, when paired with free-connex acyclic
conjunctive queries [4], some unions of conjunctive queries [9], or
conjunctive queries with bounded submodular width [8]. Allowing for more
powerful query languages requires restrictions on the database part.
Evaluation algorithms with linear preprocessing exist for FO queries over
classes of databases with bounded degree [10, 17], bounded expansion [18], and
for monadic second-order (MSO) queries over classes of databases of bounded
tree-width [3, 19].

In some scenarios only pseudo-linear preprocessing time has been achieved. A
query can be enumerated with constant delay after pseudo-linear preprocessing
if for all $\epsilon$ there exists an enumeration procedure with constant
delay (the constant may depend on $\epsilon$) and preprocessing time in
$O(|\\!|\mathcal{D}|\\!|^{1+\epsilon})$, where $|\\!|\mathcal{D}|\\!|$ denotes
the size of the database. This has been achieved for FO queries over classes
of databases with low degree [11], locally bounded expansion [25], and for
nowhere dense classes of databases [14, 15, 24].

If we allow updates, the problem is at least as hard. This more restricted
line of research is quite recent but already some dynamic procedures have been
provided: for conjunctive queries over arbitrary relational structures [5, 7],
for MSO queries over words, trees, and graphs with bounded tree-with [21, 2,
23], and for FO queries over graphs with bounded degree [6] and bounded
expansion [26].

Interested readers can look at the third chapter (Figure 3.1) of the Thesis
[27], or Figures 4 and 5 of [16] for a more detailed overview of these
results.

###  1.2 Main results

Our first result concerns classes of databases with low degree. We show that
for such classes, and for any first order query, there is a data structure
that can be computed in time $O(n^{1+\epsilon})$ (where $n$ is the size of the
database) and recomputed in time $O(n^{\epsilon})$ when the database is
updated. Using the data structure, the answering processes for the model-
checking, testing and counting problems can be performed in constant time.
Additionally, the set of solutions can be enumerated with constant delay,
without further preprocessing. See Theorems 7 and 8 for formal statements of
that result.

The second result concerns classes of graphs with bounded degree. We expand on
existing results and show that a single linear time preprocessing can be used
to model-check, test, and count in constant time, and also to enumerate with
constant delay the solutions of a whole family of queries. We are also able to
update the results in constant time when the database is updated. We already
knew that it was possible when only one query is given as input [6].
Additionally, one can note that if a finite family of queries is given as
input, it is easy to perform one preprocessing for each query. The parameter
would simply be the sum of the sizes of the queries. However, in our
contribution, the preprocessing time is smaller than the time it would take to
perform one preprocessing for each individual query of the inputed family.
Even better, our running time matches those of the algorithms that take as
input only one query: triply exponential in the quantifier rank of the query,
or in our case in the maximal quantifier rank amongst the possible queries.
See Theorems 14 and 15 for formal statements of that result.

###  1.3 Related techniques

While the results are new, the techniques used to obtain them are not. We are
using Gaifman local form of first order formulas, which is already at the core
of the existing results for structures with bounded and low degree [6, 11,
17].

Enumeration algorithms with constant delay often need a mechanism used to skip
irrelevant parts of the input. An adequate technique (with small variations)
has been used several times in previously published results. The firsts
appearances where in [11, Section 3.5] and [18, Section 4]. Some variations
have been used again in [6, Lemma 10.1] and [24, Lemma 3.10]. We use a similar
structure described in Lemma 12. Concerning the counting part of our results,
we use a classic inclusion-exclusion argument. This argument is materialized
in Lemma 13, which is analogous to what can be found in [25, Section 7].

The proofs of our main results follow the same path. In both cases we focus
first on centered queries (Definition 5). These queries only talk about the
neighborhood of one node. When the degree of the database is small, that
neighborhood is also small. It is therefore possible to entirely compute all
solutions of a given centered query in (pseudo) linear time. The main results
are then proved using the fact that all first order queries are combinaisons
of centered ones together with adequate tools like Lemmas 12 and 13.

###  1.4 Organization

The rest of the paper is structured as follows. Section 2 provides basic
notations and additional information about our setting and our computational
model. In Section 3 we state refinements of the results our paper is build on,
mainly, Gaifman locality of first-order queries. Finally, Section 4 and 5
prove the two main results respectively.

##  2 Preliminaries

By $\mathbb{N}$ we denote the non-negative integers, and we let
$\mathbb{N}_{\scriptstyle\geq 1}:=\mathbb{N}\setminus\\{0\\}$. Throughout this
paper, $\epsilon$ will always be a positive real number, and $d$, $i$, $j$,
$k$, $\ell$, $m$, $n$, $p$, $q$, $r$ will be elements of $\mathbb{N}$.

###  2.1 Colored graphs and first-order queries

We define _undirected colored graphs_ (or simply graphs) as sets of vertices
equipped with a symmetric binary relation (edges) and some unary predicates
(colors).

As mentioned in the introduction, our algorithms work for classes of
databases. However we will only prove results for classes of graphs. Our
algorithms can be adapted to the general case of databases (viewed as
relational structure) via standards techniques. Namely, one can take any
relational structure and compute a colored version of its adjacency graph.
Interested readers can look at [24] (Section 2, From databases to colored
graphs) to see the details of this transformation.

We denote by $|G|$ the size $|V|$ of its vertex set, and $\|G\|$ the size of
(an encoding of) $G$. Without loss of generality we assume that the set $V$
comes with a linear order. If not we arbitrarily choose one. This order
induces a lexicographical order among the tuples of vertices.

In this paper, queries are first-order formulas. We assume familiarity with
first-order logic (FO), over relational structures (see [1, 20] for more
information). We use standard syntax and semantics for FO. In particular we
write $\varphi(\overline{x})$ to denote the fact that the free variables of
the query $\varphi$ are exactly the variables in $\overline{x}$. The length of
$\overline{x}$ is called the _arity_ of the query. The _size_ of a query
$\varphi$ is the number of symbols needed to write down the formula and is
denoted by $|\varphi|$, and the _quantifier rank_ of a query $\varphi$ is the
depth of nesting of its quantifiers.

A _sentence_ (or boolean query) is a formula with no free variable, i.e. of
arity 0.

We write $G\models\varphi(\overline{a})$ to indicate that $\overline{a}$ is a
solution for $\varphi$ over $G$ and note $\varphi(G)$ the set of tuples
$\overline{a}$ such that $G\models\varphi(\overline{a})$.

###  2.2 Model of computation

As customary when dealing with linear time, we use Random Access Machines
(RAM) with uniform cost measure as a model of computation. More precisely, we
need our computational model to perform two tasks. The first one is to store
(ordered) lists with the ability of testing whether an element is in the list
in constant time. The ordered version would require logarithmic time to insert
(resp. remove) an element to (resp. from) the list. The second one is to store
the values of a given function, and later retrieve the image of a given input
in constant time. These requirements are standards, see e.g. [5] (Section 2,
Dynamic Algorithms for Query Evaluation).

Both come for free in the RAM model. For any fix integer $k$, it is possible
to associate any $k$-tuple of integers to a specific cell of the memory and,
given that tuple, to access this cell in constant time. This together with the
fact that we can assume that the memory is initially empty (which require a
technique called the lazy array initialisation [22]) enable us to perform
these two tasks.

While this works on the RAM model, it shows that we are getting away from
real-life computers.

###  2.3 Parametrized complexity

All problems encountered in this paper have two inputs: a graph $G$ and a
query $\varphi(\overline{x})$. However, they play different roles as
$|\\!|G|\\!|$ is often very large while $|\varphi|$ is generally small. We
therefore adopt the parameterized complexity point of view. When we say
_linear time_ we mean in time $O(|\\!|G|\\!|)$, the constants hidden behind
the “big $O$” depending on $\varphi$, on the class $\mathcal{C}$ of graphs
under investigation, and possibly on further parameters that will be clear
from the context.

We say that a problem is solvable in _pseudo-linear time_ if, for all
$\epsilon$, it can be solved in time $O(|\\!|G|\\!|^{1+\epsilon})$. In this
case, the constant factor also depends on $\epsilon$. If a subroutine of a
procedure depending on $\epsilon$ produces an output of size
$O(|\\!|G|\\!|^{\epsilon})$ we will say that the output is _pseudo-constant_.

###  2.4 Distance and neighborhoods

Given a graph $G=(V,E)$ and two elements $a$ and $b$ of $V$, the _distance_
between $a$ and $b$ noted $\mathrm{dist}(a,b)$ is the length of the shortest
path between $a$ and $b$ (the number of edges). If there is no such path,
$\mathrm{dist}(a,b):=\infty$. The notion of distance extends to tuples in the
usual way, i.e., the distance between two tuples $\overline{a}$ and
$\overline{b}$ is the minimum of the distances between $a_{i}$ and $b_{j}$
over all $i,j$.

For a positive integer $r$, we write $N_{r}^{G}(a)$ for the set of all
elements of $V$ at distance at most $r$ from $a$. The $r$-neighborhood of $a$
in $G$, denoted $\mathcal{N}^{G}_{r}(a)$, is the substructure of $G$ induced
by $N_{r}^{G}(a)$. Similarly, for a tuple $\overline{a}$ of arity $k$ we let
$N_{r}^{G}(\overline{a}):=\bigcup_{i\leq k}N_{r}^{G}(a_{i})$, and we define
$\mathcal{N}_{r}^{G}(\overline{a})$ as the substructure of $G$ induced by
$N_{r}^{G}(\overline{a})$.

###  2.5 Graphs with bounded and low degree

The _degree_ of an undirected graph $G=(V,E)$ is the maximal number, over all
elements $a$ of $V$, of elements $b$ in $V$ such that $(a,b)\in E$. We note
$d(G)$ the degree of $G$.

A class $\mathcal{C}$ of graphs has _bounded degree_ if there is an integer
$d$ such that every graph of $\mathcal{C}$ has degree at most $d$.

A class $\mathcal{C}$ of graphs has _low degree_ if there is a function
$f(\cdot)$ such that for any $\epsilon>0$, and for any graph $G$ of
$\mathcal{C}$, we have $d(G)\leq f(\epsilon)\cdot|G|^{\epsilon}$. Examples of
classes of graphs with low degree are classes of graphs with bounded degree
and classes of graphs $G$ with $d(G)\leq\log(|G|)$.

###  2.6 Updates

We allow graphs to be updated. A _local update_ of a graph $G$ is a graph
$G^{\prime}$ obtained from $G$ by inserting or deleting a node, an edge, or by
modifying the membership of a given node to a unary predicate (relabeling). In
this paper, we restrict our attention to classes of graphs with bounded or low
degree. Therefore when updating a graph, the update is allowed only if the
bounds on the degree are maintained in the new graph.

For classes of graphs with bounded degree, given a number $d$ it is easy to
check in time $O(d)$ whether when adding a given edge to a graph of degree at
most $d$, we make the new graph to have a degree exceeding $d$ or not.

For classes of graphs with low degree, the problem is a little bit trickier. A
class of graph $\mathcal{C}$ has _effectively low degree_ if there is a
computable function $f(\cdot)$ such that for every $\epsilon>0$, and for all
graph $G$ in $\mathcal{C}$, we have $d(G)\leq f(\epsilon)\cdot|G|^{\epsilon}$.

If $\mathcal{C}$ has effectively low degree, then it is possible (for example)
to maintain the ordered list of every vertex’s degree in time $\log(|G|)$.
Then for any $\epsilon>0$, it is possible to check in time
$\log(|G|)=O(f(\epsilon)\cdot|G|^{\epsilon})$ whether the degree of $G$ still
remains below that bound. In this paper, we only talk about classes of graphs
with effectively low degree and therefore often omit the “effectively” for
better readability. When dealing with update, the following definition and
lemma (although quite elementary) simplify every proof.

######  Definition .

Let $G$ be a graph and $G^{\prime}$ a local update of $G$. For an integer $r$
in $\mathbb{N}$, a node $a$ is _$r$ -impacted_ if it is: (i) only in $G$, or
(ii) only in $G^{\prime}$, or (iii) in both but
$\mathcal{N}^{G}_{r}(a)\neq\mathcal{N}^{G^{\prime}}_{r}(a)$.

######  Lemma 1.

Let $G$ be a graph and $G^{\prime}$ a local update of $G$. For any integer $r$
in $\mathbb{N}$, the list $L_{u}$ of all $r$-impacted nodes has size
$O(d^{r})$ and can be computed in time $O(d^{r})$, where $d$ is the degree of
$G$.

##  3 Technical definitions

In this section we explain and define some tools that are used throughout the
rest of the paper. We first define the notions of distance queries, distance
types, and later explain how they are used to express FO queries in a local
and succinct way.

###  3.1 Distance and types

A distance query is a binary query that only talks about the distance of two
nodes in a graph. For all $r\in\mathbb{N}$, the query $\mathrm{dist}_{\leq
r}(a,b)$ states that there is a path of length at most $r$ between $a$ and
$b$. It can formally be defined as follows:

$\mathrm{dist}_{\leq 0}(x,y):=(x=y)\quad\quad\mathrm{dist}_{\leq
r+1}(x,y):=\mathrm{dist}_{\leq r}(x,y)~{}\vee~{}\exists
z~{}\big{(}E(x,z)\wedge\mathrm{dist}_{\leq r}(z,y)\big{)}.$

Once this is defined, one can also make use of those variations:
$\mathrm{dist}_{>r}(x,y):=\neg\mathrm{dist}_{\leq r}(x,y)$ and
$\mathrm{dist}_{=r}(x,y):=\mathrm{dist}_{\leq
r}(x,y)\wedge\mathrm{dist}_{>r-1}(x,y)$.

######  Definition 2 (Distance type).

For a graph $G=(V,E)$ and an integer $r$ in $\mathbb{N}$, the _$r$ -distance
type_ of a tuple $\overline{a}=(a_{1},\ldots,a_{k})$ is the undirected graph
$\tau_{r}^{G}(\overline{a})$ whose nodes are $[1,k]$ and edges are exactly the
pairs $(i,j)$ such that $G\models\mathrm{dist}_{\leq r}(a_{i},a_{j})$. We
denote by ${\cal T}_{k}$ the set of all possible distance types with $k$
elements.

For every integers $r$, $k$ and distance type $\tau\in{\cal T}_{k}$, there is
a query $\Delta_{r,\tau}(\overline{x})$ such that for every graph $G$ and
tuple $\overline{a}$, we have that $G\models\Delta_{r,\tau}(\overline{a})$ if
and only if $\tau_{r}^{G}(\overline{a})=\tau$. Furthermore
$\Delta_{r,\tau}(\overline{x})$ is a boolean combination of distance queries.

For example, if $k=3$ and $\tau$ only contains the edge $(1,2)$, then
$\Delta_{r,\tau}(x,y,z):=\mathrm{dist}_{\leq
r}(x,y)\wedge\mathrm{dist}_{>r}(x,z)\wedge\mathrm{dist}_{>r}(y,z)$.

###  3.2 Normal form for FO queries

The classes of graphs we consider have small neighborhoods. It is therefore
interesting to use the locality of first order logic.

######  Definition 3 (Local queries).

A query $\varphi(\bar{x})$ is said to be $r$-local if all its quantifications
are relative to elements at distance at most $r$ from one of its free
variables $\bar{x}$, i.e. if it uses quantifications of the form $\exists
y~{}\mathrm{dist}_{\leq r}(y,\bar{x})\land\cdots$ and $\forall
y~{}\mathrm{dist}_{\leq r}(y,\bar{x})\Rightarrow\cdots$ .

######  Theorem 4 (Gaifman’s theorem. Originally [13], see [20, Theorem
4.22]).

For every FO formula $\phi(\overline{x})$, there are $r,s\in\mathbb{N}$ such
that $\phi$ is equivalent to a boolean combination of $r$-local queries and
sentences of the form:

$\exists x_{1}\ldots x_{s}~{}\Big{(}\underset{1\leq i\leq j\leq
s}{\bigwedge}~{}\mathrm{dist}_{>2r}(x_{i},x_{j})\wedge\underset{1\leq i\leq
s}{\bigwedge}\alpha(x_{i})\Big{)}$ (1)

Here $\alpha(x)$ is an $r$-local query. Moreover, this combination is
computable from $\phi$, $r=2^{O(q)}$, and $s\leq q$ where $q$ is the
quantifier rank of $\varphi$.

When working with non boolean queries, locality is not enough. We also want to
know how the free variables are scattered across the graph.

######  Definition 5 (Local centered queries).

An $r$-local query $\alpha(\overline{x})$ is said to be _$r$ -local centered_
if for every graph $G$ and tuple $\overline{a}$, if
$G\models\alpha(\overline{a})$ then the $2r$-distance type of $\overline{a}$
has only one connected component.

Note that an $r$-local centered query of arity $k$ is also $2kr$-local around
any of its free variables. It is also worth mentioning that an $r$-local query
that is unary is necessarily centered. Similarly, the query
$\mathrm{dist}_{\leq 2r}(x,y)$ is $r$-local centered, and
$\Delta_{2r,\tau}(\overline{x})$ is $r$-local centered if and only if $\tau$
has exactly one connected component.

######  Corollary 6 (Of Theorem 4).

For every integers $k$ and $q$, there is an integer $r$ such that every query
$\varphi(\overline{x})$ of arity $k$ and quantifier rank $q$ is equivalent to
a boolean combination of sentences of the form of Equation 1 and $r$-local
queries. Furthermore, once all sentences have been replaced by their truth
value, we are left with a strict disjunction of queries of the form:

$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x}),$
(2)

where $r=2^{O(q)}$, $\alpha_{i}(\overline{x}_{i})$ are $r$-local centered
queries, $(I_{1},\ldots,I_{p})$ is a partition of $[k]$ and $\tau$ is a graph
whose connected components are exactly $(I_{1},\ldots,I_{p})$, with
$I_{i}:=\\{j\leq k~{}:~{}x_{j}\in\overline{x}_{i}\\}$.

To obtain this corollary from Theorem 4, we need (among other things) to take
a disjunction over all possible $\tau$ in ${\cal T}_{k}$. For each $\tau$, the
remaining local query can be simplified as all atoms of the form
$E(x_{i},x_{j})$ can be set to false, as soon as $i$ and $j$ are not in the
same connected component of $\tau$.

##  4 Structures with low degree

This section is devoted to the proof of our first contribution.

######  Theorem 7.

For every class of graphs $\mathcal{C}$ with effectively low degree, there is
a computable function $f$ and an algorithm that upon input of a graph $G$ in
$\mathcal{C}$, an FO sentence $\phi$ and an $\epsilon>0$, computes a data
structure that:

  * •

can be computed in time $O\big{(}f(|\phi|)\cdot|G|^{1+\epsilon}\big{)}$,

  * •

can be recomputed in time $O\big{(}f(|\phi|)\cdot|G|^{\epsilon}\big{)}$ when
$G$ is subject to a local update, and

  * •

enables us to test in time $O(1)$ whether $G\models\phi$.

This theorem is proved in Section 4.2.

######  Theorem 8.

For every class of graphs $\mathcal{C}$ with effectively low degree, there is
a computable function $f$ and an algorithm that upon input of a graph $G$ in
$\mathcal{C}$, an FO query $\varphi(\overline{x})$ and an $\epsilon>0$,
computes a data structure that:

  * •

can be computed in time $O\big{(}f(|\varphi|)\cdot|G|^{1+\epsilon}\big{)}$,
and

  * •

can be recomputed in time $O\big{(}f(|\varphi|)\cdot|G|^{\epsilon}\big{)}$
when $G$ is subject to a local update.

  * •

Furthermore, the data structure enables us:

    1. 1.

(enum:) to enumerate with delay $O\big{(}f(|\varphi|)\big{)}$, and without
further preprocessing the set $\varphi(G)$ of solutions for
$\varphi(\overline{x})$ over $G$,

    2. 2.

(test:) upon input of a tuple $\overline{a}$, to test in time
$O\big{(}f(|\varphi|)\big{)}$ whether $G\models\varphi(\overline{a})$, and

    3. 3.

(count:) to compute in time $O\big{(}f(|\varphi|)\big{)}$ the number
$\\#\varphi(G)$ of solutions for $\varphi$ over $G$.

The proof of these two Theorems follow standard paths. We show in the next
section that the Theorems hold for $r$-local centered queries (see Definition
5). We then generalize to full FO with combinatorial techniques. As explained
in Section 1.3, these techniques are similar to what can be found in the
static case [11] or the dynamic case for structures with bounded degree [17,
6].

###  4.1 Centered queries

We restrict our attention to $r$-local centered queries. For these queries,
and thanks to the degree bound, it is actually possible to compute the entire
result and to recompute it when the graph is updated.

######  Lemma 9.

Let $\mathcal{C}$ be a class of graphs with effectively low degree. For every
graph $G$ in $\mathcal{C}$ with $n:=|G|$, every $\epsilon>0$, every
$r\in\mathbb{N}$ and any $r$-local centered query $\alpha(\overline{x})$, we
can:

  * •

compute $L_{\alpha}$ and $\\#\alpha$ in time $O(n^{1+\epsilon})$, and

  * •

recompute $L_{\alpha}$ and $\\#\alpha$ in time $O(n^{\epsilon})$ whenever a
local update occurs in $G$.

Here, $L_{\alpha}$ is the ordered list of tuples from $G$ satisfying
$\alpha(\overline{x})$. By $\\#\alpha$ we mean
$|\\{\overline{a}~{}:~{}G\models\alpha(\overline{a})\\}|$, which is also
$|L_{\alpha}|$.

######  Proof 4.1 (Proof of Lemma 9).

The challenging part of the proof of Lemma 9 is the update part. The
preprocessing one can be performed using the update procedure as follows:

  * •

Start with $G:=\emptyset$. We have $\\#\alpha$ equals $0$ and $L_{\alpha}$ is
empty.

  * •

Add all vertices one by one and for each perform the update procedure.

  * •

Add all edges one by one and for each perform the update procedure.

This gives a preprocessing procedure with the desired complexity. We now turn
to the update procedure.

Let $\mathcal{C}$ be a class of graph with low degree. Let $G=(V,E)$ be a
graph in $\mathcal{C}$. Let $\epsilon>0$, $r\in\mathbb{N}$ and
$\alpha(\overline{x})$ be an $r$-local centered query and $k$ its arity. Let
$\delta>0$ small enough that: $\epsilon\geq 6\delta k^{2}r\cdot|\alpha|$ and
$\log(n)\leq f(\delta)\cdot n^{\delta}$. (Recall $f(\delta)$ from the
definition of classes of graphs with effectively low degree.)

Let $G^{\prime}=(V^{\prime},E^{\prime})$ the graph obtained from $G$ after the
update. Let $n=|V^{\prime}|$. We know that $d(G^{\prime})\leq f(\delta)\cdot
n^{\delta}$. Let $L_{u}$ be the list of nodes $2kr$-impacted by the local
update. By Lemma 1, we have that $|L_{u}|$ has size at most
$O(d(G)^{2kr})=O(n^{\delta\cdot 2kr})$ and can be computed in similar time. We
then apply the following algorithm:

For every $r$-impacted node $a_{1}\in L_{u}$, we study every possible tuple
$\overline{a}=(a_{1},\ldots,a_{k})\subseteq N_{2kr}^{G^{\prime}}(a_{1})$. Then
for every such tuple, we test by brut fore whether
$\mathcal{N}_{2kr}^{G^{\prime}}(a_{1})\models\alpha(\overline{a})$. As
$\alpha$ is $r$-local centered, this is true if and only if
$G\models\alpha(\overline{a})$. We also test whether $\overline{a}$ was
already in $L_{\alpha}$. We finally update $L_{\alpha}$ and $\\#\alpha$
accordingly.

For the complexity analysis, the size of
$\mathcal{N}_{2kr}^{G^{\prime}}(a_{1})$ is bounded by $d(G)^{2kr}$, i.e.
bounded by $n^{2\delta kr}$. Therefore the number of considered tuples is
bounded by $(\mathcal{N}_{2kr}^{G^{\prime}}(a_{1}))^{k}=n^{2\delta k^{2}r}$.
Then we need time $O(|\mathcal{N}_{2kr}^{G^{\prime}}(a_{1})|^{|\alpha|})$ to
check with brute force whether
$\mathcal{N}_{2kr}^{G^{\prime}}(a_{1})\models\alpha(\overline{a})$, i.e.
$O(n^{2\delta kr\cdot|\alpha|})$. The procedures $add$ and $remove$ require
time $O(\log(n))$ to keep $L_{\alpha}$ ordered, and thus $O(f(\delta)\cdot
n^{\delta})$. Therefore the time spend for every considered $\overline{a}$ is
$O(n^{2\delta kr\cdot|\alpha|})$. Hence we spend time $O(n^{4\delta
k^{2}r\cdot|\alpha|})$ for every element $a\in L_{u}$. At the end, the overall
complexity is:
$O(|L_{u}|\cdot n^{4\delta k^{2}r\cdot|\alpha|})=O(n^{6\delta
k^{2}r\cdot|\alpha|})=O(n^{\epsilon})$.

This ends the proof of Lemma 9

We now have at our disposal a data structure that efficiently evaluates
centered queries. In the upcoming sections we generalize it to deal with full
FO.

###  4.2 The model checking problem

This section proves Theorem 7. The next lemma shows that Lemma 9 is enough to
prove the result for sentences of the form 1. By Theorem 4, every first order
sentence is a boolean combination of such sentences. As evaluating a boolean
combination takes constant time (independent from the size of $G$), Theorem 7
follows.

######  Lemma 10.

For every class of graphs $\mathcal{C}$ with effectively low degree, for every
$r$-local unary query $\alpha(x)$, for every integer $k$, for every $G$ in
$\mathcal{C}$ with $n:=|G|$, and for every $\epsilon>0$, giving $L_{\alpha}$
and $\\#\alpha$ as stated in Lemma 9, we can test in time $O(n^{\epsilon})$
whether $G$ models

$\varphi~{}:=~{}\exists x_{1}\ldots x_{k}~{}\Big{(}\underset{1\leq
i<i^{\prime}\leq
k}{\bigwedge}~{}\mathrm{dist}_{>2r}(x_{i},x_{i^{\prime}})\wedge\underset{1\leq
i\leq k}{\bigwedge}\alpha(x_{i})\Big{)}.$

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

Let $\mathcal{C}$ be a class of graphs with low degree, $G$ a graph of
$\mathcal{C}$, $n:=|G|$, and $\epsilon>0$. Let $\delta>0$ such that
$\epsilon\geq 3\delta r\cdot|\varphi|$.

We know that $d(G)\leq f(\delta)\cdot n^{\delta}$. We then distinguish two
cases whether $\\#\alpha$ is smaller than $k\cdot d(G)^{2r}$.

  * •

If $\\#\alpha>k\cdot d(G)^{2r}$, there must be $k$ elements in $L_{\alpha}$
that are pairwise at distance greater than $2r$. In that case we know that
$G\models\varphi$.

  * •

If $\\#\alpha\leq k\cdot d(G)^{2r}$, then $|N_{r}^{G}(L_{\alpha})|\leq k\cdot
d(G)^{3r}$. Furthermore, it is always the case that $G\models\varphi$ if and
only if $\mathcal{N}_{r}^{G}(L_{\alpha})\models\varphi$. Therefore we can test
whether $G\models\varphi$ in time:

$O\left(N_{r}^{G}(L_{\alpha})^{|\varphi|}\right)\quad=\quad
O\left(\big{(}k\cdot d(G)^{3r}\big{)}^{|\varphi|}\right)\quad=\quad
O\big{(}n^{3\delta r\cdot|\varphi|}\big{)}\quad=\quad
O\big{(}n^{\epsilon}\big{)}.$

This ends the proof of Lemma 10 and therefore of Theorem 7

###  4.3 The enumeration problem

The goal of this section is to prove the enumeration part of Theorem 8. Thank
to Corollary 6, every FO query is a boolean combination of sentences and FO
queries of the form:
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x}).$
Furthermore, once the sentences have been replaced by their truth value, we
are left with a strict disjunction of queries of the form above.

We can compute the data structure of Lemma 10 for each sentence of the
decomposition. Unfortunately, the value of those sentences over the graph can
be impacted by the update. Fortunately, there is only a constant number of
possible valuations for the sentences.

Every possible evaluation of the sentences gives us a strict disjunction of
queries of the form above. For each, we compute a data structure (described
below) allowing us to enumerate their solutions with constant delay. For the
enumeration phase, we first test which sentences are true. This gives us which
strict disjunction of queries of the form above needs to be enumerated. We
then simultaneously enumerate all of their solutions in lexicographical order
and with constant delay.

We therefore only prove the following lemma.

######  Lemma 11.

Let $\varphi(\overline{x})$ be an FO query of the form
$\varphi(\overline{x})=\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$,
where $\alpha_{i}$ are $r$-local centered queries. Let $G$ be a graph from a
class $\mathcal{C}$ with effectively low degree and $n:=|G|$. For every
$\epsilon>0$, there is a data-structure that:

  * •

can be computed in time $O(n^{1+\epsilon})$,

  * •

can be updated in time $O(n^{\epsilon})$ when $G$ is subject to local updates,
and

  * •

allows to enumerate $\varphi(G)$ with constant delay and no additional
preprocessing.

The proof goes by induction on $k$, which is the number of variables in
$\varphi$.

######  Proof 4.3 (Proof of Lemma 11).

Similarly to the proof of Lemma 9, we only provide the update procedure as the
preprocessing can be viewed as performing updates from the empty graph to the
desired one.

$\bullet$ If $k=1$. Then $p=1$ and this case has already been proved by Lemma
9. Once $L_{\varphi}$ has been stored on a RAM, we can simply run through it.

$\bullet$ If $k>1$. Let
$\overline{z}=(\overline{x}_{1},\ldots,\overline{x}_{p-1})$. Consider the
following two queries:

$\varphi_{1}(\overline{z}):=\exists\overline{y}_{p}~{}\varphi(\overline{z},\overline{y}_{p})\quad\text{and}\quad\varphi_{2}(\overline{x}_{p}):=\alpha_{p}(\overline{x}_{p}).$

It is easy to see that both $\varphi_{1}$ and $\varphi_{2}$ have strictly less
than $k$ variables. Therefore, the induction hypothesis holds for
$\varphi_{1}$ and $\varphi_{2}$. A simple (and wrong) idea would be to
enumerate all solutions $\overline{c}$ in $\varphi_{1}(G)$ and for each of
them enumerate all solutions $\overline{a}_{p}$ in $\varphi_{2}(G)$ and output
$(\overline{c},\overline{a}_{p})$ if and only if
$G\models\mathrm{dist}_{>2r}(\overline{c},\overline{a}_{p})$. The issue is
that given a tuple $\overline{c}$, we might encounter, in a row, a non
constant amount of tuples $\overline{a}_{p}$ that do not satisfy this
condition.

We need, for any tuple $\overline{c}$ and any tuple $\overline{a}_{p}$ in
$\varphi_{2}(G)$, to be able to compute in constant time the smallest tuple
$\overline{a}^{\prime}_{p}$ in $\varphi_{2}(G)$ that is bigger than
$\overline{a}_{p}$ and that satisfies the condition:
$G\models\mathrm{dist}_{>2r}(\overline{c},\overline{a}^{\prime}_{p})$.

An adequate technique to solve this issue has been used several times in
previously published results. The firsts appearances where in [11, Section
3.5] and [18, Section 4]. Some variations have been used again in [6, Lemma
10.1] and [24, Lemma 3.10]. We now state our version, that is particularly
suited to deal with tuples of elements.

######  Lemma 12.

Let $\mathcal{C}$ be a class of graphs with low degree. Let $G$ be a graph in
$\mathcal{C}$, $n:=|G|$, $\epsilon>0$ and $L$ be a list of $k$-ary,
$r$-centered tuples of elements of $G$ and let
$k\in\mathbb{N}_{\scriptstyle\geq 1}$. There is a data structure computable in
time $O(|L|\cdot n^{\epsilon})$ and recomputable in time $O(n^{\epsilon})$
(when a tuple is added or removed from $L$) allowing us, given a tuple
$\overline{b}$ in $L$ and a set $I$ of at most $k$ elements of $G$, to compute
in constant time the next tuple $\overline{b}^{\prime}$ in $L$ satisfying
$\mathrm{dist}_{>r}(\overline{b}^{\prime},a)$ for all $a$ in $I$.

The idea is to compute a function ${\textup{SKIP}}(\overline{b},I)$ that does
what we want. The difficulty is that this function is way too big to be
computed entirely. Fortunately only computing a small part of it (of pseudo
linear size) is enough for our needs. The proof of Lemma 12 is written in
Appendix A.1.

###  4.4 The testing problem

The goal of this section is to prove the testing part of Theorem 8.

######  Proof 4.4.

Let $G$ be a graph from a class $\mathcal{C}$ of low degree, let $n:=|G|$, and
let $\varphi(\overline{x})$ be an FO query. Thanks to Corollary 6, we know
that there is an $r$ exponential in $|\varphi|$ such that
$\varphi(\overline{x})$ is equivalent to a boolean combination of FO sentences
and FO queries of form 2.

Thanks to Theorem 7, for every FO sentence of the decomposition, there is a
data structure allowing us to test in constant time whether each sentence
holds in the graph. Thanks to Lemma 9, similar structures exist for any
$r$-local centered queries $\alpha_{i}(\overline{x}_{i})$ that appear in the
decomposition. Moreover, the distance type query
$\Delta_{2r,\tau}(\overline{x})$ is a boolean combination of $r$-local
centered queries. Hence we can also use the data structure provided by Lemma 9
for those queries.

All of these structures can be computed in time $O(n^{1+\epsilon})$ and
updated in time $O(n^{\epsilon})$. Furthermore they are only a constant number
of such queries, hence the overall complexity is exactly what we need.
Finally, when a tuple is given, we can use those data structures to test in
constant time which queries and sentences hold in the graph. Given that
information, we can compute the boolean combination and answer the testing
problem for $\varphi(\overline{x})$ over $G$ in constant time (depending only
on $\mathcal{C}$ and $\varphi$).

###  4.5 The counting problem

Here we prove the counting part of Theorem 8.

Similarly to the enumeration part, and thanks to Corollary 6 we only provide
an algorithm for queries of the form
$\varphi(\overline{x})=\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$.

The proof goes by induction on $p$, which is the number of connected
components in the distance-type $\tau$. More precisely, we show that the
problem of counting queries with several centered components can be reduced to
the problem of counting local centered queries. Counting local centered
queries is solved by Lemma 9.

######  Lemma 13.

Let $\varphi(\overline{x})$ be an $r$-local query of the form
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$
where all $\alpha_{i}$ are $r$-local centered queries.

There are $r$-local centered queries $\varphi_{1},\ldots,\varphi_{m}$ and an
arithmetic combination $F$ such that for all graph $G$, we have
$\\#\varphi(G)=F\big{(}\\#\varphi_{1}(G),\ldots,\\#\varphi_{m}(G)\big{)}$.
Furthermore, $m=O(2^{pk})$.

The proof of Lemma 13 follows an inclusions-exclusion argument.

######  Proof 4.5 (Proof of Lemma 13).

Let $\varphi(\overline{x})$ be an $r$-local query of the form
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$.
If $p=1$, we are done. If $p>1$. Let
$\overline{w}=(\overline{x}_{2},\ldots,\overline{x}_{p})$. Consider the
following three queries:

$\begin{array}[]{r
l}\varphi_{1}(\overline{x}_{1})&:=\alpha_{1}(\overline{x}_{1}),\\\
\varphi_{2}(\overline{w})&:=\alpha_{2}(\overline{x}_{2})\land\ldots\land\alpha_{p}(\overline{x}_{p})\land\Delta_{2r,\tau^{\prime}}(\overline{w}),\text{where
}\tau^{\prime}\text{ is the restriction of }\tau\text{ to }\overline{w}\\\
\varphi_{3}(\overline{x}_{1},\overline{w})&:=\varphi_{1}(\overline{x}_{1})\wedge\varphi_{2}(\overline{w})\wedge\mathrm{dist}_{\leq
2r}(\overline{x}_{1};\overline{w}).\end{array}$

For all $(\overline{a},\overline{b})\in G^{k}$, we have that:
$G\models\varphi(\overline{a}\overline{b})$ if and only if
$G\models\varphi_{1}(\overline{a})\wedge\varphi_{2}(\overline{b})\wedge\mathrm{dist}_{>2r}(\overline{a};\overline{b})$,
hence
$\varphi(G)=\varphi_{1}(G)\bowtie\varphi_{2}(G)\setminus\\{\overline{a},\overline{b}\in
G~{}|~{}\varphi_{1}(\overline{a})\wedge\varphi_{2}(\overline{b})\wedge\mathrm{dist}_{\leq
2r}(\overline{a},\overline{b})\\}$,
which gives
$\varphi(G)=\varphi_{1}(G)\bowtie\varphi_{2}(G)\setminus\varphi_{3}(G)$.
And since $\varphi_{3}(G)\subseteq\varphi_{1}(G)\bowtie\varphi_{2}(G)$, it
follows that
$\\#\varphi(G)=\\#\varphi_{1}(G)\cdot\\#\varphi_{2}(G)-\\#\varphi_{3}(G)$.

It is easy to see that both $\varphi_{1}$ and $\varphi_{2}$ have strictly less
than $p$ connected components in their distance type (respectively $1$ and
$p-1$) and are $r$-locals. Therefore, the induction hypothesis holds for
$\varphi_{1}$ and $\varphi_{2}$. I.e. $\\#\varphi_{1}(G)$ and
$\\#\varphi_{2}(G)$ are arithmetic combinations of number of solutions for
$r$-local centered queries.

We now turn our attention to $\varphi_{3}$. We say that
$(\overline{x}^{\prime}_{1};\ldots;\overline{x}^{\prime}_{p^{\prime}})\ll(\overline{x}_{1};\ldots;\overline{x}_{p})$
if and only if:

  * •

$(\overline{x}^{\prime}_{1};\ldots;\overline{x}^{\prime}_{p^{\prime}})$ is a
partition of $\overline{x}$ with $p^{\prime}<p$,

  * •

$\overline{x}_{1}\subsetneq\overline{x}^{\prime}_{1}$,

  * •

$\forall 1<j\leq p^{\prime},$ there is a $i>1$ such that
$\overline{x}^{\prime}_{j}=\overline{x}_{i}$.

Basically, $\overline{x}^{\prime}_{1}$ is the collapse of $\overline{x}_{1}$
and at least one of the $\overline{x}_{i}$. The other $\overline{x}_{i}$
remain unaltered. Given ${\cal
I}:=(\overline{x}^{\prime}_{1};\ldots;\overline{x}^{\prime}_{p^{\prime}})$,
for every $j\leq p^{\prime}$, we define:
$\alpha^{\prime}_{j}(\overline{x}^{\prime}_{j})=\bigwedge\limits_{\\{i\leq p\
|\
\overline{x}_{i}\subseteq\overline{x}^{\prime}_{j}\\}}\alpha_{i}(\overline{x}_{i})$.

It follows from those definitions that:

$\varphi_{3}(\overline{x})=\bigvee\limits_{(\overline{x}^{\prime}_{1};\ldots;\overline{x}^{\prime}_{p^{\prime}})\ll(\overline{x}_{1};\ldots;\overline{x}_{p})}\alpha^{\prime}_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha^{\prime}_{p^{\prime}}(\overline{x}^{\prime}_{p^{\prime}})\wedge\Delta_{2r,\tau^{\prime}}(\overline{x}).$

Moreover these disjunctions are strict, hence:

$\\#\varphi_{3}(G)=\sum\limits_{(\overline{x}^{\prime}_{1};\ldots;\overline{x}^{\prime}_{p^{\prime}})\ll(\overline{x}_{1};\ldots;\overline{x}_{p})}\\#\big{(}\alpha^{\prime}_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha^{\prime}_{p^{\prime}}(\overline{x}^{\prime}_{p^{\prime}})\wedge\Delta_{2r,\tau^{\prime}}(\overline{x})\big{)}.$

Since every query involved here has strictly less than $p$ connected
components in its distance type, the induction hypothesis holds. There are at
most $2^{k}$ queries involved. For each of them the induction hypothesis leads
to $2^{k(p-1)}$ queries that are $r$-local centered such that computing the
number of solutions for those queries give us the $\\#\varphi_{3}(G)$.
Therefore the total number of queries built is $O(2^{pk})$.

It is worth mentioning, that Lemma 13 never mentions the degree of the
structure and can be used in other contexts.

##  5 Structure with bounded degree

This section we move to structures of bounded degree and our second
contribution.

######  Theorem 14.

There is an algorithm that, upon input of integers $d,\ell$ and a graph $G$ of
degree bounded by $d$ with $n:=|G|$, computes a data structure that:

  * •

can be computed in time $n\cdot 2^{d^{2^{O(\ell)}}}$,

  * •

can be recomputed in time $2^{d^{2^{O(\ell)}}}$ when $G$ is subject to a local
update,

  * •

enables us to test in time $2^{d^{2^{O(|\phi|+\ell)}}}$ whether $G\models\phi$
for any FO sentences $\phi$ of quantifier rank at most $\ell$.

######  Theorem 15.

There is an algorithm that, upon input of integers $d,\ell$ and a graph $G$ of
degree bounded by $d$ with $n:=|G|$, computes a data structure that:

  * •

can be computed in time $n\cdot 2^{d^{2^{O(\ell)}}}$, and

  * •

can be recomputed in time $2^{d^{2^{O(\ell)}}}$ when $G$ is subject to a local
update.

  * •

Furthermore, upon input of a $k$-ary query $\varphi(\overline{x})$ of
quantifier rank $q$ with $k+q\leq\ell$, after a further preprocessing in time
$2^{d^{2^{O(|\phi|+\ell)}}}$, the data structure enables us:

    1. 1.

(enum:) to enumerate with delay $O(k^{3})$ the set $\varphi(G)$,

    2. 2.

(test:) upon input of a $k$-tuple $\overline{a}$, to test in time $O(k^{2})$
whether $G\models\varphi(\overline{a})$, and

    3. 3.

(count:) to compute in time $O(1)$ the number $|\varphi(G)|$ of solutions for
$\varphi$ over $G$.

###  5.1 Basic data structure

Similarly to Section 4 we start with centered queries. We describe what we
call the basic data structure ($BDS$). Informally, the basic data structure
contains all possible graphs of bounded degree and bounded radius and some
mappings between all these small graphs and our larger structure.

More formally, the data structure is defined for two integers $d,\ell$, and a
graph $G=(V,E)$ of degree at most $d$. The basic data structure is composed of
the following elements:

  * •

The set $\mathcal{H}$ of every (up to isomorphism) graph $H$ of degree bounded
by $d$, one marked node $c^{H}$, and radius at most $r\ell$ around $c^{H}$,
where $r=2^{O(\ell)}$.

  * •

A function $\mathcal{X}(\cdot)$ that associates each $a\in V$ to the only
$H\in\mathcal{H}$ such that there is an isomorphism from
$\mathcal{N}_{r\ell}^{G}(a)$ to $H$ that maps $a$ to $c^{H}$.

  * •

For all $H\in\mathcal{H}$, the list $L_{H}$ of all $a\in V$ such that
$\mathcal{X}(a)=H$.

  * •

For all $H\in\mathcal{H}$, the number $\\#L_{H}$ that is the size of $L_{H}$.

  * •

For every $a$ in $V$, we fix an isomorphism $f_{a}(\cdot)$ from
$\mathcal{N}_{r\ell}^{G}(a)$ to $H$ (that maps $a$ to $c^{H}$).

This ends the description of the basic data structure $BDS(d,\ell,G)$.

Note that an element $a$ in $G$ appears in only one of the $L_{H}$.

######  Lemma 16.

Let $d,\ell$ in $\mathbb{N}_{\scriptstyle\geq 1}$ and a graph $G$ of degree
bounded by $d$. We can:

  * •

compute $BDS(d,\ell,G)$ in time $O(|G|)$, and

  * •

update $BDS(d,\ell,G)$ into $BDS(d,\ell,G^{\prime})$ when a local update
changes $G$ into $G^{\prime}$ in time $O(1)$.

Here again, the $O(\cdot)$ hide constant factors that depend on $d$ and
$\ell$. Similarly to other proofs of this paper, we do not prove the first
item of Lemma 16 as it is enough to apply the update procedure from the empty
graph to the desired one by adding all vertices and all edges one by one.

######  Proof 5.1 (Proof of Item 2 of Lemma 16).

Let $d,\ell,G$ and $BDS(d,\ell,G)$. Let $G^{\prime}$ be the update of $G$, let
$r=2^{O(\ell)}$ given by Corollary 6 and let $L_{u}$ be the list of
$r\ell$-impacted nodes.

For all $a$ in $L_{u}$, we perform the following procedure:

  * •

Let $H=\mathcal{X}(a)$.

  * •

Remove $a$ from $L_{H}$ and put $\\#L_{H}:=\\#L_{H}-1$.

  * •

Compute $\mathcal{N}_{r\ell}^{G^{\prime}}(a)$ by performing a simple breadth-
first search in $G^{\prime}$ starting from $a$.

  * •

Scan through $\mathcal{H}$ to find $H^{\prime}$ such that
$\mathcal{N}_{r\ell}^{G^{\prime}}(a)\simeq H^{\prime}$ (with $a$ mapped to
$c^{H^{\prime}}$).

  * •

Set $\mathcal{X}(a):=H^{\prime}$.

  * •

Compute an isomorphism $f_{a}(\cdot)$ from
$\mathcal{N}_{r\ell}^{G^{\prime}}(a)$ to $H^{\prime}$ (with $a$ mapped to
$c^{H^{\prime}}$).

  * •

Set $\\#L_{H^{\prime}}\leftarrow\\#L_{H^{\prime}}+1$ and add $a$ into
$L_{H^{\prime}}$.

This computes what we need. Let us now look closely at the complexity of this
algorithm. By Lemma 1 $L_{u}$ has size $O(d^{\,r\ell})$ and can be computed in
time $O(d^{\,r\ell})$. For each $a$ in $L_{u}$, step (1), (2), (5) and (7) can
be performed in time $O(1)$ with our computational model. Step (3) can be
performed in time $O(d^{r\ell})$. Step (6) can be performed in time
$O(2^{d^{r\ell}})=2^{d^{2^{O(\ell)}}}$. For step (4), the number of elements
in $\mathcal{H}$ is bounded by $O(2^{(d^{r\ell})^{2}})$. For each we perform a
test similar to the one in Step (6), leading again to a total complexity of
$2^{d^{2^{O(\ell)}}}$.

We now turn to the application of the Basic Data structure.

###  5.2 The model checking problem

In this section we prove Theorem 14. The data structure is almost the one
defined in Section 5.1.

Let $d,\ell$ be two integers, and $G$ a graph of degree $d$. Assume that
$BDS(G,d,\ell)$ has been computed. We are now given an $FO$ sentence $\phi$ of
quantifier rank at most $\ell$. By Theorem 4, $\phi$ is equivalent to a
boolean combination of sentences of the form:

$\exists x_{1}\ldots x_{s}~{}\Big{(}\underset{1\leq i\leq j\leq
s}{\bigwedge}~{}\mathrm{dist}_{>2r}(x_{i},x_{j})\wedge\underset{1\leq i\leq
s}{\bigwedge}\alpha(x_{i})\Big{)}$

where $\alpha$ is an $r$ local query and $r=2^{O(\ell)}$. We show how to test
whether $G\models\varphi$ for sentences of the form above.

  * •

The first thing we do is to compute $\\#\alpha(G)$ that is the number of
elements of $G$ satisfying $\alpha$. Note that $G\models\alpha(a)$ if and only
if $\mathcal{N}_{r\ell}^{G}(a)\models\alpha(a)$ and therefore if and only if
$H\models\alpha(c^{H})$, where $H=\mathcal{X}(a)$ i.e. the graph isomorphic to
$\mathcal{N}_{r\ell}^{G}(a)$.

Hence we have that $\\#\alpha(G)=\sum\limits_{\\{H\in\mathcal{H}\ |\
H\models\alpha(c^{H})\\}}\\#L_{H}$. Thus we test for every $H$ in
$\mathcal{H}$ whether $H\models\alpha(c^{H})$, and if so, we add $\\#L_{H}$ to
the total.

  * •

Once $\\#\alpha(G)$ has been computed we consider two cases:

    * –

If $\\#\alpha(G)>k\cdot d^{2r}$, there must be $k$ elements satisfying
$\alpha(x)$ at distance greater than $2r$ from each other. We can therefore
assert that $G\models\varphi$.

    * –

If $\\#\alpha(G)\leq k\cdot d^{2r}$, we compute the list $\alpha(G)$ of all
elements satisfying $\alpha(x)$. Similarly to the first phase, we have that
$\alpha(G)=\bigcup\limits_{\\{H\in\mathcal{H}\ |\
H\models\alpha(c^{H})\\}}L_{H}$.

We then define $\bm{\tilde{}}{G}:=\bigcup\limits_{a\in\alpha(G)}N_{r}^{G}(a)$.
We have that $G\models\varphi$ if and only if
$\bm{\tilde{}}{G}\models\varphi$. We then use any naive algorithm to test
whether $\bm{\tilde{}}{G}\models\varphi$.

This completes the answering phase. Let us now look at the complexity of this
procedure. The number of graphs in $\mathcal{H}$ and their sizes is a function
of $d$ and $\ell$ and is independent of $|G|$. Therefore computing
$\\#\alpha(G)$ only took time $O(1)$.

More precisely, there are $O\left(2^{(d^{r\ell})^{2}}\right)$ elements in
$\mathcal{H}$ each of size $O(d^{r\ell})$. Testing whether a given $H$ models
$\alpha(c^{H})$ can therefore be performed in time
$O\left(2^{d^{r\ell}}\right)$. The overall complexity of the first phase is
therefore $2^{d^{2^{O(\ell)}}}$.

During the second phase, the first case is just a test that can be performed
in time $O(1)$. In the second case, we have that
$|\bm{\tilde{}}{G}|\leq\\#\alpha(G)\cdot d^{r}$. Since $\\#\alpha(G)\leq
k\cdot d^{2r}$, we have that $|\bm{\tilde{}}{G}|\leq k\cdot d^{3r}$. We then
check whether $\bm{\tilde{}}{G}\models\varphi$ in time
$O\big{(}|\bm{\tilde{}}{G}|^{|\varphi|}\big{)}$.

Hence the total time of the second phase $O\big{(}(k\cdot
d^{3r})^{|\phi|}\big{)}=2^{d^{2^{O(|\phi|+\ell)}}}$

###  5.3 The enumeration problem

This section is devoted to the enumerating part of Theorem 15. First we show
that the Basic Data Structure is enough if we allow the delay to depend on
both the degree $d$ and the radius $r$. In Appendix B.2, we show that
similarly to [6, Theorem 9.2] we can make the delay be $O(k^{3})$.

The first algorithm only uses the Basic Data Structure and works by induction
on the number $k$ of free variables in $\varphi$. The global proof is a
combination of these two lemmas.

######  Lemma 17.

For every fixed $G,d,\ell$, once $BDS(G,d,\ell)$ is computed, then for any
unary FO query $\varphi(x)$ of quantifier rank $q$ such that $q<\ell$, without
additional preprocessing, we can enumerate the set $\varphi(G)$ with constant
delay (depending on $d$ and $\ell$).

######  Lemma 18.

For every fixed $G,d,\ell$, once $BDS(G,d,\ell)$ is computed, for every
$k$-ary FO query $\varphi(\overline{x})$ and quantifier rank $q$ such that
$k+q\leq\ell$, without additional preprocessing and for every $k-1$ tuple
$(a_{1},\ldots a_{k-1})$, we can enumerate the set of all $b$ in $G$ such that
$G\models\varphi(a_{1},\ldots,a_{k-1},b)$ with constant delay (depending only
on $d$ and $\ell$).

The following induction on $k$ explains why these two lemmas are enough. Fix
$G,d,\ell$ and assume that $BDS(G,d,\ell)$ has been computed. We are now given
an FO query $\varphi(\overline{x})$ of arity $k$ and quantifier rank $q$ such
that $k+q\leq\ell$. If $k=1$, Lemma 17 explains how to enumerate the
solutions. If $k>1$, we define
$\varphi^{\prime}(x_{1},\ldots,x_{k-1}):=\exists
y\varphi(x_{1},\ldots,x_{k-1},y)$. Note that $\varphi^{\prime}$ has quantifier
rank $q+1$ but arity $k-1$. Therefore by induction we can enumerate without
further preprocessing the set $\varphi^{\prime}(G)$. For each tuple
$(a_{1},\ldots,a_{k-1})$ produced by this procedure, we apply Lemma 18 to
complete this tuple into a solution for $\varphi$.

It is critical to see that every tuple in $\varphi^{\prime}(G)$ can be
completed into a solution for $\varphi$. Otherwise, we might encounter a lot
of consecutive solutions for which the algorithm of Lemma 18 would produce the
empty set, making the delay not constant.

It only remains to prove the two lemmas. Here we only provide a sketch of
those proofs, the complete ones are in the appendix, Section B.1.

Proof sketch of Lemma 17. Once $BDS(G,d,\ell)$ has been computed, the list
$\varphi(G)$ for a unary query $\varphi$ is just a concatenation of lists
$L_{H}$ from the Basic Data Structure.

Proof sketch of Lemma 18. The algorithm distinguishes two cases. If $b$ must
be at distance less than $2r$ to one of the $a\in\overline{a}$, there is only
a constant number of possible $b$. If $b$ must be at distance greater than
$2r$ from $\overline{a}$, then all $b$ that satisfies some local condition
(not depending on $\overline{a}$) are solution except those that are close to
$\overline{a}$. Since they are only a constant number of $b$ close to
$\overline{a}$, even if we encounter all of them in a row, the delay remains
bounded by a constant (depending on $d$ and $r$).

###  5.4 The testing problem

In this section we prove the testing part of Theorem 15. Similarly to Section
5.2, we show that the basic data structure is enough for completing this task.

#### Naive algorithm

Let $\varphi(\overline{x})$ be an $FO$ query of arity $k$ and quantifier rank
$q$ with $k+q\leq\ell$.

By Corollary 6, $\varphi$ is equivalent to a boolean combination of sentences
of the form of Equation 1 and $r$-local queries where $r=2^{O(\ell)}$.

Since the sentences can be evaluated using Theorem 14, we are only left with
$r$-local queries. It turns out that over structures with bounded degree,
local queries can always be tested in constant time because for every
$r$-local queries $\varphi(\overline{x})$ and every tuple $\overline{a}$ in
$G$:

$G\models\varphi(\overline{a})\quad\text{ if and only if
}\quad\mathcal{N}_{r}^{G}(\overline{a})\models\varphi(\overline{a})$

We can compute $\mathcal{N}_{r}^{G}(\overline{a})$ in constant time and then
test whether any $r$-local query holds in constant time (with constant factors
depending on $r$ and $\ell$).

#### Faster algorithm

In [6, Theorem 6.1] it is shown, that the testing procedure can be performed
in time $O(k^{2})$ where $k$ is the arity of the query. One can split the
answering phase in two, the query is given first and the tuple latter. We can
enrich the data structure to match the complexity of [6].

######  Lemma 19.

For every fixed integers $d$, $\ell$ in $\mathbb{N}_{\scriptstyle\geq 1}$
there is an algorithm that, upon input of a graph $G$ of degree bounded by
$d$, computes a data structure that:

  * •

can be computed in time $|G|\cdot 2^{d^{2^{O(\ell)}}}$, and

  * •

can be recomputed in time $2^{d^{2^{O(\ell)}}}$ when $G$ is subject to a local
update.

Furthermore, upon input of a $k$-ary query $\varphi(\overline{x})$ of
quantifier rank $q$ with $k+q\leq\ell$, the data structure allows to perform a
final task in time triply exponential in $\varphi$ such that afterward upon
input of a $k$-tuple $\overline{a}$, to test in time $O(k^{2})$ whether
$G\models\varphi(\overline{a})$

The proof of Lemma 19 is in Appendix B.3.

###  5.5 The counting problem

Here we prove the counting part of Theorem 15. Again we show that the basic
data structure is enough for completing this task. Let $(G,d,\ell)$ fixed. Let
$r=2^{O(\ell)}$, and assume that $BDS(G,d,\ell)$ has been computed.

Let $\varphi(\overline{x})$ be an $FO$ query of arity $k$ and quantifier rank
$q$ with $k+q\leq\ell$.

By Corollary 6, $\varphi$ is equivalent to a boolean combination of sentences
of the form of Equation 1 and $r$-local queries. Furthermore, once all
sentences have been evaluated, we are left with a strict disjunction of
queries of the form:
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$
where $\alpha_{i}(\overline{x}_{i})$ are $r$-local centered queries. We
therefore only prove how to count the solutions for a query of the form above,
the total number can be obtained by summing the different results.

In the upcoming Lemma 20, we show that the Basic Data Structure is enough when
$p=1$. The general case is then solved by Lemma 13 that state that when $p>1$
the number of solutions is an arithmetical combination of the number of
solutions for at most $2^{pk}$ new $r_{q}$-local centered queries (centered
meaning that $p=1$).

######  Lemma 20.

For every fixed $(G,d,\ell)$, once $BDS(G,d,\ell)$ is computed. For any
$r$-local centered query $\alpha(\overline{x})$ with $k$ free variables and
quantifier rank $q$ (with $k+q\leq\ell$), the number $\\#\varphi(G)$ can be
computed in time $2^{d^{2^{O(\ell)}}}$.

######  Proof 5.2.

Let $x_{1}$ be the first element of $\overline{x}$. For all tuple
$\overline{a}$, we have that $G\models\alpha(\overline{a})$ if and only if
$H\models\alpha(f_{a_{1}}(\overline{a}))$. Where $H=\mathcal{X}(a_{1})$ is the
graph isomorphic to $\mathcal{N}^{G}_{r_{\ell}}(a_{1})$ and $f_{a_{1}}(\cdot)$
is the isomorphism from $\mathcal{N}^{G}_{r}(a_{1})$ to $H$. Remember that
given a graph $H$ in $\mathcal{H}$, we have access to the list $L_{H}$ of all
$a$ in $G$ such that $\mathcal{X}(a)=H$ and to $\\#L_{H}$, the size of this
list.

For all $H$ in $\mathcal{H}$ we compute $\\#\alpha(H,c^{H})$ that is the
number of $k$-tuple $\overline{a}$ in $H$ with $a_{1}=c^{H}$ such that
$H\models\alpha(\overline{a})$. We obtain that:
$\\#\alpha(G)=\sum\limits_{H\in\mathcal{H}}\big{(}\\#\alpha(H,c^{H})\cdot\\#L_{H}\big{)}.$

This ends the proof of Lemma 20. The time needed for this final phase is
triply exponential in $\ell$ because there are only $2^{d^{O(r\ell)}}$ graphs
in $\mathcal{H}$, and for a fixed $H$, the number $\\#\varphi(H,c^{H})$ can be
computed in time $2^{d^{O(r\ell)}}$.

##  6 Conclusion

We proved that over structures with bounded or low degree and for every first-
order query, we can efficiently compute and recompute a data structure
allowing to answer in constant time (or with constant delay) the model-
checking, testing, counting and enumeration problems. It was already known for
classes of graphs with bounded degree [6] but not for classes of graph with
low degree.

In the case of structure with bounded degree we showed that, without
increasing the preprocessing time, we can compute a data structure that does
not depend on the query but only on its quantifier rank. We can therefore
compute a single preprocessing that can later be used for a variety of
queries.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [2] Antoine Amarilli, Pierre Bourhis, and Stefan Mengel.  Enumeration on trees under relabelings.  In Intl. Conf. on Database Theory (ICDT), 2018.
  * [3] Guillaume Bagan.  MSO queries on tree decomposable structures are computable with linear delay.  In Conf. on Computer Science Logic (CSL), 2006.
  * [4] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Conf. on Computer Science Logic (CSL), 2007.
  * [5] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In Symp. on Principles of Database Systems (PODS), 2017.
  * [6] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering FO+MOD queries under updates on bounded degree databases.  ACM Trans. Database Syst., 43(2):7:1–7:32, 2018.
  * [7] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering UCQs under updates and in the presence of integrity constraints.  In Intl. Conf. on Database Theory (ICDT), 2018.
  * [8] Christoph Berkholz and Nicole Schweikardt.  Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width.  In Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), 2019.
  * [9] Nofar Carmeli and Markus Kröll.  On the enumeration complexity of unions of conjunctive queries.  In Symp. on Principles of Database Systems (PODS), 2019.
  * [10] Arnaud Durand and Etienne Grandjean.  First-order queries on structures of bounded degree are computable with constant delay.  ACM Trans. Comput. Log., page 21, 2007.
  * [11] Arnaud Durand, Nicole Schweikardt, and Luc Segoufin.  Enumerating answers to first-order queries over databases of low degree.  In Symp. on Principles of Database Systems (PODS), 2014.
  * [12] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Springer, 2006.
  * [13] Haim Gaifman.  On local and non-local properties.  In Proceedings of the Herbrand Symposium. 1982.
  * [14] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  J. ACM, pages 17:1–17:32, 2017.
  * [15] Martin Grohe and Nicole Schweikardt.  First-order query evaluation with cardinality conditions.  In Symp. on Principles of Database Systems (PODS), 2018.
  * [16] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang.  Trade-offs in static and dynamic evaluation of hierarchical queries.  In Symp. on Principles of Database Systems (PODS), 2020.
  * [17] Wojciech Kazana and Luc Segoufin.  First-order query evaluation on structures of bounded degree.  Logical Methods in Computer Science, 2011.
  * [18] Wojciech Kazana and Luc Segoufin.  Enumeration of first-order queries on classes of structures with bounded expansion.  In Symp. on Principles of Database Systems (PODS), 2013.
  * [19] Wojciech Kazana and Luc Segoufin.  Enumeration of monadic second-order queries on trees.  ACM Trans. Comput. Log., 2013.
  * [20] Leonid Libkin.  Elements of Finite Model Theory.  Springer, 2004.
  * [21] Katja Losemann and Wim Martens.  MSO queries on trees: enumerating answers under updates.  In Conf. on Computer Science Logic & Symp. on Logic in Computer Science (CSL-LICS), 2014.
  * [22] Bernard ME Moret and Henry D Shapiro.  Algorithms from P to NP (vol. 1): Design and Efficiency.  Benjamin-Cummings Publishing Co., 1991.
  * [23] Matthias Niewerth and Luc Segoufin.  Enumeration of MSO queries on strings with constant delay and logarithmic updates.  In Symp. on Principles of Database Systems (PODS), 2018.
  * [24] Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny.  Enumeration for FO queries over nowhere dense graphs.  In Symp. on Principles of Database Systems (PODS), 2018.
  * [25] Luc Segoufin and Alexandre Vigny.  Constant delay enumeration for FO queries over databases with local bounded expansion.  In Intl. Conf. on Database Theory (ICDT), 2017.
  * [26] Szymon Torunczyk.  Aggregate queries on sparse databases.  In Symp. on Principles of Database Systems (PODS), 2020.
  * [27] Alexandre Vigny.  Query enumeration and nowhere dense graphs. (Énumération des requêtes et graphes nulle-part denses).  PhD thesis, Paris Diderot University, France, 2018.

##  Appendix A Appendix for Section 4

###  A.1 Complement for the enumeration: Skip elements of a list

In this section we prove Lemma 12, reformulated as follow:

######  Lemma 21 (Skip pointers).

For every graph $G$ with $n:=|G|$, every $r,k$ and $m$ in $\mathbb{N}$, and
every list of $r$-centered tuples $L\subseteq V^{m}$, there is a data
structure, computable in time $O\big{(}|L|\cdot d(G)^{kr}\big{)}$ and
recomputable in time $O(d(G)^{(krm)^{2}})$ allowing us, when given a tuple
$\overline{b}$ in $L$ and a set $I$ of at most $k$ elements of $G$, to compute
in constant time the tuple ${\textup{SKIP}}(\overline{b},I)$ that is the next
tuple $\overline{b}^{\prime}$ of $L$ that satisfies $\overline{b}^{\prime}\cap
N^{G}_{r}(I)=\emptyset$.

Note that for classes of graphs with low degree, the complexity above become
$O(|L|\cdot n^{\epsilon})$ for the preprocessing and $O(n^{\epsilon})$ for the
update. Similarly, for classes graphs with bounded degree, it becomes $O(|L|)$
and $O(1)$ (with constants factors at most doubly exponential in $r$).

######  Proof A.1.

From now on we fix $r,k,m$, $G$, and $L$ as in the statement of the lemma and
let $d$ be the degree of $G$.

The domain of the ${\textup{SKIP}}(\cdot,\cdot)$-function is too big so we
cannot compute it during the preprocessing phase. Fortunately, computing only
a small part of it will be good enough for our needs. For each tuple
$\overline{b}$ of $L$, we define by induction a set
$\textit{SC}(\overline{b})$ of sets of at most $k$ elements. We start with
$\textit{SC}(\overline{b})=\emptyset$ and then proceed as follows.

  * •

For all tuple $\overline{b}$ of $L$ and for all element $a$ in $G$ with
$\mathrm{dist}_{\leq r}(a;\overline{b})$, we add $\\{a\\}$ to
$\textit{SC}(\overline{b})$.

  * •

For all nodes $\overline{b}$ of $L$, for all sets $I$ of elements from $G$,
and all element $a$ of $G$, if $|I|<k$ and $I\in\textit{SC}(\overline{b})$ and
${\textup{SKIP}}(\overline{b},I)\cap N^{G}_{r}(a)\neq\emptyset$, then we add
$\\{I\cup\\{a\\}\\}$ to $\textit{SC}(\overline{b})$.

In the preprocessing phase we will compute ${\textup{SKIP}}(\overline{b},I)$
for all tuples $\overline{b}$ of $L$ and all sets
$I\in\textit{SC}(\overline{b})$. Before explaining how this can be
accomplished within the desired time constraints, we first show that this is
sufficient for deriving ${\textup{SKIP}}(\overline{b},I)$ in constant time for
all tuples $\overline{b}$ and all sets $I$ consisting of at most $k$ elements
of $G$.

######  Claim 22.

Given a tuple $\overline{b}$ of $L$, a set $I$ of at most $k$ elements of $G$,
and ${\textup{SKIP}}(\overline{c},J)$ for all tuples $\overline{c}$ that are
after $\overline{b}$ in $L$ and all sets $J\in\textit{SC}(\overline{c})$, we
can compute ${\textup{SKIP}}(\overline{b},I)$ in constant time.

######  Proof A.2.

If $\overline{b}$ is the last tuple of $L$ then either
${\textup{SKIP}}(\overline{b},I)=\overline{b}$ or
${\textup{SKIP}}(\overline{b},I)=\textsf{Null}$. Otherwise let
$\overline{b}^{\prime}$ be the tuple following $\overline{b}$ in $L$. We
consider two cases (testing in which case we fall can be done in constant
time).
_Case $1$:_ $\overline{b}^{\prime}\cap N^{G}_{r}(I)=\emptyset$. In this case,
$\overline{b}^{\prime}$ is ${\textup{SKIP}}(\overline{b},I)$ and we are done.

_Case $2$:_ $\overline{b}^{\prime}\cap N^{G}_{r}(I)\neq\emptyset$. So there is
an $a\in I$ such that $\overline{b}^{\prime}\cap N^{G}_{r}(a)\neq\emptyset$
Let $J$ be a maximal (w.r.t. inclusion) subset of $I$ in
$\textit{SC}(\overline{b}^{\prime})$. Since
$\\{a\\}\in\textit{SC}(\overline{b}^{\prime})$, we know that $J$ is non-empty.

We claim that
${\textup{SKIP}}(\overline{b}^{\prime},J)={\textup{SKIP}}(\overline{b},I)$. To
prove this, let us first assume for contradiction that
${\textup{SKIP}}(\overline{b}^{\prime},J)\cap N_{r}^{G}(a)\neq\emptyset$ for
some $a\in I$. By definition, this implies that $a$ is not in $J$. Hence
$|J|<|I|\leq k$. Thus, by definition of $\textit{SC}(\overline{b}^{\prime})$
we have $J\cup\\{a\\}\in\textit{SC}(\overline{b}^{\prime})$ and $J$ was not
maximal.

Moreover, by definition of ${\textup{SKIP}}(\overline{b}^{\prime},J)$, every
tuples in $L$ between $\overline{b}^{\prime}$ and
${\textup{SKIP}}(\overline{b}^{\prime},J)$ intersect $N^{G}_{r}(a^{\prime})$
for some $a^{\prime}$ in $J$ (and therefore $a^{\prime}$ in $I$). The claim
follows.

We now show that $\textit{SC}(\overline{b})$ is small for all tuple
$\overline{b}$ of $L$ and that we can compute efficiently
${\textup{SKIP}}(\overline{b},I)$ for all tuple $\overline{b}$ and all sets
$I\in\textit{SC}(\overline{b})$.

######  Claim 23.

For each tuple $\overline{b}$ of $L$, $|\textit{SC}(\overline{b})|$ has size
$O\big{(}(m\cdot d(G)^{r})^{k}\big{)}$. Moreover, it is possible to compute
${\textup{SKIP}}(\overline{b},I)$ for all tuples $\overline{b}$ of $L$ and all
sets $I\in\textit{SC}(\overline{b})$ in time $O\big{(}|L|\cdot(m\cdot
d(G)^{r})^{k}\big{)}$.

Remember that $m$ is the length of the tuples that are in $L$.

######  Proof A.3.

We start by proving the first statement, and afterwards we use Claim 22 to
show that we can compute these pointers inductively.

By $\textit{SC}_{p}(\overline{b})$ we denote the subset of
$\textit{SC}(\overline{b})$ of sets $I$ with $|I|\leq p$. We know that
$|\textit{SC}_{1}(\overline{b})|\leq m\cdot d(G)^{r}$ for all tuples
$\overline{b}$ of $L$. For the same reason, we have that
$|\textit{SC}_{p+1}(\overline{b})|$ is of size at most $O(m\cdot
d(G)^{r}\cdot|\textit{SC}_{p}(\overline{b})|)$. Therefore, for all
$\overline{b}\in L$, we have:

$|\textit{SC}(\overline{b})|\ \ =\ \ |\textit{SC}_{k}(\overline{b})|\ \ \leq\
\ O\big{(}(m\cdot d(G)^{r})^{k}\big{)}.$

We compute the pointers for $\overline{b}$ from $\overline{b}_{\textit{last}}$
to $\overline{b}_{\textit{first}}$, where $\overline{b}_{\textit{last}}$ and
$\overline{b}_{\textit{first}}$ are respectively the last and first tuples of
$L$. Given a tuple $\overline{b}$ in $L$, assume we have computed
${\textup{SKIP}}(\overline{c},J)$ for all $\overline{c}$ after $\overline{b}$
in $L$ for all $J\in\textit{SC}(\overline{c})$. We then compute
${\textup{SKIP}}(\overline{b},I)$ for $I\in\textit{SC}(\overline{b})$ using
Claim 22.

At each step the pointer is computed in constant time. Since there are
$O\big{(}|L|(kd(G))^{kr}\big{)}$ of them, the time required to compute them is
as desired.

So far we have not use the fact that $L$ only contains $r$-centered tuples. It
is indeed only use for the update procedure. The key observation is that
${\textup{SKIP}}(\overline{b},I)$ cannot be arbitrary far from $\overline{b}$
in the list.

######  Claim 24.

When a tuple $\overline{b}$ is added to or removed from the list $L$, for
every tuple $\overline{c}$ in $L$ that is not among the $\big{(}k\cdot
d(G)^{3mr}\big{)}^{m}$ tuples that directly precede (or was preceding)
$\overline{b}$, we have that: $\textit{SC}(\overline{c})$ and
${\textup{SKIP}}(\overline{c},I)$ for every $I\in\textit{SC}(\overline{c})$ is
unaffected by the addition or deletion of $\overline{b}$.

If a tuples or arity $m$ is $r$-centered then it is included in the $2mr$
neighborhood of any of it’s element. Therefore, there are at most
$\Delta=\big{(}kd(G)^{3mr}\big{)}^{m}$ possible $r$-centered tuples of arity
$m$ that intersect the $r$ neighborhood of $I$.

When we remove or add a tuples $\overline{b}$ in $L$, we only have to
recompute the skip pointers of the $\Delta$ elements that are just before
$\overline{b}$ in $L$. Which can be done in total time $O(d(G)^{(krm)^{2}})$.

The combination of these three claims proves Lemma 21.

##  Appendix B Appendix for Section 5

###  B.1 Simple enumeration algorithm

In this section we formally prove Lemmas 17 and 18.

######  Proof B.1 (Proof of Lemma 17).

Let $(G,d,\ell)$ fixed and assume that $BDS(G,d,\ell)$ has been computed. Let
$\varphi(x)$ be a unary FO query of quantifier rank $q$ such that $q<\ell$. By
Corollary 6, $\varphi$ is equivalent to a boolean combination of sentences of
the form of Equation 1 (for $r=r_{q}$) and $r_{q}$-local queries. We then do
the following:

  * •

First, for every sentence of the decomposition, test their truth value on $G$.

  * •

Let $\alpha(x)$ be the boolean combination of the remaining $r_{q}$-local
queries.

  * •

For an element $a$ we have that $G\models\alpha(a)$ if and only if
$\mathcal{X}(a)\models\alpha(c^{H})$.
Therefore we have that $\\{a\in G\ |\
G\models\alpha(a)\\}=\bigcup\limits_{\\{H\in\mathcal{H}\ |\
H\models\alpha(c^{H})\\}}L_{H}$.

  * •

We select then all $H$ in $\mathcal{H}$ such that $H\models\alpha(c^{H})$ and
$\\#L_{H}>0$.

  * •

Finally, we run through the lists $L_{H}$ of all selected $H$ from the
previous step.

This ends the proof of Lemma 17. For the complexity analysis, the firsts four
items require a total time triply exponential in $|\varphi|$. Once this is
done the delay is truly $O(1)$ as we just read lists.

######  Proof B.2 (Proof of Lemma 18).

Let $(G,d,\ell)$ fixed and assume that $BDS(G,d,\ell)$ has been computed. Let
$\varphi(\overline{x},y)$ be an FO query of quantifier rank $q$ and arity $k$
such that $k+q\leq\ell$. By Corollary 6, $\varphi$ is equivalent to a boolean
combination of sentences of the form of Equation 1 (for $r=r_{q}$) and
$r_{q}$-local queries. We are then given a tuple
$\overline{a}=(a_{1},\ldots,a_{k-1})$ and we want to enumerate all $b$ such
that $(\overline{a},b)\in\varphi(G)$.

  * •

First, for every sentence of the decomposition, test their truth value on $G$.

  * •

We are left with a strict disjunction of queries of the form
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p},y)\wedge\tau_{2r_{q}}(\overline{x}_{1};\ldots;\overline{x}_{p})$
where all $\alpha_{i}(\overline{x}_{i})$ are $r_{q}$-locals (we can assume
without loss of generality that $y$ appears on $\alpha_{p}$). We enumerate the
appropriate $b$ for each query from the disjunction one by one.

  * •

We now have a tuple $\overline{a}=\overline{a}_{1},\ldots,\overline{a}_{p}$
and a query
$\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p},y)\wedge\tau_{2r_{q}}(\overline{x}_{1};\ldots;(\overline{x}_{p},y))$.
We check whether
$G\models\tau_{2r_{q}}(\overline{x}_{1};\ldots;\overline{x}_{p-1})$ and
$G\models\alpha_{i}(\overline{a}_{i})$ for all $i<p$. If this is not the case,
we can safely enumerate the empty set.

  * •

It remains to enumerate all $b$ such that
$G\models\alpha_{p}(\overline{a}_{p},b)$ and $\mathrm{dist}(a_{i},b)>2r_{q}$
for all $a_{i}\not\in\overline{a}_{p}$. We distinguish two cases whether
$\overline{a}_{p}=\emptyset$.

    * –

Case $1$, $\overline{a}_{p}\neq\emptyset$. Let $a_{j}$ be an element of
$\overline{a}_{p}$. All matching $b$ must be in
$\mathcal{N}^{G}_{kr_{q}}(a_{j})$ and therefore
$G\models(\alpha_{p}(\overline{a}_{p},b))$ if and only if
$\mathcal{N}^{G}_{r_{\ell}}(a_{j})\models(\alpha_{p}(\overline{a}_{p},b))$. We
can therefore look at all the elements of $N^{G}_{2kr_{q}}(a_{j})$ (there are
only $d^{2kr_{q}}$), and for each test whether
$G\models\alpha_{p}(\overline{a}_{p},b)$ and $\mathrm{dist}(a_{i},b)>2r_{q}$
for all $a_{i}\not\in\overline{a}_{p}$.

We can produce the list of these elements in time $O(2^{d^{r_{\ell}}})$ and
then enumerate the list.

    * –

Case $2$, $\overline{a}_{p}=\emptyset$. In this case, we run through the list
of all $b$ such that $G\models\alpha_{p}(b)$. For each such $b$, we test in
constant time whether it is at distance greater than $2r_{q}$ to
$\overline{a}$. If so we output it, otherwise we go to the next element of the
list. We now explain how to run through all $b$ such that
$G\models\alpha_{p}(b)$ and why this procedure as constant delay.

To compute the list of all $b$ such that $G\models\alpha_{p}(b)$, it is enough
to see that $G\models\alpha_{p}(b)$ if and only if $H\models\alpha_{p}(c^{H})$
where $H=\mathcal{X}(a)$. Therefore we have that:

$\\{b\in G\ |\
G\models\alpha_{p}(b)\\}~{}=~{}\bigcup\limits_{\\{H\in\mathcal{H}\ |\
H\models\alpha_{p}(c^{H})\\}}L_{H}$

We can test in time in constant time whether a graph $H$ satisfies the
condition and there is only a constant number of them. Hence in constant time
(triply exponential in $\ell$), we can run through all $b$ such that
$G\models\alpha_{p}(b)$.

For the constant delay, it is enough to see that testing whether $b$ is at
distance greater than $2r_{q}$ from $\overline{a}$ can be performed in
constant time, more precisely $O(kd^{2r_{q}})$. Furthermore at most $k\cdot
d^{2r_{q}}$ element are at distance less than $2r_{q}$ to $\overline{a}$ and
will not be enumerated. This makes the delay constant, i.e. only triply
exponential in $\ell$.

This ends the proof of Lemma 18.

###  B.2 Fast enumeration algorithm

In this section we explain how to improve the data structure for the
enumeration part of Theorem 15. Ideally, we would like the delay to be
independent from the degree of the graph.

######  Theorem 25.

Let $d,\ell$ in $\mathbb{N}_{\scriptstyle\geq 1}$ and a graph $G$ of degree
bounded by $d$. There is a data structure that:

  * •

can be computed in time $O(|G|)$,

  * •

can be recomputed in constant time (triply exponential in $\ell$) when $G$ is
subject to a local update, and

  * •

upon a query $\varphi(\overline{x})$ of arity $k$ and quantifier rank $q$ with
$k+q\leq\ell$ perform a final task in constant time (triply exponential in
$|\phi|+\ell$) such that afterward, the solution for $\varphi(\overline{x})$
over $G$ can be enumerated with delay $O(k^{3})$.

The data structure for Theorem 25 combine ideas from different parts of
previous algorithms. We first use the efficient testing procedure i.e. Lemma
19, precisely the fact that there is a data structure allowing to test the
distance up to some threshold in time $O(k^{2})$. We also use the Lemma 12
that allows to skip some part of a list. This enable us to improve the two
lemmas (Lemmas 17 and 18) that are at the core of the proof of the enumerating
part of Theorem 15.

The proof of Lemma 17 already matches our new standards, i.e. the list of
solution for a unary query can be enumerated with delay truly $O(1)$, after an
additional preprocessing depending on the degree of the graphs (triply
exponential in the size of the query).

Concerning the improvement of Lemma 18, we need to improve the structure using
Lemma 12 and Lemma 19. For each list $L_{H}$ of the Basic Data Structure, we
compute the skip pointers ${\textup{SKIP}}(b,I)$ (as in Lemma 12).
Additionally, for every distance query $\mathrm{dist}_{\leq r}(x,y)$ with
$r\leq 2^{\ell}$, we maintain the data structure allowing to test the
solutions in time $O(1)$.

During the enumeration phase, instead or running a BFS algorithm, we can test
all the distances in time $O(k^{2})$. We can therefore test whether we are
looking at a solution in time $O(k^{2})$. If not we can use a skip pointer
that directly gives us the next solution.

The procedure in the proof of Lemma 18 work in time $O(k^{2})$ after the
additional preprocessing (triply exponential in the size of the query).

The overall delay becomes $O(k^{3})$ because of the $k$ recursive calls
produced by the global procedure.

###  B.3 Fast algorithm for the testing problem

######  Proof B.3 (Proof of Lemma 19).

The only thing that we add (before knowing the query) is a structure that
contains the value of the function $\delta_{r}(x,y)$ that test the distance up
to threshold $r$. I.e. $\delta_{r}(a,b)=r^{\prime}$ with $r^{\prime}\leq r$ if
$G\models\mathrm{dist}_{=r^{\prime}}(a,b)$ and $\delta_{r}(a,b)$ is undefined
otherwise. Here, $r$ is obtain from $\ell$ with Corollary 6, and
$r=2^{O(\ell)}$

The size of the domain of $\delta_{r}$ is $O(|G|\cdot d^{r})$ and a simple BFS
algorithm up to distance $r$ for all node of the graphs is enough to compute
$\delta_{r}$. When an update occurs, we have to perform the BFS for all
$r$-impacted nodes, which can be done in constant time (triply exponential in
$\ell$).

Let $(G,d,\ell)$ fixed. Let $r=2^{O(\ell)}$, we assume that $BDS(G,d,\ell)$
and the function $\delta_{r}(\cdot,\cdot)$ has been computed.

We are now given an FO query $\varphi(\overline{x})$ with quantifier rank $q$
and arity $k$ such that $q+k\leq\ell$. Similarly to the Naive algorithm, we
can assume without loss of generality that
$\varphi(\overline{x})=\alpha_{1}(\overline{x}_{1})\wedge\ldots\wedge\alpha_{p}(\overline{x}_{p})\wedge\Delta_{2r,\tau}(\overline{x})$
where $(\overline{x}_{1},\ldots,\overline{x}_{p})$ is a partition of
$\overline{x}$, and all $\alpha_{i}(\overline{x}_{i})$ are $r$-locals
centered.

We then compute a final structure in constant time (triply exponential in
$|\varphi|$) before any tuple is given. The structure is composed of function
$SOL_{i,H}(\cdot)$ for all $i\leq p$ and $H$ in $\mathcal{H}$. We define and
compute these function as follows:

For all $i\leq p$, for all $H$ in $\mathcal{H}$ and for all tuple
$\overline{a}_{i}$ (with $|\overline{a}_{i}|=|\overline{x}_{i}|$), we test
whether $H\models\alpha_{i}(\overline{a}_{i})$. If so, we set
$SOL_{i,H}(\overline{a}_{i}):=1$. Those functions are stored and ready to be
accessed in constant time.

The complexity of this final phase is triply exponential in $\ell$ because
there are only $2^{d^{r}}$ graphs in $\mathcal{H}$. For a fixed $H$, there are
only $(d^{r})^{k}$ tuples and the final tests can be performed in time
$2^{d^{r}}$.

We are now given a tuple $\overline{a}$ in $G$ and we want to test whether
$G\models\varphi(\overline{a})$.

  * •

For all $(a_{j},a_{j^{\prime}})$ in $\overline{a}$ we check
$\delta_{2r}(a_{j},a_{j^{\prime}})$. Therefore in time $O(k^{2})$ we know
whether $\Delta_{2r,\tau}(\overline{a})$ holds in $G$.

  * •

For all $\overline{a}_{i}$ in $\overline{a}$, let $a^{1}_{i}$ be it’s first
elements.

  * •

Let $H_{i}=\mathcal{X}(a_{i}^{1})$ and $f_{a_{i}^{1}}(\cdot)$ the isomorphism
from $\mathcal{N}_{r}^{G}(a^{1}_{i})$ to $H_{i}$.

Since $\Delta_{2r,\tau}(\overline{a})$ holds, we have that
$\overline{a}_{i}\subseteq\mathcal{N}^{G}_{k\cdot r}(a_{i}^{1})$. Hence
$\mathcal{N}_{r}(\overline{a}_{i})\subseteq\mathcal{N}_{r\ell}(a^{1}_{i})$.
Therefore $G\models\alpha_{i}(\overline{a}_{i})$ if and only if
$H_{i}\models\alpha_{i}(f_{a_{i}^{1}}(\overline{a}_{i}))$ and this is true if
and only if $SOL_{i,H_{i}}(f_{a_{i}^{1}}(\overline{a}_{i}))=1$, which can be
tested in time $O(1)$.

This ends the testing algorithm. The structure can be updated in time triply
exponential in $\ell$, and with an additional phase performed once the query
is known, we can test whether a given tuple is a solution in time $O(k^{2})$.