Document Open Access Logo

Dynamic Complexity under Definable Changes

Authors Thomas Schwentick, Nils Vortmeier, Thomas Zeume

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2017.19.pdf
  • Filesize: 0.58 MB
  • 18 pages

Document Identifiers

Author Details

Thomas Schwentick
Nils Vortmeier
Thomas Zeume

Cite As Get BibTex

Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity under Definable Changes. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICDT.2017.19

Abstract

This paper studies dynamic complexity under definable change operations in the DynFO framework by Patnaik and Immerman. It is shown that for changes definable by parameter-free first-order formulas, all (uniform) AC1 queries can be maintained by first-order dynamic programs. Furthermore, many maintenance results for single-tuple changes are extended to more powerful change operations: (1) The reachability query for undirected graphs is first-order maintainable under single tuple changes and first-order defined insertions, likewise the reachability query for directed acyclic graphs under quantifier-free insertions. (2) Context-free languages are first-order maintainable under \EFO-defined changes. These results are complemented by several inexpressibility results, for example, that the reachability query cannot be maintained by quantifier-free programs under definable, quantifier-free deletions.

Subject Classification

Keywords
  • dynamic descriptive complexity
  • SQL updates
  • dynamic programs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Tom J. Ameloot, Jan Van den Bussche, and Emmanuel Waller. On the expressive power of update primitives. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 139-150, 2013. URL: http://dx.doi.org/10.1145/2463664.2465218.
  2. Samir Datta, William Hesse, and Raghav Kulkarni. Dynamic complexity of directed reachability and other problems. In Automata, Languages, and Programming - 41st International Colloquium (ICALP), Proceedings, Part I, pages 356-367, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_30.
  3. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. In Automata, Languages, and Programming - 42nd International Colloquium (ICALP), Proceedings, Part II, pages 159-170, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_13.
  4. Guozhu Dong, Leonid Libkin, and Limsoon Wong. On impossibility of decremental recomputation of recursive queries in relational calculus and SQL. In Proceedings of the Fifth International Workshop on Database Programming Languages (DBPL-5), page 7, 1995. Google Scholar
  5. Guozhu Dong and Chaoyi Pang. Maintaining transitive closure in first order after node-set and edge-set deletions. Inf. Process. Lett., 62(4):193-199, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00066-5.
  6. Guozhu Dong and Jianwen Su. First-order incremental evaluation of datalog queries. In Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages (DBPL-4), pages 295-308, 1993. Google Scholar
  7. Guozhu Dong and Jianwen Su. Incremental and decremental evaluation of transitive closure by first-order queries. Inf. Comput., 120(1):101-106, 1995. URL: http://dx.doi.org/10.1006/inco.1995.1102.
  8. Guozhu Dong, Jianwen Su, and Rodney W. Topor. Nonrecursive incremental evaluation of datalog queries. Ann. Math. Artif. Intell., 14(2-4):187-223, 1995. URL: http://dx.doi.org/10.1007/BF01530820.
  9. Guozhu Dong and Rodney W. Topor. Incremental evaluation of datalog queries. In Proceedings of the 4th International Conference on Database Theory (ICDT), pages 282-296, 1992. URL: http://dx.doi.org/10.1007/3-540-56039-4_48.
  10. Kousha Etessami. Dynamic tree isomorphism via first-order updates. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 235-243, 1998. URL: http://dx.doi.org/10.1145/275487.275514.
  11. Solomon Feferman. Some recent work of Ehrenfeucht and Fraïssé. In Proc. Summer Institute of Symbolic Logic, pages 201-209, 1957. Google Scholar
  12. Solomon Feferman and Robert L. Vaught. The first order properties of algebraic systems. Fund. Math., 47:57-103, 1959. Google Scholar
  13. Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012. URL: http://dx.doi.org/10.1145/2287718.2287719.
  14. Erich Grädel and Sebastian Siebertz. Dynamic definability. In 15th International Conference on Database Theory (ICDT), pages 236-248, 2012. URL: http://dx.doi.org/10.1145/2274576.2274601.
  15. Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 157-166, 1993. URL: http://dx.doi.org/10.1145/170035.170066.
  16. William Hesse. Dynamic Computational Complexity. PhD thesis, University of Massachusetts Amherst, 2003. Google Scholar
  17. William Hesse and Neil Immerman. Complete problems for dynamic complexity classes. In 17th IEEE Symposium on Logic in Computer Science (LICS), Proceedings, page 313, 2002. URL: http://dx.doi.org/10.1109/LICS.2002.1029839.
  18. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0539-5.
  19. Christoph Koch. Incremental query evaluation in a ring of databases. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 87-98, 2010. URL: http://dx.doi.org/10.1145/1807085.1807100.
  20. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. Google Scholar
  21. Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught Theorem. Ann. Pure Appl. Logic, 126(1-3):159-213, 2004. URL: http://dx.doi.org/10.1016/j.apal.2003.11.002.
  22. Chaoyi Pang, Guozhu Dong, and Kotagiri Ramamohanarao. Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL. ACM Trans. Database Syst., 30(3):698-721, 2005. URL: http://dx.doi.org/10.1145/1093382.1093384.
  23. Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1520.
  24. Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic complexity under definable changes. CoRR, abs/1701.02494, 2017. URL: http://arxiv.org/abs/1701.02494.
  25. Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: http://dx.doi.org/10.1145/2948896.2948899.
  26. Sebastian Siebertz. Dynamic definability. Diploma thesis, RWTH Aachen, 2011. Google Scholar
  27. Nils Vortmeier. Komplexitätstheorie verlaufsunabhängiger dynamischer Programme. Master’s thesis, TU Dortmund, 2013. Google Scholar
  28. Volker Weber and Thomas Schwentick. Dynamic complexity theory revisited. Theory Comput. Syst., 40(4):355-377, 2007. URL: http://dx.doi.org/10.1007/s00224-006-1312-0.
  29. Thomas Zeume. The dynamic descriptive complexity of k-clique. In Mathematical Foundations of Computer Science (MFCS) - 39th International Symposium, Proceedings, Part I, pages 547-558, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44522-8_46.
  30. Thomas Zeume. Small Dynamic Complexity Classes. PhD thesis, TU Dortmund University, 2015. Google Scholar
  31. Thomas Zeume and Thomas Schwentick. Dynamic conjunctive queries. In Proc. 17th International Conference on Database Theory (ICDT), pages 38-49, 2014. URL: http://dx.doi.org/10.5441/002/icdt.2014.08.
  32. Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of reachability. Inf. Comput., 240:108-129, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.09.011.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact