Rewriting Ontology-Mediated Property Graph Queries into GQL

arXiv:2608.20092v1 [cs.DB] 20 Aug 2026

Rewriting Ontology-Mediated Property Graph Queries into GQL Bianca Löhnert

Nikolaus Augsten

bianca.loehnert@plus.ac.at University of Salzburg Austria

nikolaus.augsten@plus.ac.at University of Salzburg Austria

Cem Okulmus

Magdalena Ortiz

cem.okulmus@upb.de Paderborn University Germany

magdalena.ortiz@tuwien.ac.at TU Wien Austria

Abstract

1

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.

A core aim of the ontology-based data access (OBDA) framework, in addition to the virtual integration of data sources, is to extend existing data with domain-specific knowledge without the need to materialise all implied facts; the framework still enables access to all consequences when answering user queries. The key question at the core of OBDA is the following: how to capture all the semantic consequences of a query in the presence of an ontology, where the query may be specified over a possibly extended signature with terms from both the data and the ontology. Such a pair of query and ontology is often called an ontology-mediated query (OMQ) and the task of producing all consequences is called OMQ answering (OMQA). The main technique for OMQA is called query rewriting: the query is rewritten into a new query that uses only the reduced signature present in the data, incorporating the knowledge in the ontology into the query itself. The rewritten query can then be evaluated using a conventional database system that does not support ontologies, while still making effective use of the ontology to retrieve implicit answers. While commercial OBDA systems already exist for relational databases [40], corresponding solutions for graph databases—the focus of this paper—are still missing. Instead of the relational model, graph databases focus on the labelled property graph (LPG) model, which allows for nodes and binary, directed edges between nodes. Both nodes and edges can be assigned multiple labels to classify them, and they can be associated with data values via so-called properties. The increasing popularity of graph databases has recently culminated in the ISO standardisation of two new graph query languages: GQL and SQL/PGQ. The key distinguishing feature of these query languages is their navigational capability, which allows them to match arbitrarily long paths in the data. Both GQL and SQL/PGQ share the same navigational core [15], which includes the standard navigational query languages: (two-way) regular path queries ((2)RPQs), nested 2RPQs (N2RPQs), and their conjunctive variants (C2RPQs resp. CN2RPQs). The extensive study of navigational queries in the context of OMQA over the past decade has led to tight complexity results for most description logics, ranging from lightweight to highly expressive, as well as for all standard navigational query languages (2RPQs, N2RPQs, C2RPQs, and CN2RPQs) [8, 10, 12, 17, 32, 33, 37]. However, these studies focused on the boundaries of decidability and computational complexity. The proposed algorithms are so unamenable to implementation that, more than a decade later, not a single practical implementation has been proposed. We differ from

CCS Concepts • Theory of computation → Description logics; • Information systems → Query languages; Graph-based database models.

Keywords ontology-based data access, graph query languages, ontologymeditated query answering, description logics ACM Reference Format: Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, and Magdalena Ortiz. 2026. Rewriting Ontology-Mediated Property Graph Queries into GQL. In Proceedings of International Conference on Information and Knowledge Management (CIKM). ACM, New York, NY, USA, 16 pages. https://doi.org/ 10.1145/3799682.3841030

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 the author(s) 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. CIKM, Rome, IT © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/10.1145/3799682.3841030

Introduction

CIKM, November 07–11,2026, Rome, IT

Loehnert et al.

these early theoretical works, by looking to develop practical techniques for pure rewritings of navigational queries (i.e., the ontology reasoning is compiled entirely into the rewritten query, which can be evaluated with standard query engines without any data preprocessing) that can pave the way towards practical implementations. There were two significant roadblocks that discouraged the development of practical techniques for OMQA over graph databases. First, practical languages imposed ad-hoc restrictions on navigational languages that rendered them unsuitable for this setting, for example, by providing only partial support for RPQs and by failing to support the basic homomorphism semantics that is natural in the OMQA context. Second, it has been shown that even plain RPQs in the presence of the simplest DL-Lite ontologies cannot be rewritten into C2RPQs [28]. Instead, such rewritings require nested RPQs, which existing technologies did not support. The arrival of GQL and SQL/PGQ has removed both obstacles at once: the standards include CN2RPQs and basic homomorphism semantics [20, 21], and practical graph query languages are now rapidly being updated to support these features [31]. This has finally made practical OMQA over graph databases feasible. Join-on-free Conjunctive Nested Two-Way Regular Path Queries Input query

𝐷𝐿 − 𝐿𝑖𝑡𝑒 PG

ARCO

𝑟𝑒𝑚𝑜𝑣𝑒∃𝑉𝑎𝑟

Nested Two-Way Regular Path Queries

𝑠𝑘𝑖𝑝𝐴𝑛𝑜𝑛𝑦𝑚𝑜𝑢𝑠 𝑠𝑘𝑖𝑝𝐶𝑜𝑟𝑒

GQL Rewritten output query

Figure 1: High-level overview of the rewriting algorithm. Seizing this opportunity, we propose the first practical query rewriting technique for a navigational query language that contains RPQs. in the presence of DL-Lite ontologies. Figure 1 provides an overview of the overall architecture, which comprises a DL-Lite ontology expressed, for example, in the Web Ontology Language (OWL) [39]; our rewriting algorithm “Automata-based Rewriting of CN2RPQs under Ontologies” or simply ARCO for short; and a property graph database with support for GQL, such as Neo4j,1 Google Spanner,2 or Oracle Database (via SQL/PGQ).3 The user poses a query over the extended signature, i.e., the query may use terms from both the ontology and the underlying database. Our rewriting algorithm compiles the user query into a semantically equivalent rewritten query that incorporates the consequences of ontology reasoning directly into the query expression. The rewritten query is subsequently evaluated by the graph database system. Although the database remains agnostic to the ontology, the answer to the rewritten query is complete with respect to the ontology semantics. In terms of query language, our approach fully covers 2RPQs and N2RPQs in the presence of DL-Lite ontologies. We also consider conjunctive N2RPQs; to ensure the algorithm remains practical 1 https://neo4j.com/

and useful, we impose a restriction called join-on-free, whereby non-answer variables cannot be shared by multiple atoms. While techniques for rewriting full C2RPQs are known [19], this fragment serves as a useful starting point for our endeavour. We also support property data values, a central feature of the labelled property graph model that is often disregarded in the OMQA literature. Property tests are also allowed along navigational paths. On the ontology side, we define a variant of DL-Lite that can use property value tests on the left-hand-side of axioms, which enables the creation of concepts and roles based on these values. In summary, we make the following contributions: (1) We present the first practical algorithm to rewrite navigational ontology-mediated queries with unrestricted regular path expressions, and with DL-Lite ontologies, into graph queries that can be evaluated with off-the-shelf query engines for graph data adopting the property graph data model. The queries can access the data values of properties, also while navigating paths. (2) We leverage the power of graph queries with nested path navigation to support the interaction between the regular path expressions in the given queries on the one hand, and the ontology axioms on the other. To our knowledge, this is the first algorithm for a navigational query language that fully supports property paths, which produces a pure rewriting that can be evaluated directly over the data, with the ontology consequences entirely rewritten into the query. (3) We demonstrate the practical utility of our technique by implementing a prototype. The system takes as input an ontology in OWL format together with navigational queries, rewrites them into the graph query language Cypher, and evaluates them on a database in Neo4j. This paper is structured as follows. In Section 2 we present the key terminology of our setting and also introduce our novel description logic to express tests over property values. In Section 3 we define procedures to rewrite N2RPEs in the presence of DL-LitePG ontologies. Then, in Section 4 we use these procedures to present our rewriting algorithm on join-on-free CN2RPQs. In Section 5 we present our proof-of-concept implementation and an experimental evaluation that aims to show its performance. In Section 6 we summarise our results and highlight future work. Related Work. 4 Early work by Di Martino et al. [16, 17] leverages the recursion in regular path queries to rewrite a fragment of EL, the lightweight description logic underlying the OWL 2 EL profile. They use navigational queries as target language for query rewriting, but their source languages are only instance queries and conjunctive queries; we support navigational source queries. The work is primarily theoretical and not aimed at implementation. It is therefore more closely related to the previously discussed theoretical studies of navigational queries in the context of OMQA [8, 10, 12] than to this paper. Aiming at practical implementation, Dragovic et al. [18] considered DL-Lite ontologies and a restricted fragment of C2RPQs that can be rewritten into unions of C2RPQs. However, the approach does not cover full RPQs. Like Di Martino et al. [16], Löhnert et al. [28] support a fragment of EL as an ontology; their

2 https://cloud.google.com/spanner 3 https://www.oracle.com/database/

4 This work is a corrected version of the preliminary algorithm presented in [27].

Rewriting Ontology-Mediated Property Graph Queries into GQL

regular path expressions are restricted to ensure rewritability into C2RPQs, i.e., to avoid the need for nested queries. Query rewriting in the presence of data tests has been explored previously, such as the work by Savković and Calvanese [35], which considered the problem of OMQ answering over an extension of DL-lite with expressions over concrete domains called datatype expressions, and the ability to express hierarchies over them. Baader et al. [5] extended this work by an even more expressive language, where the datatype expressions over the concrete domain can use 𝑛-ary predicates instead of just unary ones. Our restricted use of data values does not require reasoning over the data domains, and we can simply rely on the query engine to evaluate the data atoms.

2

Ontology Mediated Querying of Property Graphs

Data model. We are interested in querying data given as finite property graphs [1, 11, 22]. We assume disjoint, countably infinite sets C, R, K and N of concept names, role names, property keys and individuals, respectively. In the examples, we colour code the first three, as shown, for convenience. We also assume a concrete domain (D, PD ), with D a set of values and PD a set of binary predicates over D. For example, (D, PD ) could be the integers with the usual =, ≤, ≥ predicates. Definition 1 (Property Graphs). A property graph (PG) A has the form (𝑁 , 𝐸, label, prop), where: • 𝑁 is a non-empty set of nodes; • 𝐸 is the set of edges, where each edge is a triple (𝑟, 𝑛, 𝑛 ′ ) with 𝑟 ∈ R and 𝑛, 𝑛 ′ ∈ 𝑁 ; we may write such an edge in the form 𝑟 (𝑛, 𝑛 ′ ) and call it an 𝑟 -edge; • label is a total function 𝑁 → 2C ; • prop is a partial function (𝑁 ∪ 𝐸) × K → D mapping pairs (𝑢, 𝑝) with 𝑢 ∈ (𝑁 ∪ 𝐸) and 𝑝 ∈ K to a value in D. If 𝑁 ⊆ N and it is finite, we may call A an ABox. We say that A ′ = (𝑁 ′, 𝐸 ′, label′, prop′ ) is a subgraph of A if 𝑁 ′ ⊆ 𝑁 , 𝐸 ′ ⊆ 𝐸, label′ (𝑛) = label(𝑛) for all 𝑛 ∈ 𝑁 ′ , and prop′ (𝑢, 𝑝) = prop(𝑢, 𝑝) for all 𝑢 ∈ 𝑁 ′ ∪ 𝐸 ′ , 𝑝 ∈ K. Note that we use the same name of property keys for both nodes and edges, as usually done in PGs [11, 22]. We differ slightly from the usual definition of PGs, by allowing only a single edge for each role between pairs of nodes. This is puts our data model in between the usual DL setting and what real-world PG database systems like Neo4j [22] support, where multiple edges with the same role between the same pair of nodes are allowed Example 2. Figure 2 shows profile information from a social network (such as LinkedIn), represented as a PG. Ontology language. In ontology mediated query answering, an ontology captures domain knowledge and it allows us to infer implicit facts from the given data at query time. Here, the ontology language is called DL-LitePG . It extends the well-known DL-Lite [13] with tests over property values, which can be used in the left-handside both concept and role inclusions. Definition 3 (DL-LitePG ). The set of roles is defined as R = R ∪ {𝑟 − | 𝑟 ∈ R}, where 𝑟 − is called the inverse of 𝑟 and the set of data tests as TD = {𝑝 ⊙ 𝑣 ? | 𝑝 ∈ K, ⊙ ∈ PD, 𝑣 ∈ D}.

CIKM, November 07–11,2026, Rome, IT

We use the following syntax, where 𝐴 ∈ C, 𝑟 ∈ R and 𝑇 ⊆ TD . 𝐵 := ⊤ | 𝐴 | ∃𝑟 .⊤ | 𝑇 𝐸 := 𝑟 | 𝑟 − 𝐶 := 𝐵 | ¬𝐵

(basic concepts, data-test concepts) (basic roles) (general concept)

𝐹 := 𝐸 | 𝑇

(roles, data-test roles)

𝑅 := 𝐸 | ¬𝐸

(general role)

The symbol ⊤, called ‘top concept’, refers to the set of all nodes of the domain in question. A concept inclusion (CI) has the form 𝐵 ⊑ 𝐶 and a role inclusion (RI) the form 𝐹 ⊑ 𝑅. A TBox is a finite set of CIs and RIs. We use ⊑∗T to denote the reflexive transitive closure of {(𝑟, 𝑡) | 𝑟 ⊑ 𝑡 ∈ T } and call 𝑟 a subrole of 𝑡 (in T ) if 𝑟 ⊑∗T 𝑡. The semantics of concepts, roles and data sets is defined with respect to a given PG A. In the description logic (DL) literature, this is usually defined by a so-called interpretation of the form I = (𝛥 I , · I ), with 𝛥 I a non-empty set called the abstract domain and · I as the interpretation function. In this paper, we consider a given PG to be an interpretation in the DL sense. Hence, given a PG A, by slight abuse of notation, we may also use it as an interpretation function that maps concepts, roles and data sets to, resp., sets of nodes, pairs of nodes or a union of the two. This function is given in Table 1. In the sequel, when the PG A = (𝑁 , 𝐸, label, prop) is clear from context, we shall refer to it as “interpretation” and, for example, refer to its set of nodes 𝑁 as its domain 𝛥 A . As for the rest of the semantics, the satisfaction of CIs and RIs is as expected: I |= 𝐶 ⊑ 𝐷 iff 𝐶 I ⊆ 𝐷 I , and I |= 𝐸 ⊑ 𝐹 iff 𝐸 I ⊆ 𝐸 I . We write I |= T iff I |= 𝐶 ⊑ 𝐷 for every 𝐶 ⊑ 𝐷 ∈ T . We write T |= 𝐶 ⊑ 𝐷 iff for every PG I with I |= T we also have I |= 𝐶 ⊑ 𝐷. For readabilty, in the examples we use CIs of the form A ⊑ ∃r.B, which are not strictly in DL-LitePG . These are just syntactic sugar: we can write A ⊑ ∃r.B in DL-LitePG using a fresh role name rB and three axioms: A ⊑ ∃rB .⊤, ∃rB .⊤ ⊑ 𝐵, rB ⊑ r. Example 4. The following DL-LitePG TBox provides knowledge that can be applied to the social network graph of Example 2: {born ≥ 1997 ?, born ≤ 2012 ?} ⊑ GenZ,            ∃emp − .⊤ ⊑ Employed, {time ≥ (2025-01-01)?} ⊑ Recent,    T=   Employed ⊑ ¬Unemployed, Opole ⊑ Poland, ∃ann.⊤ ⊑ Hiring        TechCompany ⊑ ∃emp.Engineer, friend ⊑ friend. −   

To briefly explain a few of the axioms, we see that the first axiom in T defines the new concept GenZ, which applies to anyone born between the years 1997 and 2012. The second axiom says that someone who has an employer is employed, and the fourth that no one can be both employed and unemployed. For the problem of checking whether a given PG is consistent with an DL-LitePG TBox, we refer to the work of Artale et al. [4]; their algorithms can be easily tuned to account for our restricted use of property values. Query Language. We study conjunctive nested two-way regular path queries (CN2RPQs), the extension of C2RPQs, the navigational query language for graphs that has received most attention in OMQA. We enhance CN2RPQs by data tests similar to data tests for navigational conjunctive queries in [18] to query for property values, assuming that the predicates in PD can be realized in GQL and

CIKM, November 07–11,2026, Rome, IT

Loehnert et al.

{ Job }

{ announce }

Software Engineer

e2 on = 14.03.2025

starts = 21.09.2025

{ TechCompany } SmartBees revenue = 500k founded = 2012 { owns }

{ locatedIn }

e6 since = 2025

e1 since = 2012

{ Company }

{ employs }

{ viewed }

City17

nuCompany

e5 time = 24.04.2025

population = 2, area = 3

revenue = 50k founded = 2015

e3 since = 2010

{ Opole }

{ User }

{ friendsWith }

{ User }

Alice born = 2000

e4

Bob born = 1980

since = 2012

Figure 2: Property Graph of Example 2 Table 1: Semantics of DL-LitePG concepts, roles and data tests given A = (𝑁 , 𝐸, label, prop). 𝐶

𝐶A ⊆ 𝑁

𝐹 𝐹A ⊆ 𝑁 ×𝑁

𝑇

𝑇 A ⊆ (𝑁 × 𝑁 ) ∪ 𝑁

⊤ 𝑁 𝑟 {(𝑛, 𝑚) | 𝑟 (𝑛, 𝑚) ∈ 𝐸} 𝑝 ⊙ 𝑣? {𝑛 ∈ 𝑁 | 𝑣 ′ ⊙ 𝑣 where prop(𝑛, 𝑝) = 𝑣 ′ } ∪
𝐴 {𝑛 ∈ 𝑁 | 𝐴 ∈ label(𝑛)} 𝑟 − {(𝑚, 𝑛) | 𝑟 (𝑛, 𝑚) ∈ 𝐸} {(𝑛, 𝑚) | 𝑣 ′ ⊙ 𝑣 where ∃𝑟 ∈ R. prop(𝑟 (𝑛, 𝑚), 𝑝) = 𝑣 ′ and 𝑟 (𝑛, 𝑚) ∈ 𝐸 } A A ∃𝑟 .⊤ {𝑛 | 𝑟 (𝑛, 𝑚) ∈ 𝐸} {𝑇1, . . . ,𝑇𝑛 } {𝑇1 ∩ · · · ∩ 𝑇𝑛 } ¬𝐶 𝑁 \ 𝐶 A

Cypher. To represent CN2RPQs we rely on nested nondeterministic finite automaton (n-NFA), following generally the notions from [8], with some simplifications. We first define nested two-way regular path expressions using NFAs, and then define conjunctive nested two-way regular path queries based on them. We assume a given alphabet Σ, and to define nested automata, we extend it by allowing n-NFAs as symbols. Definition 5. Let A0 be the set of all NFAs over a given alphabet Σ. For 𝑘 > 0, the set A𝑘 of nested NFA (n-NFA) over Σ of nesting depth 𝑘 contains all automata over Σ𝑘 = Σ ∪ {⟨𝛼⟩ | 𝛼 ∈ A𝑖 , 1 ≤ 𝑖 < 𝑘 }. We omit the nesting depth of an n-NFA when it is irrelevant. We are interested in n-NFAs that use the alphabet of symbols and tests that may occur in our PGs. Definition 6. A nested two-way regular path expression (N2RPE) is an n-NFA over the specific alphabet D

Σ𝑃𝐺 = 2R∪T ∪ TD ∪ {C? | C ∈ C}. Σ𝑃𝐺 consists of three kinds of symbols: 1) sets of (possibly inverted) role labels and data tests, which allow the expression to perform a series of data tests while traversing an edge that has all the role labels in the test; 2) individual data tests, which are checked against the properties of a node and lastly, 3) concept tests, which check whether the current node is part of the required concept. Sets of binary (data and role) tests allow us to do several tests while traversing one edge. In contrast, sets of unary (data and concept) tests do not need to be performed simultaneously; they can be tested equivalently by consecutive transitions.

We can now use N2RPEs as a query language for PGs. We define the semantics of a 2NRPE 𝛼 via paths that match 𝛼, possibly with outgoing paths to match the nested automata.

Definition 7 (Run of an N2RPEs). Let 𝛼 0 = ⟨𝑄 0, Σ𝑃𝐺 , 𝑆 0, 𝛿 0, 𝐹 0 ⟩ be an N2PRE of nesting depth 𝑘 and let 𝛼 1, . . . , 𝛼𝑚 be the N2PREs of nesting depth < 𝑘 mentioned in the transtions of 𝛼 0 . We let 𝛼𝑖 = ⟨𝑄𝑖 , Σ𝑃𝐺 , 𝑆𝑖 , 𝛿𝑖 , 𝐹𝑖 ⟩ for each 𝛼𝑖 . Then, a run for 𝛼 on I is a finite node-labelled tree (𝑇 , 𝑙) such that every node is labelled with an Ð element from Δ I × 𝑖 𝑄𝑖 . Furthermore, for the root 𝑟𝑇 of 𝑇 we have that 𝑙 (𝑟𝑇 ) = (𝑛𝑟 , 𝑠𝑟 ), where 𝑠𝑟 ∈ 𝑆 0 and for every leaf node 𝑒 ∈ 𝑁 (𝑇 ), it holds that 𝑙 (𝑒) = (𝑛, 𝑠𝑛 ), with 𝑠𝑛 ∈ 𝐹𝑖 for some 𝑖 and there exists exactly one leaf 𝑛 ′ such that 𝑙 (𝑒 ′ ) = (𝑛 ′, 𝑠 ′ ), with 𝑠 ′ ∈ 𝐹 0 , called the accepting node. For each non-leaf node 𝑣 ∈ 𝑁 (𝑇 ) having label 𝑙 (𝑣) = (𝑛 𝑣 , 𝑠 𝑣 ) with 𝑠 𝑣 ∈ 𝑄𝑖 , one of the following holds: • 𝑣 has a unique child 𝑣𝑐 with 𝑙 (𝑣𝑐 ) = (𝑛𝑐 , 𝑠𝑐 ), and there exists (𝑠 𝑣 , 𝜎, 𝑠𝑐 ) ∈ 𝛿𝑖 , such that one of the following holds: D – If 𝜎 ∈ 2R∪T then: (i) (𝑛 𝑣 , 𝑛𝑐 ) ∈ (𝑝 ⊙ 𝑣?) I for each data test 𝑝 ⊙ 𝑣? ∈ 𝜎 I , and (ii) (𝑛 𝑣 , 𝑛𝑐 ) ∈ 𝑟 I for each 𝑟 ∈ 𝜎 I ∩ R; – if 𝜎 = C? , then 𝑛𝑐 = 𝑛 𝑣 and 𝑛 𝑣 ∈ C I , and – if 𝜎 = 𝑝 ⊙ 𝑣?, then 𝑛 𝑣 = 𝑛𝑐 and 𝑛 𝑣 ∈ (𝑝 ⊙ 𝑣?) I . • 𝑣 has exactly two children 𝑣𝑐 1 and 𝑣𝑐 2 with 𝑙 (𝑣𝑐 1 ) = (𝑛 𝑣 , 𝑠𝑐 1 ) and 𝑙 (𝑣𝑐 2 ) = (𝑛 𝑣 , 𝑠𝑐 2 ), with 𝑠𝑐 2 the initial state of 𝛼 𝑗 , and there exists a transition (𝑠 𝑣 , ⟨𝛼 𝑗 ⟩, 𝑠𝑐 1 ) ∈ 𝛿𝑖 . If the root 𝑟𝑇 is labelled (𝑛𝑟 , 𝑠 0 ) and the accepting node 𝑢 is labelled (𝑛𝑢 , 𝑠𝑢 ) with 𝑠 0 ∈ 𝑆 0 and 𝑠𝑢 ∈ 𝐹 0 , then (𝑇 , 𝑙) is called an (𝑛𝑟 , 𝑛𝑢 )-run, and if such a run exists, we write (𝑛𝑟 , 𝑛𝑢 ) ∈ 𝛼 0I .

Rewriting Ontology-Mediated Property Graph Queries into GQL

N2RPEs are a very rich query language in their own right, but we get even more flexible querying if we join N2RPEs using variables. Definition 8. A conjunctive N2RPQ (CN2RPQ) 𝑞(𝑥) ® is a conjunction of atoms 𝛼 1 (𝑥 1, 𝑦1 ) ∧ · · · 𝛼𝑖 (𝑥𝑖 , 𝑦𝑖 ) · · · ∧ 𝛼𝑛 (𝑥𝑛 , 𝑦𝑛 ) with each 𝛼𝑖 Ð𝑛 an N2RPE and 𝑥® ⊆ 𝑖 {𝑥𝑖 , 𝑦𝑖 } is a tuple of answer variables. We call a CN2RPQ Boolean if 𝑥® is empty. The set of join variables Join(𝑞(𝑥)) ® of a CN2RPQ 𝑞(𝑥) ® is the set of those variables that occur in two different atoms of 𝑞(𝑥). ® If Join(𝑞(𝑥)) ® ⊆ 𝑥® for a CN2RPQ that is not Boolean, then we call 𝑞(𝑥) ® a join-on-free CN2RPQ. We sometimes abbreviate atoms of the form ⟨𝛼⟩(𝑥, 𝑥) as ⟨𝛼⟩(𝑥), and similary, 𝐴?(𝑥) as 𝐴(𝑥). We assume that CN2RPQs are connected, that is, the graph whose vertices are the variables and that has an edge between two variables if they occur in the same atom is a connected graph. Disconnected queries can be answered as separate queries and then their answers intersected. Note that, under this assumption, every atom in a joinon-free CN2RPQ has at least one answer variable. Definition 9 (Semantics of CN2RPQs). Consider a CN2RPQs 𝑞(𝑥) ® and a PG A = (𝑁 , 𝐸, label, prop). A match 𝜇 for 𝑞(𝑥) ® in A is a mapping from the variables in 𝑞 to nodes in 𝑁 such that (𝜇 (𝑥), 𝜇 (𝑦)) ∈ 𝛼 IA for every atom 𝛼 (𝑥, 𝑦) occurring as a conjunct in 𝑞(𝑥). ® The tuple 𝜇 (𝑥) ® is then called an answer for 𝑞(𝑥) ® in A. Example 10. To illustrate our query language, we use the schema introduced in Example 4 and present four example queries, with informal explanations of their semantics following below. 𝑞 1 (𝑥, 𝑦) := friendsWith∗ · employs − (𝑥, 𝑦), ⟨locatedIn · Poland?⟩ · Hiring? · TechCompany?(𝑦, 𝑧 ) 𝑞 2 (𝑥, 𝑦) := {employs− , since ≤ 2023?} · friendsWith∗ · born ≥ 2000?(𝑥, 𝑦), ⟨ {viewed, time ≥ 01.01.2024?} ⟩ · friendsWith(𝑧, 𝑦) 𝑞 3 (𝑥, 𝑦) := founded ≤ 2003? · revenue ≥ 105 ?· ( {owns, since ≥ 2020?} · ⟨locatedIn · Poland?⟩ ) ∗ (𝑥, 𝑦) 𝑞 4 (𝑥, 𝑦) := Company? · employs · friendsWith · GenZ?(𝑥, 𝑦), viewed · Job? · announce− (𝑦, 𝑥 )

The query 𝑞 1 (𝑥, 𝑦) retrieves all technical companies located in Poland that are currently hiring and that have an employee who is a friend of friends of the user. In query 𝑞 2 (𝑥, 𝑦) a recruiter might be interested in friends (and friends of friends) born after 2000 of an employee, who has been working for the company for over three years. In query 𝑞 3 (𝑥, 𝑦), we look for companies that were founded before 2003, with a revenue of 105 or more, and want to find all Polish companies that they own since 2020, and also look for all companies that these companies own, and so on. In query 𝑞 4 (𝑥, 𝑦), we look for all companies that employ workers that are friends with some user of GenZ, and return the pairs of company and users, when the user also viewed a job offer by the company that the friend is currently employed. Following the OMQA literature, we use the homomorphism or walk semantics for path queries [2], and in the presence of a TBox, adopt the certain answer semantics. Definition 11. Consider an PG A and a TBox T . A tuple 𝑎® of individuals in A is called a certain answer to 𝑞(𝑥) ® over (T , A) if it is an answer to 𝑞(𝑥) ® in PG(I) for every model I of A and T .

CIKM, November 07–11,2026, Rome, IT

The worst-case complexity of evaluating navigational queries over ontologies is well understood. Unfortunately, when we take the ontology’s size and the query into account, it is highly intractable. Theorem 12 (Theorem 5.1 & Corollary 6.8 [8]). In DL-Lite, N2RPQ answering is NL-complete in data complexity and Expcomplete in combined complexity. In all description logics containing EL and contained in Horn-SH IQ, N2RPQ answering is P-complete in data complexity and Exp-complete in combined complexity. Our aim here is not worst-case optimal complexity, but to develop techniques that may lead to tractable evaluation of nested navigational queries over ontologies in practice.

3

Rewriting N2RPQs

We present a rewriting algorithm for N2RPQs with data tests. In this section and the next, we assume a fixed DL-LitePG TBox T , and provide an algorithm for rewriting a given input N2RPQ 𝑞 into an N2RPQ 𝑞 T that is sound and complete for all ABoxes that are consistent with T . In the next section, we lift this algorithm to (restricted) conjunctions of N2RPQs. Our algorithm draws inspiration from and builds on previous techniques for navigational ontology-mediated querying [9, 14, 19, 32], but it focuses on potential implementability. As usual for ontology-mediated querying, we rely on the fact that for every PG A that is consistent with T , there is a canonical model IT,A that gives exactly the certain answers to all N2RPQs. Below we give the construction for the canonical model. Definition 13 (Canonical Model). Consider a DL-LitePG TBox T and a PG A. Let I0 = A. Then, we construct the canonical model IT,A by exhaustively applying the following rules to I0 . (Ch1) If 𝑟 ⊑ 𝑟 ′ ∈ T , (𝑣, 𝑤) ∈ 𝑟 I𝑖 and (𝑣, 𝑤) ∉ 𝑠 I𝑖 , then I𝑖+1 is I𝑖 with 𝑟 ′ I𝑖+1 = 𝑟 ′ I𝑖 ∪ {(𝑣, 𝑤)} in case 𝑟 ∈ R, otherwise 𝑟 ′ I𝑖+1 = 𝑟 ′ I𝑖 ∪ {(𝑤, 𝑣)}. (Ch2) If 𝑇 ⊑ 𝑟 ′ ∈ T , (𝑣, 𝑤) ∈ 𝑇 I𝑖 and (𝑣, 𝑤) ∉ 𝑟 ′ I𝑖 , then I𝑖+1 is I𝑖 with 𝑟 ′ I𝑖+1 = 𝑟 ′ I𝑖 ∪ {(𝑣, 𝑤)}. (Ch3) If 𝐴 ⊑ 𝐵 ∈ T , 𝑣 ∈ 𝐴 I𝑖 and 𝑣 ∉ 𝐵 I𝑖 , then I𝑖+1 is I𝑖 with 𝐵 I𝑖+1 = 𝐵 I𝑖 ∪ {𝑣 }. (Ch4) If ∃𝑟 .⊤ ⊑ 𝐵 ∈ T , 𝑣 ∈ (∃𝑟 .⊤) I𝑖 and 𝑣 ∉ 𝐵 I𝑖 , then I𝑖+1 is I𝑖 with 𝐵 I𝑖+1 = 𝐵 I𝑖 ∪ {𝑣 }. (Ch5) If 𝑇 ⊑ 𝐵 ∈ T , 𝑣 ∈ 𝑇 I𝑖 and 𝑣 ∉ 𝐵 I𝑖 , then I𝑖+1 is I𝑖 with 𝐵 I𝑖+1 = 𝐵 I𝑖 ∪ {𝑣 }. (Ch6) If 𝐴 ⊑ ∃𝑟 .⊤ ∈ T , 𝑣 ∈ 𝐴 I𝑖 and 𝑣 ∉ (∃𝑟 .⊤) I𝑖 , then I𝑖+1 is I𝑖 with a fresh 𝑤 in 𝛥 I𝑖+1 . In case 𝑟 ∈ R then 𝑟 I𝑖+1 = 𝑟 I𝑖 ∪ {(𝑣, 𝑤)}, otherwise 𝑟 I𝑖+1 = 𝑟 I𝑖 ∪ {(𝑤, 𝑣)}. (Ch7) If ∃𝑟 .⊤ ⊑ ∃𝑟 ′ .⊤ ∈ T , 𝑣 ∈ (∃𝑟 .⊤) I𝑖 and 𝑣 ∉ (∃𝑠.⊤) I𝑖 , then I𝑖+1 is I𝑖 with a fresh 𝑤 in 𝛥 I𝑖+1 . In case 𝑠 ∈ R then 𝑟 ′ I𝑖+1 = 𝑟 ′ I𝑖 ∪ {(𝑣, 𝑤)}, otherwise 𝑟 ′ I𝑖+1 = 𝑟 ′ I𝑖 ∪ {(𝑤, 𝑣)}. Note that the property values in DL-LitePG have no effect when it comes to the canonical model construction. Since data value tests only occur on the left-hand-side of axioms, in IT,A the partial function prop stays as-is and does not assign any new data values, neither to nodes in A nor to freshly added ones. For convenience, we may think of IT,A as a set of facts: 𝐴(𝑜) and 𝑟 (𝑜, 𝑜 ′ ) assert node and edge labels, plus facts 𝑜.(𝑝 = 𝑣), 𝑟 (𝑜, 𝑜 ′ ).(𝑝 = 𝑣) that assert property value assignments. where 𝑜, 𝑜 ′ are nodes, 𝐴 ∈ C, 𝑟 ∈ R, 𝑝 ∈ K and 𝑣 ∈ D. We call a fact explicit if

CIKM, November 07–11,2026, Rome, IT

it is present in A, and implicit otherwise. That is, implicit facts are those introduced by the canonical model construction that extends the explicit facts to satisfy the TBox T . All property value assertions are explicit. Note that, as usual for DL-Lite variants, each rule application that adds an implicit fact 𝜉 ℓ tests for the presence of one fact 𝜉 ℓ −1 , which may be explicit or added by a previous rule application. In this way, every implicit fact is triggered by one explicit fact and a sequence of rule applications. Note that all explicit facts mention only the individual names in A, but the implicit ones may mention additional nodes introduced to satisfy existential restrictions. We call the latter, that is, the nodes in IT,A \ A, the anonymous nodes, and we refer to the facts in IT,A that mention at least one anonymous node as the anonymous part of IT,A . It is not hard to see that if there is a single fact 𝐶 (𝑎) in A, then all the anonymous nodes added during the model construction form a tree-shaped graph rooted at 𝑎. Moreover, since all rules are deterministic, this tree is unique up to renaming of nodes, and the canonical model of any ABox containing an individual that satisfies 𝐶 will contain a copy of this tree. Our rewriting of a single N2RPQ 𝑞 is based on two skipping functions that take an N2RPE as input and output a modified N2RPE with additional transitions that allow it to ‘skip over’ implicit facts, and instead look for the explicit facts that trigger their generation. The rewriting is done in two phases. First, to account for the anonymous part, the function skipAnon adds transitions that skip over the anonymous part of the canonical model. The answers of the resulting query over the facts of IT,A involving only non-anonymous individuals coincide with the answers of the original 𝑞 over the whole IT,A . Then a second function skipCore adds more transitions to yield complete answers when evaluated over A alone, without any implicit facts.

3.1

Skipping over the Anonymous Part

Given T and A, we use GT,A to denote the restriction of the canonical model IT,A to the nodes in A, and call it the core of IT,A . The goal of the first phase of the rewriting is to obtain a query that skips over the anonymous part of IT,A and finds all query answers when evaluated over the core GT,A alone. To this aim, we rely on the following SkipRel(𝛼, T ) relation, originally defined as two relations JumpTrans and JumpFinal in [8]. This relation characterises the parts of the input N2RPQ 𝛼 that can be matched in the canonical models of each tree-shaped part that can possibly appear in a canonical model constructed from T . Recall the definition of run from Definition 7. A partial run for 𝛼 is defined analogously, but does not need to satisfy the conditions on the leafs, i.e. it may simply end on non-final states. Definition 14. Let T be a DL-LitePG TBox and 𝛼 0 an n-NFA of depth 𝑘, and let 𝛼 1, . . . , 𝛼𝑛 be the n-NFAs of nesting depth ≤ 𝑘 mentioned in the transitions of 𝛼 0 . The set SkipRel(𝛼 0, T ) consists of tuples (𝐶, 𝑠 01, 𝑠 02, Γ) where 𝐶 ∈ C ∪ {⊤}, 𝑠 01 ∈ 𝑄 0 is a state from 𝛼 0 , 𝑠 02 ∈ (𝑄 0 ∪ {f}) \ {𝑠 01 } is either a different state from 𝛼 0 or the special Ð marker f, and Γ ⊆ 1≤ 𝑗 ≤𝑛 𝑄 𝑗 is a set of states from the automata nested in 𝛼 0 . Such a tuple (𝐶, 𝑠 01, 𝑠 02, Γ) belongs to SkipRel(𝛼 0, T ) if there exists a partial run (𝑇 , 𝑙) of 𝛼 0 on the canonical model IT,{𝐶 (𝑎) } that satisfies the following conditions: • The root of 𝑇 is labelled (𝑎, 𝑠 01 ).

Loehnert et al.

• If 𝑠 02 ∈ 𝑄 0 , there is a leaf node 𝑣 with 𝑙 (𝑣) = (𝑎, 𝑠 02 ). • For every leaf node 𝑣 with 𝑙 (𝑣) = (𝑜, 𝑠) ≠ (𝑎, 𝑠 02 ), either 𝑠 ∈ 𝐹 𝑗 for some 0 ≤ 𝑗 ≤ 𝑛, or 𝑜 = 𝑎 and 𝑠 ∈ Γ. If 𝑇 has at least one node (𝑜, 𝑠) with 𝑜 ≠ 𝑎, then we call the tuple (𝐶, 𝑠 01, 𝑠 02, Γ) strictly anonymous. Intuitively, a tuple (𝐶, 𝑠 01, 𝑠 02, Γ) is in SkipRel(𝛼 0, T ) precisely when in the canonical model of every ABox containing a node 𝑎 with 𝑎 ∈ 𝐶 IT,A , we are guaranteed to find a match for the query 𝛼 ′ obtained by making 𝑠 01 the initial state of 𝛼 0 , 𝑠 02 the final state, and making all the states in Γ initial states of the respective automata. The match uses only the tree of IT,A rooted at 𝑎, and it is such that the automata will be at 𝑎 whenever they visit a state 𝑠 in Γ (which intuitively acts as initial state in the modified 𝛼 ′ but not in the original 𝛼 0 ). This allows us to ’glue’ together the partial match in the tree rooted at 𝑎 with any partial matches for the rest of the query found in the rest of the canonical model. Hence, if we find a node that satisfies 𝐶, we can fully skip the subquery 𝛼 ′ . The computation of SkipRel(𝛼 0, T ) can be easily reduced to standard description logics reasoning. In the claim below, we use a TBox in the well-known description logic ELH I, where concept inclusions take the form 𝐶 ⊑ 𝐷 with 𝐶, 𝐷 concepts formed according to the grammar 𝐶, 𝐷 := ⊤ | 𝐴 | ∃𝑟 .𝐶, and role inclusions take the form 𝑟 ⊑ 𝑡, with 𝐴 ∈ C and 𝑟, 𝑡 ∈ R. Lemma 1 (Proposition 6.3 in [8]). Consider an n-NFA 𝛼 0 and a DL-LitePG TBox T , and let 𝛼 1, . . . , 𝛼𝑛 be the n-NFAs of nesting depth 𝑘 mentioned in the transitions of 𝛼 0 . For every state 𝑠 ∈ 𝑄𝑖 of 𝛼𝑖 , with 1 ≤ 𝑖 ≤ 𝑘, we use a fresh concept name 𝐴𝑠 , and we let 𝐴f = ⊤. Let T ′ be obtained by keeping only the ELH I axioms of T, and adding to it the following concept inclusions, for every {𝑠, 𝑠 ′ } ⊆ 𝑄𝑖 , 0 ≤ 𝑖 ≤ 𝑛: • ⊤ ⊑ 𝐴𝑠 , for every 𝑠 ∈ 𝐹 𝑗 with 𝛼 𝑗 , • ∃𝑟 .𝐴𝑠 ′ ⊑ 𝐴𝑠 for every (𝑠, 𝑟, 𝑠 ′ ) ∈ 𝛿𝑖 , • 𝐴𝑠 ′ ⊓ 𝐵 ⊑ 𝐴𝑠 , whenever (𝑠, 𝐵?, 𝑠 ′ ) ∈ 𝛿𝑖 , and • 𝐴𝑠 ′ ⊓ 𝐴𝑠 ′′ ⊑ 𝐴𝑠 , whenever (𝑠, ⟨𝛼 𝑗 ⟩, 𝑠 ′ ) ∈ 𝛿𝑖 and 𝑠 ′′ ∈ 𝑆 𝑗 is an initial state of 𝛼 𝑗 . Then the following holds: l (𝐶, 𝑠 01, 𝑠 02, Γ) ∈ SkipRel(𝛼 0, T ) iff T ′ |= (𝐶 ⊓ 𝐴𝑠 2 ⊓ 𝐴𝑠 ) ⊑ 𝐴𝑠 1 . 0

𝑠 ∈Γ

0

Example 15. To illustrate SkipRel, we consider an example nNFA 𝛼 0 , given in Figure 3. We furthermore consider a TBox T = {A ⊑ ∃r, r − ⊑ t, D ⊑ ∃t’.⊤, ∃t’.⊤ ⊑ C, {p ≥ 10?} ⊑ D}. Then, the following holds:  SkipRel(𝛼 0, T ) = (A, 𝑠 0, 𝑠 3, {𝑠 5, 𝑠 8 }), (A, 𝑠 0, 𝑠 3, {𝑠 6, 𝑠 9 }), (A, 𝑠 5, 𝑠 6, ∅) To see why, for example (A, 𝑠 0, 𝑠 3, {𝑠 5, 𝑠 8 }) is in the set, we note that in the run of 𝛼 0 starting from 𝑠 0 , we must have a node 𝑎 in the graph that has an outgoing r edge and by r − ⊑ t also an incoming t. In state 𝑠 5 in 𝛼 1 we previously followed a 𝑡 edge and in state 𝑠 8 in 𝛼 2 an r − edge. Thus, the run can just follow that same edge in reverse, landing at 𝑎 again. Deciding T |= 𝐶 ⊑ 𝐷 is an instance of a well-studied problem: subsumption in ELH I. It is Exp-complete [26], but efficient off-the-shelf reasoners are available, [6, 25, 38]. However, there are exponentially many possible candidates to populate the set SkipRel(𝛼 0, T ), and testing them all (as assumed in [8]) would require strictly exponentially many calls to the external reasoner,

Rewriting Ontology-Mediated Property Graph Queries into GQL

CIKM, November 07–11,2026, Rome, IT

r start

𝑠0

⟨𝛼 1 ⟩

𝑠1

⟨𝛼 2 ⟩

r− 𝑠2

𝑠3

start

r−

(a) 𝛼 0

p 𝑠5

𝑠4

start

𝑠6

r−

t 𝑠7

𝑠8

(b) 𝛼 1

𝑠9

C?

𝑠 10

(c) 𝛼 2

Figure 3: Example N2RPQ with nesting level 𝑘 = 1. which is clearly impractical. Fortunately, a simple pruning of the search space can discard many irrelevant candidates. First, we can restrict our attention to tuples that are strictly anonymous, as otherwise the partial runs do not use the anonymous part and are already present in GT,A . For the strictly anonymous tuples, we make a simple relevance test: there must be some edge in the canonical model that allows the query to enter the anonymous part and exit it again. Definition 16. Let T be a DL-LitePG TBox and 𝛼 0 an n-NFA of depth 𝑘, and let 𝛼 1, . . . , 𝛼𝑛 be the n-NFAs of nesting depth 𝑘 mentioned in the transitions of 𝛼 0 . A tuple (𝐶, 𝑠 01, 𝑠 02, Γ) where Ð 𝐶 ∈ C ∪ {⊤}, 𝑠 01, 𝑠 02 ∈ 𝑄 0 and Γ ⊆ 𝑗 𝑄 𝑗 , with 1 ≤ 𝑖, 𝑗 ≤ 𝑛, is called relevant if {𝑠 01 } ∪ Γ does not contain any final states and the tuple satisfies all the following conditions (with ‘_‘ we denote an arbitrary state). (1) 𝐵 ⊑ ∃𝑟 .⊤ ∈ T , 𝑟 ⊑∗T 𝑟 ′ , and 𝑟 ⊑∗T 𝑡. (2) For some 0 ≤ 𝑖 ≤ 𝑛, we have {(_, 𝑟 ′, _)} ⊆ 𝛿𝑖 . (3) If 𝑠 02 ≠ f, then for some 0 ≤ 𝑖 ≤ 𝑛, we have {(_, 𝑡 − , _)} ⊆ 𝛿𝑖 . Lemma 2. If (𝐶, 𝑠 01, 𝑠 02, Γ) ∈ SkipRel(𝛼 0, T ) and it is strictly anonymous, then it is relevant. Proof. Given an n-NFA 𝛼 0 , let 𝛼 1, . . . , 𝛼𝑛 be the n-NFAs of nesting depth 𝑘 mentioned in the transitions of 𝛼 0 . Consider (𝐶, 𝑠 01, 𝑠 02, Γ) ∈ SkipRel(𝛼 0, T ) with Γ = {𝑠 1, . . . , 𝑠𝑛 }, then we show that each of the conditions in Definition 16 is satisfied. By Definition 14 there is a partial run (𝑇 , 𝑙) of 𝛼 0 in the canonical model I of T and A = {𝐶 (𝑎)} such that the following are satisfied. • The root of 𝑇 is labelled (𝑎, 𝑠 01 ). • If 𝑠 02 ∈ 𝑄 0 , there is a leaf node 𝑣 with 𝑙 (𝑣) = (𝑎, 𝑠 02 ). • For every leaf node 𝑣 with 𝑙 (𝑣) = (𝑜, 𝑠) ≠ (𝑎, 𝑠 02 ), either 𝑠 ∈ 𝐹 𝑗 for some 0 ≤ 𝑗 ≤ 𝑛, or 𝑜 = 𝑎 and 𝑠 ∈ Γ. • 𝑇 has at least one node (𝑜, 𝑠) with 𝑜 ≠ 𝑎. It is not hard to argue that the conditions of Definition 16 hold. Since the construction of canonical model I is based on the ABox A = {𝐶 (𝑎)} with 𝑎 being the only individual, if there is an individual 𝑜 ≠ 𝑎, it must have been added by rules (Ch6) or (Ch7) in Definition 13, which requires the existence of an axiom 𝐵 ⊑ ∃𝑟 .⊤ ∈ T , as desired, and it is triggered by 𝑎 ∈ 𝐵 IT,A . By construction, (𝑎, 𝑜) ∈ 𝑟 IT,A . Moreover, for every 𝑟 ′ ∈ R, we have that (𝑎, 𝑜) ∈ 𝑟 ′IT,A implies 𝑟 ⊑∗T 𝑟 ′ , as (Ch1) is the only rule that can add role names for already existing pairs of nodes. Moreover, the partial run can only visit 𝑜 after 𝑎 if it has a transition using such an 𝑟 ′ . Hence, conditions (1) and (2) hold. Finally, if 𝑠 02 ≠ f then there is a leaf with label (𝑎, 𝑠 02 ), which means that the partial run returns to 𝑎 after 𝑜, which it can only do using some 𝑡 − ∈ R that occurs in the transition function, and such that (𝑎, 𝑜) ∈ 𝑡 IT,A , which as argued above, implies 𝑟 ⊑∗T 𝑡, ensuring that (3) holds. □ Each tuple (𝐶, 𝑠 01, 𝑠 02, Γ) in SkipRel(𝛼 0, T ) tells us that if our data has a node 𝑎 that satisfies 𝐶, we can skip directly from 𝑠 01 to 𝑠 02 ,

since a path that satisfies the transitions between them always exists in the canonical model, specifically in the anonymous part below 𝑎. Moreover, any nested automata that started but did not finish their runs in the anonymous part below 𝑎 will have to ‘exit’ the anonymous part in some state 𝑠. These exit states 𝑠 are stored in Γ, and the corresponding nested automaton only needs to be executed from 𝑠 onwards to complete its run. We modify our input 𝛼 0 to do precisely that: look for a 𝐶, jump from 𝑠 01 to 𝑠 02 , and still look for partial runs that complete the nested automata, setting the states in Γ as their initial states. We introduce some notation. For an n-NFA 𝛼 = ⟨𝑄, Σ𝑃𝐺 , 𝑆, 𝛿, 𝐹 ⟩ of nesting depth 𝑘, we denote by 𝛼 |𝑠0 the n-NFA ⟨𝑄, Σ𝑃𝐺 , {𝑠 0 }, 𝛿, 𝐹 ⟩, that is, we make 𝑠 0 the single initial state. Definition 17 (Skipping Anonymous). Given a DL-LitePG TBox T and an n-NFA 𝛼 0 = ⟨𝑄 0, Σ𝑃𝐺 , 𝑆 0, 𝛿 0, 𝐹 0 ⟩, let 𝛼 1, . . . , 𝛼𝑛 be the nNFAs of nesting depth 𝑘 mentioned in the transitions of 𝛼 0 . Let (𝐶, 𝑠 01, 𝑠 02, Γ) ∈ SkipRel(𝛼 0, T ) with Γ = {𝑠 1, . . . 𝑠𝑛 }. We associate a state to 𝑠 02 as follows: if 𝑠 02 ∈ 𝑄 0 , then state(𝑠 02 ) = 𝑠 02 , and if 𝑠 02 = f, then state(𝑠 02 ) is a fresh state 𝑠 f . If Γ = ∅, we use 𝑠 1′ to denote state(𝑠 02 ), and for each 𝑠 𝑗 ∈ Γ, we let 𝛼 𝑗 denote the 𝛼𝑖 with 𝑠 𝑗 ∈ 𝑄 𝑗 . Then skipAnon T (𝛼 0 ) = ⟨𝑄 0′ , Σ𝑃𝐺 , 𝑆 0, 𝛿 0′ , 𝐹 0′ ⟩ is the n-NFA with: 𝑄 0′ =𝑄 0 ∪ {state(𝑠 02 )} ∪ {𝑠 ′𝑗 | 𝑠 𝑗 ∈ Γ} 𝐹 0′ =𝐹 0 ∪ {𝑠 f } if 𝑠 02 = f and 𝐹 0′ = 𝐹 0 otherwise, and 𝛿 0′ = 𝛿 0 ∪ {(𝑠 01, 𝐶?, 𝑠 1′ )} ∪ ′ ′ , ⟨𝛼 𝑛−1 {(𝑠 1′ , ⟨𝛼 1|𝑠1 ⟩, 𝑠 2′ )} ∪ · · · ∪ {(𝑠𝑛−1 |𝑠𝑛−1 ⟩, 𝑠𝑛 )} ∪

{(𝑠𝑛′ , ⟨𝛼 𝑛|𝑠𝑛 ⟩, 𝑠 02 )} In particular if Γ = ∅, the only new transition is {(𝑠 01, 𝐶?, state(𝑠 02 ))}. We can show that skipAnon T (𝛼) correctly skips over the anonymous part of IT,A and finds all query answers when evaluated over the core GT,A alone. Example 18. Consider the N2RPQ from Figure 3 and the TBox T from Example 15. Then, by skipAnon T (𝛼 0 ) and for the tuple (A, 𝑠 0, 𝑠 3, {𝑠 5, 𝑠 8 }) ∈ SkipRel(𝛼 0, T ) we add the following transitions and fresh states to 𝛼 0 . 𝑠0

A

𝑠 5′

⟨𝛼 1|𝑠5 ⟩

𝑠 8′

⟨𝛼 2|𝑠8 ⟩

𝑠3

Lemma 3. Let T be a DL-LitePG TBox and 𝛼 be an N2RPE. Then, for every PG A and every pair of nodes 𝑜𝑠 , 𝑜 𝑓 from A, it holds that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A iff (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A . Proof sketch. The proof is contained in the proof of Proposition 6.6 in [8]; there is a one-to-one correspondence between the nested automata added by skipAnon T (T )(𝛼 0 ) and the recursive calls to EvalAtom in cases (3.b.ii) and (3.b.iii). Only a minor adaptation is needed to argue that soundness and completeness are not

CIKM, November 07–11,2026, Rome, IT

Loehnert et al.

compromised if the tests are restricted to strictly anonymous, relevant tuples in SkipRel. The rest of the evaluation, which is done only over the individuals in A, coincides exactly with the standard evaluation over GT,A . □

3.2

Rewriting over the Core

We know that skipAnon T (𝛼) finds all query answers when evaluated over GT,A , but we want to execute the rewritten query over A alone, that is, over the explicit facts only. Again, we achieve this by adding transitions that allow us to look for explicit facts only and skip over their consequences. As usual for DL-Lite variants, in the canonical model obtained from a DL-LitePG TBox, every implicit fact 𝜉 ℓ is implied by some other fact 𝜉 ℓ −1 , which is either explicit or is also implied by another fact 𝜉 ℓ −2 and so on, until we reach some explicit fact 𝜉 0 that triggered the existence of 𝜉 ℓ . We add transitions to 𝛼 0 that allow it to use any of these 𝜉𝑖 when looking for some 𝜉 ℓ . Definition 19 (Skipping Core). Let T be a DL-LitePG TBox, and let T ∗ be the result of closing T under the following rule: (★) If {𝐶 ⊑ ∃𝑟 .⊤, ∃𝑟 ′ .⊤ ⊑ 𝐷} ⊆ T ∗ and 𝑟 ⊑∗T 𝑟 ′ , then 𝐶 ⊑ 𝐷 ∈ T ∗ . Given a N2RPE 𝛼 with alphabet Σ𝑃𝐺 , we denote by skipCore T (𝛼) the n-NFA obtained by exhaustively adding transitions as follows. In each rule, 𝛿, 𝑠𝑖 , 𝑠 𝑗 and 𝑠𝑘 denote the transition function and states of one (arbitrary but fixed) automaton that occurs (possibly nested) in 𝛼, and as usual, 𝑟, 𝑝 ∈ R, 𝐶, 𝐷 ∈ C and 𝑇 = {𝑡 1, . . . , 𝑡𝑘 } ⊆ TD . (R1) If 𝑟 ⊑ 𝑝 ∈ T and (𝑠𝑖 , 𝑆, 𝑠 𝑗 ) ∈ 𝛿 with 𝑝 ∈ 𝑆 (or 𝑝 − ∈ 𝑆), then add (𝑠𝑖 , 𝑅, 𝑠 𝑗 ) to 𝛿 with 𝑅 = (𝑆 \{𝑝})∪{𝑟 } (or 𝑅 = (𝑆 \{𝑝 − })∪{𝑟 − }). (R2) If 𝑇 ⊑ 𝑟 ∈ T and (𝑠𝑖 , 𝑅, 𝑠 𝑗 ) ∈ 𝛿 with 𝑟 ∈ 𝑅, add (𝑠𝑖 ,𝑇 , 𝑠 𝑗 ) to 𝛿. (R3) If 𝐶 ⊑ 𝐷 ∈ T ∗ and (𝑠𝑖 , 𝐷?, 𝑠 𝑗 ) ∈ 𝛿, then add (𝑠𝑖 , 𝐶?, 𝑠 𝑗 ) to 𝛿. (R4) If ∃𝑟 .⊤ ⊑ 𝐵 ∈ T ∗ and (𝑠𝑖 , 𝐵?, 𝑠 𝑗 ) ∈ 𝛿, then add (𝑠𝑖 , ⟨𝛼𝑟 ⟩, 𝑠 𝑗 ) to 𝛿 for a fresh two-state NFA 𝛼𝑟 with a single transition 𝛿𝑟 (𝑠 01, {𝑟 }, 𝑠 𝑓 ) between its initial state 𝑠 01 and its final state 𝑠 𝑓 . (R5) If 𝑇 ⊑ 𝐷 ∈ T ∗ and (𝑠𝑖 , 𝐷?, 𝑠 𝑗 ) ∈ 𝛿, then add, for each 𝑡 ℓ ∈ 𝑇 , ′ ) to 𝛿, where 𝑠 = 𝑠 ′ , 𝑠 ′ a transition (𝑠 ℓ′ , 𝑡 ℓ ?, 𝑠 ℓ+1 𝑖 1 𝑘+1 = 𝑠 𝑗 , and ′ ′ 𝑠 2, . . . , 𝑠𝑘 are fresh states. Intuitively, each rule application adds a transition that allows 𝛼 to ‘skip’ an implicit fact 𝜉 𝑗 in IT,A and use instead a fact 𝜉𝑖 , 𝑖 < 𝑗, that participated in its creation. We illustrate skipCore T (𝛼) on a simple example. Example 20. Let us again consider the N2RPQ 𝛼 2 from Figure 3 and the TBox T from Example 15. Then, by skipCore T (𝛼 2 ) we add the dotted transitions shown below. {p ≥ 10?} t − C? t r 𝑠8 𝑠9 𝑠 10 start 𝑠 7 D? T

We can now show that skipCore (𝛼)(𝑥, 𝑦) , when evaluated over A, correctly accounts for the implicit facts in GT,A . Lemma 4. Let T be a DL-LitePG TBox and 𝛼 be an N2RPE. Then, for every PG A and every pair of nodes 𝑜𝑠 , 𝑜 𝑓 from A, it holds that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 GT,A iff (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipCore T (𝛼) A . ∗ be the restriction of T ∗ to the axioms Proof sketch. Let Tcore that do not have existential concepts on the right, and for readability, ∗ ,A . for a given A, we denote by A ∗ the canonical model ITcore

One can prove in the usual way (see, e.g., [19]) that GT,A = A ∗ . We can thus show that, for every 𝛼: ∗

𝛼 A = (skipCore T (𝛼)) A . Given the one-to-one correspondence between the rules (Ch1) to (Ch5), which add facts to A ∗ and the rules (R1) to (R5), which add transitions to skipCore T (𝛼), the equality is established by a simple rule-by-rule analysis. □ Together, Lemma 3 and Lemma 4 give us the desired rewriting. Proposition 1. Let T be a DL-LitePG TBox and 𝛼 be an N2RPE. Then, for every PG A and every pair of nodes 𝑜𝑠 , 𝑜 𝑓 from A, it holds that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A iff (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipCore T (skipAnon T (𝛼)) A .

4

Rewriting join-on-free CN2RPQs

Utilising the two skip procedures from Section 3, we can now present an algorithm for the rewriting of join-on-free CN2RPQs under DL-LitePG ontologies. We dub this procedure “Automata-based Rewriting of CN2RPQs under Ontologies”, or ARCO for short. We proceed to describe the key parts of the procedure. We use a function that inverts nested automata, that is, it transforms the automata to accept the same words, but inverted. Definition 21. We define an inverse function over the alphabet Ð D D Σ𝑃𝐺 ∪ 𝑘 ∈N A𝑘 : if 𝜎 ∉ 2R∪T , then 𝜎 − = 𝜎, and if 𝜎 ∈ 2R∪T , then 𝜎 − = {𝑡 | 𝑡 ∈ 𝜎 ∩ TD } ∪ {𝑟 − | 𝑟 ∈ 𝜎 ∩ R} ∪ {𝑟 | 𝑟 − ∈ 𝜎, 𝑟 ∈ R}. Let 𝛼 = ⟨𝑄, Σ𝑃𝐺 , 𝑆, 𝛿, 𝐹 ⟩ be an N2RPE with 𝑆 ⊆ 𝑄 the initial states and 𝐹 ⊆ 𝑄 are the final states. Then 𝛼 can be inverted to obtain 𝛼¯ = ⟨𝑄, Σ𝑃𝐺 , 𝐹, 𝛿 − , 𝑆⟩, where 𝛿 − = {(𝑠 𝑗 , 𝜎 − , 𝑠𝑖 ) | (𝑠𝑖 , 𝜎, 𝑠 𝑗 ) ∈ 𝛿 }. Lemma 5. For every N2RPE 𝛼, PG I, and pairs of nodes 𝑛 1, 𝑛 2 , ¯ I (𝑛 1, 𝑛 2 ) ∈ 𝛼 I if and only if (𝑛 1, 𝑛 2 ) ∈ (𝛼) The first step of our rewriting algorithm removes all non-answer variables from the query by making use of nested expressions. Definition 22. For a join-on-free CN2RPQ 𝑞(𝑥), ® we denote by 𝑞 ⟨∃⟩ (𝑥) ® the result of replacing each atom 𝛼 (𝑥, 𝑦) with 𝑦 ∉ 𝑥® by ¯ ⟨𝛼⟩(𝑥), and each 𝛼 (𝑥, 𝑦) with 𝑥 ∉ 𝑥® by ⟨𝛼⟩(𝑦). A simple inspection of the CN2RPQ semantics shows that the transformation preserves query answers. Lemma 6. Let 𝑞(𝑥) ® be a join-on-free CN2RPQ. For every interpretation I and tuple of nodes 𝑎, ® we have that 𝑎® is an answer to 𝑞(𝑥) ® in I iff 𝑎® is an answer to 𝑞 ⟨∃⟩ (𝑥) ® in I. We emphasise again that the transformation to 𝑞 ⟨∃⟩ only removes non-answer variables and leaves all other variables untouched. We denote by arco T (𝑞 ⟨∃⟩ (𝑥)) ® the result of executing Algorithm 1 on 𝑞(𝑥) ® and T . As we can see, it begins with the removal of non-answer variables using 𝑞 ⟨∃⟩ , and then applies skipCore T (𝛼) and skipAnon T (𝛼) to each atom in 𝑞 ⟨∃⟩ (𝑥). ® Next we show that Algorithm 1 is indeed sound and complete. Theorem 23. Let T be a DL-LitePG TBox and 𝑞(𝑥) ® be a join-onfree CN2RPQ. Then, for every ABox A and every tuple 𝑎® of individuals from A, it holds that 𝑎® is a certain answer to 𝑞(𝑥) ® over (T , A) iff 𝑎® is an answer to arco T (𝑞 ⟨∃⟩ (𝑥)) ® over A.

Rewriting Ontology-Mediated Property Graph Queries into GQL

Algorithm 1: Automata-based Rewriting of CN2RPQs under Ontologies (ARCO) Input : join-on-free CN2RPQ 𝑞(𝑥), ® TBox T Output : CN2RPQ 𝑞 ′ 1 function arco(𝑞): 2 𝑞=remove∃Var(𝑞) 3 while 𝑞 ≠ 𝑞 ′ do 4 𝑞′ = 𝑞 5 foreach 𝛼 (𝑥, 𝑦) ∈ 𝑞 do 6 𝑞 ′ = 𝑞 ′ [𝛼\skipAnon T (𝛼) ] 7 𝑞 ′ = 𝑞 ′ [𝛼\skipCore T (𝛼) ] 8 return 𝑞 9 function remove∃Var(𝑞): 10 foreach 𝛼 (𝑥, 𝑦) ∈ 𝑞 do 11 if 𝑦 ∉ 𝑥® then 12 𝑞 = 𝑞 [𝛼 (𝑥, 𝑦) \ ⟨𝛼⟩(𝑥)] 13 else if 𝑥 ∉ 𝑥® then 14 𝑞 = 𝑞 [𝛼 (𝑥, 𝑦) \ ⟨𝛼 − ⟩(𝑦)] 15 return 𝑞

Example 24. For the algorithm ARCO the only new step in this section is the removal of existential variables. For demonstration purposes consider the query 𝑞(𝑥, 𝑦) := 𝛼 1 (𝑥, 𝑦), 𝛼 2 (𝑥 1, 𝑦), 𝛼 3 (𝑥, 𝑦1 ). Then, the returned query of remove∃Var(q) is 𝑞(𝑥, 𝑦) := 𝛼 1 (𝑥, 𝑦), ⟨𝛼 2− ⟩(𝑦), ⟨𝛼 3 ⟩(𝑥). Since for 𝛼 2 (𝑥 1, 𝑦) variable 𝑦 on the right side is bound, we have to invert 𝛼 2 . If we consider 𝛼 2 to be from Figure 3c, then the following is the inverse 𝛼 2− . t−

5

r 𝑠8

𝑠9

C?

𝑠 10

Table 2: Statistics of ontologies and Neo4j data

ontology

# concepts

# roles

Neo4j data #nodes #relations

DBPedia MMM

1230 53

1212 18

10 075 182 107 624

22 194 296 379 002

Setup and Implementation. All experiments were executed on a virtual machine with 400 GB RAM and 16 cores running Debian GNU/Linux 12 (Bookworm). The host machine is equipped with an AMD EPYC 7313 processor clocked at 2.00 GHz. Neo4j 5.25.0 was deployed on the same virtual machine. We implemented a prototype of our rewriting algorithm ARCO in Java. We base our implementation on several external libraries: the OWL API [24] to parse and extend OWL ontologies, the Hermit reasoner [23] to verify the JumpTrans candidates, ANTLR [34] for parsing the input CN2RPQs, the Java library JgraphT [30] for the internal representation of n-NFAs, and finally Cypher DSL [36] to convert the output into Cypher syntax.

Proof. Given a DL-LitePG TBox T and an ABox A and a joinon-free CN2RPQ 𝑞(𝑥). ® From For (⇒) assume that 𝑎® of individuals from A is a certain answer to 𝑞(𝑥) ® over (T , A). From Lemma 6 it holds that 𝑎® is a certain answer to 𝑞 ⟨∃⟩ (𝑥) ® over (T , A), i.e., 𝑎® = 𝜇 (𝑥) ® and (𝜇 (𝑥), 𝜇 (𝑦)) ∈ 𝛼 IT,A (or (𝜇 (𝑥) ∈ 𝛼 IT,A ) for each atom 𝛼 (𝑥, 𝑦) (or 𝛼 (𝑥)) in 𝑞 ⟨∃⟩ (𝑥). ® By Lemma 4 we can imply that (𝜇 (𝑥), 𝜇 (𝑦)) ∈ arco T (𝛼) A and (𝜇 (𝑥) ∈ arco T (𝛼) A respectively. Thus, the claim holds that 𝑎® is an answer to arco T (𝑞 ⟨∃⟩ (𝑥)) ® over A. Since the claims in Lemma 4 and Lemma 6 hold in both directions, the proof for (⇐) is analogous. □

𝑠7

CIKM, November 07–11,2026, Rome, IT

Ontology and Data. To evaluate our rewriting algorithm, we considered two real-world ontologies from different domains with divergent characteristics. In Table 2 we provide the number of concepts and roles for each ontology. DBPedia [29] is a dataset containing extracted data from Wikipedia articles, which is of interest to our rewriting algorithm due to its size. The second dataset is the open data of Montpellier Méditerranée Métropole [7] (MMM), which covers the sewer system of the city. This ontology contains existentials on the right-hand side, which triggers skipAnon T (𝛼 0 ) from Section 3. To the best of our knowledge, the current version of the OWL2 standard [39] does not support data tests in role inclusions, i.e., axioms of the form {𝑝 ⊙ 𝑣 ?} ⊑ 𝑟 ; therefore, we do not consider this kind of axioms in the evaluation. Each ontology in Table 2 is associated with a corresponding dataset stored in a separate Neo4j database. We choose Neo4j because it provides a level of GQL compliance sufficient for our experimental evaluation. We relate concepts in the ontology to node labels in the database, while roles are related to relationship types, i.e., edge labels.

start

Implementation & Experiments

In this section, our aim is to show the practical utility of our rewriting algorithm ARCO (cf. Section 4). To this end, we implemented a prototype of our rewriting algorithm in Java. This prototype takes as input a navigational query (join-on-free CN2PRQ), using a custom format, and rewrites it with respect to a DL-LitePG ontology (our DL-Lite extension supporting tests over property values) expressed in the OWL format. As part of the experiments, we then run the produced Cypher queries over a Neo4j database and report on the results. We share the source code of our prototype anonymously5 and will make it publicly available in the future. 5 https://anonymous.4open.science/r/owl2cypher/README.md

Queries. Since no benchmark queries are available for rewriting join-on-free CN2RPQs, we adopt two approaches for constructing evaluation queries: (1) to evaluate the rewriting algorithm we synthetically generate 100 N2RPQs by randomly selecting concepts and roles from a given ontology, and by randomly applying operators such as concatenation, union, and the Kleene star, while enforcing structural constraints such as bounded path lengths and nesting levels; (2) for the evaluation with Neo4j of the rewritten queries we additionally handcraft a set of 5 queries based on the MMM dataset and the SPARQL queries therein. Results. Figure 4 shows the results of rewriting the generated queries. Notice in these figures we report the results as pairs: for each query, we show its transitions (seen as an N2RPE) before and after rewriting, on the x axis. Both data poins share the same y-axis,

CIKM, November 07–11,2026, Rome, IT

input output

input output

150

100

600 Rewriting Time [ms]

600 Rewriting Time [ms]

Rewriting Time [ms]

200

Loehnert et al.

400

200

400

200

50 0

0 0

50

100 150 200 250 Number of Transitions

300

5

(a) DBPedia

10 15 20 25 Number of Transitions

0

30

1,000

2,000

3,000

4,000

5,000

Number of relevant skipRel tuples

(b) MMM

(c) MMM

Figure 4: Runtime of the rewriting algorithm.

›) at 1000s.

Evaluation Time [s]

15

Table 3: Evaluation of MMM dataset. Timeout(

10

query Q1 Q2 Q3 Q4 Q5

5

0

0

50 100 150 200 250 Number of Transitions (Output)

300

transitions input output 6 6 6 9 3 6 5 20 4 10

# skipRel 52 468 52 624 312

time [ms] rew. eval. 153 52 114 137 42 377 845 69 41

› › ›

Figure 5: Evaluation of DBPedia dataset. 56 timeouts at 20s.

6 indicating the rewriting time. Although the DBPedia ontology contains significantly more concepts and roles, rewriting is generally faster (under 250 ms) than with the MMM ontology (around 600 ms). This is because DBPedia does not contain any axioms with existentials on the right-hand side (𝐴 ⊑ ∃𝑟 .⊤). Therefore, there are no relevant SkipRel tuples. As can be seen from Figure 4a, the rewriting time depends on the number of transitions in the rewritten query for DBPedia. From the results with the MMM dataset, we can conclude that, if there are relevant SkipRel tuples, they seem to impact the rewriting time more than a high number of concepts (see Figure 4b and Figure 4c). It should be noted that for 62 of the 100 generated queries computing the power set was not feasible given the number of states of the query (≥ 30). While the evaluation of rewriting times already shows practical feasibility, the generated queries with Neo4j still seems to be a challenge, as suggested by the results in Table 3 and Figure 5. In the DBPedia dataset, we see queries falling into two groups: either running within 2 to 8 seconds or quickly timing out (with the timeout at 20s). We see only a weak correlation with number of transitions in the output. Similarly, 3 of 5 queries over the MMM dataset time out. The reasons for the high evaluation times may be, on the one hand, query constructions that initiate the computation of the Cartesian product or, on the other hand, a high number of query answers. Note, that the generated queries do not return any answers, as could be anticipated. However, optimising the evaluation of the generated queries was out of scope. From these results, it is clear that there is a need to understand exactly why rewritten queries time-out and how to achieve optimal rewritten queries.

Conclusion

In this paper, we present the first practical algorithm for rewriting N2RPQs and a significant subset of CN2RPQs, making use of the ability of modern graph databases to express complex navigational queries with nesting. We particularly note the ability of our approach to access key values within path expressions in the presence of an ontology with data tests. The result is a highly flexible approach to ontology-mediated querying of property graphs that still allows for query rewriting into native graph database technologies. We have demonstrated the formal correctness of our approach and provided a proof-of-concept implementation that can rewrite Cypher queries to incorporate ontological knowledge and evaluate the rewritten queries using Cypher. To achieve a simple and practicable solution we focused on joinon-free CN2RPQs. This does not seem too limiting: even plain N2RPEs can already express many realistic examples that involve complex bidirectional navigation on the anonymous implicit facts; arbitrary conjunctions over the free variables make the query language even more powerful. We expect that real-world queries that require different regular paths to travel separately and join somewhere in the unnamed part of the canonical model will very rarely emerge in practice, if at all. We stress that algorithms for full extended CN2RPQs in expressive DLs have been available for over a decade [8]. It is not difficult to adapt these algorithms and extend our technique to be complete for all CN2RPQs and DL-LitePG ontologies; in fact, we do that in the extended version of this paper. However, this seems to dramatically increase the run time of the rewriting algorithm, and the added value seems limited, as we have not yet found a good use case for queries beyond our join-on-free fragment. We may explore this further.

Rewriting Ontology-Mediated Property Graph Queries into GQL

Other promising extensions that we plan to explore include improved the support for property values and more expressive ontology languages. For the former, we will consider existing works on query rewriting with data values [5, 35]. For the latter, we will build on recent efforts to identify richer ontology languages with NL data complexity [3, 17, 28]. This work brings us significantly closer to making ontologybased data-access over graph databases a reality, and as such, we aim to explore the potential of our technique for real-life OBDA systems with navigational capabilities, and to conduct experiments on systems supporting GQL as soon as they become available. This includes the work of extending our data model to align more closely with PGs and also to explore practical methods to go beyond the join-on-free fragment. Another interesting line of future work would be the creation of useful benchmarks that combine both complex navigational queries with rich ontologies expressed over them.

Acknowledgments This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/COE12, 10.55776/PIN8884924 and 10.55776/P34962. For open access purposes, the author has applied a CC BY public copyright license to any author accepted manuscript version arising from this submission. This work was partially supported by the State of Salzburg under grant number 20102F2101143-FPR (DNI). We thank the reviewers for their insightful comments and Jean Christoph Jung for pointing out a crucial issue with the completeness of the rewriting algorithm in a preliminary version of this paper.

References [1] Renzo Angles. 2018. The Property Graph Database Model. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21-25, 2018 (CEUR Workshop Proceedings, Vol. 2100), Dan Olteanu and Barbara Poblete (Eds.). CEUR-WS.org. https://ceur-ws.org/Vol2100/paper26.pdf [2] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5 (2017), 68:1–68:40. doi:10.1145/3104031 [3] János Arpási, Bartosz Bednarczyk, and Magdalena Ortiz. 2025. A Horn Extension of DL-Lite with NL Data Complexity. In Proceedings of the International Workshop on Description Logics (DL 2025). To appear. [4] Alessandro Artale, Vladislav Ryzhikov, and Roman Kontchakov. 2012. DL-Lite with Attributes and Datatypes. In ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31 , 2012 (Frontiers in Artificial Intelligence and Applications, Vol. 242), Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, and Peter J. F. Lucas (Eds.). IOS Press, 61–66. doi:10.3233/978-1-61499-098-7-61 [5] Franz Baader, Stefan Borgwardt, and Marcel Lippmann. 2017. Query Rewriting for DL-Lite with n-ary Concrete Domains. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, Carles Sierra (Ed.). ijcai.org, 786–792. doi:10.24963/ IJCAI.2017/109 [6] Andrew Bate, Boris Motik, Bernardo Cuenca Grau, Frantisek Simancík, and Ian Horrocks. 2016. Extending Consequence-Based Reasoning to SRIQ. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, Cape Town, South Africa, April 25-29, 2016, Chitta Baral, James P. Delgrande, and Frank Wolter (Eds.). AAAI Press, 187–196. https: //aaai.org/papers/20-12882-extending-consequence-based-reasoning-to-sriq/ [7] Haydar Batoul, Nanée Chahinian, and Claude Pasquier. 2024. From Standards to an Ontology-Based Data Access system for Sewer Networks. In 10ème Journées Doctorales en Hydrologie Urbaine. [8] Meghyn Bienvenu, Diego Calvanese, Magdalena Ortiz, and Mantas Simkus. 2014. Nested Regular Path Queries in Description Logics. In Principles of Knowledge

CIKM, November 07–11,2026, Rome, IT

Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014, Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter (Eds.). AAAI Press. http://www.aaai.org/ocs/index. php/KR/KR14/paper/view/8000 [9] Meghyn Bienvenu and Magdalena Ortiz. 2015. Ontology-Mediated Query Answering with Data-Tractable Description Logics. In Reasoning Web. Web Logic Rules - 11th International Summer School 2015, Berlin, Germany, July 31 - August 4, 2015, Tutorial Lectures (Lecture Notes in Computer Science, Vol. 9203), Wolfgang Faber and Adrian Paschke (Eds.). Springer, 218–307. https://doi.org/10.1007/9783-319-21768-0_9 [10] Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. 2015. Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms. J. Artif. Intell. Res. 53 (2015), 315–374. doi:10.1613/jair.4577 [11] Angela Bonifati, George H. L. Fletcher, Hannes Voigt, and Nikolay Yakovets. 2018. Querying Graphs. Morgan & Claypool Publishers. doi:10.2200/ S00873ED1V01Y201808DTM051 [12] Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. 2009. Regular Path Queries in Expressive Description Logics with Nominals. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, Craig Boutilier (Ed.). 714–720. http://ijcai.org/Proceedings/ 09/Papers/124.pdf [13] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2007. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Journal of Automated Reasoning 39, 3 (20 jul 2007), 385–429. doi:10.1007/s10817-007-9078-x [14] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 1999. Rewriting of Regular Expressions and Regular Path Queries. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA, Victor Vianu and Christos H. Papadimitriou (Eds.). ACM Press, 194–204. doi:10.1145/ 303976.303996 [15] Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL/PGQ. In SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, Zachary G. Ives, Angela Bonifati, and Amr El Abbadi (Eds.). ACM, 2246–2258. doi:10.1145/3514221.3526057 [16] Mirko Michele Dimartino, Andrea Calì, Alexandra Poulovassilis, and Peter T. Wood. 2016. Query Rewriting under Linear EL Knowledge Bases. In Web Reasoning and Rule Systems - 10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings (Lecture Notes in Computer Science, Vol. 9898), Magdalena Ortiz and Stefan Schlobach (Eds.). Springer, 61–76. https://doi.org/ 10.1007/978-3-319-45276-0_6 [17] Mirko Michele Dimartino, Peter T. Wood, Andrea Calì, and Alexandra Poulovassilis. 2025. Efficient Ontology-Mediated Query Answering: Extending DL-liteR and Linear ELH. J. Artif. Intell. Res. 82 (2025), 851–899. doi:10.1613/JAIR.1.16401 [18] Nikola Dragovic, Cem Okulmus, and Magdalena Ortiz. 2023. Rewriting OntologyMediated Navigational Queries into Cypher. In Proceedings of the 36th International Workshop on Description Logics (DL 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning (KR 2023 and NMR 2023)., Rhodes, Greece, September 2-4, 2023 (CEUR Workshop Proceedings, Vol. 3515), Oliver Kutz, Carsten Lutz, and Ana Ozaki (Eds.). CEUR-WS.org. https://ceur-ws.org/Vol-3515/paper-9.pdf [19] Thomas Eiter, Magdalena Ortiz, Mantas Simkus, Trung-Kien Tran, and Guohui Xiao. 2012. Query Rewriting for Horn-SHIQ Plus Rules. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, Jörg Hoffmann and Bart Selman (Eds.). AAAI Press, 726–733. http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4931 [20] Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2022. GPC: A Pattern Calculus for Property Graphs. CoRR abs/2210.16580 (2022). arXiv:2210.16580 doi:10.48550/arXiv.2210.16580 [21] Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. A Researcher’s Digest of GQL (Invited Talk). In 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece (LIPIcs, Vol. 255), Floris Geerts and Brecht Vandevoort (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1:1–1:22. doi:10.4230/LIPIcs.ICDT.2023.1 [22] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 1433–1445. doi:10.1145/3183713.3190657

CIKM, November 07–11,2026, Rome, IT

[23] Birte Glimm, Ian Horrocks, Boris Motik, Giorgos Stoilos, and Zhe Wang. 2014. HermiT: An OWL 2 Reasoner. J. Autom. Reason. 53, 3 (2014), 245–269. doi:10. 1007/S10817-014-9305-1 [24] Matthew Horridge, Sean Bechhofer, and Olaf Noppens. 2007. The OWL API. https://owlcs.github.io/owlapi/ Accessed: 2026-05-21. [25] Yevgeny Kazakov. 2009. Consequence-Driven Reasoning for Horn SHIQ Ontologies. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, Craig Boutilier (Ed.). 2040–2045. http://ijcai.org/Proceedings/09/Papers/336.pdf [26] Markus Krötzsch, Sebastian Rudolph, and Pascal Hitzler. 2013. Complexities of Horn Description Logics. ACM Trans. Comput. Log. 14, 1 (2013), 2:1–2:36. doi:10.1145/2422085.2422087 [27] Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, and Magdalena Ortiz. 2025. Query Rewriting for Nested Navigational Queries over Property Graphs. In Proceedings of the 38th International Workshop on Description Logics - DL 2025, Opole, Poland, September 3-6, 2025 (CEUR Workshop Proceedings), Lidia Tendera, Yazmín Ibáñez-García, and Patrick Koopmann (Eds.). CEUR-WS.org. https://ceurws.org/Vol-4091/paper40.pdf [28] Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, and Magdalena Ortiz. 2025. Towards Practicable Algorithms for Rewriting Graph Queries beyond DL-Lite. In The Semantic Web - 22nt International Conference, ESWC 2025, Portorož, Slovenia, June 1-5, 2025 (accepted for publication) (Lecture Notes in Computer Science). Springer. [29] Pablo N Mendes, Max Jakob, and Christian Bizer. 2012. DBpedia: A multilingual cross-domain knowledge base. European Language Resources Association (ELRA). [30] Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. 2020. JGraphT – A Java Library for Graph Data Structures and Algorithms. https://jgrapht.org/ Accessed: 2026-05-21. [31] Neo4j Contributors. [n. d.]. GQL Conformance - Cypher Manual. https://neo4j. com/docs/cypher-manual/current/appendix/gql-conformance/ Accessed: 202605-23. [32] Magdalena Ortiz, Sebastian Rudolph, and Mantas Simkus. 2011. Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ. In IJCAI 2011,

Loehnert et al.

Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, Toby Walsh (Ed.). IJCAI/AAAI, 1039–1044. doi:10.5591/978-1-57735-516-8/IJCAI11-178 [33] Piotr Ostropolski-Nalewaja and Sebastian Rudolph. 2024. The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024, Pierre Marquis, Magdalena Ortiz, and Maurice Pagnucco (Eds.). doi:10.24963/KR.2024/54 [34] Terence Parr. 2012. ANTLR (ANother Tool for Language Recognition). https: //www.antlr.org/ Accessed: 2026-05-21. [35] Ognjen Savkovic and Diego Calvanese. 2012. Introducing Datatypes in DLLite. In ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31 , 2012 (Frontiers in Artificial Intelligence and Applications). IOS Press, 720–725. doi:10.3233/978-1-61499-098-7-720 [36] Michael J. Simons and Neo4j Contributors. 2020. The Neo4j Cypher-DSL. https: //github.com/neo4j/cypher-dsl Accessed: 2026-05-21. [37] Giorgio Stefanoni, Boris Motik, Markus Krötzsch, and Sebastian Rudolph. 2014. The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases. J. Artif. Intell. Res. 51 (2014), 645–705. doi:10.1613/JAIR.4457 [38] Andreas Steigmiller, Thorsten Liebig, and Birte Glimm. 2014. Konclude: System description. J. Web Semant. 27-28 (2014), 78–85. doi:10.1016/J.WEBSEM.2014.06. 003 [39] W3C OWL Working Group. 2012. OWL 2 Web Ontology Language Document Overview (Second Edition). https://www.w3.org/TR/owl2-overview/ W3C Recommendation. Accessed: 2026-05-21. [40] Guohui Xiao, Diego Calvanese, Roman Kontchakov, Domenico Lembo, Antonella Poggi, Riccardo Rosati, and Michael Zakharyaschev. 2018. Ontology-Based Data Access: A Survey. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, Jérôme Lang (Ed.). ijcai.org, 5511–5519. doi:10.24963/IJCAI.2018/777

Received 23 May 2026; revised 7 August 2026; accepted 20 August 2026

Rewriting Ontology-Mediated Property Graph Queries into GQL

A

CIKM, November 07–11,2026, Rome, IT

Proofs for Section 3 (Rewriting N2RPQs)

In order to prove Lemma 3, we recall the following standard fact on canonical model homomorphism from the Description Logic literature. Fact 1. Let T be a TBox and A an ABox. Then, suppose that two nodes 𝑜 1 and 𝑜 2 are such that 𝑜 1 ∈ 𝐴 IT,A iff 𝑜 2 ∈ 𝐴 JT,A for every concept name 𝐴. Then, the two submodels IT,A rooted at 𝑜 1 and JT,A rooted at 𝑜 2 are isomorphic. Lemma 3. Let T be a DL-LitePG TBox and 𝛼 be an N2RPE. Then, for every PG A and every pair of nodes 𝑜𝑠 , 𝑜 𝑓 from A, it holds that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A iff (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A . Proof. Consider an DL-LitePG TBox T , a PG A = (𝑁 , 𝐸, label, prop) and an N2RPE 𝛼 = ⟨𝑄, Σ𝑃𝐺 , 𝑆, 𝛿, 𝐹 ⟩ of nesting depth 𝑘. (⇒) For the first direction, we show the claim by induction on the nesting depth 𝑘 of 𝛼. In the following we prove that, whenever (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A , then (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A for every pair of nodes 𝑜𝑠 , 𝑜 𝑓 in A. From (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A , it follows that there is a run (𝑇 , 𝑙) for 𝛼 on IT,A such that 𝑙 (𝑜𝑠 , 𝑠 0 ) and 𝑙 (𝑜 𝑓 , 𝑠 𝑓 ) with 𝑠 0 ∈ 𝑆 and 𝑠 𝑓 ∈ 𝐹 . Base Case. Suppose that 𝑘 = 0, then 𝑇 consists of a single path with the sequence of labels (𝑜 0, 𝑠 0 )(𝑜 1, 𝑠 1 ) . . . (𝑜𝑚 , 𝑠𝑚 ) from root to leaf. Note that 𝑜 0 = 𝑜𝑠 , 𝑜𝑚 = 𝑜 𝑓 and 𝑠𝑚 = 𝑠 𝑓 . We know from Definition 7 that for each 𝑖 ∈ {1, . . . , 𝑚} there is a transition (𝑠𝑖 −1, 𝜎𝑖 , 𝑠𝑖 ) ∈ 𝛿 such that one of the following cases holds (here we make use of the fact that there are no transitions with nested NFAs of the form ⟨𝛼𝑖 ⟩): D • 𝜎𝑖 ∈ 2R∪T and either (1) or (2): I (1) (𝑜𝑖 −1, 𝑜𝑖 ) ∈ (𝑝 ⊙ 𝑣?) IT,A for each data test 𝑝 ⊙ 𝑣? ∈ 𝜎𝑖 T,A I

(2) (𝑜𝑖 −1, 𝑜𝑖 ) ∈ 𝑟 IT,A for each 𝑟 ∈ 𝜎𝑖 T,A ∩ R • 𝜎𝑖 = 𝐶?, 𝑜𝑖 −1 = 𝑜𝑖 and 𝑜𝑖 ∈ 𝐶 IT,A • 𝜎𝑖 = 𝑝 ⊙ 𝑣?, 𝑜𝑖 −1 = 𝑜𝑖 and 𝑜𝑖 ∈ (𝑝 ⊙ 𝑣?) IT,A We can suppose without loss of generality that there is no 0 ≤ 𝑖, 𝑖 ′ ≤ 𝑚 such that 𝑖 ≠ 𝑖 ′ , 𝑠𝑖 = 𝑠𝑖 ′ , and 𝑜𝑖 = 𝑜𝑖 ′ (this can always be ensured by deleting parts of the path). Now let 𝑖 1 < · · · < 𝑖 𝑝 be all the indices 𝑖 such that 𝑜𝑖 ∈ 𝑁 of A (note that 𝑖 1 = 0 and 𝑖 𝑝 = 𝑚). Intuitively, 𝑖 1, . . . , 𝑖 𝑝 are the indices of the "projection" of the run obtained by restricting it to individuals occurring in the ABox. Claim 1 (cf. Claim 3 in [BCOS14]). For every 1 < ℓ ≤ 𝑝, one of the following holds: G (1) (𝑜𝑖 ℓ −1 , 𝑜𝑖 ℓ ) ∈ 𝜎𝑖 ℓ T,A , or (2) 𝑜𝑖 ℓ = 𝑜𝑖 ℓ −1 and there exists a strictly anonymous tuple (𝐶, 𝑠𝑖 ℓ −1 , 𝑠𝑖 ℓ , ∅) ∈ SkipRel(𝛼, T ) such that 𝑜𝑖 ℓ −1 ∈ 𝐶 GT,A . G

Proof of Claim 1. For the case where 𝑖 ℓ = 𝑖 ℓ −1 + 1 we immediately obtain (𝑜𝑖 ℓ −1 , 𝑜𝑖 ℓ ) ∈ 𝜎𝑖 ℓ T,A . Further, if 𝑖 ℓ ≠ 𝑖 ℓ −1 + 1, then 𝑜𝑖 ℓ −1 +1 ∉ 𝑁 . From this we can infer that all the objects 𝑜𝑖 ℓ −1 +1, . . . , 𝑜𝑖 ℓ −1 must be descendants of 𝑜𝑖 ℓ = 𝑜𝑖 ℓ −1 in IT,A . Now, let J be the canonical model of T and {𝐶 (𝑎)}. Then, by Fact 1 there is a homomorphism ℎ from IT,A to J with ℎ(𝑜𝑖𝑙 −1 ) = 𝑎. Consider the labelled tree (𝑇 ′, 𝑙 ′ ) obtained from (𝑇 , 𝑙) by (1) making the node labelled (𝑜𝑖 ℓ −1 , 𝑠𝑖 ℓ −1 ) the root and the node labelled (𝑜𝑖 ℓ , 𝑠𝑖 ℓ ) the unique leaf, and (2) replacing every node label (𝑜 ′, 𝑠 ′ ) by (ℎ(𝑜 ′, 𝑠 ′ ). It holds that (𝑇 ′, 𝑙 ′ ) is a partial run of 𝛼 on J . Hence, by Definition 14, (𝐶, 𝑠𝑖 ℓ −1 , 𝑠𝑖 ℓ , ∅) ∈ SkipRel(𝛼, T ) and since 𝑜𝑖 ℓ −1 +1 ∉ 𝑁 it follows that the tuple is strictly anonymous. (end proof of Claim 1) To conclude the base case for the main claim, we can simply construct a run (𝑇 , 𝑙) for skipAnon T (𝛼) GT,A , by combining all (𝑜𝑖 ℓ , 𝑠𝑖 ℓ ) from Claim 1. From the construction of skipAnon T (𝛼) in Definition 17 it follows that (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A . Induction Hypothesis. Assume that if (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A , then (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A holds for 𝛼 of nesting depth 𝑘. Induction step. Let us now consider the case where 𝛼 has nesting depth 𝑘 + 1. Let 𝑣 0, . . . , 𝑣𝑚 be the sequence of nodes in 𝑇 that begins with the root node labelled (𝑜𝑠 , 𝑠 0 ) and ends with the unique leaf node labelled (𝑜 𝑓 , 𝑠 𝑓 ). In the following we use (𝑜 ℓ , 𝑠 ℓ ) for the label of node 𝑛 ℓ . We can again assume w.l.o.g. that (𝑇 , 𝑙) is minimal in the sense that there are no distinct positions 0 ≤ 𝑖, 𝑖 ′ ≤ 𝑚 such that 𝑛𝑖 and 𝑛𝑖 ′ has the same label. Let 𝑖 1 < · · · < 𝑖 𝑝 be all of the indices 𝑖 such that 𝑜𝑖 ∈ 𝑁 and 𝑖𝑚 = 𝑜 𝑓 ∈ 𝑁 . Claim 2 (cf. Claim 6 in [BCOS14]). For every 1 < ℓ ≤ 𝑝, one of the following holds: G (1) there is some 𝛼 𝑗 of nesting depth ≤ 𝑘 + 1 with (𝑠𝑖 ℓ −1 , 𝜎, 𝑠𝑖 ℓ ) ∈ 𝛿 𝑗 such that (𝑜𝑖 ℓ −1 , 𝑜𝑖 ℓ ) ∈ 𝜎𝑖 ℓ T,A , or (2) 𝑜𝑖 ℓ = 𝑜𝑖 ℓ −1 and there exists a strictly anonymous tuple (𝐶, 𝑠𝑖 ℓ −1 , 𝑠𝑖 ℓ , Γ) ∈ skipRel(𝛼, T ) such that 𝑜𝑖 ℓ −1 ∈ 𝐶 GT,A Proof of Claim 2. From Definition 7 there are three possible cases: (a) 𝑛𝑖 ℓ is the unique child of node 𝑛𝑖 ℓ −1 (b) 𝑛𝑖 ℓ is one of two children of node 𝑛𝑖 ℓ −1 (c) node 𝑛𝑖 ℓ is a descendant, but not a child of 𝑛𝑖 ℓ −1 G

First consider case (a), then by Definition 7 there must be a transition (𝑠𝑖 ℓ −1 , 𝜎, 𝑠𝑖 ℓ ) ∈ 𝛿 𝑗 such that (𝑜𝑖 ℓ −1 , 𝑜𝑖 ℓ ) ∈ 𝜎𝑖 ℓ T,A , which satisfies the first statement of the claim. If case (b) holds, then by Definition 7 it follows that (𝑠𝑖 ℓ −1 , ⟨𝛼 ′ ⟩, 𝑠𝑖 ℓ ) ∈ 𝛿 𝑗 , 𝑜𝑖𝑙 = 𝑜𝑖 ℓ −1 , and the other child of 𝑛𝑖 ℓ −1 has label (𝑜𝑖 ℓ −1 , 𝑢), with 𝑢 the initial state of 𝛼 ′ . The labelled subtree of (𝑇 , 𝑙) that is rooted at (𝑜𝑖 ℓ −1 , 𝑢) is a run for 𝛼 ′ on IT,A . Since the nesting depth of 𝛼 ′ is ≤ 𝑘, we can apply the induction hypothesis. Thus, the first statement holds, i.e., (𝑠𝑖 ℓ −1 , 𝜎, 𝑠𝑖 ℓ ) ∈ 𝛿 𝑗 such that (𝑜𝑖 ℓ −1 , 𝑢) ∈ 𝜎 GT,A . Finally, consider case (c) where 𝑛𝑖 ℓ is not a child of 𝑛𝑖 ℓ −1 , which means that 𝑜𝑖 ℓ −1 +1 ∉ 𝑁 of A. From this we can infer that all nodes 𝑜𝑖 ℓ −1 +1, . . . , 𝑜𝑖 ℓ −1 must be descendants of 𝑜𝑖 ℓ −1 in IT,A , and 𝑜𝑖𝑙 = 𝑜𝑖 ℓ −1 . Let (𝑇 ′, 𝑙 ′ ) be the partial run obtained from (𝑇 , 𝑙) by

CIKM, November 07–11,2026, Rome, IT

Loehnert et al.

1. making 𝑛𝑖 ℓ −1 the new root node, 2. making 𝑣 a leaf node by dropping all children, for every descendant 𝑣 of 𝑛𝑖 ℓ −1 such that 𝑙 (𝑣) = (𝑜𝑖 ℓ −1 , 𝑠) and such that there is no 𝑣 ′ (different from 𝑣 and 𝑛𝑖 ℓ −1 ) with 𝑙 (𝑣 ′ ) = (𝑜𝑖 ℓ −1 , 𝑠 ′ ) and occurring along the path from 𝑛𝑖 ℓ −1 to 𝑣. Note that since (𝑇 , 𝑙) is a run, there are three types of leaf nodes in (𝑇 ′, 𝑙 ′ ): • node 𝑛𝑖 ℓ with label (𝑜𝑖 ℓ −1 , 𝑠𝑖 ℓ ) (on the main path) • nodes with labels of the form (𝑜𝑖 ℓ −1 , 𝑠) • nodes with labels of the form (𝑜, 𝑠 𝑓 ) with 𝑠 𝑓 ∈ 𝐹 𝑗 for some 𝛼 𝑗 (Observe that every label (𝑜, 𝑠) that appears in (𝑇 ′, 𝑙 ′ ) is an individual in the subtree in the anonymous part of IT,A rooted at 𝑜𝑖 ℓ −1 .) Now let J be the canonical model of T and 𝐶 (𝑑), then it follows from Fact 1 there exists a homomorphism ℎ between IT,A to J with ℎ(𝑜𝑖𝑙 −1 ) = 𝑑. Consider the labelled tree (𝑇 ′′, 𝑙 ′′ ) obtained from (𝑇 ′, 𝑙 ′ ) by replacing every node label (𝑜, 𝑠) by (ℎ(𝑜), 𝑠). Using the fact that ℎ is a homomorphism with ℎ(𝑜𝑖 ℓ −1 ) = 𝑑 and the above description of leaf nodes in (𝑇 ′, 𝑙 ′ ), one can show that (𝑇 ′′, 𝑙 ′′ ) is a partial run of 𝛼 on J that satisfies: • the root of 𝑇 ′′ is labelled (𝑑, 𝑠𝑖 ℓ −1 ) • there is a leaf node labelled (𝑑, 𝑠𝑖 ℓ ) • for every leaf node 𝑣 with 𝑙 (𝑣) = (𝑜, 𝑠) ≠ (𝑑, 𝑠𝑖 ℓ ), either 𝑠 ∈ 𝐹 𝑗 or 𝑜 = 𝑑 Since this partial run satisfies the conditions in Definition 14 the tuple (𝐶, 𝑠𝑖 ℓ −1 , 𝑠𝑖 ℓ , Γ) belongs to skipRel(𝛼, T ), if we let Γ contain all those states 𝑢 such that there is a leaf node (𝑑, 𝑢) with 𝑢 ≠ 𝑠𝑖𝑙 . Since we have that 𝑜𝑖𝑙 −1 +1 ∉ 𝑁 , the tuple is strictly anonymous and the second statement of the claim holds. (end of proof Claim 2) To conclude the proof for the first direction, we construct a run (𝑇 , 𝑙) for skipAnon T (𝛼) in GT,A in a similar fashion as for the base case by combining all labels (𝑜𝑖 ℓ , 𝑠𝑖 ℓ ) for 1 < ℓ < 𝑝. For tuples (𝐶, 𝑠𝑖 ℓ −1 , 𝑠𝑖 ℓ , Γ) ∈ skipRel(𝛼, T ) the run contains labels (𝑜𝑖 ℓ , 𝑢) for each 𝑢 ∈ Γ. By induction hypothesis there is a run (𝑇𝑢 , 𝑙𝑢 ) for 𝛼 𝑢 and by Definition 17 we can verify that (𝑇 , 𝑙) is a valid run for skipAnon T (𝛼), thus (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A holds. (⇐) The second direction we prove by induction on the nesting depth of skipAnon T (𝛼). Suppose that (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A for skipAnon T (𝛼) = ⟨𝑄 skip, Σ𝑃𝐺 , 𝑆 skip, 𝛿 skip, 𝐹 skip ⟩, then we prove that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A . From (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A it follows that there is a run (𝑇 , 𝑙) for skipAnon T (𝛼) on GT,A such that 𝑙 (𝑜𝑠 , 𝑠 0 ) and 𝑙 (𝑜 𝑓 , 𝑠 𝑓 ) with 𝑠 ∈ 𝑆 skip and 𝑠 𝑓 ∈ 𝐹 skip . Base Case. Consider the nesting depth of skipAnon T (𝛼) to be 𝑘 = 0. Then, 𝑇 has only a single path with the sequence of labels (𝑜 0, 𝑠 0 ) (𝑜 1, 𝑠 1 ) . . . (𝑜𝑚 , 𝑠𝑚 ) from root 𝑜 0 = 𝑜𝑠 to leaf 𝑜𝑚 = 𝑜 𝑓 . It suffices to show the following claim. I

Claim 3 (cf. Claim 2 in [BCOS14]). For every 0 ≤ 𝑖 ≤ 𝑚, it holds that (𝑜𝑖 , 𝑜𝑚 ) ∈ 𝛼 |𝑠T,A . 𝑖

Proof of Claim 3. The proof is by induction on 𝑖. The base case is when 𝑖 = 𝑚, in which case 𝑠𝑖 = 𝑠𝑚 and the claim trivially holds since 𝑠𝑚 is a final state. Now suppose that the claim holds for 𝑖 such that 𝑔 < 𝑖 ≤ 𝑚 (induction hypothesis). Consider the induction step with 𝑖 − 1 = 𝑔, we know by Definition 17 that (𝑜𝑔 , 𝑠𝑔 ) must satisfy one of the following conditions: (i) there is a transition (𝑠𝑔 , 𝜎, 𝑠𝑖 ) ∈ 𝛿, or (ii) there is a transition (𝑠𝑔 , 𝐶, 𝑠𝑖 ) such that there is a tuple (𝐶, 𝑠𝑔 , 𝑠𝑖 , ∅) ∈ skipRel(𝛼, T ). If (i) holds, then (𝑜𝑔 , 𝑜𝑖 ) ∈ 𝜎 IT,A by construction of the canonical model Definition 13. By induction hypothesis there is a (𝑇𝑖 , 𝑙𝑖 ) run, which is a (𝑜𝑖 , 𝑜𝑚 )-run for 𝛼 |𝑠𝑖 on IT,A . Now, let (𝑇 ′, 𝑙 ′ ) be the labelled tree obtained by creating a new node labelled (𝑜𝑔 , 𝑠𝑔 ) and making it the leaf of (𝑇 ′, 𝑙 ′ ). It is easy to verify that (𝑇 ′, 𝑙 ′ ) is a run of 𝛼 |𝑠𝑔 on IT,A . Next consider the case (ii) where (𝐶, 𝑠𝑔 , 𝑠𝑖 , ∅) ∈ skipRel(𝛼, T ), from which follows that 𝑜𝑔 = 𝑜𝑖 and 𝑜𝑔 ∈ 𝐶 IT,A . From Definition 14 we can infer that there is a partial run (𝑇𝐶 , 𝑙𝐶 ) of 𝛼 in the canonical model of (T , {𝐶 (𝑎)}) that satisfies the conditions below: • the root of 𝑇𝐶 is labelled (𝑎, 𝑠𝑔 ) • there is a unique leaf node 𝑣 with 𝑙𝐶 (𝑣) = (𝑎, 𝑠𝑖 ) Since 𝑜𝑔 ∈ 𝐶 IT,A it follows from Fact 1 that there is a homomorphism ℎ from the canonical model of (T , {𝐶 (𝑎)}) to IT,A with ℎ(𝑎) = 𝑜𝑔 . We obtain (𝑇𝐶′ , 𝑙𝐶′ ) by replacing every label (𝑜, 𝑠) in 𝑇𝐶 by (ℎ(𝑜), 𝑠). Using the fact that ℎ is a homomorphism, one can show that (𝑇𝐶′ , 𝑙𝐶′ ) defines a partial run of 𝛼 in IT,A that satisfies the following conditions: • the root of 𝑇𝐶′ is labelled (𝑜𝑔 , 𝑠𝑔 ) • there is a unique leaf node 𝑣 with 𝑙𝐶′ (𝑣) = (𝑜, 𝑠𝑖 ) Let (𝑇 , 𝑙) be the labelled tree obtained from (𝑇𝐶′ , 𝑙𝐶′ ) by replacing the unique leaf node labelled (𝑜𝑔 , 𝑠𝑖 ) by the tree (𝑇𝑖 , 𝑙𝑖 ). It follows from the components that (𝑇 , 𝑙) is a (𝑜𝑔 , 𝑜𝑚 )-run of 𝛼 |𝑠𝑔 on IT,A . (end proof of Claim 3) Since 𝑠 0 is an initial state of 𝛼, the statement can be generalized and it follows that (𝑜 0, 𝑜𝑚 ) ∈ 𝛼 IT,A . Induction Hypothesis. Assume that if (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipAnon T (𝛼) GT,A , then (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A holds for skipAnon T (𝛼) of nesting depth 𝑘. Induction Step. Suppose that (𝑜 0, 𝑠 0 )(𝑜 1, 𝑠 1 ) . . . (𝑜𝑚 , 𝑠𝑚 ) is the sequence of the run (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 GT,A such that 𝑜𝑠 = 𝑜 0 , 𝑜 𝑓 = 𝑜𝑚 and 𝑠 0, . . . , 𝑠𝑚 ∈ 𝑄, i.e., states of the automaton with the highest nesting depth. I

Claim 4 (cf. Claim 4 in [BCOS14]). For every 0 ≤ 𝑖 ≤ 𝑚, it holds that (𝑜𝑖 , 𝑜𝑚 ) ∈ 𝛼 |𝑠T,A . 𝑖

Proof of Claim 4. The proof is by induction on 𝑖. The base case is when 𝑖 = 𝑚, in which we consider a tree with a single node 𝑖 = 𝑚 and the claim is trivially satisfies since 𝑠𝑚 is a final state. Now suppose that the claim holds for 𝑖 such that 𝑔 < 𝑖 ≤ 𝑚. Consider the case

Rewriting Ontology-Mediated Property Graph Queries into GQL

CIKM, November 07–11,2026, Rome, IT

where 𝑖 − 1 = 𝑔, then the pair (𝑜𝑖 , 𝑠𝑖 ) satisfies one of the conditions, either: (i) there is a transition (𝑠𝑔 , 𝜎, 𝑠𝑖 ) ∈ 𝛿 or (ii) there is a tuple (𝐶, 𝑠𝑔 , 𝑠𝑖 , {𝑠 1Γ , . . . , 𝑠𝑛Γ }) ∈ skipRel(𝛼, T ) and there are corresponding transitions (𝑠𝑔 , 𝐶, 𝑠 1′ ), (𝑠 1′ , ⟨𝛼 1 Γ ⟩, 𝑠 2′ ), . . . , (𝑠𝑛′ , ⟨𝛼 𝑛 Γ ⟩) in skipAnon T (𝛼). If |𝑠 1

|𝑠𝑛

(i) holds we can immediately construct a (𝑜𝑔 , 𝑜𝑚 )-run of 𝛼 |𝑠𝑔 on IT,A in the same manner as in the base case. Next assume that case (ii) holds for (𝑜𝑔 , 𝑠𝑔 ). Then, 𝑜𝑔 = 𝑜𝑖 and there exists a tuple (𝐶, 𝑠𝑔 , 𝑠𝑖 , Γ) such that 𝑜𝑔 ∈ 𝐶 IT,A . By Definition 14 the existence of (𝐶, 𝑠𝑔 , 𝑠𝑖 , Γ) implies that there is a partial run (𝑇𝐶 , 𝑙𝐶 ) of 𝛼 in the canonical model of (T , {𝐶 (𝑎)}) that satisfies the following conditions: • the root of 𝑇𝐶 has label (𝑎, 𝑠𝑔 ) • there is a leaf node 𝑣 with 𝑙 (𝑣) = (𝑎, 𝑠𝑖 ) • for every leaf node 𝑣 with 𝑙𝐶 (𝑣) = (𝑜, 𝑠) ≠ (𝑎, 𝑠𝑖 ), either 𝑠 ∈ 𝐹 𝑗 , or 𝑜 = 𝑎 and 𝑠 ∈ Γ Since 𝑜𝑔 ∈ 𝐶 IT,A , it follows from Fact 1 that there is a homomorphism ℎ from the canonical model of (𝑇 , {𝐶 (𝑎)}) to IT,A with ℎ(𝑎) = 𝑜𝑔 . Let (𝑇 ′, 𝑙 ′ ) be obtained by replacing every label (𝑜, 𝑠) in 𝑇𝐶 by (ℎ(𝑜), 𝑠). Since ℎ is a homomorphism, one can show that (𝑇𝐶′ , 𝑙𝐶′ ) defines a partial run of 𝛼 in IT,A that satisfies the following conditions: • the root of 𝑇𝐶′ is labelled (𝑜𝑔 , 𝑠𝑔 ) • there is a leaf node 𝑣 with 𝑙𝐶′ (𝑣) = (𝑜𝑔 , 𝑠𝑖 ) • for every leaf node 𝑣 with 𝑙𝐶′ (𝑣) = (𝑜, 𝑠) ≠ (𝑜𝑙 , 𝑠𝑖 ), either 𝑠 ∈ 𝐹 𝑗 , or 𝑜 = 𝑜𝑔 and 𝑠 ∈ Γ. Next we consider the states in Γ, by induction hypothesis we can find for each 𝑠 𝑗 ∈ Γ a run (𝑇𝑠Γ𝑗 , 𝑙𝑠Γ𝑗 ) for 𝛼 |𝑠𝑗 on IT,A . Finally, we can conclude 𝑗

the claim by applying the induction hypothesis and the fact that 𝑐𝑔 = 𝑐𝑖 . Thus, we can construct a run (𝑇𝑔 , 𝑙𝑔 ) such that (𝑜𝑔 , 𝑜𝑚 ) ∈ 𝛼 IT,A from (𝑇𝐶′ , 𝑙𝐶′ ): • replace (unique) leaf node labelled (𝑜𝑔 , 𝑠𝑖 ) by the tree (𝑇𝑖 , 𝑙𝑖 ) • replace each leaf node labelled (𝑜𝑔 , 𝑠 𝑗 ) for 𝑠 𝑗 ∈ Γ by the tree (𝑇𝑠Γ𝑗 , 𝑙𝑠ΓΓ ) (end proof of Claim 4) I From Claim 4) it follows that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 |𝑜T,A , since 𝑜𝑠 is an initial state of 𝛼, we can conclude that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 IT,A . 𝑠

□

Lemma 4. Let T be a DL-LitePG TBox and 𝛼 be an N2RPE. Then, for every PG A and every pair of nodes 𝑜𝑠 , 𝑜 𝑓 from A, it holds that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 GT,A iff (𝑜𝑠 , 𝑜 𝑓 ) ∈ skipCore T (𝛼) A . ∗ be the restriction of T ∗ to the axioms that do not have existential concepts on the right, and for readability, for a given Proof. Let Tcore ∗ ,A . One can prove in the usual way (see, e.g., [EOS+ 12]) that G T,A = A ∗ . We can thus show A, we denote by A ∗ the canonical model ITcore that, for every 𝛼: ∗ 𝛼 A = (skipCore T (𝛼)) A .

Given the one-to-one correspondence between the rules (Ch1) to (Ch5), which add facts to A ∗ and the rules (R1) to (R5), which add transitions to skipCore T (𝛼), the equality is established by a simple rule-by-rule analysis in both directions. For the (⇐) direction, assume that an n-NFA 𝛼𝑖+1 was obtained by applying one of the rules (R1) to (R5) in Definition 19 to 𝛼𝑖 . In the G G following we show for each of the rules that it holds if (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖+1T,A (𝑥, 𝑦), then (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖 T,A (𝑥, 𝑦). I

T,A (𝑥, 𝑦) was obtained by applying the rule for 𝑟 ⊑ 𝑝 ∈ T and (𝑠 𝑗 , 𝑃, 𝑠 𝑗+1 ) ∈ 𝛿𝑖 with 𝑝 ∈ 𝑃 (or 𝑝 − ∈ 𝑃). (R1) Assume that 𝛼𝑖+1

G

Then, 𝛼𝑖+1T,A (𝑥, 𝑦) contains the transition (𝑠 𝑗 , 𝑅, 𝑠 𝑗+1 ) with 𝑅 = (𝑃 \ {𝑝}) ∪ {𝑟 } (or 𝑅 = (𝑃 \ {𝑝 − }) ∪ {𝑟 − }). We assume that (𝑜 𝑗 , 𝑜 𝑗+1 ) ∈ 𝑟 GT,A (or (𝑜 𝑗+1, 𝑜 𝑗 ) ∈ 𝑟 GT,A ) and from Definition 13 it follows that (𝑜 𝑗 , 𝑜 𝑗+1 ) ∈ 𝑝 GT,A (or (𝑜 𝑗+1, 𝑜 𝑗 ) ∈ 𝑝 GT,A ). (R2),(R3) The proof for these rules works equivalent to (R1). IT,A (R4) Assume that 𝛼𝑖+1 (𝑥, 𝑦) was obtained by the rule for ∃𝑟 .⊤ ⊑ 𝐵 and (𝑠 𝑗 , 𝐵?, 𝑠 𝑗+1 ) ∈ 𝛿𝑖 . Then, the function adds a transition with a nested NFA ⟨𝛼𝑟 ⟩ that contains a single transition with 𝑟 . By Definition 7 of a run and 𝛼𝑖+1 it holds that there has to be an individual 𝑜 𝑗 = 𝑜 𝑗+1 and a pair (𝑜 𝑗 , 𝑜 ′ ), such that (𝑜 𝑗 , 𝑜 ′ ) ∈ 𝑟 GT,A . From Definition 13 it follows that 𝑜 𝑗 ∈ 𝐵 GT,A and G thus (𝑜 𝑗 , 𝑜 𝑗+1 ) ∈ 𝛼𝑖 T,A . (R5) In this case 𝛼𝑖+1 was obtained based on 𝑇 ⊑ 𝐷 ∈ T ∗ and (𝑠 𝑗 , 𝐷?, 𝑠 𝑗+1 ) ∈ 𝛿𝑖 . For each 𝑡 ℓ ∈ 𝑇 there is a transition ′ ) ∈ 𝛼 ′ ′ ′ ′ ′ ′ (𝑠 ℓ′ , 𝑡 ℓ ?, 𝑠 ℓ+1 𝑖+1 , where 𝑠 𝑗 = 𝑠 1 , 𝑠𝑘+1 = 𝑠 𝑗 and 𝑠 2 , . . . , 𝑠𝑘 are fresh states, i.e., 𝑠 2 , . . . , 𝑠𝑘 ∉ 𝑆𝑖 . By Definition 7 and ′ ) ∈ 𝛼 GT,A . Further, by the construction of the canonical model item (𝑠 ℓ′ , 𝑡 ℓ ?, 𝑠 ℓ+1 , it follows that 𝑜 = 𝑜 and 𝑜 ∈ 𝑇 𝑖+1 𝑗 𝑗+1 𝑗 (Ch5) we can infer that 𝑜 𝑗 ∈ 𝐷 GT,A . (⇒) In order to show completeness we first introduce the notion of degree, that comes from the canonical model construction: We denote individuals or pair of individuals in the extension of concepts and roles as facts, i.e., 𝑣 ∈ 𝐵 G𝑗 or (𝑣, 𝑤) ∈ 𝑟 G𝑗 . A fact that occurs for the first time in G𝑗 has degree 𝑗, and a set of facts gets the sum of the degrees of its elements. The degree of sequence 𝑜𝑠 𝜎1𝑜 1 . . . 𝜎𝑛 𝑜𝑛 𝜎 𝑓 𝑜 𝑓 witnessing (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼 GT,A (𝑥, 𝑦) is the minimal degree of a set of facts that is sufficient to witness all a run in Definition 7, including the nested automata. Note that there may be more than one way to witness not only the automata, but even for a fixed (top level) sequence, we may have choices, but we don’t care. We set the degree to be the smallest, and then every added transition will allow us to witness the same sequence but with a strictly smaller degree. Having the notion of degree for a pair in place we show by induction that in each rewriting step we are "moving up" the part of the canonical model (decreasing the degree) that is induced by the axioms in T . In the following we show

CIKM, November 07–11,2026, Rome, IT

Loehnert et al.

that for each of the rules in Definition 13 there is a corresponding rule in Definition 17 producing a n-NFA 𝛼𝑖+1 from 𝛼𝑖 such that the degree of the accepted sequence is strictly smaller. (Ch1) Consider 𝑟 ⊑ 𝑝 ∈ T and (𝑜𝑘 , 𝑜𝑘+1 ) ∈ 𝑟 G𝑗 , (𝑜𝑘 , 𝑜𝑘+1 ) ∉ 𝑝 G𝑗 and (𝑜𝑘 , 𝑜𝑘+1 ) ∈ 𝑝 G𝑗 +1 by construction of the canonical model. G Consider the sequence (𝑜𝑠 𝜎1𝑜 1 . . . 𝑜𝑘 𝑟𝑜𝑘+1 . . . 𝑜𝑛 𝜎 𝑓 𝑜 𝑓 ) such that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖 T,A . In the rewriting we apply (R1) to obtain 𝛼𝑖+1 from 𝛼𝑖 , where we add for each transition (𝑠, 𝑃, 𝑠 ′ ) with 𝑝 ∈ 𝑃 (or 𝑝 − ∈ 𝑃) a new transition (𝑠, 𝑅, 𝑠 ′ ) such that G 𝑅 = (𝑃 \ {𝑝}) ∪ {𝑟 } (or 𝑅 = (𝑃 \ {𝑝 − }) ∪ {𝑟 − }), thus (𝑜 1 . . . 𝑜𝑘 𝑟𝑜𝑘+1 . . . 𝑜𝑛 ) will be accepted by 𝛼𝑖+1T,A , for which the degree is strictly smaller then for (𝑜𝑠 𝜎1𝑜 1 . . . 𝑜𝑘 𝑝𝑜𝑘 . . . 𝑜𝑛 𝜎 𝑓 𝑜 𝑓 ). (Ch2),(Ch3) For 𝑇 ⊑ 𝑟 ′ ∈ T the skipping rule (R2) and for 𝐴 ⊑ 𝐵 ∈ T (R3) applies. In both cases the reasoning is similar to (Ch1). (Ch4) Given ∃𝑟 .⊤ ⊑ 𝐵 ∈ T and by construction of the canonical model some individual 𝑜𝑘 ∈ (∃𝑟 .⊤) G𝑗 , 𝑜𝑘 ∉ 𝐵 G𝑗 𝑜𝑘 ∈ 𝐵 I𝑗 +1 . G Consider a sequence of the form (𝑜𝑠 𝜎1𝑜 1 . . . 𝑜𝑘 𝐵𝑜𝑘 . . . 𝑜𝑛 𝜎 𝑓 𝑜 𝑓 ) such that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖 T,A . In skipping we apply rule (R4) to ′ ′ obtain 𝛼𝑖+1 and add for each (𝑠, 𝐵?, 𝑠 ) ∈ 𝛿 the transition (𝑠, ⟨𝛼𝑟 ⟩, 𝑠 ) to 𝛿, where 𝛼𝑟 is a fresh two-state NFA with a single G transition (𝑠 01, {𝑟 }, 𝑠 1𝑓 ). Since 𝑜𝑘 ∈ (∃𝑟 .⊤) G𝑗 there has to be some sequence (𝑜𝑘 𝑟𝑜𝑘′ ), such that (𝑜𝑘 , 𝑜𝑘′ ) ∈ 𝛼𝑟 T,A and we can G

construct a run with strictly smaller degree such that (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖+1T,A . (Ch5) In this case that 𝑇 ⊑ 𝐵 ∈ T , 𝑜𝑘 ∈ 𝑇 𝑗G and 𝑜𝑘 ∉ 𝐵 𝑗G triggered the rule. Consider again the sequence G

(𝑜𝑠 𝜎1𝑜 1 . . . 𝑜𝑘 𝐵𝑜𝑘 . . . 𝑜𝑛 𝜎 𝑓 𝑜 𝑓 ) with (𝑜𝑠 , 𝑜 𝑓 ) ∈ 𝛼𝑖 T,A . Based on 𝑇 ⊑ 𝐵 ∈ T , 𝑜𝑘 ∈ 𝑇 𝑗G the skipping function applies rule (R5). It follows that for (𝑠, 𝐵?, 𝑠 ′ ) ∈ 𝛿 we add for each 𝑡 ℓ ∈ 𝑇 a transition (𝑠 ℓ , 𝑡 ℓ ?, 𝑠 ℓ+1 ), where 𝑠 = 𝑠 1 and 𝑠 𝑗+1 = 𝑠 ′ , and 𝑠 2′ , . . . , 𝑠𝑘′ G

are fresh states. Since 𝑜𝑘 ∈ 𝑇 G𝑗 , it holds that 𝑜𝑘 ∈ 𝑡 ℓ 𝑗 for each of the 𝑡 ℓ ∈ 𝑇 and the degree of the sequence from 𝑜𝑠 to 𝑜 𝑓 is strictly smaller. ∗ these rules do not apply (and are covered by Definition 17). (Ch6),(Ch7) Since we only consider Tcore □

References for the Appendix [BCOS14] Meghyn Bienvenu, Diego Calvanese, Magdalena Ortiz, and Mantas Simkus. Nested regular path queries in description logics. In Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. AAAI Press, 2014. [EOS+ 12] Thomas Eiter, Magdalena Ortiz, Mantas Simkus, Trung-Kien Tran, and Guohui Xiao. Query rewriting for Horn-SHIQ plus rules. In Jörg Hoffmann and Bart Selman, editors, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, pages 726–733. AAAI Press, 2012.

Related documents

• Rewriting Ontology-Mediated Property Graph Queries into GQL#1084325
• Flexible and Expressive Typed Path Patterns for GQL#336032
• Expressive Power of Property Graph Constraint Languages#1084152
• CADENZA: Compiling Natural-Language Intent into Task-Specific Operator DAGs for Semantic Query Processing#324988
• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window#1084587