Sketches of Dynamic Complexity
Thomas Schwentick, Nils Vortmeier, Thomas Zeume · ACM SIGMOD Record · 2020
How can the result of a query be updated after changing a database? This is a fundamental task for database management systems which ideally takes previously computed information into account. In dynamic complexity theory, it is studied from a theoretical perspective where updates are specified by rules written in first-order logic. In this article we sketch recent techniques and results from dynamic complexity theory with a focus on the reachability query.