Carmin.tv

Mathématiques
et Interactions

Merci de nous donner votre avis pour que nous puissions améliorer votre expérience !
Hadamard Lectures 2025 – Thomas Hutchcroft –Dimension Dependence of Critical Phenomena in Percolation
5 videos

Hadamard Lectures 2025 – Thomas Hutchcroft –Dimension Dependence of Critical Phenomena in Percolation

Families of Kähler spaces / Familles d'espaces kählériens
4 videos

Families of Kähler spaces / Familles d'espaces kählériens

Dispersive Integrable Equations: Pathfinders in Infinite-Dimensional Hamiltonian Systems / Équations Intégrables Dispersives, Pionniers des Systèmes Hamiltoniens en Dimension Infinie
5 videos

Dispersive Integrable Equations: Pathfinders in Infinite-Dimensional Hamiltonian Systems / Équations Intégrables Dispersives, Pionniers des Systèmes Hamiltoniens en Dimension Infinie

Not Only Scalar Curvature Seminar
74 videos

Not Only Scalar Curvature Seminar

Toutes les collections
CIMPA
CIRM
IHES
IHP
LMR
SMF
Tous les instituts
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

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

Organisateur(s) Gheerbrant, Amélie ; Segoufin, luc ; Senellart, Pierre ; Sirangelo, Cristina ; Libkin, Leonid
Date(s) 08/04/2019 - 12/04/2019
URL associée https://conferences.cirm-math.fr/1934.html
00:00:00 / 00:00:00
3 6

Chapitres

Graph data management – part 1

De Wim Martens

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.

Informations sur la vidéo

Données de citation

  • DOI 10.24350/CIRM.V.19519403
  • Citer cette vidéo Martens, Wim (10/04/2019). Graph data management – part 1. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19519403
  • URL https://dx.doi.org/10.24350/CIRM.V.19519403

Domaine(s)

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

Codes MSC

Document(s)

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Copyright Carmin.tv 2025
En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies pour améliorer votre expérience. En savoir plus sur notre politique de confidentialité.
Accepter
Donner son avis