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.