CS Paper Radar

Rewriting Ontology-Mediated Property Graph Queries into GQL

Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, Magdalena Ortiz

cs.DB ·submitted 2026-08-20 14:23 UTC · v2
top venue

Abstract

Ontology-based data access is intended for graph data, but practical support remains limited to SQL-like languages lacking the navigational and path-matching features fundamental to graph querying. Theoretical algorithms for navigational queries have long been available. Still, they have never been implemented, largely because practical graph query languages fell short of their theoretical counterparts and lacked the expressive power needed to support rewriting common ontology languages. The recent standardisation efforts around GQL and SQL/PGQ finally allow us to overcome this barrier and present a practical query rewriting technique for ontology-mediated navigational graph queries. Ontologies are written in a DL-Lite variant tuned to property graphs, and the queries in a GQL fragment with nested two-way regular path queries and which can be evaluated in Cypher. Preliminary experiments with our proof-of-concept prototype suggest that querying graph data with ontological knowledge may finally be within reach.

DOI
10.1145/3799682.3841030

Closest papers

Nearest neighbours by meaning across the whole index.

MGQL: An Executable, Small-Step Semantics of GQL

cs.PL cs.DB ·2026-08-25 ·Aditya Thimmaiah, Tong-Nong Lin, Milos Gligoric
publishedtheory similarity 0.75
Abstract · Accepted at OOPSLA 2026

ISO Graph Query Language (GQL) is the first international standard for property graph-based graph query languages, standardized as ISO/IEC 39075 in 2024. However, ISO/IEC 39075 codifies its semantics informally across 600+ pages of prose, making it difficult to formally reason about the standard or for a standard-faithful implementation. Existing formalizations are not adequate because they either: (1) significantly reduce the semantic complexity by omitting bag semantics, schemas, and composite queries on multiple graphs; (2) or significantly reduce the syntactic complexity by only considering isolated fragments such as pattern-matching, leaving the full query pipeline unformalized. Yet it is these semantic-syntactic features that make formalizing GQL non-trivial. We present MGQL, the first mechanized, small-step operational semantics for a substantial read-only fragment of GQL that is grounded in the ISO/IEC 39075 standard. Our formalization models multi-graph property graphs with mixed edge directionality and supports a large fraction of GQL pattern constructs: quantified paths and edges, directional and undirected matching, label expressions, pattern lists, and composite queries. The semantics is supported by a schema-aware type system that refines variable types via closed-graph schemas, tracks nullability, supports multiple composite query operators, and models quantified-path bindings with list types. We prove that our type system is sound, ensuring an end-to-end guarantee of well-formed queries yielding results that conform to their declared schemas. MGQL provides the first bridge between GQL's informal specification and a mechanized implementation, enabling formal reasoning about correctness.

0.37

GQL Datatypes as an RDF Vocabulary

cs.DB ·2026-10-12 ·Dominik Tomaszuk, Daniel Szałaj
similarity 0.68
Abstract · 13 pages, 7 figures, 3 tables. Accepted for DMKG 2026 (2nd International Workshop on Data Management for Knowledge Graphs), Bari, Italy

The ISO GQL standard introduces a rich value-type system for property graphs, including scalar, temporal, byte-string, list, record, and dynamic union datatypes. The vocabulary presented here additionally covers a vector extension. At the same time, RDF-based knowledge graph systems identify literal datatypes by IRIs and interpret typed literals through value spaces, lexical spaces, and lexical-to-value mappings. This paper presents the GQL Datatypes RDF Vocabulary, a lightweight RDF vocabulary that represents selected GQL datatypes and the vector extension as RDF datatype IRIs and describes their hierarchy, aliases, and selected constraints using RDF, RDFS, OWL, and XML Schema Datatypes vocabulary terms. The vocabulary is intended to support interoperability between GQL-oriented property graph systems and RDF-based knowledge graph systems. We describe its namespace and datatype model, summarize its datatype coverage, and show how the accompanying generator and validator use the vocabulary. In the reference implementation, RDF literals retain GQL datatype IRIs; XSD mappings declared in the vocabulary support scalar validation, while lists, records, and vectors are encoded directly as JSON lexical forms of vocabulary-typed literals.

