  We study how to evaluate MSO queries with free variables on trees, within the
framework of enumeration algorithms. Previous work has shown how to enumerate
answers with linear-time preprocessing and delay linear in the size of each
output, i.e., constant-delay for free first-order variables. We extend this
result to support relabelings, a restricted kind of update operations on trees
which allows us to change the node labels. Our main result shows that we can
enumerate the answers of MSO queries on trees with linear-time preprocessing
and delay linear in each answer, while supporting node relabelings in
logarithmic time. To prove this, we reuse the circuit-based enumeration
structure from our earlier work, and develop techniques to maintain its index
under node relabelings. We also show how enumeration under relabelings can be
applied to evaluate practical query languages, such as aggregate, group-by, and
parameterized queries.
