English
Graph data management – part 1
Post-edited
Auteurs : Martens, Wim (Auteur de la conférence)
CIRM (Editeur )
68P15 - Database theory
68Q19 - Descriptive complexity and finite models
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/1934/Slides/martens-graphs.pdf
CIRM (Editeur )
Loading the player...
|
| motivation of graph databases data models for graph data bases graph database queries query evaluation query containment |
Résumé :
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.
Codes MSC : 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.
68P15 - Database theory
68Q19 - Descriptive complexity and finite models
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/1934/Slides/martens-graphs.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de Publication : 09/05/2019 Date de Captation : 10/04/2019 Sous Collection : Research School Catégorie arXiv : Computer Science Domaine(s) : Analyse Numérique & Calcul Formel ; Informatique Format : MP4 (.mp4) - HD Durée : 01:26:16 Audience : Chercheurs Download : https://videos.cirm-math.fr/2019-04-10_Martens_Part_1.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Ecole de Printemps d'Informatique Théorique (EPIT) 2019 - Données, logique et automates / Spring school on Theoretical Computer Science (EPIT) - Databases, Logic and AutomataOrganisateurs de la Rencontre : Gheerbrant, Amélie ; Libkin, Leonid ; Segoufin, luc ; Senellart, Pierre ; Sirangelo, Cristina Dates : 08/04/2019 - 12/04/2019 Année de la rencontre : 2019 URL de la Rencontre : https://conferences.cirm-math.fr/1934.html
Données de citation
DOI : 10.24350/CIRM.V.19519403Citer cette vidéo: Martens, Wim (2019). Graph data management – part 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19519403 URI : http://dx.doi.org/10.24350/CIRM.V.19519403 |
Voir Aussi
- [Multi angle] Graph data management – part 2 / Auteur de la conférence Martens, Wim.
- [Multi angle] Semistructured data, logic, and automata – part 2 / Auteur de la conférence Figueira, Diego.
- [Multi angle] Databases and descriptive complexity – part 2 / Auteur de la conférence Schweikardt, Nicole.
- [Multi angle] Databases and descriptive complexity – part 1 / Auteur de la conférence Schweikardt, Nicole.
- [Multi angle] Semistructured data, logic, and automata – part 1 / Auteur de la conférence Figueira, Diego.
Bibliographie
- 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
