  We introduce the logic FOCN(P) which extends first-order logic by counting
and by numerical predicates from a set P, and which can be viewed as a natural
generalisation of various counting logics that have been studied in the
literature.
  We obtain a locality result showing that every FOCN(P)-formula can be
transformed into a formula in Hanf normal form that is equivalent on all finite
structures of degree at most d. A formula is in Hanf normal form if it is a
Boolean combination of formulas describing the neighbourhood around its tuple
of free variables and arithmetic sentences with predicates from P over atomic
statements describing the number of realisations of a type with a single
centre. The transformation into Hanf normal form can be achieved in time
elementary in $d$ and the size of the input formula. From this locality result,
we infer the following applications: (*) The Hanf-locality rank of first-order
formulas of bounded quantifier alternation depth only grows polynomially with
the formula size. (*) The model checking problem for the fragment FOC(P) of
FOCN(P) on structures of bounded degree is fixed-parameter tractable (with
elementary parameter dependence). (*) The query evaluation problem for fixed
queries from FOC(P) over fully dynamic databases of degree at most d can be
solved efficiently: there is a dynamic algorithm that can enumerate the tuples
in the query result with constant delay, and that allows to compute the size of
the query result and to test if a given tuple belongs to the query result
within constant time after every database update.
