mlsanityData to 7 Oct 2026

Foundations of Modern Query Languages for Graph Databases

arXiv 1610.06264 ↗First posted 20 Oct 2016cs.DBcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 3; 2024: 3; 2025: 4; 2026: 4.

22 papers.

Sort:

By area:

  1. 2022GraphQ IR: Unifying the Semantic Parsing of Graph Query Languages with One Intermediate Representationcited by 13
  2. 2022Neural Graph Databasescited by 11
  3. 2025Large Language Models, Knowledge Graphs and Search Engines: A Crossroads for Answering Users' Questionscited by 8
  4. 2022Unveiling the Black Box of PLMs with Semantic Anchors: Towards Interpretable Neural Semantic Parsingcited by 5
  5. 2023Knowledge Graphs Queryingcited by 5
  6. 2023A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphscited by 4
  7. 2025Personalizing Large Language Models using Retrieval Augmented Generation and Knowledge Graphcited by 3
  8. 2021Querying in the Age of Graph Databases and Knowledge Graphscited by 2
  9. 2024Construction of Hyper-Relational Knowledge Graphs Using Pre-Trained Large Language Modelscited by 2
  10. 2021Subgraph nomination: Query by Example Subgraph Retrieval in Networkscited by 1
  11. 2021Creating Knowledge Graphs Subsets using Shape Expressionscited by 1
  12. 2022On the complexity of finding set repairs for data-graphscited by 1
10 more
  1. 2023Current and Future Challenges in Knowledge Representation and Reasoningcited by 1
  2. 2022Absolute Expressiveness of Subgraph-based Centrality Measurescited by 0
  3. 2024Mining Path Association Rules in Large Property Graphs (with Appendix)cited by 0
  4. 2024Graph Neural Networks on Graph Databasescited by 0
  5. 2025Higher-Order Graph Databasescited by 0
  6. 2025SHARP: Shared State Reduction for Efficient Matching of Sequential Patternscited by 0
  7. 2026Graphs RAG at Scale: Beyond Retrieval-Augmented Generation With Labeled Property Graphs and Resource Description Framework for Complex and Unknown Search Spacescited by 0
  8. 2026WikiKV: Schema-Evolving Path-Indexed Storage for Hierarchical Knowledge Navigationcited by 0
  9. 2026Hidden relationships in a document-derived property graph: top-k chunk embeddings and inverse-distance weighting over a dynamically evolving ontologycited by 0
  10. 2026TCMaster: Confidence-Aware Querying and Workload-Guided Physical Design for Multi-Source Traditional Chinese Medicine Knowledge Graphscited by 0