Dynamic transitive closure with immediate new reachability facts
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