0.28

Property Graph Techniques in Relational Databases

cs.DB ·2026-08-11 ·Malcolm Crowe, Fritz Laux
published similarity 0.66
Abstract · 6 pages, 1 figure

Current developments in standardization activities for database management systems include the development of the next versions of the Structured Query Language (SQL), and related standards for labelled property graphs. This short paper explores mechanisms for unified implementation of record-based relational and property graph databases: its contribution is that modeling SQL foreign keys as reference keys facilitates the graph insert and advanced pattern matching mechanisms of Property Graph Database Management Systems (PGDMS) and allows the construction of multiple type graph models on a single relational database.

0.60

ArcRAG: Agentic Compositional Retrieval over Knowledge Graphs

cs.CL cs.AIcs.IR ·2026-11-04 ·Jyotin Goel, Abhinav Arun, Tejas Prakash Agarwal, Bhaskarjit Sarmah, Stefano Pasquali
similarity 0.65
Abstract · Preprint

Graph-based retrieval-augmented generation (GraphRAG) answers questions by retrieving over a knowledge graph built from a corpus. Yet retrieval strategies are designed around the structure their own construction pipeline produces, and whether they survive a change of construction is rarely tested. We study this cross-construction portability: whether one retrieval procedure, with no construction-specific schema, relation names, or retuning, stays effective when the graph is built differently. We introduce ArcRAG, which induces a query-local graph interface at inference time (the node labels, relation descriptors, and property keys reachable from the entities a question names), plans multi-hop traversals against it, and executes and repairs them as Cypher. We build each of the MuSiQue, HotpotQA, and TriviaQA corpora as a schema-guided graph (typed nodes, a closed relation set, source provenance) and as an open-information-extraction graph (untyped nodes, free-text relations), with the retriever's configuration fixed across them. We compare against a construction-agnostic Direct-Cypher agent, ablate each stage across retry and pass budgets on both graph families, and compare with results reported for prior GraphRAG systems, most of which design retrieval together with their own graph construction. Across the two constructions, we find that retrieval need not be co-designed with the graph: query-time interface induction keeps a construction-agnostic retriever effective when the construction changes, although construction still shapes absolute accuracy.

0.09

KGVoyager: Knowledge Graph Agnostic Question Answering via Agentic Navigation

cs.IR ·2026-09-01 ·Essam Wisam, Chengkai Li
similarity 0.64
Abstract · 16 pages, 12 figures, 13 tables

Knowledge Graph Question Answering (KGQA) over RDF graphs remains challenging in domain-specific settings, where formal ontologies and curated text-SPARQL pairs are often unavailable. We present KG Voyager, a KG-agnostic agentic architecture that generates SPARQL queries from natural language questions by dynamically discovering graph structure and semantics, requiring only a query endpoint of the underlying graph. Using a think-act-observe loop with search, exploration, and execution tools, KG Voyager maps terms to graph Internationalized Resource Identifiers (IRIs), uncovers structure, and refines queries through execution feedback -- all without pre-existing ontologies or examples. Unlike the prior state of the art, KG Voyager requires only a lightweight class index which renders it applicable for far more real-world endpoints. Across four benchmarks, KG Voyager improves F1 by $\sim$4 points on average compared to the state of the art while cutting cost by $\sim$38% and runtime by $\sim$24%.

0.26

Relational-Core Graph Analytics Querying graphs at SQL scale, and why the node/edge model is a performance tax, not a truer picture of connected data

cs.DB cs.AIcs.PL ·2026-09-01 ·Gene Zhang
benchmarkposition similarity 0.63
Abstract

