2026-07-25T03:03:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8611 2024-03-06T10:42:26Z ddc:004 open_access

An Update on Dynamic Complexity Theory Zeume, Thomas Dynamic descriptive complexity SQL updates Reachability In many modern data management scenarios, data is subject to frequent changes. In order to avoid costly re-computing query answers from scratch after each small update, one can try to use auxiliary relations that have been computed before. Of course, the auxiliary relations need to be updated dynamically whenever the data changes. Dynamic complexity theory studies which queries and auxiliary relations can be updated in a highly parallel fashion, that is, by constant-depth circuits or, equivalently, by first-order formulas or the relational algebra. After gently introducing dynamic complexity theory, I will discuss recent results of the area with a focus on the dynamic complexity of the reachability query. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Zeume 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.3 urn:nbn:de:0030-drops-86117 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode