Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

<EMAIL_ADDRESS>]

[orcid=0000-0002-3036-6201<EMAIL_ADDRESS>]

[orcid=0000-0002-7742-0439<EMAIL_ADDRESS>]

[orcid=0000-0002-2344-9658<EMAIL_ADDRESS>]

# Towards Practicable Algorithms for Rewriting Graph Queries beyond DL-Lite

Bianca Löhnert  Nikolaus Augsten  Cem Okulmus  Magdalena Ortiz

(2024)

###### Abstract

Despite the many advantages that ontology-based data access (OBDA) has brought
to a range of application domains, state-of-the-art OBDA systems still do not
support popular graph database management systems such as Neo4j. Algorithms
for query rewriting focus on languages like conjunctive queries and their
unions, which are fragments of first-order logic and were developed for
relational data. Such query languages are poorly suited for querying graph
data. Moreover, they also limit the expressiveness of the ontology languages
that admit rewritings, restricting them to those where the data complexity of
reasoning is not higher than it is in first-order logic. In this paper, we
propose a technique for rewriting a family of navigational queries for a
suitably restricted fragment of $\mathcal{ELHI}$ that extends DL-Lite and that
is NL-complete in data complexity. We implemented a proof-of-concept prototype
that rewrites into Cypher queries, and tested it on a real-world cognitive
neuroscience use case with promising results.

##  1 Introduction

The virtual knowledge graph (VKG) paradigm [1], also known as ontology-based
data access (OBDA), has seen successful adoption and brought significant
advantages to a range of applications [2]. But so far, it remains limited to
relational database management systems (RDBMS), and does not support popular
graph databases and their query languages. The key problem to address here is
_ontology-mediated query answering_ (OMQA), where a query is to be evaluated
not directly over a plain dataset, but over the consequences of the given
dataset together with the knowledge in the ontology. The predominant technique
for OMQA is _query rewriting_ , where an input query is transformed to
incorporate the ontological knowledge so that the rewritten query can be
evaluated over any input dataset using standard technologies (i.e., SQL
queries and standard RDBMs), without further ontological reasoning, and give
complete answers that take into account implicit facts [3]. The so-called
_union of conjunctive queries_ , which capture popular SQL fragments [4] are
used as source and target languages for query rewriting. However, this
technique can only be deployed for ontology languages whose data complexity is
not higher than that of SQL evaluation. The DL-Lite family of description
logics (DLs) was introduced with this goal in mind, and has become the
ontology language of choice for OMQA [3].

But while traditional RDBMS are not going away, recent years have seen huge
adoption of new paradigms for storing and querying data, and bringing the VKG
paradigm to them would open up opportunities in many application domains.
Particularly popular are _graph databases_ that adopt the _property graph_
(PG) data model [5]. PGs comprise nodes and edges between them; both nodes and
edges can be labelled, and have assigned key-value pairs. In addition to a new
data model, graph databases also provide unique querying abilities not found
in the relational setting. Ongoing efforts at the International Organisation
for Standardization (ISO) are now in an advanced phase, close to a new
standard for graph query languages. This upcoming standard, called GQL [6],
captures and extends _conjunctive two-way regular path queries_ (C2RPQ), the
query language for graphs most widely studied in the OMQA literature.

Query languages for graph data like C2RPQ and GQL are characterised by the
_navigational features_ that allow queries to traverse paths of arbitrary
length that comply with some _regular path expression_. This fundamentally
recursive feature results in a higher data complexity than that of SQL, and
graph query languages are typically NL complete in data complexity (under the
so-called _walk semantics_). This higher complexity, however, also means that
we are not bound to DL-Lite and can potentially consider richer query
languages with NL data complexity. To our knowledge, the only such DLs so far
are the linear fragments of $\mathcal{ELH}$ and $\mathcal{ELHI}$ identified by
Dimartino et al. [7], which we consider in this paper (with minor
restrictions). That work also introduced a query rewriting procedure for
instance queries and CQs based on finite state automata but, unfortunately, it
seems that it was never implemented. When it comes to navigational ontology
mediated queries, there is a rich body of theoretical work that considers
C2RPQs as the input query language [8, 9, 10], but the goal of those works was
to understand the computational complexity and they do not provide
implementable query rewriting algorithms. The only practical approach to
rewriting navigational queries is the recent algorithm for DL-Lite [11] that
we extend to linear $\mathcal{ELHI}$. Our main contributions are as follows.
• In Section 3, we explore the limitations of C2RPQ rewriting, showing that
even for lightweight ontologies, it is not possible to rewrite C2RPQs to
capture all consequences from the ontology.
• Inspired by this insight, we identify a subset of C2RPQs, which we call
Navigational Conjunctive Queries (NCQs), which can be rewritten into unions of
C2RPQs.
• We propose such a rewriting for OMQs that pair NCQs with ontolgies in a
fragment of $\mathcal{ELHI}$ that allows for reasoning in NL in data
complexity. We obtain the rewriting in three steps. First, in Section 4, we
address standard reasoning in DL leveraging a graph structure, which we then
use in Section 5 to rewrite atomic queries into C2RPQs that capture all the
relevant consequences from the ontology. Finally, we combine this algorithm
with the ideas behind the well-known Clipper rewriting [12] to obtain a
rewriting of NCQ into UC2RPQs in Section 6.
• We present a proof-of-concept prototype of our technique and use it to
evaluate queries over data from a real-world use case in the domain of
cognitive neuroscience.

##  2 Preliminaries

### Ontology language

$\mathcal{ELHI}^{lin}$ is tailored to subsume (the positive fragment of) DL-
LiteR and extend it with some of the expressiveness of
$\mathcal{E}\mathcal{L}$, while keeping data complexity in NL.

######  Definition 1 ($\mathcal{ELHI}^{lin}$).

We assume disjoint countably infinite sets $\mathbf{C}$, $\mathbf{R}$ and
$\mathbf{N}$ of _concept names_ , _role names_ , and _individuals_
respectively, and define the set of _roles_ as
$\overline{\mathbf{R}}=\mathbf{R}\cup\\{r^{-}\mid r\in\mathbf{R}\\}$.
_Concepts_ are inductively defined according to the following syntax rule

$\displaystyle C,D::=A\mid\top\mid\exists r.C\mid\exists r^{-}.\top$

where $A\in\mathbf{C}$ and $r\in\mathbf{R}$. A _concept inclusion_ (CI) is an
expression $C\sqsubseteq D$, where $C,D$ are concepts. A _role inclusion_ (RI)
is an expression $r\sqsubseteq s$, where $r,s\in\mathbf{R}$. A finite set of
CIs and RIs forms a _TBox_ $\mathcal{T}$. For a set of RIs in $\mathcal{T}$ we
use $\sqsubseteq^{*}_{\mathcal{T}}$ to denote the reflexive transitive closure
of $\\{(r,s)\mid r\sqsubseteq s\in\mathcal{T}\\}$. We say $r$ is a _subrole of
$s$ (in $\mathcal{T}$)_ if $r\sqsubseteq^{*}_{\mathcal{T}}s$.

As usual, the semantics is given by _interpretations_
$\mathcal{I}=(\varDelta^{\mathcal{I}},\cdot^{\mathcal{I}})$, where
$\varDelta^{\mathcal{I}}$ is a non-empty set called the _domain_ and
$\cdot^{\mathcal{I}}$ is the _interpretation function_ , which assigns to
every $A\in\mathbf{C}$ a set
$A^{\mathcal{I}}\subseteq\varDelta^{\mathcal{I}}$, and to every
$r\in\mathbf{R}$ a relation
$r^{\mathcal{I}}\subseteq\varDelta\times\varDelta$. It is extended to concepts
and CIs in the usual way, see the appendix. We say $\mathcal{I}$ is a _model_
of $\mathcal{T}$ if $\mathcal{I}$ satisfies every axiom in $\mathcal{T}$.

$\mathcal{ELHI}^{lin}$ restricts the usual $\mathcal{ELHI}_{\bot}$ by
disallowing conjunction and existential restrictions of the form $\exists
r^{-}.B$, since both are well-known to increase the data complexity to P-hard,
and are thus not rewritable into usual graph query languages. Note that we
must disallow inverse roles from role inclusions to ensure $\exists r^{-}.B$
is not expressible. For convenience, we recall in the appendix how these
existential restrictions can simulate conjunction. $\mathcal{ELHI}^{lin}$ is
closely related, but different from the _harmless fragment of linear
$\mathcal{ELHI}$_ studied in [13]; we defer a detailed comparison to future
work. To keep the material accessible despite the space constraints, we omit
disjointness axioms from $\mathcal{ELHI}^{lin}$, but they can be incorporated
with relative ease.

It will be convenient to focus on TBoxes in normal form; the proof that every
TBox can be linearly normalized while preserving the semantics is standard.

######  Definition 2 (Normalized $\mathcal{ELHI}^{lin}$ TBox).

A $\mathcal{ELHI}^{lin}$ TBox $\mathcal{T}$ is normalized, if each CI or RI in
$\mathcal{T}$ has one of the following forms, where
$A,B\in\mathbf{C}\cup\\{\top\\}$ and $r,s\in\mathbf{R}$.

$\displaystyle(NF1)\ A\sqsubseteq B$ $\displaystyle(NF2)$ $\displaystyle\
\exists r.A\sqsubseteq B$ $\displaystyle(NF3)$ $\displaystyle\
A\sqsubseteq\exists r.B$ $\displaystyle(NF4)\ r\sqsubseteq s$
$\displaystyle(NF5)$ $\displaystyle\ \exists r^{-}.\top\sqsubseteq B$
$\displaystyle(NF6)$ $\displaystyle\ A\sqsubseteq\exists r^{-}.\top$

### Data model

In this paper we assume that the data, that is, the ABox, takes the form of a
finite _property graph_. A TBox $\mathcal{T}$ paired with an ABox
$\mathcal{A}$ is sometimes called a _knowledge base_.

######  Definition 3 (Property Graph).

A property graph $\mathcal{A}=(N,E,\mathsf{label},\mathsf{prop})$ is a tuple,
where

  * •

$N$ is a non-empty set of nodes, where some subset of $N$ is defined as the
set of _individuals_ ;

  * •

$E$ is the multiset of edges; it assigns to each role $r$ a relation on
$N\times N$ which we view as the set of $r$-label edges; We write edges in the
form $r(n,n^{\prime})$ with $n,n^{\prime}\in N$ and $r\in\mathbf{R}$;

  * •

$\mathsf{label}$ is a total function $N\rightarrow 2^{\mathbf{C}}$ with
$2^{\mathbf{C}}$ the power set over the set of concepts $\mathbf{C}$; and

  * •

$\mathsf{prop}$ is a partial function $(N\cup E)\times K\rightarrow V$ that
maps a property key $K$ to a value $V$.

If $\mathcal{A}$ is finite and all nodes are individuals, we call it an
_ABox_.

Note that every interpretation can be seen as a property graph, and vice-
versa.

######  Definition 4.

For a property graph $\mathcal{A}=(N,E,\mathsf{label},\mathsf{prop})$, define
$\mathcal{I}_{\mathcal{A}}=(N,\cdot^{\mathcal{I}})$ as follows:
$C^{\mathcal{I}}=\\{n\in N\mid C\in\mathsf{label}(n)\\}$ and
$r^{\mathcal{I}}=\\{(n,n^{\prime})\mid r(n,n^{\prime})\in E\\}$. Conversely,
$\mathcal{I}=(\varDelta^{\mathcal{I}},\cdot^{\mathcal{I}})$ induces a
(possibly infinite) property graph
$\mathit{PG}(\mathcal{I})=(\varDelta^{\mathcal{I}},E,\mathsf{label},\mathsf{prop})$,
where $E=\\{r(n,n^{\prime})\mid(n,n^{\prime})\in r^{\mathcal{I}}\\}$ and
$\mathsf{label}(n)=\\{C\in\mathbf{C}\mid n\in C^{\mathcal{I}}\\}$. Further,
$\mathcal{I}$ is a _model_ of an ABox $\mathcal{A}$, if $\mathcal{A}$ is a
subgraph of $PG(\mathcal{I})$. An ABox $\mathcal{A}$ is _consistent_ with a
TBox $\mathcal{T}$ iff there exists a model of $\mathcal{A}$ and
$\mathcal{T}$.

### Query Language

We focus on _conjunctive two-way regular path queries_ (C2RPQs), the
navigational query language for graphs that has received most attention in
OMQA. C2RPQs are a fragment of GQL [6] and SPARQL[14], and of Cypher [15]
under some restrictions.

######  Definition 5 (C2RPQs).

A _regular path expression_ (RPE) $\pi$ is defined as follows.

$\displaystyle\pi:=r\mid r^{-}\mid\langle
A\rangle\mid\pi\pi\mid\pi\cup\pi\mid\pi^{*}\mid\pi^{+}\quad\text{ where
}\pi^{+}=\pi\pi^{*}\text{ and }A\in\mathbf{C}\text{ and
}r\in\mathbf{R}.\text{\vspace{-4mm}}$

We assume a countably infinite set $\mathbf{V}$ of _variables_ , disjoint from
$\mathbf{C}$, $\mathbf{R}$ and $\mathbf{N}$, and define _atoms_ of the form
$\pi(x,y)$ with $\pi$ a regular path expression and $x,y\in\mathbf{V}$. A
_conjunctive two-way regular path query_ (C2RPQ) is a pair
$q=(\varphi,\vec{x})$ where $\varphi$ is a conjunction of atoms
$\pi_{1}(x_{1},y_{1})\land\cdots\land\pi_{n}(x_{n},y_{n})$ and the _answer
variables_ $\vec{x}$ are a tuple of variables. We write
$\mathit{vars}(q)\subseteq\mathbf{V}$ for the set of all variables occurring
in atoms of $\varphi$, where $\vec{x}\subseteq\mathit{vars}(q)$. A variable
$x$ is _unbound_ in $q$ if $x\not\in\vec{x}$ and it occurs in exactly one atom
of $\varphi$. We may write $q(\vec{x})$ for a C2RPQ with answer variables
$\vec{x}$.

Note that Definitions 4 and 5 do not refer to the eponymous “properties” of
property graphs, as the focus is on the navigational features of graph
queries. Nevertheless, we take property graphs as the data model due to their
prevalence in graph database systems that provide navigational query
languages. Practical implementation can easily refer to property-value pairs,
as in [11]. Following the OMQA literature, we use the _homomorphism_ or _walk_
semantics [5].

######  Definition 6 (Semantics of C2RPQs).

Consider a C2RPQ $q(\vec{x})$, a property graph
$\mathcal{A}=(N,E,\textsf{label, prop})$. We define the evaluation of
$q(\vec{x})$ in terms of a function $\llbracket\cdot\rrbracket^{\mathcal{A}}$
in Table 3.A tuple $\vec{a}\subseteq N$ is an _answer_ of $q(\vec{x})$ in
$\mathcal{A}$ iff there exists a mapping
$\mu\in\llbracket\varphi\rrbracket^{\mathcal{A}}$ such that
$\mu(\vec{x})=\vec{a}$.

As usual in the setting of OMQA, we adopt the _certain answer_ semantics.

######  Definition 7.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, $\mathcal{A}$ an ABox,
and $q(\vec{x})$ a C2RPQ. A tuple $\vec{a}\in N$ is a certain answer to
$(\mathcal{T},\mathcal{A},q(\vec{x}))$ iff $\vec{a}$ is an answer to
$q(\vec{x})$ in $\mathit{PG}(\mathcal{I})$ for every model $\mathcal{I}$ of
$\mathcal{A}$ and $\mathcal{T}$.

Like other lightweight DLs, in $\mathcal{ELHI}^{lin}$ we can rely on the
existence of a _universal model_ $\mathcal{I}_{\mathcal{T},\mathcal{A}}$ that
can be leveraged for answering all queries, and which can be constructed with
a _chase_ procedure as known from databases; this construction is described in
the appendix.

######  Lemma 1.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, $\mathcal{A}$ a property
graph, and $Q(\vec{x})$ a C2RPQ. If $\mathcal{A}$ is consistent with
$\mathcal{T}$, then a tuple $\vec{a}\subseteq N$ is a certain answer to
$(\mathcal{T},\mathcal{A},Q)$ iff $\vec{a}$ is an answer to $Q(\vec{x})$ in
$PG(\mathcal{I}_{\mathcal{T},\mathcal{A}})$, the property graph corresponding
to the canonical model $\mathcal{I}_{\mathcal{T},\mathcal{A}}$.

##  3 Limits of C2RPQs for Ontology-mediated Graph Querying

In this section we show that, unfortunately, it is in general not possible to
rewrite C2RPQs into UC2RPQs for any ontology language that allows
$\mathcal{T}\models\exists r.\top\sqsubseteq\exists s.\top$ for role names $r$
and $s$.

######  Theorem 1.

There exist C2RPQs that cannot be rewritten into UC2RPQs w.r.t. TBoxes
containing concepts of the form $\exists r.\top$ on both sides of CIs. This
holds already for C2RPQs with only one atom.

This negative result motivates the need for a restricted query language that
admits a rewriting into UC2RPQs under $\mathcal{ELHI}^{lin}$ TBoxes. We
consider a very similar language to that of Dragovic et al. [16], which we
call _Navigational Conjunctive Queries_ (NCQs).

######  Definition 8 (Navigational Conjunctive Query).

A _Navigational Conjunctive Query_ (NCQ) is a C2RPQ where each atom takes one
of the following restricted forms:

$\displaystyle\langle A_{1}\rangle\cup\cdots\cup\langle
A_{n}\rangle(x,x)\quad\text{ or
}\quad\big{(}\pi_{1}\cup\cdots\cup\pi_{n}\big{)}(x,y)\quad\text{ or
}\quad\big{(}\pi_{1}\cup\cdots\cup\pi_{n}\big{)}^{*}(x,y)$

where each $A_{i}\in\mathbf{C}$ and each $\pi_{i}$ is a _restricted regular
path expression_ $\pi_{i}:=r\mid r^{-}\mid r^{*}\mid(r^{-})^{*}$.

While in NCQs we cannot use concatenation, it can still be simulated outside
the scope of Kleene stars as usual. Atomic concept tests are always binary
atoms $\langle A\rangle(x,x)$, but we often shorten this to $A(x)$. We refer
to atoms of form $A(x)$ and $\pi(x,y)$ as _atomic queries_ in the sequel.

##  4 Standard Reasoning in $\mathcal{ELHI}^{lin}$

In order to realise our goal of rewriting NCQs to UC2RPQs, we first consider
concept subsumption in $\mathcal{ELHI}^{lin}$ TBoxes via a graph structure
called _concept dependency graph_. We shall make use of this graph in Section
5 when rewriting atomic queries into C2RPQs.

######  Definition 9 (Concept Dependency Graph).

Given a TBox $\mathcal{T}$ in normal form, the concept dependency graph (CDG)
of $\mathcal{T}$, denoted $G_{\mathcal{T}}$, is the directed multigraph
defined as follows.

  * •

The set $N_{\mathcal{T}}$ of nodes of $G_{\mathcal{T}}$ contains the top
concept $\top$, all concept names occurring in $\mathcal{T}$, and all concepts
of the form $\exists r.B$ with $r\in\overline{\mathbf{R}}$ and
$B\in\mathbf{C}\cup\\{\top\\}$ that occur on the right hand side of some axiom
of shape (LABEL:NF4) in $\mathcal{T}$.

  * •

Three types of edges may connect nodes $A$ and $B$ in $G_{\mathcal{T}}$:
_$\varepsilon$ -propagating edges_ $\varepsilon(A,B)$, _$r$ -propagating
edges_ $r(A,B)$ and _$r$ -existential edges_ $\exists{r}(A,B)$, for
$r\in\overline{\mathbf{R}}$. The set of edges $E_{\mathcal{T}}$ of
$G_{\mathcal{T}}$ is the smallest set that satisfies the following:

    1. (i)

$\varepsilon(\top,A)\in E_{\mathcal{T}}$ for each $A\in N_{\mathcal{T}}$.

    2. (ii)

$\varepsilon(B,A)\in E_{\mathcal{T}}$ for each $A\sqsubseteq B$ of shape
(LABEL:NF1) in $\mathcal{T}$.

    3. (iii)

$r(B,A)\in E_{\mathcal{T}}$ for each $\exists r.A\sqsubseteq B$ of shape
(LABEL:NF3) or (LABEL:NF7) in $\mathcal{T}$.

    4. (iv)

$r(B,\top)\in E_{\mathcal{T}}$ whenever there are $r(B,A)\in E_{\mathcal{T}}$
and $s^{-}(A,\top)\in E_{\mathcal{T}}$ with $r\sqsubseteq^{*}_{\mathcal{T}}s$.

    5. (v)

$\exists r(A,\exists r.B)\in E_{\mathcal{T}}$ and $\varepsilon(B,{\exists
r.B})\in E_{\mathcal{T}}$ for each $A\sqsubseteq\exists r.B$ of shape
(LABEL:NF4) in $\mathcal{T}$.

    6. (vi)

$\exists r^{-}(A,\exists r^{-})\in E_{\mathcal{T}}$ for each
$A\sqsubseteq\exists r^{-}.\top$ of shape (LABEL:NF8) in $\mathcal{T}$.

    7. (vii)

$\varepsilon(C,D)\in E_{\mathcal{T}}$ whenever there is some $\exists
r^{-}.\top\sqsubseteq C$ of shape (LABEL:NF7) in $\mathcal{T}$ and there is an
edge $\exists s(A,D)\in E_{\mathcal{T}}$, with
$s\sqsubseteq^{*}_{\mathcal{T}}r$.

    8. (viii)

$\varepsilon(C,D)\in E_{\mathcal{T}}$ whenever there is some $\exists
r.A\sqsubseteq C$ of shape (LABEL:NF7) in $\mathcal{T}$ and there is an edge
$\exists s^{-}(A,D)\in E_{\mathcal{T}}$, with
$s\sqsubseteq^{*}_{\mathcal{T}}r$.

    9. (ix)

$\varepsilon(C,A)\in E_{\mathcal{T}}$ if there is a node $N$ and roles
$s,r\in\overline{\mathbf{R}}$ with $s\sqsubseteq^{*}_{\mathcal{T}}r$ such that
$\exists s(A,N)\in E_{\mathcal{T}}$ and there is a sequence of edges from $C$
to $N$ where exactly one edge is an $r$-propagating edge, and the rest are all
$\varepsilon$ propagating edges.

######  Example 1.

For the TBox $\mathcal{T}=\\{{A_{2}\sqsubseteq A_{1}},\ {\exists
r.B_{1}\sqsubseteq A_{1}},\ {\exists r_{3}.B_{1}\sqsubseteq B_{3}},\
{A_{3}\sqsubseteq A_{2}},\ {\exists r_{1}.B_{2}\sqsubseteq B_{1}},$ ${\exists
r_{2}^{-}.\top\sqsubseteq A_{3}},\ {s\sqsubseteq r_{2}},\ {\exists
r_{2}.B_{3}\sqsubseteq B_{2}},{B_{1}\sqsubseteq\exists r_{2}.B_{3}}\\}$ the
CDG $G_{\mathcal{T}}$ is as follows. (For readability, we omit edges added by
Definition 9 item (i)).

${B_{1}}$${B_{2}}$${B_{3}}$ $\exists r_{2}.$ $B_{3}$
${A_{1}}$${A_{2}}$${A_{3}}$${\top}$$r_{1}$$\varepsilon$$r_{2}$a$r_{3}$$\varepsilon$$\exists
r_{2}$$r$$\varepsilon$$\varepsilon$$\varepsilon$$r_{2}^{-}$

Note that existential edges always lead to nodes of the form $\exists r.B$,
which never have outgoing edges, hence neither of them participate in the
_propagating_ paths of $G_{\mathcal{T}}$ that we define next.

######  Definition 10 (Propagating path).

Let $A_{0}\in\mathbf{C}$ and let $G_{\mathcal{T}}$ be the CDG of a TBox
$\mathcal{T}$. A _propagating path_ $p$ from $A_{0}$ (to $A_{n}$) is a
(possibly empty) sequence of ($\varepsilon$\- or $r$-)propagating edges of the
form $\rho_{1}(A_{0},A_{1})$, …, $\rho_{n}(A_{n-1},A_{n})$ in
$G_{\mathcal{T}}$, $n\geq 0$. For convenience, we write $p$ in the form
$A_{0}\rho_{1}A_{1}\dots\rho_{i}A_{i}\dots A_{n}$; note that
$\rho_{i}\in\overline{\mathbf{R}}\cup\\{\varepsilon\\}$ and
$A_{i}\in\mathbf{C}\cup\\{\top\\}$ for all $1\leq i\leq n$. If
$(r_{1},\dots,r_{k})$ are exactly the roles that occur in
$\rho_{1}\dots\rho_{n}$ (that is, the ordered sequence of non $\varepsilon$
edges), then we say that $p$ is _$(r_{1},\dots,r_{k})$ -propagating_. If $p$
is _$()$ -propagating_, that is, it contains only $\varepsilon$-propagating
edges, then we call it a $\varepsilon^{*}$-path.

The propagating paths capture all relevant $\mathcal{ELHI}^{lin}$ entailments.

######  Lemma 2.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, let $G_{\mathcal{T}}$ be
its dependency graph, and let $\exists r_{1}\cdots\exists r_{k}.A\sqsubseteq
B$ be an $\mathcal{ELHI}^{lin}$ concept inclusion with $n\geq 0$ and
$B\in\mathbf{C}$. Then $\mathcal{T}\models\exists r_{1}\cdots\exists
r_{k}.A\sqsubseteq B$ iff there exists a path from $B$ to $A$ in
$G_{\mathcal{T}}$ that is $(s_{1}\cdots s_{k})$-propagating with
$r_{i}\sqsubseteq^{*}_{\mathcal{T}}s_{i}$ for all $1\leq i\leq k$.

The key to our rewriting of atomic queries is that instance checking for a
concept $A_{0}$ reduces to finding a set of ABox assertions in the given ABox
that match a propagating path from $A_{0}$.

######  Lemma 3.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox. For each ABox
$\mathcal{A}$, $A_{0}\in\mathbf{C}$ and individual $n_{0}$, we have
$\mathcal{T},\mathcal{A}\models A_{0}(n_{0})$ iff there exists an $(s_{1}\dots
s_{k})$-propagating path from $A_{0}$ to some $A_{k}$ in $G_{\mathcal{T}}$ and
$n_{1},\ldots,n_{k}$ such that $r_{i}(n_{i},n_{i+1})\in\mathcal{A}$ with
$r_{i}\sqsubseteq^{*}_{\mathcal{T}}s_{i}$ for each $0\leq i<k$, and
$A_{k}(n_{k})\in\mathcal{A}$.

To show both of lemmas, we describe in [17] how to construct, using
$G_{\mathcal{T}}$, a model $\mathcal{I}_{\mathcal{A},\mathcal{T}}$ of
$\mathcal{T}$ and a given ABox $\mathcal{A}$ that makes true exactly the
$\mathcal{ELHI}^{lin}$ inclusions witnessed by the propagating paths.
Moreover, since all the consequences of the axioms with existentials on the
right-hand side are already made explicit in the $r$\- and
$\varepsilon$-propagating edges, each propagating path that causes the
entailment of some concept is realized by a sequence of ABox individuals,
without needing to pass any existentially quantified objects in
$\mathcal{I}_{\mathcal{A},\mathcal{T}}$.

##  5 Query Rewriting Algorithm for Atomic Queries

Having introduced CDGs in Section 4, we can now make use of them to introduce
a rewriting algorithm for atomic queries (AQ) under $\mathcal{ELHI}^{lin}$
TBoxes. Our aim for this section is to present a rewriting algorithm for an AQ
$C(x)$ which produces a regular path query for each of the paths in
$G_{\mathcal{T}}$ starting from the corresponding node $C$. In order to
capture all such paths in a single regular path expression (RPE), we make use
of a non-deterministic finite automaton (NFA) translation of
$G_{\mathcal{T}}$, and use standard methods (such as Kleene’s algorithm) to
extract RPEs.

######  Definition 11 (Path-Generating NFA).

Given a CDG $G_{\mathcal{T}}$ and a concept $B\in\mathbf{C}$, we define the
_$B$ -path-generating NFA of $G_{\mathcal{T}}$_, termed
$G_{T}^{\mathbb{A}}(B)=\langle Q,\Sigma,\delta,q_{0},F\rangle$ as follows:

$\displaystyle Q$ $\displaystyle=\\{C\mid
C\in\mathbf{C}\cup\top\\}\cup\\{\Omega\\}$ $\displaystyle\Sigma$
$\displaystyle=\mathbf{C}\cup\overline{\mathbf{R}}\cup\top\text{\phantom{space}}q_{0}=B\text{\phantom{space}}F=\\{\Omega\\}$
$\displaystyle\delta(n_{0},X)$ $\displaystyle=\begin{cases}n_{1}&\text{ with
}X=r\text{ and }r(n_{0},n_{1})\in E_{\mathcal{T}}\\\ n_{1}&\text{ with
}X=\varepsilon\text{ and }\varepsilon(n_{0},n_{1})\in E_{\mathcal{T}}\\\
\Omega&\text{ with }X=C\text{ and }n_{0}=C\text{ and
}C\in\mathbf{C}\cup\top\\\ \end{cases}$

The set $Q$ describes the states, where for each node in $G_{\mathcal{T}}$
that represents a concept or $\top$, we produce one state. We introduce a
unique accepting state $\Omega$. The alphabet $\Sigma$ consists of the
(inverse) roles and concepts from $G_{\mathcal{T}}$ and $\top$. For the
transition function, we capture the edges in $G_{\mathcal{T}}$ over roles and
$\varepsilon$, plus a transition for every node to the unique accepting state.

######  Example 2.

In order to illustrate how the path-generating NFAs are constructed, we look
at the CDG $G_{\mathcal{T}}$ given in Example 1 and show its corresponding
$B_{1}$-path-generating NFA $G_{\mathcal{T}}^{\mathbb{A}}(B_{1})$.

${B_{1}}$start$\Omega$${A_{1}}$${A_{2}}$${A_{3}}$${B_{2}}$${B_{3}}$${\top}$r$\varepsilon$$\varepsilon$$B_{1}$$A_{1}$$A_{2}$a$A_{3}$$r_{2}^{-}$$B_{2}$$B_{3}$$\top$$\varepsilon$$r_{1}$$r_{2}$$r_{3}$

The extracted RPE is:
$\big{(}\overbrace{((r_{1}\cup(r_{1}r_{2}r_{3}))^{*}B_{1})}^{\text{paths
ending in
}B_{1}}\cup\overbrace{(r_{1}^{+}(r_{2}r_{3}r_{1}^{+})^{*}B_{2})}^{\text{paths
ending in
}B_{2}}\cup\overbrace{(r_{1}^{+}r_{2}(r_{3}r_{1}^{+}r_{2})^{*}B_{3})}^{\text{paths
ending in }B_{3}}\big{)}$.

### Extracting regular path expressions.

Given a CDG $G_{\mathcal{T}}$ and a concept $B\in\mathcal{N}_{T}$, we shall
use the function $\mathtt{rpe}(B,G_{\mathcal{T}})$ to signify the regular path
expression constructed in the following manner: we first construct
$G_{\mathcal{T}}^{\mathbb{A}}(B)$; next we produce a regular expression of
this NFA, expressing all possible propagating paths in $G_{\mathcal{T}}$ which
start at node $B$ and end in another concept while passing over only roles or
$\varepsilon$. From this regular expression, we eliminate any occurrence of
$\varepsilon$.

######  Lemma 4.

$\mathtt{rpe}(B,G_{\mathcal{T}})$ contains exactly the words of the form
$s_{1},\dots,s_{k}A$ such that there is an $(s_{1},\dots,s_{k})$-propagating
path from $B$ to $A$ in $G_{\mathcal{T}}$.

From Lemmas 3 and 4 we easily get:

######  Corollary 1.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox. For each ABox
$\mathcal{A}$, $B\in\mathbf{C}$ and individual $n_{0}$, we have
$\mathcal{T},\mathcal{A}\models B(n_{0})$ iff there is a word $s_{1}\dots
s_{k}A$ in $\mathtt{rpe}(B,G_{\mathcal{T}})$ such that
$r_{i}(n_{i},n_{i+1})\in\mathcal{A}$ with
$r_{i}\sqsubseteq^{*}_{\mathcal{T}}s_{i}$ for each $1\leq i\leq k$, and
$A(n_{k})\in\mathcal{A}$.

1

2

Input : AQ $\alpha$, $G_{\mathcal{T}}$

Output : C2RPQ $q$

3 begin

4 if  _$\alpha$ is an atom $r(x,y)$_ then

5 return $\big{(}\bigcup r_{i}\big{)}(x,y)$ where
$r_{i}\sqsubseteq^{*}_{\mathcal{T}}r$

6 if  _$\alpha$ is an atom $A(x)$_ then

7 $\pi=\mathtt{rpe}(A,G_{\mathcal{T}})$

8 foreach  _$r\in\pi$_ do

9 $\pi:=\pi[r\backslash\bigcup_{s\sqsubseteq^{*}_{\mathcal{T}}r}s]$

10 return $\pi(x,y)$ where $y$ is a fresh variable

Algorithm 1 Function $\mathtt{rewriteAQ}$

### Description of Algorithm 1.

We begin by considering whether the input atom is a concept test ($A(x)$) or
consists of a role atom ($r(x,y)$). Let us recall that $A(x)$ is actually a
short-hand for the binary form $\langle A\rangle(x,x)$. In case the input is a
concept test, we first extract the regular path expression, as described
above, seen on line 1. Next, starting on algorithm 1, we iterate over each
role in the produced regular path expression and replace its occurrence in
$\pi$ with a union over all subroles of $r$. In case the input was a role atom
$r(x,y)$, we simply check for any other roles which imply $r$ w.r.t.
$\mathcal{T}$ and produce the union over all of them on algorithm 1. The
algorithm now returns a C2RPQs in two ways: if the input atom was of the form
$A(x)$, where $A$ is a concept test, then we create a fresh variable $y$ and
return the produced regular expression with variables $x$ and $y$. In case of
role atoms, we return the regular path expression with the same two variables.
Below we show the correctness of Algorithm 1.

######  Theorem 2 (Soundness and Completeness).

Let $\varphi(x,y)$ be an arbitrary AQ where $\varphi(x,y)=\langle
A\rangle(x,y)$ or $\varphi(x,y)=r(x,y)$, $\mathcal{T}$ an
$\mathcal{ELHI}^{lin}$ TBox, $\mathcal{A}$ an ABox consistent with
$\mathcal{T}$ and $G_{\mathcal{T}}$ the CDG of $\mathcal{T}$. Then, $a$ is an
answer to $q_{r}(x)=\mathtt{rewriteAQ}(\varphi(x,y),G_{\mathcal{T}})$ in
$\mathcal{A}$, iff $a$ is a certain answer to
$(\mathcal{T},\mathcal{A},\varphi(x,y))$.

##  6 Query Rewriting Algorithm for Navigational Queries

In this section we give the complete algorithm for rewriting NCQs and a given
$\mathcal{ELHI}^{lin}$ TBox into UC2RPQs. For this purpose, we make use of the
algorithm for rewriting atomic queries given in Section 5. We thus introduce a
new function, called _clipping_ , which makes use of axioms in the TBox to
rewrite a given NCQ into a union of NCQs, inspired by [12].

Given a regular path expression $\pi$ and a role $r$, we construct a new
expression $\pi|^{\mathcal{T}}{r}$ in the following way. Let $\pi$ be an
expression of the form $\pi_{1}\cup\cdots\cup\pi_{n}$, and let $r$ be a role.
Then the _$r$ -restriction of $\pi$_, written as $\pi|^{\mathcal{T}}{r}$, is
the union of all those $\pi_{j}$ s.t. there exists some $s$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$, where $s$ is in $\pi_{j}$. Informally,
$\pi|^{\mathcal{T}}{r}$ matches only those paths of $\pi$ that contain the
role $r$ or a super-role of $r$. For a set of atoms $\mathbb{A}$ and atom
$\pi$ we use $\pi(x,y)\mathbin{\widehat{\in}}\mathbf{A}$ to mean
$\pi(x,y)\in\mathbf{A}$ or $\pi^{-}(y,x)\in\mathbf{A}$. Note that
$\pi^{-}(x,y)$ is built from $\pi(y,x)$, where $r^{-}\in\pi^{-}$ iff
$r\in\pi$.

######  Definition 12 (Clipping Function).

Given a query $q(\vec{x})$, we select a set $Y$ of variables such that
$Y\cap\vec{x}=\emptyset$, and a concept inclusion $A\sqsubseteq\exists
r.B\in\mathcal{T}$. Then, do the following:

  1. (C1)

Pick any $y\in Y$, and replace each $y^{\prime}\in Y$ by $y$ everywhere in
$q(\vec{x})$.

  2. (C2)

Check that at least one of the following is satisfied for every atom $\alpha$
where $y$ occurs:

    1. (A)

$\alpha$ contains a star, and if it contains a variable different from $y$, it
is an unbound variable.

    2. (B)

$\alpha$ contains a concept name $C$ with $\mathcal{T}\vDash B\sqsubseteq C$,
or $\mathcal{T}\vDash\exists r^{-}\sqsubseteq C$, and if it contains a
variable different from $y$, it is an unbound variable.

    3. (C)

$\alpha$ is of the form $\pi(x,y)$ or $\pi^{-}(y,x)$ where $x\neq y$ and $\pi$
contains some $s$ with $r\sqsubseteq^{*}_{\mathcal{T}}s$.

Let $\mathbf{C}_{y}=\\{\pi(x,y)\mid\pi(x,y)\text{~{}satisfies
\ref{clipRule:roles}}\\}\cup\\{\pi^{-}(x,y)\mid\pi(y,x)\text{~{}satisfies
\ref{clipRule:roles}}\\}$. Define $\mathbf{C}_{y}^{*}$ as the set of atoms
$\alpha$ in $\mathbf{C}_{y}$ that contain a role $s$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$ occurring in $\alpha$ in the scope of a
star. Let $\mathbf{C}^{1}_{y}=\mathbf{C}_{y}\setminus\mathbf{C}^{*}_{y}$, and
let $X$ be the set of all variables different from $y$ that occur in
$\mathbf{C}_{y}^{1}$.

  1. (C3)

Drop from $q(\vec{x})$ every atom that satisfies (C2)(A) or (C2)(B), and every
atom $\alpha\mathbin{\widehat{\in}}\mathbf{C}^{1}_{y}$.

  2. (C4)

Replace each $x\in X$ by $y$, everywhere in $q(\vec{x})$.

  3. (C5)

Replace each atom $\pi(x,y)\mathbin{\widehat{\in}}q$ such that
$\pi(x,y)\in\mathbf{C}_{y}^{*}$ by $\pi|^{\mathcal{T}}{r}(x,y)$.

  4. (C6)

Add $A(y)$ to $q(\vec{x})$.

1

2

Input : NCQ $q(\vec{x})$, $\mathcal{ELHI}^{lin}$ TBox $\mathcal{T}$

Output : UC2RPQs $Q$

3 begin

4 $Q=\\{q\\},Q^{\prime}=\emptyset$

5 while  _$Q^{\prime}\neq Q$_ do

6 $Q^{\prime}=Q$

7 foreach  _$q\in Q^{\prime}$_ do

8 foreach  _$A\sqsubseteq\exists r.B\in\mathcal{T}$ and
$Y\subseteq\mathit{vars}(q),Y\cap\vec{x}=\emptyset$_ do

9 $Q=Q\cup\mathtt{clipping}(q^{\prime},A\sqsubseteq\exists
r.B\in\mathcal{T},Y)$

10

11 foreach  _$q\in Q$_ do

12 foreach  _role $r$ in $q$_ do

13 $q[r\backslash\textnormal{{$\mathtt{rewriteAQ}$}}(r)]$

14 foreach  _atom $\bigcup C(x)$ in $q$_ do

15 $q[\bigcup C(x)\backslash\bigcup\langle C\rangle(x,y)]$ where
$y\not\in\mathit{vars}(q)$

16 $q[\langle C\rangle\backslash\textnormal{{$\mathtt{rewriteAQ}$}}(\langle
C\rangle)]$

17

18 return $Q$

Algorithm 2 Function $\mathtt{rewriteNCQ}$

The clipping function relies on a well-known property of $\mathcal{ELHI}$: for
each $\mathcal{T}$ and $\mathcal{A}$ there is a universal, tree-shaped model
$\mathcal{I}^{u}$ that can be used for answering all C2RPQs. Intuitively, we
consider each possible set $Y$ of variables that may be mapped to the same
’anonymous’ object $d$ of maximal depth in $\mathcal{I}^{u}$. Each such $d$ is
triggered by one existential axiom $A\sqsubseteq\exists r.B$, that is, if $d$
was added to $\mathcal{I}^{u}$, we know that it has a parent $d_{p}$ that is
$A$, and $d$ was introduced as an $r$-child of $d_{p}$ to satisfy
$A\sqsubseteq\exists r.B$. Exploiting this, we can modify the query to require
that we map a variable to the object $d_{p}$ that is $A$, and drop from the
query all (parts of) atoms that are already guaranteed by the existence of
$d$. We show in the appendix that each application of the function results in
a rewritten query with exactly the same answers, but whose mappings have a
strictly lower depth (as at least one variable now is mapped to $d_{p}$
instead of to its child $d$). By repeated application, we eventually obtain a
query whose variables are always mapped to ABox individuals. Such a query is
nothing else but a conjunction of atomic queries as in Section 5, so we can
just apply that rewriting to each atom.

Algorithm 2 takes as input an NCQ $q(\vec{x})$ and an $\mathcal{ELHI}^{lin}$
TBox $\mathcal{T}$. Between algorithms 2 and 2, we iterate over all variable
subsets $Y$ and axioms in $\mathcal{T}$ of the form LABEL:NF4 and LABEL:NF8,
and apply the clipping function exhaustively. Then in lines 2 to 2 we apply
Algorithm 1 to each atoms of each queries, to finally return the union of all
produced queries.

Using Theorem 2 and the lemmas about the clipping function in the Appendix, we
obtain:

######  Theorem 3 (Soundness and Completeness).

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, let $q(\vec{x})$ be a
NCQ, and let $q_{r}=\mathtt{rewriteNCQ}(q(\vec{x}),\mathcal{T})$. For every
ABox $\mathcal{A}$, $\vec{a}$ is a certain answer to $q(\vec{x})$ over
$(\mathcal{T},\mathcal{A})$, iff $\vec{a}$ is an answer to $q_{r}$ over
$\mathcal{A}$.

This theorem shows that NCQ answering for $\mathcal{ELHI}^{lin}$ can be
reduced to C2RPQ query evaluation, which is in NL in data complexity (see
[18]). This is worst-case optimal.

##  7 Implementation and Experiments

Table 1: Experimental results of the algorithm from Section 6. #$\lor$ is the number of C2RPQs, $\\#\mathbf{\alpha}$ the number of atoms and $\\#\mathbf{C}$ the number of distinct concepts in the output, $\varnothing_{\cup}$ is the average and $\max_{\cup}$ the maximal number of expressions in unions inside the C2RPQs, $t_{\textsf{rew}}$ and $t_{\textsf{eval}}$ the times for rewriting and evaluation in seconds. We indicate the results on the modified ontology with ⊔ and set a timeout at 1000 seconds.  | $\\#\lor$ | $\\#\mathbf{\alpha}$ | $\\#\mathbf{C}\mid\\#\mathbf{C}^{\sqcup}$ | $\varnothing_{\cup}\mid\varnothing^{\sqcup}_{\cup}$ | $\max_{\cup}\mid\max^{\sqcup}_{\cup}$ | $t_{\textsf{rew}}\mid t^{\sqcup}_{\textsf{rew}}$ | $t_{\textsf{eval}}\mid t^{\sqcup}_{\textsf{eval}}$
---|---|---|---|---|---|---|---
Q1 | 60 | 313 | 934$\mid$957 | 987$\mid$1007 | 995$\mid$1062 | 17.78$\mid$32.76 | 904.13$\mid$ 800.25
Q2 | 23 | 123 | 951$\mid$972 | 995$\mid$1020 | 1036$\mid$1062 | 7.44$\mid$8.770 | 253.60$\mid$245.77
Q3 | 1 | 3 | 3$\mid$3 | 2$\mid$2 | 2$\mid$2 | 0.08$\mid$0.08 | 0.23$\mid$0.71
Q4 | 1 | 3 | 3$\mid$3 | 2$\mid$2 | 2$\mid$2 | 0.07$\mid$0.07 | 0.11$\mid$0.03
Q5 | 1 | 3 | 12$\mid$12 | 11$\mid$11 | 11$\mid$11 | 0.07$\mid$0.06 | 2.08$\mid$1.94
Q6 | 297 | 1891 | 1018$\mid$1042 | 1063$\mid$1085 | 1169$\mid$1178 | 131.55$\mid$132.31 | >1000$\mid$>1000
Q7 | 77 | 509 | 922$\mid$932 | 988$\mid$1002 | 994$\mid$1009 | 32.24$\mid$54.20 | >1000$\mid$>1000
Q8 | 1 | 4 | 2$\mid$2 | 0$\mid$0 | 0$\mid$0 | 0.2$\mid$0.2 | 0.08$\mid$0.08

