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. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.  The past decade has seen a resurgence of interest in graph databases, wherein entities from the domain of interest are represented by nodes and relationships between them by edges. Part of this resurgence stems from the growing realisation that there are a variety of domains for which graph databases offer a more intuitive conceptualisation than their more well-established relational cousins. For example, one can view a social network as a graph of people who know each other. One may likewise view transport networks, biological pathways, citation networks, and so on, as a graph. Although graphs can still be (and sometimes still are) stored in relational databases, the choice to use a graph database for certain domains has significant benefits in terms of querying, where the emphasis shifts from joining various tables to specifying graph patterns and navigational patterns between nodes that may span arbitrary-length paths. Scope. Our goal in this survey is to give an in-depth discussion of the main conceptual features found in modern graph query languages, as both supported by graph database engines and studied in the theoretical literature. By organising our survey at the level of query features, rather than languages, we provide a foundational introduction to the area, which helps to understand, and even define, individual query languages as the composition of features. We consider two highlevel categories of query features: graph patterns and path expressions. These features collectively form the core of a variety of modern graph query languages ( After introducing and defining the graph query features in each category, we list various semantics under which such features can be evaluated, provide examples of how such features are applied in a selection of modern query languages, discuss the computational complexity of key problems underlying such features, and present some of their most important extensions as implemented in modern graph database engines. We wrap up by drawing all of the foundational discussion together into a summary of the types of features we have covered, how these features can be used to understand the complexity and expressivity of modern query languages, the importance of formalisation for such languages, the key challenges underlying their implementation and optimisation in practical engines, and possible ways in which they might evolve. Survey Structure. The survey is structured as follows: -We first discuss two graph data models in Section 2: edge-labelled graphs, which is the foundational model considered in the graph database literature, and property graphs, which is a model commonly employed in practice, where nodes and edges in labelled graphs can be annotated with additional meta-information. -In Section 3, we discuss graph patterns, where a graph-structured query is matched against the graph database. We also discuss the extension of such graph patterns with additional operators, such as projection, difference, union, and so on. -Section 4 then introduces navigational expressions, which, unlike graph patterns, can match paths of arbitrary length. -In Section 5, we present our final remarks. Online Appendix. An online appendix for this article contains several aspects of graph query languages that, while not mainstream, have enjoyed some coverage in the research literature and in practical systems. These include an alternative semantics for matching patterns to graphs;
Recently, Angles et al. REF presented a study on fundamental graph querying functionalities (mainly graph patterns and navigational queries) and their implementation in modern graph query languages.
Foundations of Modern Query Languages for Graph Databases
CSUR
Computer Science