Graph data management – part 2 | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Graph data management – part 2

Appears in collection : Ecole de Printemps d'Informatique Théorique (EPIT) 2019 - Données, logique et automates / Spring school on Theoretical Computer Science (EPIT) - Databases, Logic and Automata

After giving a motivation of graph databases and an overview of the main data models, we will dive into foundational aspects of graph database query languages, with a strong focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will consider the different semantics that graph database systems use for such queries (every path, simple path, trail), and we will look into the computational complexities of query evaluation and query containment. After having gone through these foundations, we plan to do some excursions into connections between tree-structured and graph-structured data, adding data value comparisons, and aspects of real-life queries.

Information about the video

Date of recording 10/04/2019
Date of publication 13/05/2019
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Guillaume Hennenfent
Format MP4

Citation data

DOI 10.24350/CIRM.V.19519703
Cite this video Martens, Wim (10/04/2019). Graph data management – part 2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19519703
URL https://dx.doi.org/10.24350/CIRM.V.19519703

Domain(s)

Bibliography

Angles, Renzo, Marcelo Arenas, Pablo Barceló, Peter Boncz, George Fletcher, Claudio Gutierrez, Tobias Lindaaker et al. "G-CORE: A core for future graph query languages." In Proceedings of the 2018 International Conference on Management of Data, pp. 1421-1432. ACM, 2018 - https://doi.org/10.1145/3183713.3190654
Gaifman, Haim. "On local and non-local properties." In Studies in Logic and the Foundations of Mathematics, vol. 107, pp. 105-135. Elsevier, 1982 - https://doi.org/10.1016/s0049-237x(08)71879-2
Hanf, W. "Model-theoretic methods in the study of elementary logic, in “The Theory of Models”(J. Addison, L. Henkin, and A. Tarski, Eds.)." (1965): 132
Cruz, Isabel F., Alberto O. Mendelzon, and Peter T. Wood. "A graphical query language supporting recursion." In ACM SIGMOD Record, vol. 16, no. 3, pp. 323-330. ACM, 1987 - http://dx.doi.org/10.1145/38714.38749
LaPaugh, Andrea S., and Christos H. Papadimitriou. "The even‐path problem for graphs and digraphs." Networks 14, no. 4 (1984): 507-513 - http://dx.doi.org/10.1002/net.3230140403
Calvanese, Diego, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. "Containment of conjunctive regular path queries with inverse." KR 2000 (2000): 176-185. - http://www.dis.uniroma1.it/~degiacom/papers/2000/CDLV00kr.pdf
Miklau, Gerome, and Dan Suciu. "Containment and equivalence for a fragment of XPath." Journal of the ACM (JACM) 51, no. 1 (2004): 2-45 - http://dx.doi.org/10.1145/962446.962448
CzerwiŃski, Wojciech, Wim Martens, Matthias Niewerth, and Paweł Parys. "Minimization of Tree Patterns." Journal of the ACM (JACM) 65, no. 4 (2018): 26. - http://dx.doi.org/10.1145/3180281
MIKLAU, Gerome et SUCIU, Dan. Containment and equivalence for a fragment of XPath. Journal of the ACM (JACM), 2004, vol. 51, no 1, p. 2-45 - https://doi.org/10.1145/962446.962448
CZERWIŃSKI, Wojciech, MARTENS, Wim, NIEWERTH, Matthias, et al. Minimization of Tree Patterns. Journal of the ACM (JACM), 2018, vol. 65, no 4, p. 26. - https://doi.org/10.1145/3180281
FOMIN, Fedor V., LOKSHTANOV, Daniel, PANOLAN, Fahad, et al. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM (JACM), 2016, vol. 63, no 4, p. 29. - https://doi.org/10.1145/2886094

MSC codes

Document(s)

https://www.cirm-math.fr/RepOrga/1934/Slides/martens-graphs.pdf

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback