Property Graph database evaluation of exact path pattern matching queries

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2020-08-18
Department
Major/Subject
Visual Computing and Communication
Mcode
SCI3102
Degree programme
Master's Programme in ICT Innovation
Language
en
Pages
55+5
Series
Abstract
In 2019, a new ISO standard for a Property Graph Database query language was approved. A working group is actively developing this new language, called GQL. It draws inspiration from existing languages developed by independent vendors and communities, expressing queries with the help of graph patterns. Graph pattern matching will become a field of interest in order to efficiently evaluate these queries that are highly dependent on the connectivity of data. An algorithm is proposed in order to evaluate these graph patterns, which makes use of an intermediate tree structure to build the result set. A comparison of runtime of the algorithm is carried out, with different variations of the algorithm that start the evaluation of the path patterns of the graph pattern at different locations. It is found that there is an advantage to starting path pattern evaluation by traversing it ways other than a standard left-to-right traversal, but that this is dependent on factors such as the path pattern itself, the graph size, and the estimated result set size.
Description
Supervisor
Vuorimaa, Petri
Thesis advisor
Saarela, Janne
Keywords
property graph database, GQL, query evaluation, pattern matching
Other note
Citation