Dynamic transitive closure with immediate new reachability facts The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, most works on time complexity provide separated estimations on update operation and reachability query evaluation. But what about the case when one wants to get new reachability facts immediately on the update? So, we have only update queries, and as a result of each edge insertion we want to get all new reachable pairs (for edge deletion --- all pairs that became unreachable, for example). Are there any results on the theoretical time complexity of such a case?
Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried.  It would be useful to know why you want an immediate query?  The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.
https://arxiv.org/pdf/1512.05511.pdf