A durable assumption holds that graph analytics requires a purpose-built graph engine, and that relational systems are ill-suited to connected data. We argue the opposite for the workloads enterprises actually run. A columnar relational engine fronted by a graph query language matches or exceeds native graph engines on analytical graph queries, and - decisively - scales past the point where in-memory graph engines fail. We further argue that the node/edge property graph is not a more faithful model of connected data but a re-encoding of relationships that already exist explicitly in relational tables; reconstructing them at query time is pure overhead. We present ClickGraph and its Databricks-dialect sibling DeltaGraph, systems that translate Cypher directly onto the native relational schema - the tables, columns, and foreign keys as they already exist - and execute in place on ClickHouse, Databricks, or in-process on lakehouse files, with no import and no separate cluster. Because the output is ordinary SQL, an underperforming query is an open optimization surface: it can be rewritten, and the engine itself extended. We support the argument with a peer system's own published benchmark, in which a columnar engine outruns Neo4j by two-to-four orders of magnitude, and with reproducible measurements across the LDBC Social Network Benchmark suite.

0.19

Build2SPARQL: A Large-Scale Text-to-SPARQL Benchmark Dataset for Building Knowledge Graph Querying

cs.AI ·2026-09-22 ·Wooyoung Jung
benchmarkcode/data similarity 0.63
Abstract · 26 pages, 2 figures, 16 tables. Data paper. Dataset openly available at https://zenodo.org/records/20451474. Under review at the ASCE Journa…

Building automation systems are increasingly represented as semantic knowledge graphs (KGs) using ontologies such as Brick and ASHRAE 223P, creating a machine-readable substrate for artificial-intelligence applications. One promising application is translating natural-language questions into SPARQL (text-to-SPARQL), which would let building operators query these graphs through language agents, but progress is limited by the scarcity of large natural-language/SPARQL benchmarks. This paper presents Build2SPARQL, a large-scale benchmark for building KGs generated by a KG-grounded pipeline: SPARQL queries are produced and validated entirely by graph-traversal code, while large language models generate only the natural-language questions, keeping query correctness independent of model behavior. The pipeline mines six query-pattern families -- linear chains, branching, UNION, aggregation, OPTIONAL, and attribute-filtered -- and phrases each query across five vocabulary registers. Applied to 201 building KGs (180 Brick, 21 ASHRAE 223P), it yields 6,136 executable SPARQL queries and 30,680 questions. A two-rater human validation of 300 questions found 98.8% semantic fidelity, 98.8% naturalness, and 84.0% operational plausibility. A retrieval-augmented evaluation across three open-weight language models raised exact-match accuracy from 0.2-20% (zero-shot) to 56-65% (three-shot retrieved).

0.21

An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation

cs.DB ·2026-08-12 ·Wolfgang Gatterbauer
top venue similarity 0.62
Abstract · 7 pages, VLDB 2026 tutorial, tutorial page: https://northeastern-datalab.github.io/relational-language-tutorial/

Relational query languages have been studied and used for more than 50 years, with SQL dominant in practice. Today, queries are increasingly generated by machines and read by humans. At the same time, the landscape also includes dataframe, pipeline, logical, functional, graph, and relational programming notations. These developments invite two related questions beyond expressive power: which relational structures do languages make explicit, and how well can notation support users in reading and revising queries? This 3-hour tutorial extends an earlier SIGMOD'26 tutorial in three directions: recursive and path queries (connecting relational and graph query languages), nested relational data, and relational languages for problems beyond PTIME. Rather than beginning from formal definitions, we start from example queries and compare how different languages express the same intent. To compare recurring structure across notations, we use Abstract Relational Calculus (ARC) and Relational Diagrams as reference representations. From these examples, we develop a vocabulary for relational language design, including information need, query mapping, relational pattern structure, relational pattern denotation, and semantic conventions. Participants will leave with a framework for comparing existing and future relational languages, a precise vocabulary for articulating design trade-offs, and a concrete set of examples connecting classical database languages with alternative proposals.

0.48