 Reinitialize \(b\)  to the successor of \(b^{\prime }\)  in \(L\) 
and continue with Step .
We now show that the algorithm is correct.
The algorithm clearly outputs only solutions as it tests whether
\(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \models \psi (\bar{a} b^{\prime })\)  before outputting \(b^{\prime }\) .
By the definition of sets \(S_{i}\)  and \(\textsc {next}_{\vec{S}}(b) \) , for each \(b \le v < b^{\prime }\) 
there is a \(i\)  and \(j\)  such that \(g(a_{j}) = f_{i}(v)\)  and
\(g(x_{j}) \ne f_{i}(y)\)  is a conjunct of \(\Delta ^{\ne }\) . This way the
algorithm does not skip any solutions at Step  and so
it outputs exactly all solutions.
It remains to show that there is a constant time between any two outputs.
Step  takes constant time due to Claim . From
there the algorithm either immediately outputs a solution at
Step  or jumps to Step REF . In the second case,
this means that \(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \lnot \models \psi (\bar{a} b^{\prime })\) , but from the definitions
of list \(L\) , sets \(S_{i}\)  and shortcut pointers \(\textsc {next}_{\vec{S}}(b) \)  this can only happen
if \(\Delta ^{\ne }\)  is falsified and this is because of an inequality of the
form \(y \ne g(x_{j})\)  for some suitable \(g\)  and \(j\)  (where \(g\)  may possibly be
identity). Hence \(b^{\prime }=g(a_j)\) . As all the elements on \(L\)  are
distinct, the algorithm can skip over Step  up to
\((k-1) \cdot (\alpha _{(q) +1) times for each tuple \bar{a} (there are up to thatmany different images of nodes from \bar{a} under \alpha _{(q)  differentfunctions). The delay is therefore bounded by k \cdot (\alpha _{(q) +1) consecutive applications of Claim~\ref {claim-SC-okjump}.}}As the list L was sorted with respect to the linear order on the domain,it is clear that the enumeration procedure outputs the set of solutions inlexicographical order.}This concludes the proof of the theorem.\)
Counting
In this section we investigate the problem of counting the number of solutions
to a query, i.e. computing \(|q({\textbf {D}})|\) . As usual we only state and prove our
results over graphs but they generalize to arbitrary relational structures
via Lemma REF .
Let b̏e class of graphs with bounded expansion and let \(\phi (\bar{x})\) 
be a first-order formula. Then, for all \(\textsc {f}\vec{\textbf {G}} \in , we can compute \) |(\(\textsc {f}\vec{\textbf {G}}\) )|\(in time \) O(||\(\textsc {f}\vec{\textbf {G}}\)  ||)\(.\)
The key idea is to prove a weighted version of the desired result. Assume
\(\phi (\bar{x})\)  has exactly \(k\)  free variables and for \(1 \le i \le k\)  we have
functions \(\#_{i} : V \rightarrow \mathbb {N}\) . We will compute in time linear in
\(|\!|\textsc {f}\vec{\textbf {G}} |\!|\)  the following number:
\(|\phi (\textsc {f}\vec{\textbf {G}})|_{\#} := \sum _{\bar{u} \in \phi (\textsc {f}\vec{\textbf {G}})} \prod _{1 \le i \le k} \#_{i}(u_{i}).\) 
By setting all \(\#_{i}\)  to be constant functions with value 1 we get the
regular counting problem. Hence Theorem  is an immediate
consequence of the next lemma.
Let b̏e class of graphs with bounded expansion and let \(\phi (\bar{x})\) 
be a first-order formula with exactly \(k\)  free variables.
For \(1 \le i \le k\) 
let \(\#_{i} : V \rightarrow \mathbb {N}\)  be functions such that for each \(v\) 
the value of \(\#_i(v)\)  can be computed in constant time.
Then, for all \(\textsc {f}\vec{\textbf {G}} \in , we can compute \)\(|\phi (\textsc {f}\vec{\textbf {G}})|_{\#}\)  \(in time \) O(||\(\textsc {f}\vec{\textbf {G}}\)  ||)\(.\)
The proof is by induction on the number of free variables.
The case \(k = 1\)  is trivial: in time linear in \(|\!|\textsc {f}\vec{\textbf {G}} |\!|\)  we compute
\(\phi (\textsc {f}\vec{\textbf {G}})\)  using Corollary REF . By hypothesis, for each \(v \in \phi (\textsc {f}\vec{\textbf {G}})\) , we
can compute the value of \(\#_{1}(v)\)  in constant time. Therefore the value
\(|\phi (\textsc {f}\vec{\textbf {G}})|_{\#} = \sum _{v \in \phi (\textsc {f}\vec{\textbf {G}})} \#_{1}(v)\) 
can be computed in linear time as desired.
Assume now that \(k > 1\)  and that \(\bar{x}\)  and \(y\)  are the free variables of
\(\phi \) , where \(|\bar{x}|=k-1\) .
We apply Theorem REF  to get a simple quantifier-free query
\(\varphi (\bar{x} y)\)  and a structure \(\textsc {f}\vec{\textbf {G}}^{\prime } \in {p} \) , for some \(p\)  that does not
depend on \(\textsc {f}\vec{\textbf {G}} \) , such that \(\varphi (\textsc {f}\vec{\textbf {G}}^{\prime })=\phi (\textsc {f}\vec{\textbf {G}})\)  and \(\textsc {f}\vec{\textbf {G}}^{\prime } \)  can be
computed in linear time from \(\textsc {f}\vec{\textbf {G}} \) . Note that \(|\phi (\textsc {f}\vec{\textbf {G}})|_{\#} =|\varphi (\textsc {f}\vec{\textbf {G}}^{\prime })|_{\#} \) ,
so it is enough to compute the latter value.
We normalize the resulting simple quantifier-free query using
Proposition , and obtain an equivalent quantifier-free
formula \(\psi \)  and a structure \(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \in {q} \) , where \(q\)  depends only on
\(p\)  and \(\varphi \) , \(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \)  can be computed in linear time from \(\textsc {f}\vec{\textbf {G}}^{\prime } \) ,
\(\varphi (\textsc {f}\vec{\textbf {G}}^{\prime })=\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })\)  and \(\psi \)  is a disjunction of formulas
of the form ():
\(\psi _1(\bar{x}) \wedge \tau (y) \wedge \Delta ^{=}(\bar{x} y) \wedge \Delta ^{\ne }(\bar{x} y),\) 
where \(\Delta ^{=}(\bar{x} y)\)  is either empty or
contains one clause of the form \(y=f(x_i)\)  or one clause of the form
\(f(y)=g(x_i)\)  for some suitable \(i\) , \(f\)  and \(g\) ; and \(\Delta ^{\ne }(\bar{x} y)\) 
contains arbitrarily many clauses of the form \(y\ne f(x_i)\)  or \(f(y) \ne g(x_j)\) .
Note that \(|\varphi (\textsc {f}\vec{\textbf {G}}^{\prime })|_{\#} =|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} \) , so it is enough
to compute the latter value.
Observe that it is enough to solve the weighted counting problem for each
disjunct separately, as we can then combine the results using a simple
inclusion-exclusion reasoning (the weighted sum for \(q \vee q^{\prime }\)  is obtained by
adding the weighted sum for \(q\)  to the weighted sum for \(q^{\prime }\)  and then
subtracting the weighted sum for \(q \wedge q^{\prime }\) ). In the sequel we then assume that \(\psi \)  has the form
described in ().
The proof now goes by induction on the number of inequalities in
\(\Delta ^{\ne }\) . While the inductive step turns out to be fairly easy, the
difficult part is the base step of the induction.
We start with proving the inductive step. Let \(g(y) \ne f(x_i)\)  be an
arbitrary inequality from \(\Delta ^{\ne }\)  (where \(g\)  might possibly be the
identity). Let \(\psi ^{-}\)  be \(\psi \)  with this inequality removed and \(\psi ^{+}= \psi ^{-} \wedge g(y) = f(x_i)\) . Of course \(\psi \)  and \(\psi ^{+}\)  have disjoint
sets of solutions and we have:
\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} = |\psi ^{-}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} - |\psi ^{+}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#}.\) 
Note that \(\psi ^-\)  and \(\psi ^{+}\)  have one less conjunct in
\(\Delta ^{\ne }\) . The problem is that \(\psi ^+\)  is not of the form ()
as it may now contain two elements in \(\Delta ^=\) . However it can be seen that
the removal of the extra equality in \(\Delta ^=\)  as described in the proof of
Proposition  does not introduce any new elements in
\(\Delta ^{\ne }\) .
.
There exists a query \(\psi ^{+}_{\textup {NF}} \)  such that:
its size depends only on the size of \(\psi ^{+}\) , \(\psi ^{+}_{\textup {NF}} \) 
is in the normal form given by (),
it contains an inequality conjunct \(h(y) \ne g_{1}(x_{i})\)  (where
\(h\)  might possibly be identity) iff \(\psi ^{+}\)  also contains
such conjunct and \(\psi ^{+}_{\textup {NF}} (\textsc {f}\vec{\textbf {G}}^{\prime \prime }) = \psi ^{+}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\) .
Moreover, \(\psi ^{+}_{\textup {NF}} \)  can be constructed in time linear in the
size of \(\psi ^{+}\) .
The proof is a simple case analysis of the content of \(\Delta ^{=}\)  of \(\psi \) .
If its empty, then \(\psi ^{+}_{\textup {NF}} \)  is already in the desired form.
If it contains an atom of the form \(y = h_{2}(x_j)\) , then
equality \(g(y) = f(x_i)\)  is equivalent to \(g(h_{2}(x_j)) = f(x_i)\) 
and we are done.
If it contains an atom of the form \(h_{3}(y) = h_{2}(x_j)\) 
and \(g\)  is identity, then \(h_{3}(y) = h_{2}(x_j)\)  is equivalent
to \(h_{3}(f(x_{i})) = h_{2}(x_j)\) . If \(g\)  is not identity, then
\(\tau (y)\)  ensures us that either \(g(y)\)  determines \(h_{3}(y)\) 
or vice versa. If we have \(h_{4}(g(y)) = h_{3}(y)\) , then
\(h_{3}(y) = h_{2}(x_j)\)  is equivalent to \(h_{4}(f(x_i)) = h_{2}(x_j)\) .
The other case is symmetric.
The fact that \(\psi ^{+}_{\textup {NF}} \)  does not contain any additional inequalities,
that it can be computed in time linear in the size of \(\psi ^{+}\) 
and that \(\psi ^{+}_{\textup {NF}} (\textsc {f}\vec{\textbf {G}}^{\prime \prime }) = \psi ^{+}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\)  follows from the
above construction.
We can therefore remove
the extra element in \(\Delta ^+\)  and assume that \(\psi ^+\)  has the desired
form. We can now use the inductive hypothesis on the size of \(\Delta ^{\ne }\) 
to both \(\psi ^-\)  and \(\psi ^+\)  in order to compute both
\(|\psi ^{-}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} \)  and \(|\psi ^+(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} \)  and derive
\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} \) .
It remains to show the base of the inner induction.
In the following we assume that \(\Delta ^{\ne }\)  is empty.
The rest of the proof is a case analysis on the content of \(\Delta ^{=}\) .
Assume first that \(\Delta ^{=}\)  consists of an atom of the form \(y = f(x_1)\) .
Note that the solutions to \(\psi \)  are of the form \((\bar{v} f(v_1))\) . We have:


\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} \!&= \!\!\!\!\!\!\!\!\!\sum _{(\bar{v} u) \in \psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left(\#_k(u) \prod _{1 \le i \le k-1} \#_{i}(v_{i})\right)\\&= \!\!\!\!\!\!\!\!\!\!\!\!\sum _{(\bar{v} f(v_1)) \in \psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left(\#_k(f(v_1)) \prod _{1 \le i \le k-1} \#_{i}(v_{i}) \right)\\&= \!\!\!\!\!\!\!\!\!\!\!\!\sum _{(\bar{v} f(v_1)) \in \psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left( \#_1(v_1) \#_k(f(v_1))\!\!\! \prod _{2 \le i \le k-1}\!\!\! \#_{i}(v_{i})\right)\) 


In linear time we now iterate through all nodes \(w\)  in \(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \)  and set
\(\#^{\prime }_1(w) &:= \#_1(w) \cdot \#_k(f(w))\\\#^{\prime }_{i}(w) &:= \#_{i}(w) & \text{ for } 2 \le i \le k-1.\) 

Let \(\vartheta (\bar{x})\)  be \(\psi \)  with all occurrences of \(y\)  replaced with \(f(x_1)\) .
We then have:


\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#}&= \sum _{(\bar{v} f(v_1)) \in \psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left( \#^{\prime }_1(v_1) \prod _{2 \le i \le k-1} \#^{\prime }_{i}(v_{i})\right)\\&= \sum _{\bar{v} \in \vartheta (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\prod _{1 \le i \le k-1} \#^{\prime }_{i}(v_{i})\\&= |\vartheta (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#^{\prime }}\) 


By induction on the number of free variables, as \(\#^{\prime }_i(w)\)  can be computed in
constant time for each \(i\)  and \(w\) , we can compute \(|\vartheta (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#^{\prime }} \)  in time linear in
\(|\!|\textsc {f}\vec{\textbf {G}}^{\prime \prime } |\!|\)  and we are done.
Assume now that \(\Delta ^{=}\)  consists of an atom \(g(y) = f(x_1)\) . Let
\(\psi ^{\prime }(y)\)  be the formula \(\exists \bar{x} \psi (\bar{x} y)\)  and \(\psi ^{\prime \prime }(\bar{x})\) 
the formula \(\exists y \psi (\bar{x} y)\) . We first compute set \(\psi ^{\prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\)  in
linear time using Corollary REF . We now define a function \(\#^{\prime \prime }_{k}: V \rightarrow \mathbb {N}\)  as:
\(\#^{\prime \prime }_k(w) := \sum _{\begin{array}{c}\lbrace u \in \psi ^{\prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\\ g(u) = w\rbrace  \end{array}} \#_k(u).\) 
Note that this function can be easily computed in linear time by going through
all nodes \(w\)  and adding \(\#_k(w)\)  to \(\#^{\prime \prime }_k(g(w))\) .
Finally we set:
\(\#^{\prime }_1(w) &:= \#_1(w) \#^{\prime \prime }_k(f(w))\\\#^{\prime }_i(w) &:= \#_{i}(w) & \text{ for } 2 \le i \le k-1.\) 

Let \(u_1, u_2 \in \psi ^{\prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\)  be such that \(g(u_1) = g(u_2)\) . Because
\(\Delta ^{\ne }\)  is empty, observe that \(\textsc {f}\vec{\textbf {G}}^{\prime \prime } \models \forall \bar{x}(\psi (\bar{x} u_1) \leftrightarrow \psi (\bar{x} u_2))\) . Based on this
observation we now group the solutions to \(\psi \)  according to their last \(k-1\) 
values and get:
\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#}&= \sum _{(\bar{v} u) \in \psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left(\#_k(u) \prod _{1 \le i \le k-1} \#_{i}(v_{i})\right)\\&=\!\!\! \sum _{\bar{v} \in \psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\sum _{\begin{array}{c}\lbrace u \in \psi ^{\prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\\ g(u) = f(v_1)\rbrace  \end{array}}\left(\#_k(u) \prod _{1 \le i \le k-1} \#_{i}(v_{i}) \right)\\&= \sum _{\bar{v} \in \psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })} \left(\sum _{\begin{array}{c}\lbrace u \in \psi ^{\prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })\\ g(u) = f(v_1)\rbrace  \end{array}} \#_k(u)\right)\prod _{1 \le i \le k-1} \#_{i}(v_{i})\\&= \sum _{\bar{v} \in \psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left(\#^{\prime \prime }_k(f(v_1)) \prod _{1 \le i \le k-1} \#_{i}(v_{i})\right)\\&=\!\!\!\! \sum _{\bar{v} \in \psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\left(\#_1(v_1)\#^{\prime \prime }_k(f(v_1)) \prod _{2 \le i \le k-1} \#^{\prime }_{i}(v_{i})\right)\\&= \sum _{\bar{v} \in \psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })}\prod _{1 \le i \le k-1} \#^{\prime }_{i}(v_{i})\\&= |\psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#^{\prime }}\) 


By induction on the number of free variables, as \(\#^{\prime }_i(w)\)  can be computed in
constant time for each \(i\)  and \(w\) , we can compute \(|\psi ^{\prime \prime }(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#^{\prime }} \) 
and we are done with this case.
The remaining case when \(\Delta ^{=}\)  is empty is handled similarly to the previous one.
We then have
\(\psi (\bar{x} y) = \psi _{1}(\bar{x}) \wedge \tau (y).\) 
After setting
\(\#^{\prime }_1(w) &:= \#_2(w) \cdot \sum _{u \in \tau (\textsc {f}\vec{\textbf {G}}^{\prime \prime })} \#_{1}(u)\\\#^{\prime }_i(w) &:= \#_{i+1}(w) & \text{ for } 2 \le i \le k-1\) 

we see that
\(|\psi (\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#} = |\psi _{1}(\textsc {f}\vec{\textbf {G}}^{\prime \prime })|_{\#^{\prime }}\) 
and we conclude again by induction on the number of free variables.

As we said earlier, Theorem  is an immediate
consequence of Lemma .

Conclusions
Queries written in first-order logic can be efficiently processed over the
class of structures having bounded expansion. We have seen that over this class
the problems investigated in this paper can be computed in time linear in the
size of the input structure. The constant factor however is high. The
approach taken here, as well as the ones of [1]}, [2]},
yields a constant factor that is a tower of exponentials whose height depends
on the size of the query. This nonelementary constant factor is unavoidable
already on the class of unranked trees, assuming
FPT\(\ne \) AW\([*]\)  [3]}. In comparison, this factor can be
triply exponential in the size of the query in the bounded degree
case [4]}, [5]}.
Since the submission of this work, the result has been extended to a larger
class of structures. In [6]} the class of nowhere dense graphs was
introduced and it generalizes the notion of bounded expansion. It has
been shown that the model checking problem of first-order logic can be done in
nearly linear time (i.e. for any \(\epsilon >0\)  it can be done in
\(O(n^{1+\epsilon })\) ) over any nowhere dense class of
graph [7]}. Recently an enumeration procedure has
been proposed for first-order queries over nowhere dense graph classes, with a
nearly linear preprocessing time and constant
delay [8]}.
For graph classes closed under substructures, the nowhere dense property seems
to be the limit for having good algorithmic properties for first-order
logic. Indeed, it is known that the model checking problem of first-order logic
over a class of structures that is not nowhere dense cannot be FPT [9]}
(modulo some complexity assumptions).
For structures of bounded expansion, an interesting open question is whether a
sampling of the solutions can be performed in linear time. For instance: can we
compute the \(j\) -th solution in constant time after a linear preprocessing? This
can be done in the bounded degree case [10]} and in the bounded
treewidth case [11]}. We leave the bounded expansion case for future
research.
Finally it would be interesting to know whether the index structure computed in
linear time for the enumeration process could be updated efficiently. In the
boolean case, queries of arity 0, updates can be done in constant
time [1]}, assuming the underlying graph is not changed too
much. In particular a relabeling of a node require only constant update
time. It would be interesting to know whether this constant update time could
also be achieved for an index structure allowing for constant delay
enumeration.
