Graph databases in many applications---semantic web, transport or biological networks among others---are not only large, but also frequently modified. Evaluating graph queries in this dynamic context is a challenging task, as small changes in the database make old answers incomplete or incorrect. What’s more, the size of these applications makes reevaluation from scratch prohibitively expensive. It is conceivable, though, for answers to a query before and after small modifications to be closely related. One thus hopes to update the answer to a query in more a efficient way than recomputing it from scratch. Even more so if one stores auxiliary information that may ease the task, updating it accordingly. To what extent this is possible, and in which precise conditions, is the subject of dynamic computational complexity. In this talk I will go through the basics of the descriptive framework for dynamic complexity, where the goal is to keep the answer to a query on a input database updated by First Order queries (or core SQL) evaluated on the input database extended with auxiliary data. I'll exhibit the main features of dynamic programs on simple examples, with emphasis on queries for graphs, to then present preliminary results on dynamically maintaining traditional graph query languages (regular path queries and extensions thereof), pointing out interesting directions for further research (joint work with Nils Vortmeier and Thomas Zeume).