We implemented a proof-of-concept prototype that, given an
$\mathcal{ELHI}^{lin}$ TBox (in OWL syntax), rewrites NCQs into UC2RPQs and
translates them into Cypher, a declarative query language for the Neo4j
property graph database. The Cypher query is then evaluated over real-world
data stored in Neo4j. The Java source code of the prototype is publicly
available [19].

Setup. We execute the experiments on a machine running Ubuntu 22.04.4 with an
Intel Core i7-6700HQ CPU clocked at 2.60 GHz and 8 GB RAM; with Neo4j 5.18.1
running on it.

Ontology. As a TBox (OWL ontology) we use the Cognitive Task Ontology (COGITO)
[20], which integrates the Cognitive Atlas Ontology [21] with the Hierarchical
Event Descriptors (HED) [22]. This ontology includes about $4700$ concepts and
$9000$ axioms in $\mathcal{ELHI}$: $25$ of the axioms fall into LABEL:NF4
after normalisation, while all others are concept inclusions in form of
LABEL:NF1. For example, the axiom
$\mathsf{ReadingTask}\sqsubseteq(\exists\mathsf{has.Read}\sqcap\exists\mathsf{has.Language\text{-}item})$
defines a reading task by referring to the HEDs $\mathsf{Read}$ and
$\mathsf{Language\text{-}item}$ (where the conjunction is just a shortcut for
two axioms in normal form). COGITO also includes the converse axiom, which is
not in $\mathcal{ELHI}^{lin}$. In our experiments, we address this by
considering experiments over two separate ontologies: in the first, we dropped
the axioms; in the second, we replace the conjunction on the left-hand side of
this type of axiom with a disjunction, i.e., we consider one
$\mathcal{ELHI}^{lin}$ axioms for each conjunct. These new axioms do not
preserve the semantics, of course, and in general, may retrieve candidates
that are not true answers with the original ontology. However, from the use
case perspective this seems preferable to discarding the
non-$\mathcal{ELHI}^{lin}$ axioms: neuroscientists do not want potentially
relevant answers to be excluded from the downstream tasks, which typically
filter out many candidates anyway. Including the second ontology also makes
our evaluation more significant, as its use can result in more complex
rewritten queries.

Data. The prototype rewrites an NCQ into a Cypher query assuming that concepts
in the ontology correspond to node labels in the database, and roles
correspond to relationships (i.e., edge labels). For the experiments we chose
a dataset from the domain of cognitive neuroscience [23]. This dataset—stored
in our Neo4j database—consists of $15\,512$ nodes and $78\,113$ relationships.
It contains meta-information about fMRI data from OpenNeuro [24].

Queries. One use case of COGITO is to query for fMRI data that contains a set
of targeted HEDs, even if the data has only annotations for names of cognitive
tasks, or vice-versa. For our experiments, we manually created 8 queries,
structurally similar to those in [23]. The queries Q1-Q8 request fMRI datasets
with a specific cognitive task, either by its concept name (Q3-Q5) or by a
combination of HEDs, e.g. the Reading Task in Q1. Since the depth at which the
event tags occur varies from an fMRI scan to another, the queries use the
Kleene star to navigate to them; see [17]. Currently, no database systems
support GQL, which would allow us to evaluate our queries under the walk-based
semantics, and Cypher only supports the so-called _trail semantics_. Through
careful manual inspection, we chose queries were both semantics coincide.
Finding syntactic conditions for the two semantics to match is left for future
work.

Results. In Table 1, we report the results of the experiments with two
different versions of an ontology. As explained above: one drops axioms that
are not in $\mathcal{ELHI}^{lin}$ and one rewrites them to be in
$\mathcal{ELHI}^{lin}$, albeit producing more answers than intended. For each
of the 8 queries we provide the number of C2RPQs in the union, atoms and
distinct concepts, as well as the average and the maximum of expressions in
unions of the C2RPQs of the rewritten query. Lastly, we state how many seconds
it took to produce the Cypher query and how many seconds it took to evaluate
them on our test machine. Note that the additional axioms in the modified
ontology do not affect the number of C2RPQs or the number of atoms, but they
may make the atoms more complex. Constructing the CDG, on which Algorithm 2
depends, takes around two minutes. Unsurprisingly, queries producing a small
number of C2RPQs (Q3, Q4, Q5 & Q8) were evaluated quickly, in a few seconds at
most. As expected, it seems that number of C2RPQs is a good predictor of
evaluation time: once we move to 23 C2RPQs (Q2), evaluation time shoots up,
and at 60 (Q1) we are already at the limit of our timeout, and indeed we cross
it once we reach 77 (Q7). The time it takes to rewrite the queries is in most
cases below 30 seconds, only the largest two rewritings (Q6 & Q7) take longer.
The number of concepts seems independent of the number of C2RPQs: Q6 and Q7
have a comparable number of distinct concepts, but Q6 has three times more
C2RPQs. The rewrite and evaluation time for both ontologies is comparable.
This is surprising, as one would expect the second version to lead to more
rewritings and answers. Assuming this is representative of real-world
performance, this bodes well for our approach.

##  8 Conclusion and Future Work

We presented an algorithm for rewriting NCQs into UC2RPQs over a lightweight
ontology that extends DL-Lite with some of the expressive features of
$\mathcal{ELH}$ while keeping the data complexity of reasoning in NL. Our
restricted input query language (NCQs) is justified by the fact that we have
proven the impossibility of using (U)C2RPQs as both the input and output
language of query rewriting. Nested regular path queries seem a promising
target language for rewriting ontology-mediated C2RPQs. One of our goals is to
make progress towards a practicable algorithm, and our prototype
implementation, which rewrites the queries into Cypher, suggests that we may
be on track. It shows promising results on a real-world dataset from cognitive
neuroscience. In our future work, we aim to support a richer ontology
language, and to target the upcoming GQL standard to support full C2RPQs.

