This paper is the journal version of [1]}. All proofs
are now detailed and the whole story has been simplified a bit, without changing
the key ideas. Since the publication of the conference version, constant delay
enumeration has been obtained for first-order queries over any class of
structures having local bounded expansion [2]} or
being nowhere dense [3]}
These two classes of structures generalize bounded expansion. However the
preprocessing time that has been achieved for these two classes is not linear but
pseudo-linear (i.e for any \(\epsilon \)  there is an algorithm working in time
\(O(n^{1+\epsilon })\) ) and the enumeration algorithms are significantly more complicated.
