  We investigate the query evaluation problem for fixed queries over fully
dynamic databases where tuples can be inserted or deleted. The task is to
design a dynamic data structure that can immediately report the new result of a
fixed query after every database update. We consider unions of conjunctive
queries (UCQs) and focus on the query evaluation tasks testing (decide whether
an input tuple belongs to the query result), enumeration (enumerate, without
repetition, all tuples in the query result), and counting (output the number of
tuples in the query result).
  We identify three increasingly restrictive classes of UCQs which we call
t-hierarchical, q-hierarchical, and exhaustively q-hierarchical UCQs. Our main
results provide the following dichotomies: If the query's homomorphic core is
t-hierarchical (q-hierarchical, exhaustively q-hierarchical), then the testing
(enumeration, counting) problem can be solved with constant update time and
constant testing time (delay, counting time). Otherwise, it cannot be solved
with sublinear update time and sublinear testing time (delay, counting time),
unless the OV-conjecture and/or the OMv-conjecture fails.
  We also study the complexity of query evaluation in the dynamic setting in
the presence of integrity constraints, and we obtain according dichotomy
results for the special case of small domain constraints (i.e., constraints
which state that all values in a particular column of a relation belong to a
fixed domain of constant size).
