Analyse und Vergleich von gängigen Graph-Anfragesprachen

Abstract

Graphdatenbanken werden immer öfter verwendet um vernetzte Daten abzuspeichern. Viele dieser Systeme bieten ein flexibles Datenmodell basierend auf property graphs, das sind Graphen wo Knoten und Kanten mit Tags gekennzeichnet und weitere Eigenschaften in Schlüssel-Wert Paaren gespeichert werden können. Um auf Daten in solch einer Datenbank zuzugreifen verwendet man Anfragesprachen. Im Unterschied zu relationalen Datenbanken, wo SQL die standardisierte Anfragesprache ist, gibt es noch keine standardisierte Anfragesprache für Graphdatenbanken. Nutzer können daher von einer breiten Palette an Sprachen wählen die sich in dem verwendeten Datenmodell, der Ausdrucksstärke, der Einfachheit der Verwendung und so weiter unterscheiden. Das Ziel dieser Arbeit ist ein systematischer Vergleich von solchen Sprachen. Daraus wollen wir Hilfestellungen zur Sprachauswahl bei bestimmten Anwendungsfällen ableiten. In einem ersten Schritt identifizieren und analysieren wir Kernfunktionen die in allen Anfragesprachen für Graphdatenbanken vorhanden sind. Dazu zählt das Finden von Teilgraphen anhand von Graphmustern (patterns), von Pfaden mittels Pfadanfragen (path queries) und die Kombination dieser beiden zu Navigationsanfragen (navigational queries). Wir erweitern diese Funktionen um strukturunabhängige Anfragen sowie Datenmanipulations- und Datendefinitions- Operationen. Anhand dieser Funktionen analysieren wir fünf moderne Anfragesprachen für Graphdatenbanken: Cypher, Gremlin, PGQL, GSQL und G-CORE. Wir analysieren die Sprachen nicht nur anhand von generellen Charakteristika, sondern implementieren auch Teile des „Social Network Benchmarks“ und analysieren diese Anfragen. Es stellt sich heraus, dass Cypher, PGQL und G-CORE eine ähnliche Syntax verwenden sowie ähnlich ausdrucksstark und einfach zu verwenden sind. Auf der anderen Seite ähneln sich GSQL und Gremlin: beide sind Turing-vollständig und unterstützen nicht nur deklarative, sondern auch imperative Konstruktionen.

Graph databases are increasingly adopted in industry as they offer native support for graph-like data. Many such systems use a flexible data model based on property graphs, these are graphs where vertices and edges can be labeled and augmented with key-value pairs, the properties. Data stored in such a database is accessed via graph query languages. Unlike SQL, that is the standardized query language for relational databases, there is no standard for a graph query language yet. Users can therefore choose from a range of languages that vary in their specific data model, expressiveness, ease of use and so on. The goal of this thesis is a systematic comparison of graph query languages and to give guidelines for choosing a language for specific application scenarios. Towards achieving this goal, we identify and analyze core features inherent to such languages. The most common ones are subgraph discovery by matching graph patterns, path discovery using path queries and the combination of both in navigational queries. We extend these features to also include structure independent queries as well as data manipulation and data definition operations. Based on these features, we then analyze five contemporary graph query languages: Cypher, Gremlin, PGQL, GSQL and G-CORE. The analysis is not only based on general characteristics of the languages as we also implement parts of the Social Network Benchmark and analyze these queries. It turns out that Cypher, PGQL and G-CORE are quite similar in their syntax, expressiveness and ease of use. On the other hand, GSQL and Gremlin share some similarities as they are both Turing-complete languages that are not solely declarative but also offer imperative constructs.