A new preprint reports a method for translating ontology-mediated navigational property-graph queries into executable Cypher, allowing a graph database to evaluate the resulting query without being made ontology-aware. The formal result is paired with a warning from the tests: the rewriting search could not finish for 62 of 100 generated queries with at least 30 states, and the DBPedia evaluation figure reports 56 timeouts at 20 seconds.
Within its stated formal model, the paper says Algorithm 1 is sound and complete for the join-on-free rewriting procedure. In ordinary terms, the procedure is intended to keep the ontology-derived certain answers while changing how the query is represented for execution. The result addresses whether the rewrite preserves the intended answers, while the experiments address how long the rewrite and its execution take.
The problem the method tackles
The paper frames its task as compiling ontology reasoning into a semantically equivalent property-graph query. Here, ontology reasoning means using formal descriptions of concepts and relationships when deciding which answers should count. The resulting query is intended to be evaluated by a graph database that has not itself been made ontology-aware.
The proposed method covers two formal path-query forms, 2RPQs and N2RPQs, with DL-Lite ontologies. For conjunctive N2RPQs—queries that combine several such patterns—it supports only the join-on-free subset. That boundary matters because the formal guarantee is attached to the stated fragment, not to every possible conjunctive graph query.
At the implementation level, the method turns the rewritten result into Cypher, the query language used in the prototype's graph-database tests. The prototype was written in Java and used OWL API, Hermit, ANTLR, JgraphT and Cypher DSL for ontology handling, reasoning, parsing, automata representation and Cypher conversion.
The tests behind the claim
The evaluation used two ontology–dataset pairs: DBPedia and MMM. The reported DBPedia row contains 1,230 concepts, 1,212 roles, 10,075,182 nodes and 22,194,296 relations. The MMM row contains 53 concepts, 18 roles, 107,624 nodes and 379,002 relations.
The reported workload consisted of 100 synthetic N2RPQs and five handcrafted MMM queries. The paper notes that benchmark queries were unavailable, so those workloads formed the basis of the experiments described in the preprint.
The tests ran on one virtual machine with 400 GB of RAM and 16 CPU cores, using Debian GNU/Linux 12, an AMD EPYC 7313 processor at 2.00 GHz and Neo4j 5.25.0. The timings therefore come from a specific hardware and software setup.
Fast translation, harder follow-through
The first timing result was relatively quick. Rewriting was generally under 250 milliseconds for DBPedia and around 600 milliseconds for MMM. These figures concern the step that constructs the executable query; they do not describe the subsequent time taken by Neo4j to evaluate it.
The rewriting step also exposed a computational bottleneck. To explore possible rewrites, the procedure used a power-set computation; that calculation was infeasible for 62 of the 100 generated queries when a query had at least 30 states. Those cases were therefore not carried through the reported rewriting search.
On DBPedia, query evaluation showed two patterns. Queries either completed in 2 to 8 seconds or reached a 20-second timeout. The evaluation figure reports 56 timeouts at the 20-second mark.
MMM produced a similar warning, though its reported workload was only five handcrafted queries: three of the five timed out. That result sits alongside the roughly 600-millisecond rewriting time, underscoring the difference between preparing a query and evaluating it.
What the results do—and do not—show
The generated queries returned no answers, and optimizing their evaluation was outside the study's scope. That leaves an important part of the practical question open: the tests show how the rewriting process behaved and whether the database crossed the timeout threshold, but they do not stress retrieval of nonempty result sets.
Taken together, the results separate a formal success from an engineering problem. The paper reports sound and complete rewriting for the join-on-free procedure, but the reported workloads also contain rewrite-search failures and database timeouts. The evidence supports a method for preserving the intended query semantics in the stated fragment; it does not, on these tests alone, settle how reliably the approach will execute as workloads become more demanding.
The restriction to join-on-free CN2RPQs is central to that reading. The method's stated scope includes 2RPQs and N2RPQs with DL-Lite ontologies, but not an unrestricted set of conjunctive N2RPQs. Any extension beyond that boundary would be a new test of both the rewriting procedure and its performance.
For readers trying to judge what has been demonstrated, the clearest conclusion is narrow but useful: the preprint presents a formal route from ontology-mediated graph-query reasoning to executable Cypher, with a soundness-and-completeness claim in a restricted fragment. Its measurements show that the translation itself can be relatively quick, while search complexity and query execution can still stop the workload before completion.
A prototype still in development
The prototype's availability is also limited in the supplied record. Its source code was shared anonymously and was said to be planned for future public release. The work reports support from the Austrian Science Fund and partial support from the State of Salzburg.
Further work, as indicated by the reported results, would have to address the power-set bottleneck and the 20-second execution failures while testing broader query forms and workloads. Until then, the study is best read as a demonstration that semantic rewriting is possible under the stated assumptions—not as evidence that ontology-mediated graph queries already run efficiently in general.
Paper data and sources
Original title: Rewriting Ontology-Mediated Property Graph Queries into GQL
Authors: Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, Magdalena Ortiz
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text