## References

  * Xiao et al. [2023] G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, M. Zakharyaschev,  Ontology-based data access: A survey,  in: In Proc., IJCAI 2018, 2023, pp. 5511–5519.
  * Xiao et al. [2019] G. Xiao, L. Ding, B. Cogrel, D. Calvanese,  Virtual knowledge graphs: An overview of systems and use cases,  Data Intell. 1 (2019) 201–223. URL: https://doi.org/10.1162/dint_a_00011. doi:10.1162/DINT_A_00011.
  * Calvanese et al. [2007] D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, R. Rosati,  Tractable reasoning and efficient query answering in description logics: The DL-lite family,  Journal of Automated Reasoning 39 (2007) 385–429. doi:10.1007/s10817-007-9078-x.
  * Abiteboul et al. [1995] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  * Angles et al. [2017] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, D. Vrgoc,  Foundations of modern query languages for graph databases,  ACM Comput. Surv. 50 (2017) 68:1–68:40. doi:10.1145/3104031.
  * Francis et al. [2023] N. Francis, A. Gheerbrant, P. Guagliardo, L. Libkin, V. Marsault, W. Martens, F. Murlak, L. Peterfreund, A. Rogova, D. Vrgoc,  A researcher’s digest of GQL (invited talk),  in: F. Geerts, B. Vandevoort (Eds.), 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece, volume 255 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 1:1–1:22. doi:10.4230/LIPIcs.ICDT.2023.1.
  * Dimartino et al. [2019] M. M. Dimartino, A. Calì, A. Poulovassilis, P. T. Wood,  Efficient ontological query answering by rewriting into graph queries,  in: A. Cuzzocrea, S. Greco, H. L. Larsen, D. Saccà, T. Andreasen, H. Christiansen (Eds.), Flexible Query Answering Systems - 13th International Conference, FQAS 2019, Amantea, Italy, July 2-5, 2019, Proceedings, volume 11529 of Lecture Notes in Computer Science, Springer, 2019, pp. 75–84. URL: https://doi.org/10.1007/978-3-030-27629-4_10. doi:10.1007/978-3-030-27629-4_10.
  * Bienvenu et al. [2013] M. Bienvenu, M. Ortiz, M. Simkus,  Conjunctive regular path queries in lightweight description logics,  in: F. Rossi (Ed.), IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, IJCAI/AAAI, 2013, pp. 761–767. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6886.
  * Bienvenu et al. [2014] M. Bienvenu, D. Calvanese, M. Ortiz, M. Simkus,  Nested regular path queries in description logics,  in: C. Baral, G. D. Giacomo, T. Eiter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014, AAAI Press, 2014. URL: http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/8000.
  * Bienvenu et al. [2015] M. Bienvenu, M. Ortiz, M. Simkus,  Regular path queries in lightweight description logics: Complexity and algorithms,  J. Artif. Intell. Res. 53 (2015) 315–374. URL: https://doi.org/10.1613/jair.4577. doi:10.1613/JAIR.4577.
  * Dragovic et al. [2023] N. Dragovic, C. Okulmus, M. Ortiz,  Rewriting ontology-mediated navigational queries into cypher,  in: O. Kutz, C. Lutz, A. Ozaki (Eds.), 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, volume 3515 of CEUR Workshop Proceedings, CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3515/paper-9.pdf.
  * Eiter et al. [2012] T. Eiter, M. Ortiz, M. Simkus, T. Tran, G. Xiao,  Query rewriting for Horn-SHIQ plus rules,  in: J. Hoffmann, B. Selman (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, AAAI Press, 2012, pp. 726–733. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4931.
  * Dimartino [2020] M. M. Dimartino, Integrating and querying linked datasets through ontological rules, Ph.D. thesis, University of London, Birkbeck College, UK, 2020. URL: https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.852364.
  * Pérez et al. [2006] J. Pérez, M. Arenas, C. Gutierrez,  Semantics and complexity of SPARQL,  in: I. F. Cruz, S. Decker, D. Allemang, C. Preist, D. Schwabe, P. Mika, M. Uschold, L. Aroyo (Eds.), The Semantic Web - ISWC 2006, 5th International Semantic Web Conference, ISWC 2006, Athens, GA, USA, November 5-9, 2006, Proceedings, volume 4273 of Lecture Notes in Computer Science, Springer, 2006, pp. 30–43. URL: https://doi.org/10.1007/11926078_3. doi:10.1007/11926078_3.
  * Francis et al. [2018] N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, P. Selmer, A. Taylor,  Cypher: An evolving query language for property graphs,  in: G. Das, C. M. Jermaine, P. A. Bernstein (Eds.), Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, ACM, 2018, pp. 1433–1445. URL: https://doi.org/10.1145/3183713.3190657. doi:10.1145/3183713.3190657.
  * Dragovic [2022] N. Dragovic, Querying Property Graphs with Ontologies, Master’s thesis, TU Wien, 2022.
  * Löhnert et al. [2024] B. Löhnert, N. Augsten, C. Okulmus, M. Ortiz, Towards practicable algorithms for rewriting graph queries beyond dl-lite – full version, 2024. URL: https://www.dropbox.com/scl/fi/q4dbawxvujszt7r15nyns/OMQs_for_PropGraphs-withAppendix.pdf?rlkey=eslefhjz531at9r6kb7gybco3&dl=0, accessed: 2024-05-27.
  * Baeza [2013] P. B. Baeza,  Querying graph databases,  in: R. Hull, W. Fan (Eds.), Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA \- June 22 - 27, 2013, ACM, 2013, pp. 175–188. doi:10.1145/2463664.2465216.
  * Dragovic and Löhnert [2022] N. Dragovic, B. Löhnert, Ontology-mediated querying for property graphs, 2022\. URL: https://gitlab.com/ccns/neurocog/neurodataops/dni/owl2cypher, accessed: 2024-05-24.
  * Löhnert [2024] B. Löhnert, Cognitive task ontology (COGITO), 2024. URL: https://gitlab.com/ccns/neurocog/neurodataops/anc/classification/cogito/, accessed: 2024-05-24.
  * Poldrack et al. [2011] R. A. Poldrack, A. Kittur, D. J. Kalar, E. Miller, C. Seppa, Y. Gil, D. S. Parker, F. W. Sabb, R. M. Bilder,  The cognitive atlas: Toward a knowledge foundation for cognitive neuroscience,  Frontiers Neuroinformatics 5 (2011) 17. doi:10.3389/fninf.2011.00017.
  * Robbins et al. [2021] K. Robbins, D. Truong, S. Appelhoff, A. Delorme, S. Makeig,  Capturing the nature of events and event context using hierarchical event descriptors (hed),  NeuroImage 245 (2021) 118766.
  * Ravenschlag et al. [2023] A. Ravenschlag, M. Denissen, B. Löhnert, M. Pawlik, N. A. Himmelstoß, F. Hutzler,  Effective queries for mega-analysis in cognitive neuroscience,  in: G. Fletcher, V. Kantere (Eds.), Proceedings of the Workshops of the EDBT/ICDT 2023 Joint Conference, Ioannina, Greece, March, 28, 2023, volume 3379 of CEUR Workshop Proceedings, CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3379/CoMoNoS_2023_id252_Mateusz_Pawlik.pdf.
  * for Reproducible Neuroscience [2017] S. C. for Reproducible Neuroscience, OpenNeuro MRI platform, 2017. URL: https://openneuro.org/search/modality/mri, accessed: 2024-05-24.
  * Calvanese et al. [2013] D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, R. Rosati,  Data complexity of query answering in description logics,  Artif. Intell. 195 (2013) 335–360. doi:10.1016/j.artint.2012.10.003.
  * McNaughton and Yamada [1960] R. McNaughton, H. Yamada,  Regular expressions and state graphs for automata,  IRE transactions on Electronic Computers (1960) 39–47.

##  Appendix A Definitions from Preliminaries

Table 2: Syntax and Semantics of $\mathcal{ELHI}^{lin}$ Name | Syntax | Semantics
---|---|---
top concept | $\top$ | $\varDelta^{\mathcal{I}}$
concept name | $A$ | $A^{\mathcal{I}}\subseteq\varDelta^{\mathcal{I}}$
negation | $\lnot A$ | $\varDelta^{\mathcal{I}}\setminus A^{\mathcal{I}}$
role name | $r$ | $r^{\mathcal{I}}\subseteq\varDelta^{\mathcal{I}}\times\varDelta^{\mathcal{I}}$
inverse role | $r^{-}$ | $\\{(b,a)\mid(a,b)\in r^{\mathcal{I}}\\}$
exist. restriction | $\exists r.C$ | $\\{a\mid b\in C^{\mathcal{I}}:(a,b)\in r^{\mathcal{I}}\\}$
concept inclusion | $C\sqsubseteq D$ | $C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$
Table 3: Walk-based evaluation function for C2RPQs. $\llbracket\langle A\rangle(x,y)\rrbracket^{\mathcal{A}}=\\{\mu\mid A\in\mathsf{label}(\mu(x)),\mu(x)=\mu(y)\\}$ |
---|---
$\llbracket r(x,y)\rrbracket^{\mathcal{A}}=\\{\mu\mid r(\mu(x),\mu(y))\in E\\}$ | $\llbracket r^{-}(x,y)\rrbracket^{\mathcal{A}}=\\{\mu\mid r(\mu(y),\mu(x))\in E\\}\quad$
$\llbracket(\pi\pi^{\prime})(x,z)\rrbracket^{\mathcal{A}}=\\{\mu\cup\mu^{\prime}\mid\mu\in\llbracket\pi(x,y)\rrbracket^{\mathcal{A}},\mu^{\prime}\in\llbracket\pi^{\prime}(y,z)\rrbracket^{\mathcal{A}},\mu(y)=\mu^{\prime}(y)\\}$
$\llbracket(\pi\cup\pi^{\prime})(x,y)\rrbracket^{\mathcal{A}}=\llbracket\pi(x,y)\rrbracket^{\mathcal{A}}\cup\llbracket\pi^{\prime}(x,y)\rrbracket^{\mathcal{A}}$
$\llbracket\pi^{*}(x,y)\rrbracket^{\mathcal{A}}=\\{\mu\mid\mu(x)\in
N,\mu(x)=\mu(y)\\}\cup\llbracket\pi(x,y)\rrbracket^{\mathcal{A}}\cup\llbracket\pi\pi(x,y)\rrbracket^{\mathcal{A}}\cup\llbracket\pi\pi\pi(x,y)\rrbracket^{\mathcal{A}}\cup\dots$
$\llbracket\varphi\land\varphi^{\prime}\rrbracket^{\mathcal{A}}=\llbracket\varphi\rrbracket^{\mathcal{A}}\cap\llbracket\varphi^{\prime}\rrbracket^{\mathcal{A}}$ |

######  Definition 13 (Canonical Model).

Consider an $\mathcal{ELHI}^{lin}$ TBox $\mathcal{T}$ and an ABox
$\mathcal{A}$. Let $\mathcal{I}_{0}$ be the initial interpretation with
$\mathcal{A}$ the corresponding property graph. Then, we construct the
_canonical model_ $\mathcal{I}_{\mathcal{T},\mathcal{A}}$ by exhaustively
applying the following rules to $\mathcal{I}_{0}$.

  1. (Ch1)

If $A\sqsubseteq B\in\mathcal{T}$, $v\in A^{\mathcal{I}_{i}}$ and $v\notin
B^{\mathcal{I}_{i}}$, then $\mathcal{I}_{i+1}$ is $\mathcal{I}_{i}$ with
$B^{\mathcal{I}_{i+1}}=B^{\mathcal{I}_{i}}\cup\\{v\\}$.

  2. (Ch2)

If $\exists r.C\sqsubseteq B\in\mathcal{T}$, $v\in(\exists
r.C)^{\mathcal{I}_{i}}$ and $v\notin B^{\mathcal{I}_{i}}$, then
$\mathcal{I}_{i+1}$ is $\mathcal{I}_{i}$ with
$B^{\mathcal{I}_{i+1}}=B^{\mathcal{I}_{i}}\cup\\{v\\}$.

  3. (Ch3)

If $A\sqsubseteq\exists r.C\in\mathcal{T}$, $v\in A^{\mathcal{I}_{i}}$ and
$v\notin(\exists r.C)^{\mathcal{I}_{i}}$, then $\mathcal{I}_{i+1}$ is
$\mathcal{I}_{i}$ with a fresh $w$ in $\varDelta^{\mathcal{I}_{i+1}}$ and
$C^{\mathcal{I}_{i+1}}=C^{\mathcal{I}_{i}}\cup\\{w\\}$. In case
$r\in\mathbf{R}$ then
$r^{\mathcal{I}_{i+1}}=r^{\mathcal{I}_{i}}\cup\\{(v,w)\\}$, otherwise
$r^{\mathcal{I}_{i+1}}=r^{\mathcal{I}_{i}}\cup\\{(w,v)\\}$.

  4. (Ch4)

If $r\sqsubseteq s\in\mathcal{T}$, $(v,w)\in r^{\mathcal{I}_{i}}$ and
$(v,w)\notin s^{\mathcal{I}_{i}}$, then $\mathcal{I}_{i+1}$ is
$\mathcal{I}_{i}$ with
$s^{\mathcal{I}_{i+1}}=s^{\mathcal{I}_{i}}\cup\\{(v,w)\\}$ in case
$r\in\mathbf{R}$, otherwise
$s^{\mathcal{I}_{i+1}}=s^{\mathcal{I}_{i}}\cup\\{(w,v)\\}$.

##  Appendix B Further Examples

Adding qualified existentials to the languages of the DL-Lite family makes
query answering become P in data complexity. Below we show an example of how
to entail conjunction with a TBox that has axioms with qualified existentials
and inverse roles only.

######  Example 3.

We take this example from [25] where they demonstrate how to entail
conjunction, i.e., $\mathcal{T}\vDash A_{1}\sqcap A_{2}\sqsubseteq A_{3}$ by
introducing a fresh concept and role.

$\displaystyle\mathcal{T}=\\{A_{1}\sqsubseteq\exists r_{123},\exists
r^{-}_{123}.A_{2}\sqsubseteq A_{123},\exists r_{123}.A_{123}\sqsubseteq
A_{3}\\}$

##  Appendix C Proof from Section 3

######  Theorem 1.

There exist C2RPQs that cannot be rewritten into UC2RPQs w.r.t. TBoxes that
contain concepts of the form $\exists r.\top$ on both sides of CIs. This holds
already for C2RPQs with only one atom.

###### Proof.

Consider the C2RPQ $q(x,y)=(rpp^{-})^{+}(x,y)$ (where $(rpp^{-})^{+}$ stands
for $(rpp^{-})(rpp^{-})^{*}$) and a the TBox $\mathcal{T}=\\{\exists
s.\top\sqsubseteq\exists p.\top\\}$. A valid rewriting of $q$ w.r.t.
$\mathcal{T}$ into a nested two-way regular path query would be
$Q_{r}(x,y)=(r(pp^{-}\cup\langle s\rangle))^{+}(x,y)$, where we denote nested
queries by "$\langle\rangle$". In the following we show that it is not
possible to express the same with the language of UC2RPQ, i.e., there is no
UC2RPQ $Q_{r}(x,y)$ such that, for every ABox $\mathcal{A}$, the answers to
$Q_{r}$ over $\mathcal{A}$ coincide with the answers to $q$ over $\mathcal{A}$
and $\mathcal{T}$.

For the sake of contradiction we assume that there is a UC2RPQ rewriting
$Q_{r}(x,y)$ with $N$ the maximal number of conjuncts in a disjunct of
$Q_{r}(x,y)$. Then, consider the following ABox $\mathcal{A}$ (without the
grayed-out nodes and edges)

where $K>N+1$. Since we assume that there is a UC2RPQ $Q_{r}(x,y)$ and given
that $(n_{0},n_{K})$ is a certain answer to
$(\mathcal{T},\mathcal{A},q(x,y))$, there exists a disjunct $q_{r}(x,y)$ such
that $(n_{0},n_{K})\in\llbracket q_{r}(x,y)\rrbracket^{\mathcal{A}}$. Then, we
assume without loss of generality that the C2RPQ $q_{r}(x,y)$ is of the form
$r_{1}(z_{1},z_{1}^{\prime})\land\dots\land r_{N}(z_{N},z_{N}^{\prime})$ for
which there exists a mapping $\mu$ from
$\\{z_{1},z_{1}^{\prime},\dots,z_{N},z_{N}^{\prime}\\}$ to
$\\{n_{0},n_{1},m_{1},\dots,n_{K},m_{K}\\}$ such that $\mu(x)=n_{0}$,
$\mu(y)=n_{K}$ and for $1\leq i\leq N$ there is a path $\pi_{i}$ between
$\mu(z_{i})$ and $\mu(z_{i}^{\prime})$, such that the sequence of edge labels
$L_{i}$ associated to $\pi_{i}$ satisfies the regular path expression $r_{i}$.

Consider the following steps to construct an ABox $\mathcal{A}_{r}$ from the
mapping $\mu$ and $q_{r}$. First, add all $\mu(z_{i})$ and
$\mu(z^{\prime}_{i})$ with $1\leq i\leq N$ as nodes to the ABox. In a second
step we extend the graph at $a_{0}=\mu(z_{i})$ by fresh nodes and edges
matching the regular path expression $r_{i}$. For that consider the sequence
of edges (with inverses) $L_{i}=e_{0}e_{1}\dots e_{k}$ from above, satisfying
the regular path expression $r_{i}$. Then, we add the nodes
$a_{1},\dots,a_{k}$ with $a_{k+1}=\mu(z^{\prime}_{i})$ and the following edges
to the ABox, where $1\leq j\leq$ $k+1$

  * •

if $e_{j}=r$ or $e_{j}=s$, then add $e_{j}(a_{j-1},a_{j})$

  * •

if $e_{j}=r^{-}$ or $e_{j}=s^{-}$, then add $e_{j}(a_{j},a_{j-1})$.

By the construction it follows that $(n_{0},n_{K})\in\llbracket
q_{r}(x,y)\rrbracket^{\mathcal{A}_{r}}$ for $\mu(x)=n_{0}$, $\mu(y)=n_{K}$. It
remains to show that $(n_{0},n_{K})$ is not an answer to $q(x,y)$ over
$(\mathcal{T},\mathcal{A}_{r})$, i.e. an answer over
$\mathcal{A}_{\mathcal{T},\mathcal{A}_{r}}$ the corresponding property graph
to the canonical model of $(\mathcal{T},\mathcal{A}_{r})$.

First assume that $n_{0}$ and $n_{K}$ are in the same connected component,
because if $n_{0}$ and $n_{K}$ are not connected in
$\mathcal{A}_{\mathcal{T},\mathcal{A}_{r}}$, then obviously
$(n_{0},n_{K})\notin\llbracket
q(x,y)\rrbracket^{\mathcal{A}_{\mathcal{T},\mathcal{A}_{r}}}$. Next, observe
that $\mathcal{A}_{r}$ contains only edges from the construction step above
that converted a sequence of edge labels into a _semi-path_ (a path
disregarding the direction), that is _linear_ , i.e., the sum of out and in-
degree for each node on the path is at most 2. This and the fact that $K>N+1$
with $N$ the number of conjuncts in $q_{r}$ implies that there are
intermediate nodes that have at most 2 as sum of in- and out-degrees in
$\mathcal{A}_{r}$. Further, the sequences of edge labels $L_{i}$ consists of
either $r$, $s$ or their inverses, but not label $p$. Thus, for the C2RPQ
$q(x,y)=(rpp^{-})^{+}(x,y)$ to have a mapping in
$\mathcal{A}_{\mathcal{T},\mathcal{A}_{r}}$, an edge with label $p$ must be
added in the construction of the canonical model based on an edge with label
$s$ in $\mathcal{A}_{r}$. But then every node on a path that has a mapping for
$(rpp^{-})^{+}(x,y)$ (besides start and end node) must have in-degree at least
1 (in-going edge with label $r$) and out-degree at least 2 (out-going edges
with labels $r$ and $s$). Therefore, $(n_{0},n_{K})$ cannot be in $\llbracket
q(x,y)\rrbracket^{\mathcal{A}_{\mathcal{T},\mathcal{A}_{r}}}$, which
contradicts the initial assumption that there exists a UC2RPQ rewriting for
$q(x,y)$ over the given TBox. ∎

##  Appendix D Proofs of Section 4

To prove Lemma 2, we proceed in three steps. We first show separate lemmas for
the case of the form $A\sqsubseteq B$ (i.e., $n=0$ in Lemma 5) and for
entailments of the form $\exists r.A\sqsubseteq B$ (i.e., $n=1$ in Lemma 6),
which allow for proofs with a simpler model construction.111A direct proof can
be done with an analogous construction; we will include it in the full
version. Then we obtain Lemma 2 using an inductive argument.

######  Lemma 5.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ and $G_{\mathcal{T}}$ its
dependency graph. Then, for all concept names $A$ and $B$ occurring in
$\mathcal{T}$, have $\mathcal{T}\vDash A\sqsubseteq B$ iff there exists an
$\varepsilon^{*}\text{-path from }B\text{ to }A$ in $G_{\mathcal{T}}$.

###### Proof.

For ($\Rightarrow$), we build from
$G_{\mathcal{T}}=(N_{\mathcal{T}},E_{\mathcal{T}})$ a model $\mathcal{I}$ of
$\mathcal{T}$ such that, if there is no $\varepsilon^{*}\text{-path from
}B\text{ to }A$, then $A\not\sqsubseteq B$. $\mathcal{I}$ is defined as
follows:

$\displaystyle\varDelta^{\mathcal{I}}:=$ $\displaystyle\\{[C]\mid C\in
N_{\mathcal{T}}\\}$ $\displaystyle A^{\mathcal{I}}:=$
$\displaystyle\\{[C]\in\varDelta^{\mathcal{I}}\mid\text{~{}there is
an~{}}\varepsilon^{*}\text{-path from }A\text{ to }C\\}$ $\displaystyle
r^{\mathcal{I}}:=$
$\displaystyle\\{([B],[S])\in\varDelta^{\mathcal{I}}\times\varDelta^{\mathcal{I}}\mid\text{~{}there
is an~{}}\varepsilon^{*}\text{-path from }A\text{ to }B,\exists s(A,S)\in
E_{\mathcal{T}},s\sqsubseteq^{*}_{\mathcal{T}}r\\}$
$\displaystyle\\{([S],[B])\in\varDelta^{\mathcal{I}}\times\varDelta^{\mathcal{I}}\mid\text{~{}there
is an~{}}\varepsilon^{*}\text{-path from }A\text{ to }B,\exists s^{-}(A,S)\in
E_{\mathcal{T}},s\sqsubseteq^{*}_{\mathcal{T}}r\\}$

The construction guarantees that $[A],[B]\in\varDelta^{\mathcal{I}}$, that
$[A]\in A^{\mathcal{I}}$, and that if there is no $\varepsilon^{*}\text{-path
from }B\text{ to }A$, then $[A]\not\in B^{\mathcal{I}}$ as desired. So we only
need to verify that $\mathcal{I}\models\mathcal{T}$. For this, we consider the
following cases according to the axiom shapes in $\mathcal{T}$:

  * •

$C\sqsubseteq D$. Let $[C^{\prime}]\in C^{\mathcal{I}}$, then by construction
of $\mathcal{I}$ it holds that $\varepsilon^{*}\text{-path from }C\text{ to
}C^{\prime}$. From item (ii) in Definition 9 it follows that
$\varepsilon^{*}\text{-path from }D\text{ to }C$. Hence,
$\varepsilon^{*}\text{-path from }D\text{ to }C^{\prime}$ and $[C^{\prime}]\in
D^{\mathcal{I}}$.

  * •

$C\sqsubseteq\exists r.D$. Let $[C^{\prime}]\in C^{\mathcal{I}}$, then by
construction of $\mathcal{I}$ it holds that there is an $\varepsilon^{*}$-path
from $C$ to $C^{\prime}$. By Definition 9 item (v) we add $\exists r(C,\exists
r.D)$ and $\varepsilon(D,\exists r.D)$ to $G_{\mathcal{T}}$ and from the
construction of the model $\mathcal{I}$ it follows that
$([C^{\prime}],[\exists r.D])\in r^{\mathcal{I}}$. Since
$\varepsilon(D,[\exists r.D])\in G_{\mathcal{T}}$ and $[\exists r.D]\in
D^{\mathcal{I}}$ by construction of $\mathcal{I}$ it holds that
$[C^{\prime}]\in(\exists r.D)^{\mathcal{I}}$.

  * •

$C\sqsubseteq\exists r^{-}.\top$. Let $[C^{\prime}]\in C^{\mathcal{I}}$, then
by construction of $\mathcal{I}$ it holds that there is an
$\varepsilon^{*}$-path from $C$ to $C^{\prime}$. By Definition 9 item (vi) we
add $\exists r^{-}(C,\exists r^{-})$ and by item (i) $\varepsilon(\top,\exists
r^{-})$ to $G_{\mathcal{T}}$. From the construction of the model $\mathcal{I}$
it follows that $([\exists r^{-}],[C^{\prime}])\in r^{\mathcal{I}}$, therefore
$[C^{\prime}]\in(\exists r^{-}.\top)$.

  * •

$\exists r.C\sqsubseteq D$. Let $[E]\in(\exists r.C)$, then by Definition 9
item (iii) we add $r(D,C)$ to $G_{\mathcal{T}}$ and based on the definition
for $r^{\mathcal{I}}$ we distinguish two cases:

    1. (a)

There is a $[F]\in\varDelta^{\mathcal{I}}$ such that $([E],[F])\in
r^{\mathcal{I}}$ and $[F]\in C^{\mathcal{I}}$. By construction of model
$\mathcal{I}$ it follows that there is $\exists s(E,S)$ and
$\varepsilon^{*}\text{-path from }F\text{ to }S$ in $G_{\mathcal{T}}$ with
$s\sqsubseteq^{*}_{\mathcal{T}}r$. Further, since $[F]\in C^{\mathcal{I}}$ it
holds by construction of $\mathcal{I}$ that there is
$\varepsilon^{*}\text{-path from }C\text{ to }F$, and subsequently
$\varepsilon^{*}\text{-path from }C\text{ to }S$. From the facts that
$r\text{-path from }D\text{ to }C\in E_{\mathcal{T}},\exists
s(E,S),s\sqsubseteq^{*}_{\mathcal{T}}r$ and $\varepsilon^{*}\text{-path from
}C\text{ to }S$ it follows by Definition 9 item (ix) that there is
$\varepsilon(D,E)$ in $G_{\mathcal{T}}$ and $[E]\in D^{\mathcal{I}}$ holds.

    2. (b)

If $[E]=[S]$ then $([S],[C^{\prime}])\in r^{\mathcal{I}}$ and $[C^{\prime}]\in
C^{\mathcal{I}}$. From the construction of $\mathcal{I}$ we know that there
must exist $\exists s^{-}(C,S)$ where $s\sqsubseteq^{*}_{\mathcal{T}}r$. By
Definition 9 item (viii) there is an $\varepsilon(D,S)$ edge and it holds that
$[E]\in D^{\mathcal{I}}$.

  * •

$\exists r^{-}.\top\sqsubseteq C$. Let $[F]\in(\exists
r^{-}.\top)^{\mathcal{I}}$, from Definition 9 item (iii) there is an
$r^{-}(C,\top)$ in $G_{\mathcal{T}}$. Further, by the construction of model
$\mathcal{I}$ there are two possible cases for $([E],[F])\in r^{\mathcal{I}}$:

    1. (a)

There is a $\exists s(E,F)$ in $G_{\mathcal{T}}$ and
$s\sqsubseteq^{*}_{\mathcal{T}}r$. Since there is $r^{-}\text{-path from
}C\text{ to }\top$ and $\exists s(E,F)$ in $G_{\mathcal{T}}$ we add
$\varepsilon(C,F)$ by Definition 9 item (vii). Because of this edge it holds
that $\varepsilon^{*}\text{-path from }C\text{ to }F$ and thus $[F]\in
C^{\mathcal{I}}$.

    2. (b)

There is $\exists s^{-}(F,E)$ in $G_{\mathcal{T}}$ and
$s\sqsubseteq^{*}_{\mathcal{T}}r$. Since we have $r^{-}\text{-path from
}C\text{ to }\top$, $\varepsilon(\top,E)$ and $\exists s^{-}(F,E)$ with
$s\sqsubseteq^{*}_{\mathcal{T}}r$ it holds by Definition 9 item (ix) that
there is $\varepsilon(C,F)$ in $G_{\mathcal{T}}$. It follows that $[F]\in
C^{\mathcal{I}}$.

  * •

$s\sqsubseteq r$. Let $([C],[D])\in s^{\mathcal{I}}$, then it follows from the
definition of $\mathcal{I}$ that there is $C\sqsubseteq\exists t.D$ and
$t\sqsubseteq^{*}_{\mathcal{T}}s$. Since $t\sqsubseteq^{*}_{\mathcal{T}}r$ we
can conclude that $([C],[D])\in r^{\mathcal{I}}$ holds.

For ($\Leftarrow$), the claim follows by construction of the concept
dependency graph $G_{\mathcal{T}}$. In the following we show soundness for
each item in Definition 9. First, consider Item (i), where soundness is given
since $\mathcal{T}\models\top\sqsubseteq A$ for any concept $A$ in
$\mathcal{T}$. Also Item (ii) and Item (iii) immediately follow from the fact
that the CIs are in $\mathcal{T}$. Item (v) and Item (vi) do not add any edges
to the $G_{\mathcal{T}}$ that affect this claim, since $\exists r.B$ is not a
concept name. However, they are relevant to show soundness of the subsequent
items. In item (vii) we add $\varepsilon(C,W_{\exists s.D})$ to
$G_{\mathcal{T}}$, if there is $\exists r^{-}.\top\sqsubseteq C$ in
$\mathcal{T}$ and $\exists s(A,W_{\exists s.D})$ in $G_{\mathcal{T}}$ with
$s\sqsubseteq^{*}_{\mathcal{T}}r$. From $\exists s(A,W_{\exists s.D})$ and
Definition (v) it follows that $A\sqsubseteq\exists s.D\in\mathcal{T}$ and
$\mathcal{T}\models A\sqsubseteq\exists r.D$. Then, under the condition that
$\exists r^{-}.\top\sqsubseteq C\in\mathcal{T}$ it holds that $[W_{\exists
s.D}]\in C^{\mathcal{I}}$. We continue with Item (viii) where we add
$\varepsilon(C,D)$ to $G_{\mathcal{T}}$ if there is $\exists r.A\sqsubseteq C$
in $\mathcal{T}$ and $\exists s^{-}(A,D)$ with
$s\sqsubseteq^{*}_{\mathcal{T}}r$. The argumentation is similar as before.
From $\exists s^{-}(A,D)$ and Item (v) it follows that $A\sqsubseteq\exists
s^{-}.W\in\mathcal{T}$ and $\varepsilon(D,W)\in G_{\mathcal{T}}$. Further, it
holds that $\mathcal{T}\models A\sqsubseteq\exists r^{-}.W$ and from $\exists
r.A\sqsubseteq C\in\mathcal{T}$ we conclude that for an
$\varepsilon^{*}\text{-path from }C\text{ to }W$ it holds that
$\mathcal{T}\models W\sqsubseteq C$. Finally, Item (ix) where we add an
$\varepsilon(C,A)$ if there is $\exists s(A,B)$ in $G_{\mathcal{T}}$ for some
$s\sqsubseteq^{*}_{\mathcal{T}}r$ and there is an $r$-path from some node $C$
in $G_{\mathcal{T}}$ to $B$. The latter implies that there has to be an
$\varepsilon^{*}\text{-path from }C\text{ to }D$, an axiom $\exists
r.E\sqsubseteq C$ in $\mathcal{T}$ and an $\varepsilon^{*}\text{-path from
}E\text{ to }B$, whereas $B$ must be a node of the form $\exists s.W$. Since
there is an $\varepsilon^{*}\text{-path from }E\text{ to }\exists s.W$ and
$\mathcal{T}\models A\sqsubseteq\exists r.W$ it follows that
$\mathcal{T}\models A\sqsubseteq\exists r.E$. From this fact and the axiom
$\exists r.E\sqsubseteq C$ in $\mathcal{T}$ we conclude that
$\mathcal{T}\models A\sqsubseteq C$. ∎

######  Definition 14.

For a given ABox $\mathcal{A}$ and a TBox $\mathcal{T}$. Let $G_{\mathcal{T}}$
be the concept dependency graph of $\mathcal{T}$. We define $\mathcal{I}_{0}$
as follows:

$\displaystyle\Delta^{\mathcal{I}_{0}}=$ $\displaystyle\\{a\mid A(a)\text{ or
}r(a,b)\text{ or }r(b,a)\text{ is in }\mathcal{A}\\}$
$\displaystyle\cup\\{[\exists r.D]\text{ in $G_{\mathcal{T}}$ such that
}\exists r(A,\exists r.D)\in E_{\mathcal{T}}\text{ and }A\text{ occurs in
$\mathcal{A}$}\\}$ $\displaystyle A^{\mathcal{I}_{0}}=$
$\displaystyle\\{[\exists r.D]\mid\text{ there is an
}\varepsilon^{*}\text{-path from }A\text{ to }\exists r.D\text{ in
}G_{\mathcal{T}}\\}$ $\displaystyle\cup\\{a\mid B(a)\in\mathcal{A}\text{ for
some }B\text{ that has an }\varepsilon^{*}\text{-path from }A\text{ in
}G_{\mathcal{T}}\\}$ $\displaystyle r^{\mathcal{I}_{0}}=$
$\displaystyle\\{(a,b)\mid s(a,b)\in A\text{ for some
}s\sqsubseteq^{*}_{\mathcal{T}}r\\}$ $\displaystyle\cup\\{(a,[\exists
s.B])\mid a\in A^{\mathcal{I}}\text{ for some }A\in N_{\mathcal{T}}$
$\displaystyle\text{ and some }\exists s.B\text{ where }\exists s(A,\exists
s.B)\in G_{\mathcal{T}}\text{ and }s\sqsubseteq^{*}_{\mathcal{T}}r\\}$
$\displaystyle\cup\\{([\exists r^{-}.B],a)\mid a\in A^{\mathcal{I}}\text{ and
}\exists r^{-}(A,\exists r^{-}.B)\in E_{\mathcal{T}}\\}$

Then, we obtain a model $\mathcal{I}$ by chasing $\mathcal{I}_{0}$ under the
following two rules until we reach a fixpoint.

  1. 1.

If $a\in(\exists r.B)^{\mathcal{I}_{i}}$ and there is an $r\text{-path from
}A\text{ to }B$, then add $a$ to $A^{\mathcal{I}_{i+1}}$.

  2. 2.

If $a\in B^{\mathcal{I}_{i}}$ and there is an $\exists r\text{-path from
}A\text{ to }B$, then add $(a,\exists r.A)\in r^{I_{i+1}}$ for all
$r\sqsubseteq^{*}_{\mathcal{T}}s$.

For the proof of Lemma 2, we introduce the following Lemma.

######  Lemma 6.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, and let $G_{\mathcal{T}}$
be its concept dependency graph. For every $\mathcal{ELHI}^{lin}$ concept of
the form $\exists r.A$, and for every concept name $B$ (such that there is no
$\varepsilon^{*}$-path from $B$ to $\top$), we have that
$\mathcal{T}\models\exists r.A\sqsubseteq B$ iff there exists an $(r)$-path
from $B$ to $A$ in $G_{\mathcal{T}}$.

###### Proof.

We show ($\Rightarrow$) in the following by contraposition, we construct a
model $\mathcal{I}$ according to Definition 14 with a given TBox $\mathcal{T}$
and the ABox $\mathcal{A}=\\{r(c,d),A(d)\\}$. Assume that there is no
$r\text{-path from }B\text{ to }A$ and observe that $c\in(\exists
r.A)^{\mathcal{I}}$, we need to show that $c\not\in B^{\mathcal{I}}$. Since
$A^{\prime}(c)\not\in\mathcal{A}$ for some concept name $A^{\prime}$ in
$\mathcal{T}$, it follows by construction of $\mathcal{I}_{0}$ that $c\not\in
A^{\mathcal{I}_{0}}$. It trivially holds for every individual
$a\in\Delta^{\mathcal{I}}$ that $a\in\top^{\mathcal{I}}$. However, from the
condition in the claim, that there must not be a $\varepsilon^{*}$-path from
$B$ to $\top$, the assumption that there is no $r\text{-path from }B\text{ to
}A$ and by the two additional rules to obtain $\mathcal{I}$ we follow that $c$
must not be in $B^{\mathcal{I}_{i}}$.

It remains to show that $\mathcal{I}$ is a model.

  * •

$C\sqsubseteq D$. Let $c\in C^{\mathcal{I}}$, it follows by item (ii) that
$\varepsilon(D,C)\in G_{\mathcal{T}}$ and thus $c\in D^{\mathcal{I}}$.

  * •

$C\sqsubseteq\exists r.D$. Let $c\in C^{\mathcal{I}}$, further it follows from
the construction of the concept dependency graph that $\exists r(C,\exists
r.D)$ and $\varepsilon(A,\exists r.D)$ in $G_{\mathcal{T}}$. From these facts
and $c\in C^{\mathcal{I}}$ it follows that $(c,\exists r.D)\in
r^{\mathcal{I}}$. Since $\exists r.D\in A^{\mathcal{I}}$ we conclude with
$c\in(\exists r.D)^{\mathcal{I}}$.

  * •

$C\sqsubseteq\exists r^{-}.\top$. Let $c\in C^{\mathcal{I}}$ and from the
construction of the concept dependency graph it holds that $\exists
r^{-}(C,\exists r^{-})\in G_{\mathcal{T}}$. From $c\in C^{\mathcal{I}}$ it
follows that $([\exists r^{-}.\top],c)\in r^{\mathcal{I}}$, thus $c\in(\exists
r^{-}.\top)^{\mathcal{I}}$.

  * •

$\exists r.C\sqsubseteq D$. For $c\in(\exists r.C)^{\mathcal{I}}$ it follows
by construction of $\mathcal{I}$ that $c\in D^{\mathcal{I}}$.

  * •

$\exists r^{-}.\top\sqsubseteq D$. For $c\in(\exists
r^{-}.\top)^{\mathcal{I}}$ it follows by construction of $\mathcal{I}$ that
$c\in D^{\mathcal{I}}$.

The proof for $(\Leftarrow)$ follows the same argumentation as ($\Leftarrow$)
in the proof of Lemma 2. ∎

######  Lemma 7.

Given an $\mathcal{ELHI}^{lin}$ TBox $\mathcal{T}$. If
$\mathcal{T}\models\exists r_{1}\dots\exists r_{n+1}.A\sqsubseteq B$ with
$r_{1},\dots,r_{n+1}\in\overline{\mathbf{R}}$, then there is
$\mathcal{T}\models\exists r_{1}\dots\exists r_{n}.A^{\prime}\sqsubseteq B$
and $\mathcal{T}\models\exists r_{n+1}.A\sqsubseteq A^{\prime}$ for some
$A^{\prime}\in\mathbf{C}\cup\top$.

###### Proof.

We show the claim by contradiction. For that assume that
$\mathcal{T}\models\exists r_{1}\dots\exists r_{n+1}.A\sqsubseteq B$ holds,
i.e., there is an $\mathcal{I}$ such that $(a_{0},a_{n+1})\in(\exists
r_{1}\dots\exists r_{n+1})^{\mathcal{I}}$, $a_{0}\in B^{\mathcal{I}}$ and
$a_{n+1}\in A^{\mathcal{I}}$. Then, we distinguish two cases, either (1)
$\mathcal{T}\not\models\exists r_{1}\dots\exists r_{n}.A^{\prime}\sqsubseteq
B$ and $\mathcal{T}\models\exists r_{n+1}.A\sqsubseteq A^{\prime}$ for some
$A^{\prime}\in\mathbf{C}\cup\top$ or (2) $\mathcal{T}\models\exists
r_{1}\dots\exists r_{n}.A^{\prime}\sqsubseteq B$ and
$\mathcal{T}\not\models\exists r_{n+1}.A\sqsubseteq A^{\prime}$ for some
$A^{\prime}\in\mathbf{C}\cup\top$. Consider case (1), which means there is no
model $\mathcal{I}_{1}$, such that $(a^{\prime}_{0},a^{\prime}_{n})\in(\exists
r_{1}\dots\exists r_{n})^{\mathcal{I}_{1}}$, $a^{\prime}_{0}\in
B^{\mathcal{I}_{1}}$ and $a^{\prime}_{n}\in A^{\prime\mathcal{I}_{1}}$ for
some arbitrary $A^{\prime}\in\mathbf{C}\cup\top$. Now, we consider the model
$\mathcal{I}$, for which holds that there is some $a_{n}$, such that
$(a_{n},a_{n+1})\in(\exists r_{n})^{\mathcal{I}}$. From
$\mathcal{T}\models\exists r_{1}\dots\exists r_{n+1}.A\sqsubseteq B$ and the
fact that we consider normalised TBoxes only, there must be some axiom in
LABEL:NF3 or LABEL:NF7 in $\mathcal{T}$, i.e., $\exists r_{n+1}.C\sqsubseteq
B\in\mathcal{T}$ with $C\in\mathbf{C}\cup\top$. Hence, there is a model
$\mathcal{I}_{1}$, such that $(a^{\prime}_{0},a^{\prime}_{n})\in(\exists
r_{1}\dots\exists r_{n})^{\mathcal{I}_{1}}$, $a^{\prime}_{0}\in
B^{\mathcal{I}_{1}}$ and $a^{\prime}_{n}\in A^{\prime\mathcal{I}_{1}}$ for
some arbitrary $A^{\prime}\in\mathbf{C}\cup\top$, which is a contradiction.
From the assumption in case (2) it follows that there is no model
$\mathcal{I}_{2}$, such that
$(a^{\prime\prime}_{n},a^{\prime\prime}_{n+1})\in(\exists
r_{n+1})^{\mathcal{I}_{2}}$, $a^{\prime\prime}_{n}\in
A^{\prime\mathcal{I}_{2}}$ and $a^{\prime\prime}_{n+1}\in
B^{\mathcal{I}}_{2}$. Since $\mathcal{T}\models\exists r_{1}\dots\exists
r_{n}.A^{\prime}\sqsubseteq B$ it holds for model $\mathcal{I}$ that $a_{n}\in
A^{\prime\mathcal{I}}$ and $(a_{n},a_{n+1})\in r_{n+1}^{\mathcal{I}}$, which
is a contradiction to the previous statement that there is no model
$\mathcal{I}_{2}$. ∎

######  Lemma 2.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, and let $G_{\mathcal{T}}$
be its concept dependency graph. For every $\mathcal{ELHI}^{lin}$ concept of
the form $\exists r_{1}\cdots\exists r_{n}.A$ with $n\geq 1$, and for every
concept name $B$, we have that $\mathcal{T}\models\exists r_{1}\cdots\exists
r_{n}.A\sqsubseteq B$ iff there exists an $(r_{1}\cdots r_{n})$-path from $B$
to $A$ in $G_{\mathcal{T}}$.

###### Proof.

We proceed to show each direction of the claim by induction on $n$.

$(\Rightarrow)$ The base case for $n=1$ holds by Lemma 6, stating that if
$\mathcal{T}\models\exists r_{1}.A\sqsubseteq B$ then there is a
$(r_{1})$-path from $B$ to $A$. We continue to show the induction step
($n+1$). Assume that $\mathcal{T}\models\exists r_{1}\cdots\exists
r_{n+1}.A\sqsubseteq B$. By Lemma 7 it follows that there is $\exists
r_{1}\cdots\exists r_{n}.A^{\prime}\sqsubseteq B$ and
$\mathcal{T}\models\exists r_{n+1}.A\sqsubseteq A^{\prime}$ for some
$\in\mathbf{C}\cup\top$. From the induction hypothesis there exists an
$(r_{1}\dots r_{n})$-path from $B$ to $A^{\prime}$ in $G_{\mathcal{T}}$ and
from Lemma 6 there is a $r_{n+1}$-path from $A^{\prime}$ to $A$. By combining
these two paths, we can conclude that there exists a $(r_{1}\dots
r_{n+1})$-path from $B$ to $A$ in $G_{\mathcal{T}}$.

$(\Leftarrow)$ The base case with $n=1$ again follows from Lemma 6, stating
that if there is an $(r_{1})$-path from $B$ to $A$ then
$\mathcal{T}\models\exists r_{1}.A\sqsubseteq B$. Next, we show the induction
step with $n+1$. From the induction hypothesis, we know that if there is an
$(r_{1}\dots r_{n})$-path from $B$ to $A$ in $G_{\mathcal{T}}$ then it must
hold that $\mathcal{T}\models\exists r_{1}\cdots\exists r_{n}.A\sqsubseteq B$.
Assume that we have an $(r_{n+1})$-path from $A$ to $A^{\prime}$. From Lemma 6
it holds that $\mathcal{T}\models\exists r_{n+1}.A^{\prime}\sqsubseteq A$. To
sum it up, from the fact that there is a $(r_{1}\dots r_{n}r_{n+1})$-path from
$B$ to $A^{\prime}$ it follows that $\mathcal{T}\models\exists
r_{1}\cdots\exists r_{n}\exists r_{n+1}.A^{\prime}\sqsubseteq B$. ∎

######  Lemma 3.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox. For each ABox
$\mathcal{A}$, each $A_{0}\in\mathbf{C}$ and each individual $n_{0}$, we have
$\mathcal{T},\mathcal{A}\models A_{0}(n_{0})$ if and only if there exists an
$(r_{1}\dots r_{k})$-path from $A_{0}$ to some $A_{k}$ in $G_{\mathcal{T}}$
and individuals $n_{1},\ldots,n_{k}$ such that ${\mathcal{A}}\models
r_{j}(n_{j},n_{j+1})$ for all $0\leq j<k$ and ${\mathcal{A}}\models
A_{k}(n_{k})$.

###### Proof.

Given an ABox $\mathcal{A}$ and a TBox $\mathcal{T}$, to show the claim for
($\Rightarrow$) we use the model construction for $\mathcal{A}$ and
$\mathcal{T}$ from Definition 14 to obtain $\mathcal{I}$. From that proof we
already know that $\mathcal{I}$ is a valid model.

It remains to show that if (i) no $(r_{1}\dots r_{k})$-path in
$G_{\mathcal{T}}$, or for all individuals $n_{1},\dots,n_{k}$, either (ii)
$\mathcal{T},\mathcal{A}\not\models r_{j}(n_{j},n_{j+1})$ for some
$j\in\\{0,\dots,k\\}$. or (ii) $\mathcal{T},\mathcal{A}\not\models
A_{k}(n_{k})$, then it holds that $n_{0}\not\in A_{0}^{\mathcal{I}}$. Note
that $A_{k}$ can be $\top$ and we assume that $\top(n_{j})\in\mathcal{A}$.

  1. (i)

Consider the case with no $(r_{1}\dots r_{k})$-path from $A_{0}$ to $A_{k}$ in
$G_{\mathcal{T}}$, $(n_{j},n_{j+1})\in r_{j}^{\mathcal{I}}$ for $0\leq j<k$
and $n_{k}\in A_{k}^{\mathcal{I}}$. From the fact that there is no
$(r_{1}\dots r_{k})$-path from $A_{0}$ to $A_{k}$ and the construction of
$\mathcal{I}$ it follows that $n_{0}\not\in A_{0}^{\mathcal{I}}$.

  2. (ii)

Assume that $(n_{j},n_{j+1})\not\in r_{j}^{\mathcal{I}}$ for $0\leq j<k$,
$n_{k}\in A_{k}^{\mathcal{I}}$ and there is a $(r_{1}\dots r_{k})$-path in
$G_{\mathcal{T}}$ from $A_{0}$ to $A_{k}$. Then, by assumption there is
$(n_{j},n_{j+1})\not\in r_{j}^{\mathcal{I}}$ for some $j\in\\{0,\dots,k\\}$.
Since there is a $(r_{1}\dots r_{j}r_{j+1}\dots r_{k})$-path from $A_{0}$ to
$A_{k}$ there has to be an axiom of the form $\exists
r_{j+1}A_{j+1}\sqsubseteq A_{j}\in\mathcal{T}$ with $A_{j},A_{j+1}$ concept
names on the $(r_{1}\dots r_{j}r_{j+1}\dots r_{k})$-path in $G_{\mathcal{T}}$.
From the fact that $n_{j}$ not in $(\exists r_{j}.A_{j+1})^{\mathcal{I}}$ it
holds by construction of $\mathcal{I}$ that $n_{j}\not\in
A_{j}^{\mathcal{I}}$. Subsequently, $n_{i}\not\in A_{i}^{\mathcal{I}}$ for
$0\leq i\leq j$ and $A_{i}$ a concept name along the $(r_{1}\dots r_{i}\dots
r_{j})$-path, we conclude that $n_{0}\not\in A_{0}^{\mathcal{I}}$.

  3. (iii)

$n_{k}\not\in A_{k}^{\mathcal{I}}$, there is a $(r_{1}\dots r_{k})$-path from
$A_{0}$ to $A_{k}$, and $(n_{j},n_{j+1})\in r_{j}^{\mathcal{I}}$ for
individuals $n_{1},\dots,n_{k}$, $0\leq j<k$. Since $n_{k}\not\in
A_{k}^{\mathcal{I}}$ it follows that $(n_{k-1},n_{k})\not\in
r_{k-1}^{\mathcal{I}}$ and from the construction of $\mathcal{I}$ it holds
that $n_{k-1}\not\in A_{k-1}^{\mathcal{I}}$ with $A_{k-1}$ a concept name
along the $(r_{1}\dots r_{k})$-path. Then, we keep decreasing $k$ until we
reach $k=1$ and it holds that $n_{0}\not\in A_{0}^{\mathcal{I}}$.

The proof for $(\Leftarrow)$ almost immediately follows from Lemma 2. ∎

##  Appendix E Proof from Section 5

######  Lemma 4.

$\mathtt{rpe}(B,G_{\mathcal{T}})$ contains exactly the words of the form
$s_{1},\dots,s_{k}A$ such that there is an $(s_{1},\dots,s_{k})$-propagating
path from $B$ to $A$ in $G_{\mathcal{T}}$.

For the proof of Lemma 4 we refer to [26].

######  Theorem 2 (Soundness and completeness).

Let $\varphi(x,y)$ be an arbitrary atomic concept query, where
$\varphi(x,y)=\langle A\rangle(x,y)$ or $\varphi(x,y)=r(x,y)$, $\mathcal{T}$
an $\mathcal{ELHI}^{lin}$ TBox, $\mathcal{A}$ an ABox consistent with
$\mathcal{T}$ and $G_{\mathcal{T}}$ the concept dependency graph of
$\mathcal{T}$. Then, $a$ is an answer to
$q_{r}(x)=\mathtt{rewriteAQ}(\varphi(x,y),G_{\mathcal{T}})$ in $\mathcal{A}$,
iff $a$ is a certain answer to $(\mathcal{T},\mathcal{A},\varphi(x,y))$.

The proof for Theorem 3 concerning queries of the form $\varphi=\langle
A\rangle(x,y)$ follows from LABEL:corollary:rpeWithAbox. For a given query of
the form $\varphi(x,y)=r(x,y)$ it is easy to see that $\big{(}\bigcup
r_{i}\big{)}(x,y)$ with $r_{i}\sqsubseteq^{*}_{\mathcal{T}}r$ is a correct
rewriting.

##  Appendix F Proofs of Section 6

######  Lemma 8.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox and $\mathcal{A}$ an ABox
consistent with $\mathcal{T}$. For two NCQs $q_{1}(\vec{x})$ and
$q_{2}(\vec{x})$ with
$q_{2}(\vec{x})=\mathtt{clipping}(q_{1}(\vec{x}),A\sqsubseteq\exists r.B,y)$
such that $A\sqsubseteq\exists r.B\in\mathcal{T}$ and $y\not\in\vec{x}$, it
holds that $\vec{a}$ is an answer to $q_{2}(\vec{x})$ over
$(\mathcal{T},\mathcal{A})$ implies $\vec{a}$ is an answer to $q_{1}(\vec{x})$
over $(\mathcal{T},\mathcal{A})$.

###### Proof.

Assume that we obtain
$q_{2}(\vec{x})=\mathtt{clipping}(q_{1}(\vec{x}),A\sqsubseteq\exists r.B,Y)$
where $\mu_{2}$ is a mapping for $q_{2}$ in
$\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$, the corresponding
property graph of the canonical model $\mathcal{I}_{\mathcal{T},\mathcal{A}}$
and $\vec{a}=\mu_{2}(\vec{x})$, i.e., $\mu_{2}\in\llbracket
q_{2}\rrbracket^{\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}}$.
Moreover, let $a=\mu_{2}(y)$. Then, since by step (C6) we add $A(y)$ to
$q_{2}$ we know that $a\in(\exists
r.B)^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. From this follows that there
has to be a $b\in\varDelta^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ such that
$(a,b)\in r^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ and $b\in
B^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. We define the mapping $\mu_{1}$
for the variables of $q_{1}$ as given below:

  1. (a)

