{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T22:26:12Z","timestamp":1672611972152},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,10,9]],"date-time":"2018-10-09T00:00:00Z","timestamp":1539043200000},"content-version":"vor","delay-in-days":9,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["683080"]},{"name":"DFG","award":["SCHW678\/6-2"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"In the setting of dynamic complexity, the goal of a dynamic program is to maintain the result of a fixed query for an input database that is subject to changes, possibly using additional auxiliary relations. In other words, a dynamic program updates a materialized view whenever a base relation is changed. The update of query result and auxiliary relations is specified using first-order logic or, equivalently, relational algebra.<\/jats:p>\n \n The original framework by Patnaik and Immerman only considers changes to the database that insert or delete single tuples. This article extends the setting to\n definable changes<\/jats:italic>\n , also specified by first-order queries on the database, and generalizes previous maintenance results to these more expressive change operations. More specifically, it is shown that the undirected reachability query is first-order maintainable under single-tuple changes and first-order defined insertions, likewise the directed reachability query for directed acyclic graphs is first-order maintainable under insertions defined by quantifier-free first-order queries.\n <\/jats:p>\n \n These results rely on\n bounded bridge properties<\/jats:italic>\n , which basically say that, after an insertion of a defined set of edges, for each connected pair of nodes there is some path with a bounded number of new edges. While this bound can be huge, in general, it is shown to be small for insertion queries defined by unions of conjunctive queries. To illustrate that the results for this restricted setting could be practically relevant, they are complemented by an experimental study that compares the performance of dynamic programs with complex changes, dynamic programs with single changes, and with recomputation from scratch.\n <\/jats:p>\n The positive results are complemented by several inexpressibility results. For example, it is shown that\u2014unlike for single-tuple insertions\u2014dynamic programs that maintain the reachability query under definable, quantifier-free changes strictly need update formulas with quantifiers.<\/jats:p>\n \n Finally, further positive results unrelated to reachability are presented: it is shown that for changes definable by parameter-free first-order formulas, all LOGSPACE-definable (and even AC\n 1<\/jats:sup>\n -definable) queries can be maintained by first-order dynamic programs.\n <\/jats:p>","DOI":"10.1145\/3241040","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T13:30:46Z","timestamp":1539178246000},"page":"1-38","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Complexity under Definable Changes"],"prefix":"10.1145","volume":"43","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"given":"Nils","family":"Vortmeier","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,10,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley , Boston, MA . Retrieved from http:\/\/webdam.inria.fr\/Alice\/. Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley, Boston, MA. Retrieved from http:\/\/webdam.inria.fr\/Alice\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465218"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2633993"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_13"},{"key":"e_1_2_1_5_1","volume-title":"Reachability is in DynFO. CoRR abs\/1502.07467","author":"Datta Samir","year":"2015","unstructured":"Samir Datta , Raghav Kulkarni , Anish Mukherjee , Thomas Schwentick , and Thomas Zeume . 2015. Reachability is in DynFO. CoRR abs\/1502.07467 ( 2015 ). arxiv:arXiv:abs\/1502.07467. Retrieved from http:\/\/arxiv.org\/abs\/1502.07467. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. 2015. Reachability is in DynFO. CoRR abs\/1502.07467 (2015). arxiv:arXiv:abs\/1502.07467. Retrieved from http:\/\/arxiv.org\/abs\/1502.07467."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"80","author":"Datta Samir","year":"2017","unstructured":"Samir Datta , Anish Mukherjee , Thomas Schwentick , Nils Vortmeier , and Thomas Zeume . 2017 . A strategy for dynamic programs: Start over and muddle through . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.) , Vol. 80 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 98:1--98:14. Retrieved from Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. 2017. A strategy for dynamic programs: Start over and muddle through. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.), Vol. 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 98:1--98:14. Retrieved from"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Datta Samir","year":"2018","unstructured":"Samir Datta , Anish Mukherjee , Nils Vortmeier , and Thomas Zeume . 2018 . Reachability and distances under multiple changes . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs), Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.) , Vol. 107 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 120:1--120:14. Retrieved from Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. 2018. Reachability and distances under multiple changes. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs), Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.), Vol. 107. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 120:1--120:14. Retrieved from"},{"key":"e_1_2_1_8_1","volume-title":"Algorithms and Theory of Computation Handbook","author":"Demetrescu Camil","unstructured":"Camil Demetrescu , David Eppstein , Zvi Galil , and Giuseppe F Italiano . 2010. Dynamic graph algorithms . In Algorithms and Theory of Computation Handbook . Chapman 8 Hall\/CRC, 9--9. Camil Demetrescu, David Eppstein, Zvi Galil, and Giuseppe F Italiano. 2010. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook. Chapman 8 Hall\/CRC, 9--9."},{"key":"e_1_2_1_9_1","first-page":"46","article-title":"Maintaining transitive closure of graphs in SQL","volume":"51","author":"Dong Guozhu","year":"1999","unstructured":"Guozhu Dong , Leonid Libkin , Jianwen Su , and Limsoon Wong . 1999 . Maintaining transitive closure of graphs in SQL . Int. J. Info. Technol. 51 , 1 (1999), 46 -- 78 . Guozhu Dong, Leonid Libkin, Jianwen Su, and Limsoon Wong. 1999. Maintaining transitive closure of graphs in SQL. Int. J. Info. Technol. 51, 1 (1999), 46--78.","journal-title":"Int. J. Info. Technol."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00017-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00066-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/648290.754351"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1102"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018951521198"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1565"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530820"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 4th International Conference on Database Theory (ICDT\u201992)","author":"Dong Guozhu","unstructured":"Guozhu Dong and Rodney W. Topor . 1992. Incremental evaluation of datalog queries . In Proceedings of the 4th International Conference on Database Theory (ICDT\u201992) . 282--296. Retrieved from Guozhu Dong and Rodney W. Topor. 1992. Incremental evaluation of datalog queries. In Proceedings of the 4th International Conference on Database Theory (ICDT\u201992). 282--296. Retrieved from"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275514"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Summer Institute of Symbolic Logic. 201--209","author":"Feferman Solomon","year":"1957","unstructured":"Solomon Feferman . 1957 . Some recent work of Ehrenfeucht and Fra\u00efss\u00e9 . In Proceedings of the Summer Institute of Symbolic Logic. 201--209 . Solomon Feferman. 1957. Some recent work of Ehrenfeucht and Fra\u00efss\u00e9. In Proceedings of the Summer Institute of Symbolic Logic. 201--209."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-47-1-57-103"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287718.2287719"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274601"},{"key":"e_1_2_1_24_1","first-page":"3","article-title":"Maintenance of materialized views: Problems, techniques, and applications","volume":"18","author":"Gupta Ashish","year":"1995","unstructured":"Ashish Gupta and Inderpal Singh Mumick . 1995 . Maintenance of materialized views: Problems, techniques, and applications . IEEE Data Eng. Bull. 18 , 2 (1995), 3 -- 18 . Retrieved from http:\/\/sites.computer.org\/debull\/95JUN-CD.pdf. Ashish Gupta and Inderpal Singh Mumick. 1995. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull. 18, 2 (1995), 3--18. Retrieved from http:\/\/sites.computer.org\/debull\/95JUN-CD.pdf.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664594"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer. Retrieved from Neil Immerman. 1999. Descriptive Complexity. Springer. Retrieved from","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_1_29_1","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_30_1","volume-title":"Encyclopedia of Database Systems","author":"Liu Ling","unstructured":"Ling Liu and M. Tamer \u00d6zsu . 2018. Encyclopedia of Database Systems . Springer . Ling Liu and M. Tamer \u00d6zsu. 2018. Encyclopedia of Database Systems. Springer."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1093382.1093384"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182614"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_35_1","volume-title":"Database Theory and Application, Bio-Science and Bio-Technology","author":"Przymus Piotr","unstructured":"Piotr Przymus , Aleksandra Boniewicz , Marta Burza\u0144ska , and Krzysztof Stencel . 2010. Recursive query facilities in relational databases: A survey . In Database Theory and Application, Bio-Science and Bio-Technology . Springer , 89--99. Piotr Przymus, Aleksandra Boniewicz, Marta Burza\u0144ska, and Krzysztof Stencel. 2010. Recursive query facilities in relational databases: A survey. In Database Theory and Application, Bio-Science and Bio-Technology. Springer, 89--99."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 20th International Conference on Database Theory (ICDT\u201917)","volume":"68","author":"Schwentick Thomas","year":"2017","unstructured":"Thomas Schwentick , Nils Vortmeier , and Thomas Zeume . 2017 . Dynamic complexity under definable changes . In Proceedings of the 20th International Conference on Database Theory (ICDT\u201917) (LIPIcs), Michael Benedikt and Giorgio Orsi (Eds.) , Vol. 68 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 19:1--19:18. Retrieved from Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. 2017. Dynamic complexity under definable changes. In Proceedings of the 20th International Conference on Database Theory (ICDT\u201917) (LIPIcs), Michael Benedikt and Giorgio Orsi (Eds.), Vol. 68. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 19:1--19:18. Retrieved from"},{"key":"e_1_2_1_37_1","volume-title":"Dynamic complexity under definable changes. CoRR abs\/1701.02494","author":"Schwentick Thomas","year":"2017","unstructured":"Thomas Schwentick , Nils Vortmeier , and Thomas Zeume . 2017. Dynamic complexity under definable changes. CoRR abs\/1701.02494 ( 2017 ). Retrieved from http:\/\/arxiv.org\/abs\/1701.02494. Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. 2017. Dynamic complexity under definable changes. CoRR abs\/1701.02494 (2017). Retrieved from http:\/\/arxiv.org\/abs\/1701.02494."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948896.2948899"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2nd Conference on Software Engineering and Information Management (SEIM\u201917)","author":"Shalygina Galina","year":"2017","unstructured":"Galina Shalygina and Boris Novikov . 2017 . Implementing common table expressions for MariaDB . In Proceedings of the 2nd Conference on Software Engineering and Information Management (SEIM\u201917) . 12--17. Galina Shalygina and Boris Novikov. 2017. Implementing common table expressions for MariaDB. In Proceedings of the 2nd Conference on Software Engineering and Information Management (SEIM\u201917). 12--17."},{"key":"e_1_2_1_40_1","unstructured":"Sebastian Siebertz. 2011. Dynamic Definability. Diploma Thesis. RWTH Aachen. Sebastian Siebertz. 2011. Dynamic Definability. Diploma Thesis. RWTH Aachen."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/645338.650392"},{"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","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_46"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.04.005"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT\u201914)","author":"Zeume Thomas","year":"2014","unstructured":"Thomas Zeume and Thomas Schwentick . 2014 . Dynamic conjunctive queries . In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914) . 38--49. Retrieved from Thomas Zeume and Thomas Schwentick. 2014. Dynamic conjunctive queries. In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914). 38--49. Retrieved from"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.011"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3241040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T18:49:43Z","timestamp":1672512583000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3241040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,30]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3241040"],"URL":"https:\/\/doi.org\/10.1145\/3241040","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,30]]},"assertion":[{"value":"2017-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}