Property Graph database evaluation of exact path pattern matching queries

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.