  We survey foundational features underlying modern graph query languages. We
first discuss two popular graph data models: edge-labelled graphs, where nodes
are connected by directed, labelled edges; and property graphs, where nodes and
edges can further have attributes. Next we discuss the two most fundamental
graph 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 with graph patterns. We also discuss several semantics
under which queries using the previous features can be evaluated, what effects
the selection of features and semantics has on complexity, and offer examples
of such 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 what is known about
SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an
outline of possible future directions for the area.