$\mu_{1}(x)=a$ for all variables $x\in X$

  2. (b)

$\mu_{1}(y)=b$ for all variables $y\in Y$

  3. (c)

$\mu_{1}(z)=\mu_{2}(z)$ for the remaining variables z.

In the following we show that $\mu_{1}$ is a mapping for $q_{1}$ in
$\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. For that consider an
atom $\alpha$ in $q_{1}$, then there are two cases:

  1. (i)

$y$ occurs in $\alpha$, then there are three further cases:

    1. (A)

$\alpha$ contains a star and if there is a variable $z\neq y$, it is unbound.
It follows that $z\not\in X$ and also doesn’t occur in $q_{2}$, observe that
$\mu_{1}(z)=b$, and $\mu_{1}(y)=b$ by construction of $\mu_{1}$. It is a valid
mapping since $\alpha$ contains a star and $y$ can trivially be mapped to any
node.

    2. (B)

$\alpha$ contains a concept name $C$ with $\mathcal{T}\vDash B\sqsubseteq C$
or $\mathcal{T}\vDash\exists r^{-}\sqsubseteq C$ and if has a variable $z\neq
y$ it is unbound. Since $z\not\in X$ and also doesn’t occur in $q_{2}$, by
construction of $\mu_{1}$ we have $\mu_{1}(z)=b$ and $\mu_{1}(y)=b$. From
above we know that $b\in B^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$, from
which follows that $b\in C^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. Hence,
$\mu_{1}$ is a valid mapping for the atom $\alpha$.

    3. (C)

