Representing Paths in Graph Database Pattern Matching
Proceedings of the VLDB Endowment · 2023-03 · 16 (7) · 1790-1803
DOI: 10.14778/3587136.3587151 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 08.05.2023. Verfasst von Wim Martens und 5 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 63 Literaturangaben.
Abstract (Originalsprache)
Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that their pattern matching facility can return paths , as opposed to only nodes and edges. This is challenging for database engines, since graphs can have a large number of paths between a given node pair, which can cause huge intermediate results in query evaluation. We introduce the concept of path multiset representations (PMRs) , which can represent multisets of paths exponentially succinctly and therefore bring significant advantages for representing intermediate results. We give a detailed theoretical analysis that shows that they are especially well-suited for representing results of regular path queries and extensions thereof involving counting, random sampling, and unions. Our experiments show that they drastically improve scalability for regular path query evaluation, with speedups of several orders of magnitude.
Zitieren
APA
Martens, W., Niewerth, M., Popp, T., Rojas, C., Vansummeren, S., & Vrgoč, D. (2023). Representing Paths in Graph Database Pattern Matching. Proceedings of the VLDB Endowment, 16(7), 1790-1803. https://doi.org/10.14778/3587136.3587151
Vancouver
Martens W, Niewerth M, Popp T, Rojas C, Vansummeren S, Vrgoč D. Representing Paths in Graph Database Pattern Matching. Proceedings of the VLDB Endowment. 2023;16(7):1790-1803. doi:10.14778/3587136.3587151
BibTeX
@article{Martens2023,
author = {Martens, Wim and Niewerth, Matthias and Popp, Tina and Rojas, Carlos and Vansummeren, Stijn and Vrgoč, Domagoj},
title = {Representing Paths in Graph Database Pattern Matching},
journal = {Proceedings of the VLDB Endowment},
year = {2023},
volume = {16},
number = {7},
pages = {1790--1803},
doi = {10.14778/3587136.3587151}
}
EUVIMED