Document Open Access Logo

Dynamic Graph Queries

Authors Pablo Muñoz, Nils Vortmeier, Thomas Zeume

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.14.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

Pablo Muñoz
Nils Vortmeier
Thomas Zeume

Cite As Get BibTex

Pablo Muñoz, Nils Vortmeier, and Thomas Zeume. Dynamic Graph Queries. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICDT.2016.14

Abstract

Graph databases in many applications - semantic web, transport or biological networks among others - are not only large, but also frequently modified. Evaluating graph queries in this dynamic context is a challenging task, as those queries often combine first-order and navigational features. 

Motivated by recent results on maintaining dynamic reachability, we study the dynamic evaluation of traditional query languages for graphs in the descriptive complexity framework. Our focus is on maintaining regular path queries, and extensions thereof, by first-order formulas. In particular we are interested in path queries defined by non-regular languages and in extended conjunctive regular path queries (which allow to compare labels of paths based on word relations). Further we study the closely related problems of maintaining distances in graphs and reachability in product graphs.

In this preliminary study we obtain upper bounds for those problems in restricted settings, such as undirected and acyclic graphs, or under insertions only, and negative results regarding quantifier-free update formulas. In addition we point out interesting directions for further research.

Subject Classification

Keywords
  • Dynamic descriptive complexity
  • graph databases
  • graph products
  • reachability
  • path queries

Metrics

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

References

  1. Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys (CSUR), 40(1):1, 2008. Google Scholar
  2. Pablo Barceló Baeza. Querying graph databases. In Richard Hull and Wenfei Fan, editors, Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22-27, 2013, pages 175-188. ACM, 2013. URL: http://dl.acm.org/citation.cfm?id=2463664, URL: http://dx.doi.org/10.1145/2463664.2465216.
  3. Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. The MIT Press, 2008. Google Scholar
  4. Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter T. Wood. Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst., 37(4):31, 2012. URL: http://dx.doi.org/10.1145/2389241.2389250.
  5. Sanjoy Dasgupta, Christos H Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, Inc., 2006. Google Scholar
  6. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 159-170. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_13.
  7. Camil Demetrescu and Giuseppe F. Italiano. Mantaining dynamic matrices for fully dynamic transitive closure. Algorithmica, 51(4):387-427, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9051-4.
  8. Guozhu Dong and Jianwen Su. First-order incremental evaluation of datalog queries. In Catriel Beeri, Atsushi Ohori, and Dennis Shasha, editors, Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, Manhattan, New York City, USA, 30 August - 1 September 1993, Workshops in Computing, pages 295-308. Springer, 1993. Google Scholar
  9. Guozhu Dong and Rodney W. Topor. Incremental evaluation of datalog queries. In Joachim Biskup and Richard Hull, editors, Database Theory - ICDT'92, 4th International Conference, Berlin, Germany, October 14-16, 1992, Proceedings, volume 646 of Lecture Notes in Computer Science, pages 282-296. Springer, 1992. URL: http://dx.doi.org/10.1007/3-540-56039-4_48.
  10. Zvi Galil. Hierarchies of complete problems. Acta Informatica, 6(1):77-88, 1976. Google Scholar
  11. 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.
  12. Erich Grädel and Sebastian Siebertz. Dynamic definability. In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT'12, Berlin, Germany, March 26-29, 2012, pages 236-248. ACM, 2012. URL: http://dl.acm.org/citation.cfm?id=2274576, URL: http://dx.doi.org/10.1145/2274576.2274601.
  13. William Hesse. The dynamic complexity of transitive closure is in DynTC0. Theoretical Computer Science, 296(3):473-485, 2003. Google Scholar
  14. Peter Bro Miltersen. Cell probe complexity-a survey. In 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Google Scholar
  15. Pablo Muñoz, Nils Vortmeier, and Thomas Zeume. Dynamic graph queries. CoRR, abs/1512.05511, 2015. URL: http://arxiv.org/abs/1512.05511.
  16. 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.
  17. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. nSPARQL: A navigational language for RDF. J. Web Sem., 8(4):255-270, 2010. URL: http://dx.doi.org/10.1016/j.websem.2010.01.002.
  18. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput., 37(5):1455-1471, 2008. URL: http://dx.doi.org/10.1137/060650271.
  19. Dragan Stevanović. When is neps of graphs connected? Linear Algebra and its Applications, 301(1):137-144, 1999. Google Scholar
  20. 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.
  21. Peter T Wood. Query languages for graph databases. ACM SIGMOD Record, 41(1):50-60, 2012. Google Scholar
  22. Thomas Zeume. The dynamic descriptive complexity of k-clique. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 547-558. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44522-8_46.
  23. Thomas Zeume. Small Dynamic Complexity Classes. PhD thesis, TU Dortmund University, 2015. Google Scholar
  24. Thomas Zeume and Thomas Schwentick. Dynamic conjunctive queries. In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., pages 38-49. OpenProceedings.org, 2014. URL: http://openproceedings.org/edbticdt2014/ICDT_toc.html, URL: http://dx.doi.org/10.5441/002/icdt.2014.08.
  25. 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