$\alpha$ is either of the form $\pi(x,y)$ where $\pi$ contains $s$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$ or $\pi(y,x)$ with $s^{-}$, and $x\neq y$.
In both cases $\alpha\in\mathbf{C}_{y}$, then $\alpha$ can either be in
$\mathbf{C}_{y}^{1}$ or $\mathbf{C}_{y}^{*}$. Let’s first consider the case
where $\alpha\in\mathbf{C}_{y}^{1}$, which means that $s$ does not occur in
the scope of a star. Further, $x\in X$ and thus $\mu_{1}(x)=a$ and
$\mu_{1}(y)=b$. From above we know that $(a,b)\in
r^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ and since
$r\sqsubseteq^{*}_{\mathcal{T}}s$, we conclude that $\mu_{1}$ is a valid
mapping for $q_{1}(\vec{x})$ in both cases, i.e. $\pi$ contains $s$ or
$s^{-}$. Next, we show the claim for the case where
$\alpha\in\mathbf{C}_{y}^{*}$, which means that a role $s$ or $s^{-}$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$ occurs in the scope of a star, i.e., $s^{*}$
or $(s^{-})^{*}$. In (C5) we replace $\pi(x,y)$ (or $\pi(y,x)$) by
$\pi\mid^{\mathcal{T}}r(x,y)$ (resp. $\pi\mid^{\mathcal{T}}r(y,x)$) to obtain
$q_{2}$. According to the definition for $\pi\mid^{\mathcal{T}}r(x,y)$,
$s^{*}$ (resp. $(s^{-})^{*}$) remains in $\pi\mid^{\mathcal{T}}r(x,y)$. Hence,
it holds that there is a path from $\mu_{2}(x)$ to $\mu_{2}(y)$ matching
$\pi\mid^{\mathcal{T}}r(x,y)$ and therefore also $\pi(x,y)$. Moreover, by
assumption we have $\mu_{2}(y)=a$ and $(a,b)\in
r^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. Then, since
$\alpha\in\mathbf{C}_{y}^{*}$ by definition of set $X$ it follows that
$x\not\in X$ and thus $x\neq y$, hence we get from the construction
$\mu_{1}(x)=\mu_{2}(x),\mu_{1}(y)=b$. To sum it up, from the facts that
$(a,b)\in r^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$, $s$ or $(s^{-})$ occurs
in the scope of a star in $\pi(x,y)$ with $r\sqsubseteq^{*}_{\mathcal{T}}s$
and there is a path from $\mu_{2}(x)$ to $\mu_{2}(y)$ matching $\pi(x,y)$, we
conclude that $\mu_{1}$ is a valid mapping for $\alpha$.

  2. (ii)

