License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2018.3
URN: urn:nbn:de:0030-drops-86117
Go to the corresponding LIPIcs Volume Portal

Zeume, Thomas

An Update on Dynamic Complexity Theory

LIPIcs-ICDT-2018-3.pdf (0.2 MB)


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.

BibTeX - Entry

  author =	{Thomas Zeume},
  title =	{{An Update on Dynamic Complexity Theory}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-86117},
  doi =		{10.4230/LIPIcs.ICDT.2018.3},
  annote =	{Keywords: Dynamic descriptive complexity, SQL updates, Reachability}

Keywords: Dynamic descriptive complexity, SQL updates, Reachability
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI