{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:30:48Z","timestamp":1755999048983,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T00:00:00Z","timestamp":1607472000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2020,12,9]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>In this article we sketch recent techniques and results from dynamic complexity theory with a focus on the reachability query.<\/jats:p>","DOI":"10.1145\/3442322.3442325","type":"journal-article","created":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T19:16:52Z","timestamp":1607627812000},"page":"18-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Sketches of Dynamic Complexity"],"prefix":"10.1145","volume":"49","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[{"name":"TU Dortmund"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nils","family":"Vortmeier","sequence":"additional","affiliation":[{"name":"TU Dortmund"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54458-7_16"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90101-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897534"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_7_1","volume-title":"41st International Colloquium, ICALP 2014","author":"Datta S.","year":"2014","unstructured":"S. Datta , W. Hesse , and R. Kulkarni . Dynamic complexity of directed reachability and other problems. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 , Part I, pages 356--367 , 2014 . S. Datta, W. Hesse, and R. Kulkarni. Dynamic complexity of directed reachability and other problems. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Part I, pages 356--367, 2014."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212685"},{"key":"e_1_2_1_9_1","first-page":"1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020","author":"Datta S.","year":"2020","unstructured":"S. Datta , P. Kumar , A. Mukherjee , A. Tawari , N. Vortmeier , and T. Zeume . Dynamic complexity of reachability: How many changes can we handle? In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 , pages 122: 1 -- 122 :19, 2020 . S. Datta, P. Kumar, A. Mukherjee, A. Tawari, N. Vortmeier, and T. Zeume. Dynamic complexity of reachability: How many changes can we handle? In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, pages 122:1--122:19, 2020."},{"key":"e_1_2_1_10_1","volume-title":"A strategy for dynamic programs: Start over and muddle through. Logical Methods in Computer Science, 15(2)","author":"Datta S.","year":"2019","unstructured":"S. Datta , A. Mukherjee , T. Schwentick , N. Vortmeier , and T. Zeume . A strategy for dynamic programs: Start over and muddle through. Logical Methods in Computer Science, 15(2) , 2019 . S. Datta, A. Mukherjee, T. Schwentick, N. Vortmeier, and T. Zeume. A strategy for dynamic programs: Start over and muddle through. Logical Methods in Computer Science, 15(2), 2019."},{"key":"e_1_2_1_11_1","first-page":"1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Datta S.","year":"2018","unstructured":"S. Datta , A. Mukherjee , N. Vortmeier , and T. Zeume . Reachability and distances under multiple changes. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , pages 120: 1 -- 120 :14, 2018 . S. Datta, A. Mukherjee, N. Vortmeier, and T. Zeume. Reachability and distances under multiple changes. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pages 120:1--120:14, 2018."},{"issue":"1","key":"e_1_2_1_12_1","first-page":"46","article-title":"Maintaining transitive closure of graphs","volume":"51","author":"Dong G.","year":"1999","unstructured":"G. Dong , L. Libkin , J. Su , and L. Wong . Maintaining transitive closure of graphs in SQL. International Journal of Information Technology , 51 ( 1 ): 46 , 1999 . G. Dong, L. Libkin, J. Su, and L. Wong. Maintaining transitive closure of graphs in SQL. International Journal of Information Technology, 51(1):46, 1999.","journal-title":"SQL. International Journal of Information Technology"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/648290.754351"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3306063"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000302"},{"key":"e_1_2_1_16_1","volume-title":"Finite model theory","author":"Ebbinghaus H.-D.","year":"2005","unstructured":"H.-D. Ebbinghaus and J. Flum . Finite model theory . Springer Science & Business Media , 2005 . H.-D. Ebbinghaus and J. Flum. Finite model theory. Springer Science & Business Media, 2005."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275514"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.012"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"23rd International Conference on Database Theory, ICDT 2020","author":"Freydenberger D. D.","year":"2020","unstructured":"D. D. Freydenberger and S. M. Thompson . Dynamic complexity of document spanners . In 23rd International Conference on Database Theory, ICDT 2020 , pages 11: 1 -- 11 :21, 2020 . D. D. Freydenberger and S. M. Thompson. Dynamic complexity of document spanners. In 23rd International Conference on Database Theory, ICDT 2020, pages 11:1--11:21, 2020."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287718.2287719"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274601"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1023004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00740-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer 1999.  N. Immerman. Descriptive Complexity. Springer 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190632"},{"key":"e_1_2_1_28_1","first-page":"271","volume-title":"CSL 2003","author":"K\u00a8ahler D.","year":"2003","unstructured":"D. K\u00a8ahler and T. Wilke . Program complexity of dynamic LTL model checking. In Computer Science Logic , CSL 2003 , pages 271 -- 284 , 2003 . D. K\u00a8ahler and T. Wilke. Program complexity of dynamic LTL model checking. In Computer Science Logic, CSL 2003, pages 271--284, 2003."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_1_30_1","volume-title":"Humboldt University of Berlin","author":"Laubner B.","year":"2011","unstructured":"B. Laubner . The structure of graphs and new logics for the characterization of Polynomial Time. PhD thesis , Humboldt University of Berlin , 2011 . B. Laubner. The structure of graphs and new logics for the characterization of Polynomial Time. PhD thesis, Humboldt University of Berlin, 2011."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1024196"},{"key":"e_1_2_1_32_1","first-page":"1","volume-title":"19th International Conference on Database Theory, ICDT 2016","author":"Munoz P.","year":"2016","unstructured":"P. Munoz , N. Vortmeier , and T. Zeume . Dynamic graph queries . In 19th International Conference on Database Theory, ICDT 2016 , pages 14: 1 -- 14 :18, 2016 . P. Munoz, N. Vortmeier, and T. Zeume. Dynamic graph queries. In 19th International Conference on Database Theory, ICDT 2016, pages 14:1--14:18, 2016."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182614"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2010.01.002"},{"key":"e_1_2_1_37_1","first-page":"1","volume-title":"28th EACSL Annual Conference on Computer Science Logic, CSL 2020","author":"Schmidt J.","year":"2020","unstructured":"J. Schmidt , T. Schwentick , N. Vortmeier , T. Zeume , and I. Kokkinis . Dynamic complexity meets parameterised algorithms . In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020 , pages 36: 1 -- 36 :17, 2020 . J. Schmidt, T. Schwentick, N. Vortmeier, T. Zeume, and I. Kokkinis. Dynamic complexity meets parameterised algorithms. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, pages 36:1--36:17, 2020."},{"key":"e_1_2_1_38_1","first-page":"308","volume-title":"24th EACSL Annual Conference on Computer Science Logic, CSL 2015","author":"Schwentick T.","year":"2015","unstructured":"T. Schwentick , N. Vortmeier , and T. Zeume . Static analysis for logic-based dynamic programs . In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015 , pages 308 -- 324 , 2015 . T. Schwentick, N. Vortmeier, and T. Zeume. Static analysis for logic-based dynamic programs. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, pages 308--324, 2015."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241040"},{"key":"e_1_2_1_41_1","first-page":"1","volume-title":"28th EACSL Annual Conference on Computer Science Logic, CSL 2020","author":"Vortmeier N.","year":"2020","unstructured":"N. Vortmeier and T. Zeume . Dynamic complexity of parity exists queries . In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020 , pages 37: 1 -- 37 :16, 2020 . N. Vortmeier and T. Zeume. Dynamic complexity of parity exists queries. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, pages 37:1--37:16, 2020."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1312-0"},{"key":"e_1_2_1_43_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-54314-6","volume-title":"An Investigation into Dynamic Descriptive Complexity","author":"Zeume T.","year":"2017","unstructured":"T. Zeume . Small Dynamic Complexity Classes : An Investigation into Dynamic Descriptive Complexity , volume 10110 of Lecture Notes in Computer Science . Springer , 2017 . T. Zeume. Small Dynamic Complexity Classes: An Investigation into Dynamic Descriptive Complexity, volume 10110 of Lecture Notes in Computer Science. Springer, 2017."},{"key":"e_1_2_1_44_1","first-page":"38","volume-title":"Proc. 17th International Conference on Database Theory (ICDT 2014","author":"Zeume T.","year":"2014","unstructured":"T. Zeume and T. Schwentick . Dynamic conjunctive queries . In Proc. 17th International Conference on Database Theory (ICDT 2014 ), pages 38 -- 49 , 2014 . T. Zeume and T. Schwentick. Dynamic conjunctive queries. In Proc. 17th International Conference on Database Theory (ICDT 2014), pages 38--49, 2014."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.011"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442322.3442325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442322.3442325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442322.3442325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,9]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12,9]]}},"alternative-id":["10.1145\/3442322.3442325"],"URL":"https:\/\/doi.org\/10.1145\/3442322.3442325","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2020,12,9]]},"assertion":[{"value":"2020-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}