$y$ does not occur in $\alpha$, then we consider the following cases:

    1. (1)

$\alpha$ has no variable from $X$ and the claim holds by item (c) in the
construction of mapping $\mu_{1}$

    2. (2)

$\alpha$ is an atom $\bigcup\pi(x,z)$ with $x\in X$ and $\pi$ is either
$\langle C\rangle,s$ or $s^{*}$, which was replaced by $\bigcup\pi(y,z)$ in
(C4). By construction of $\mu_{1}$ we get $\mu_{1}(x)=a$ and
$\mu_{1}(z)=\mu_{1}(z)$. Since we have $\bigcup\pi(y,z)$ in $q_{2}$ it holds
that $\mu_{1}(x)=\mu_{2}(y)=a$ and $\mu_{1}(z)=\mu_{2}(z)$.

    3. (3)

The cases for $\bigcup\pi(z,x)$ or $(\bigcup\pi(z,x))^{*}$ with either $x\in
X$ and $z\not\in X$ or ${x,y}\subseteq X$ are analogous to the previous two
items.

∎

######  Definition 15 (Degree of mappings).

Given a canonical model $\mathcal{I}_{\mathcal{T},\mathcal{A}}$ with
$\mathcal{I}_{0}$ being the initial model. Let $|a|=0$ for
$a\in\varDelta^{\mathcal{I}_{0}}$. For
$p,w\in\varDelta^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$, and $p$ the parent
of $w$ in the forest of the anonymous part, let $|w|=|p|+1$. We define the
degree of a mapping $\mu$ as $deg(\mu)=\underset{y\in
vars(\mu)}{\Sigma|\mu(y)|}$.

######  Lemma 9.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, $\mathcal{A}$ an ABox
consistent with $\mathcal{T}$ and $q(\vec{x})$ a NCQ. If $q_{1}(\vec{x})$ has
a mapping $\mu_{1}$ in $\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$
such that $\vec{a}=\mu_{1}(\vec{x})$ and $deg(\mu_{1})>0$, then there exists a
$A\sqsubseteq\exists r.B\in\mathcal{T}$ and a set $Y$ where $Y\cap\vec{x}=$
such that $q_{2}(\vec{x})=\mathtt{clipping}(q_{1}(\vec{x}),A\sqsubseteq\exists
r.B,Y)$ has a mapping $\mu_{2}$ in
$\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ where
$\vec{a}=\mu_{2}(\vec{x})$ and $deg(\mu_{2})<deg(\mu_{1})$.

###### Proof.

By assumption $deg(\mu_{1})>0$ from which follows that there exists a variable
$y$ such that $\mu_{1}(y)\not\in N$ with $N$ the nodes of $\mathcal{A}$ and
$y$ a leaf node (no successors) in the anonymous part. Let $d_{y}=\mu_{1}(y)$
and $d_{p}$ be the parent of $d_{y}$ that must be introduced by an application
of a concept inclusion $A\sqsubseteq\exists r.B$ such that $d_{p}\in
A^{\mathcal{I}}_{\mathcal{T},\mathcal{A}}$. Then, we choose a set
$Y=\\{x\in\mathsf{vars}(q_{1})\mid\mu_{1}(x)=d_{y}\\}$ to obtain the query
$q_{2}=\mathtt{clipping}(q_{1},A\sqsubseteq\exists r.B,Y)$, note since
$d_{y}\not\in N$ it holds that $Y\cap\vec{x}=\emptyset$.

In the following we show that an atom $\alpha$ in $q_{1}$ where $y\in Y$
occurs must fall into an item of (C2). Observe that an atom $\alpha$ can have
the form (i) $\bigcup C(y)$ (ii) $\bigcup\pi(x,y)$ or (iii)
$(\bigcup\pi)^{*}(x,y)$ for a $\pi:=s\mid s^{-}\mid\pi^{*}$ where it either
holds for a role $s$ that $r\sqsubseteq^{*}_{\mathcal{T}}s$ or
$r\not\sqsubseteq_{\mathcal{T}}^{*}s$. Let’s first consider the cases (i) with
$\bigcup C^{\prime}(y)$. Since $\mu_{1}$ is a mapping for $q_{1}$, there has
to be some concept $C$ in the union, such that we get $\mu_{1}(y)\in
C^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ and by construction of the
canonical model it holds that $\mu_{1}(y)\in
B^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. Next, consider the case (ii) with
an atom of the form $\bigcup s(x,y)$ such that
$r\sqsubseteq^{*}_{\mathcal{T}}s$. Since $\mu_{1}$ is a mapping for $q_{1}$ in
$\mathcal{I}_{\mathcal{T},\mathcal{A}}$, $\mu_{1}(y)=d_{y}$ and $d_{y}$ must
not have a self-loop it holds that $x\neq y$. Thus, item (C) applies. The same
argument holds for atoms of the form $\bigcup s^{-}(y,x)$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$. Given the fact that $d_{y}$ is a leaf in
the anonymous part and $\mu_{1}(y)=d_{y}$ with $\mu_{1}$ a valid mapping for
$q_{1}$ in $\mathcal{I}_{\mathcal{T},\mathcal{A}}$, there cannot be atoms of
the form $\bigcup s(y,x)$ or $\bigcup s^{-}(x,y)$ in $q_{1}$. We continue with
atoms of the form $\bigcup s^{*}(x,y)$ or $\bigcup(s^{-})^{*}(y,x)$ with
$r\sqsubseteq^{*}_{\mathcal{T}}s$. If $x=y$, the atom falls into item (A),
otherwise into (C). For the inverse directions, i.e., $\bigcup s^{*}(y,x)$ or
$\bigcup(s^{-})^{*}(x,y)$ with $r\sqsubseteq^{*}_{\mathcal{T}}s$, we have
$\mu_{1}(x)=\mu_{1}(y)=d_{y}$ from which follows that $x\in Y$ and thus $x=y$.
A mapping of the form $\mu_{1}(x)\neq\mu_{1}(y)$ is not valid since $d_{y}$ is
a leaf node and $(d_{y},d_{p})\not\in
s^{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$. Further, since $\mu_{1}(y)=d_{y}$
and $\mu_{1}$ a valid mapping for $q_{1}$ over
$\mathcal{I}_{\mathcal{T},\mathcal{A}}$ there can’t be atoms containing only
roles $s$ without a star and with $r\not\sqsubseteq_{\mathcal{T}}^{*}s$. In
case there exists a role $s$ with a star, but
$r\not\sqsubseteq_{\mathcal{T}}^{*}s$ the only valid mapping must contain
$\mu_{1}(x),\mu_{1}(y)=d_{y}$, then $x\in Y$ and the atom falls into (A). The
same argumentation holds for case (iii) with $(\bigcup\pi)^{*}(x,y)$ where the
union is under the scope of a star.

Finally, we construct a mapping $\mu_{2}$ for $q_{2}$ in
$\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$ such that
$\vec{a}=\mu_{2}(\vec{x})$ and $deg(\mu_{2})\leq deg(\mu_{1})$ by setting (a)
$\mu_{2}(z)=\mu_{1}(z)$ for all variables $z$ in $q_{2}$ with $z\not\in Y$,
and (b) $\mu_{2}(y)=d_{p}$. It remains to show that $\mu_{2}$ is a valid
mapping for $q_{2}$ in $\mathcal{A}_{\mathcal{I}_{\mathcal{T},\mathcal{A}}}$.
Observe that $vars(q_{2})\subseteq vars(q_{1})$ and intuitively $q_{2}$ is a
subquery of $q_{1}$. Further, by (i) $|\mu_{2}(z)|=|\mu_{1}(z)|$ for all $z$
in $q_{2}$ with $z\not\in Y$ and (ii) $|\mu_{2}(y)|=|\mu_{1}(y)|-1$, we
conclude that $deg(\mu_{2})<deg(\mu_{1})$. ∎

######  Theorem 3.

Let $\mathcal{T}$ be an $\mathcal{ELHI}^{lin}$ TBox, let $q(\vec{x})$ be a
NCQ, and let $q_{r}=\mathtt{rewriteNCQ}(q(\vec{x}),\mathcal{T})$. For every
ABox $\mathcal{A}$, $\vec{a}$ is a certain answer to $q(\vec{x})$ over
$(\mathcal{T},\mathcal{A})$, iff $\vec{a}$ is an answer to $q_{r}$ over
$\mathcal{A}$.

In Lemma 9 and Lemma 8 we show that one step of the $\mathtt{clipping}$
function is sound and complete. In Algorithm 2 we exhaustively apply this
function, which means that we have a query that can be evaluated over the
plain ABox without the anonymous part. The correctness for the second part of
Algorithm 2 (algorithm 2 to algorithm 2) we show in Theorem 3.

##  Appendix G Artefacts of the Experiments

This is the list of input queries that we used for the experiments.

$Q_{1}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{SemanticDecisionTask}(y)\land$
---|---|---
|  | $\mathsf{has}^{*}(y,z_{1})\land\mathsf{Read}(z_{1})\land\mathsf{has}^{*}(y,z_{2})\land\mathsf{LanguageItem}(z_{2})$
$Q_{2}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{SemanticDecisionTask}(y)\land$
|  | $\mathsf{has}^{*}(y,z_{1})\land\mathsf{Discriminate}(z_{1})\land\mathsf{has}^{*}(y,z_{2})\land\mathsf{Gender}(z_{2})$
$Q_{3}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{GoNoGoTask}(y)$
$Q_{4}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{OddballTask}(y)$
$Q_{5}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{VisualAttentionTask}(y)$
$Q_{6}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{SemanticDecisionTask}(y)\land\mathsf{has}^{*}(y,z_{1})\land$
|  | $\mathsf{CategoricalValue}(z_{1})\land\mathsf{has}^{*}(y,z_{2})\land\mathsf{QuantitativeValue}(z_{2})\land$
|  | $\mathsf{has}^{*}(y,z_{3})\land(\mathsf{Discriminate}\cup\mathsf{Identify})(z_{3})$
$Q_{7}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{SemanticDecisionTask}(y)\land\mathsf{has}^{*}(y,z_{1})\land$
|  | $\mathsf{Character}(z_{1})\land\mathsf{has}^{*}(y,z_{2})\land\mathsf{Judge}(z_{2})\land\mathsf{has}^{*}(y,z_{3})\land\mathsf{Phrase}(z_{3})$
$Q_{8}(x)$ | $\leftarrow$ | $\mathsf{Dataset}(x)\land\mathsf{has}^{*}(x,y)\land\mathsf{has\\_contrast}(y)\land\mathsf{StopSignal{-}GoTrial}(y,z)$