Foundations of Modern Graph Query Languages

Abstract

We survey foundational features underlying modern graph query languages. We first discuss two populargraph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges; and propertygraphs, where nodes and edges can further have attributes. Next we discuss the two most fundamentalgraph querying functionalities: graph patterns and navigational expressions. We start with graph patterns,in which a graph-structured query is matched against the data. Thereafter we discuss navigational expressions,in which patterns can be matched recursively against the graph to navigate paths of arbitrary length;we give an overview of what kinds of expressions have been proposed, and how they can be combined withgraph patterns. We also discuss several semantics under which queries using the previous features can beevaluated, what effects the selection of features and semantics has on complexity, and offer examples ofsuch features in three modern languages that are used to query graphs: SPARQL, Cypher and Gremlin.We conclude by discussing the importance of formalisation for graph query languages; a summary of whatis known about SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an outline ofpossible future directions for the area.