Property Graph database evaluation of exact path pattern matching queries

No Thumbnail Available

URL

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