Dynamic Tree Isomorphism via First-Order Updates

In databases, as in other computational settings, one would like to efficiently update answers to queries while minor changes are being made to the data. Dynamic complexity asks what resources are required to perform such updates.
In this paper our main focus will be a particular dynamic graph problem, tree isomorphism, and the efficiency of our update scheme will be measured in terms
of how expressive a query language is required to express our update. Working in the framework developed by [DS93, PI971 for dynamic query evaluation, we show that dynamic tree isomorphism can be performed via first-order updates to a relational database (in [DS93] this framework is called a first-order incremental ed u&ion JUstem, and in [PI971 it is called Dyn-FO). In (EI96] it was shown that tree-isomorphism can not be expressed in first-order logic augmented with a transitive closure operator and counting, (8’0 + TC +
COUNT) (but without ordering). We thus obtain a Rrst example of a graph problem in Dyn-FO that is not expressible in this logic. Part of our proof shows how to build and maintain arithmetic predicates on a relevant part of the universe, from which we obtain a direct correspondence between Dyn-FO and dynamic constant parallel time. This provides some explanation for why it is so difficult to prove lower bounds for Dyn-FO.