The dynamic complexity of the reachability query is studied in
the dynamic complexity framework of Patnaik and Immerman, restricted to
quantifier-free update formulas.
It is shown that, with this restriction, the reachability query cannot
be dynamically maintained, neither with binary auxiliary relations nor
with unary auxiliary functions, and that ternary auxiliary relations are
more powerful with respect to graph queries than binary auxiliary relations.
Further results are obtained including more inexpressibility results for
reachability in a different setting, inexpressibility results for some
other queries and normal forms for quantifier-free update programs.