# Foundations of Modern Query Languages for Graph Databases

arXiv: https://arxiv.org/abs/1610.06264 · HTML: https://mlsanity.com/paper/1610.06264/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2016.

## Built on by (most cited first, 22 of 22)

- [GraphQ IR: Unifying the Semantic Parsing of Graph Query Languages with One Intermediate Representation](https://mlsanity.com/paper/2205.12078/) (2022)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [Large Language Models, Knowledge Graphs and Search Engines: A Crossroads for Answering Users' Questions](https://mlsanity.com/paper/2501.06699/) (2025)
- [Unveiling the Black Box of PLMs with Semantic Anchors: Towards Interpretable Neural Semantic Parsing](https://mlsanity.com/paper/2210.01425/) (2022)
- [Knowledge Graphs Querying](https://mlsanity.com/paper/2305.14485/) (2023)
- [A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs](https://mlsanity.com/paper/2310.04598/) (2023)
- [Personalizing Large Language Models using Retrieval Augmented Generation and Knowledge Graph](https://mlsanity.com/paper/2505.09945/) (2025)
- [Querying in the Age of Graph Databases and Knowledge Graphs](https://mlsanity.com/paper/2106.11456/) (2021)
- [Construction of Hyper-Relational Knowledge Graphs Using Pre-Trained Large Language Models](https://mlsanity.com/paper/2403.11786/) (2024)
- [Subgraph nomination: Query by Example Subgraph Retrieval in Networks](https://mlsanity.com/paper/2101.12430/) (2021)
- [Creating Knowledge Graphs Subsets using Shape Expressions](https://mlsanity.com/paper/2110.11709/) (2021)
- [On the complexity of finding set repairs for data-graphs](https://mlsanity.com/paper/2206.07504/) (2022)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Graph Neural Networks on Graph Databases](https://mlsanity.com/paper/2411.11375/) (2024)
- [Absolute Expressiveness of Subgraph-based Centrality Measures](https://mlsanity.com/paper/2206.06137/) (2022)
- [Mining Path Association Rules in Large Property Graphs (with Appendix)](https://mlsanity.com/paper/2408.02029/) (2024)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [SHARP: Shared State Reduction for Efficient Matching of Sequential Patterns](https://mlsanity.com/paper/2507.04872/) (2025)
- [Graphs RAG at Scale: Beyond Retrieval-Augmented Generation With Labeled Property Graphs and Resource Description Framework for Complex and Unknown Search Spaces](https://mlsanity.com/paper/2603.22340/) (2026)
- [WikiKV: Schema-Evolving Path-Indexed Storage for Hierarchical Knowledge Navigation](https://mlsanity.com/paper/2606.14275/) (2026)
- [Hidden relationships in a document-derived property graph: top-k chunk embeddings and inverse-distance weighting over a dynamically evolving ontology](https://mlsanity.com/paper/2609.00387/) (2026)
- [TCMaster: Confidence-Aware Querying and Workload-Guided Physical Design for Multi-Source Traditional Chinese Medicine Knowledge Graphs](https://mlsanity.com/paper/2609.25712/) (2026)

## Abstract (arXiv)

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.