Computing Concept Referring Expressions with
Standard OWL Reasoners
Moritz Illich1 , Birte Glimm1
1
    Ulm University, James-Franck-Ring, Ulm, 89081, Germany


                                         Abstract
                                         Classical instance queries over an ontology only consider explicitly named individuals. Concept referring
                                         expressions (CREs) also allow for returning answers in the form of concepts that describe implicitly given
                                         individuals in terms of their relation to an explicitly named one. Existing approaches, e.g., based on tree
                                         automata, can neither be integrated into state-of-the-art OWL reasoners nor are they directly amenable
                                         for an efficient implementation. To address this, we devise a novel algorithm that uses highly optimized
                                         OWL reasoners as a black box. In addition to the standard criteria of singularity and certainty for CREs,
                                         we devise and consider the criterion of uniqueness of CREs for Horn 𝒜ℒ𝒞 ontologies. The evaluation of
                                         our prototypical implementation shows that computing CREs for the most general concept (⊤) can be
                                         done in less than one minute for ontologies with thousands of individuals and concepts.

                                         Keywords
                                         ontologies, instance retrieval, referring expressions




1. Introduction
Regarding Description Logic (DL) ontologies, automated reasoning systems derive implicit
consequences of explicitly stated information, e.g., when answering queries for concept instances.
Classically, answers to such queries consist of individual names that are used in the knowledge
base. Consider, for example, a knowledge base that states that "every person has a mother
who is a person" and that "John is a person" (in DL syntax: Person ⊑ ∃hasMother.Person and
Person(john)). Obviously, john is an answer to the query for instances of the concept Person and
such names are also called referring expressions as they refer to elements in the models of the
knowledge base. In each model of the knowledge base, however, there is also an element that
represents "the mother of John". This anonymous element can be described by a concept referring
expression (CRE) [1, 2, 3], i.e., by a concept that describes an anonymous element w.r.t. a named
individual. For our example, we can use the CRE "the person who is the mother of John" (as DL
concept: Person ⊓ ∃hasMother− .{john}). The reasoning task of generalized instance retrieval
refers to computing entailed named and anonymous answers in the form of CREs for a concept
instance query, which allows for more comprehensive query results.
   Usually, CREs are meant to identify a single element (e.g., "John’s mother" and not some set
of elements as, e.g., the concept Person itself). While some approaches for computing CREs rely
on functionality of roles and of role paths in order to guarantee singularity, e.g., [2], we do not

  DL 2022: 35th International Workshop on Description Logics, August 7–10, 2022, Haifa, Israel
$ moritz.illich@uni-ulm.de (M. Illich); birte.glimm@uni-ulm.de (B. Glimm)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
make this restriction as also the recent work of Toman and Weddell [3]. Another challenge
when computing CREs is describing all entailed answers to (concept instance) queries. While
the approach of Toman and Weddell based on tree automata addresses this problem, it is not
well-suited for an efficient implementation. Moreover, the applied constraints that ensure the
construction of only singular CREs are actually too strict, thus neglecting query answers in some
cases, while an explicit prevention of duplicate answers referring to different, but semantically
equivalent, CREs is also not provided. In this paper, we address these issues and present the
first practical method for generalized instance retrieval that uses highly optimized reasoners as
a black box for computing CREs.
   At first, we shortly introduce necessary definitions regarding DLs and CREs. We then present
the algorithm for computing answers to generalized instance queries and prove its properties in
Section 3. In Section 4, we show the results of our empirical evaluation, followed by a discussion
of related work in Section 5 and conclusions in Section 6.


2. Preliminaries
Before we can describe our algorithm, we first have to consider some relevant definitions
concerning ontologies and CREs. However, since we assume the reader to be familiar with DLs,
we only focus on selected aspects.

2.1. Description Logics
The syntax of the DL 𝒜ℒ𝒞ℐ𝒪 is defined using a vocabulary consisting of countably infinite
disjoint sets NC of atomic concepts, NR of atomic roles, and NI of individuals. A role is either an
atomic or an inverse role 𝑟− , 𝑟 ∈ NR . An 𝒜ℒ𝒞ℐ𝒪 concept is defined as
               𝐶 ::= ⊤ | ⊥ | 𝐴 | {𝑜} | ¬𝐶 | 𝐶1 ⊓ 𝐶2 | 𝐶1 ⊔ 𝐶2 | ∀𝑅.𝐶 | ∃𝑅.𝐶,
where 𝐴 ∈ NC , 𝑜 ∈ NI , and 𝑅 is a role. The DL 𝒜ℒ𝒞 is obtained from 𝒜ℒ𝒞ℐ𝒪 by disallowing
the use of nominals ({𝑜}) and inverse roles. In the remainder, we use 𝑎, 𝑏 for individuals, 𝐴, 𝐵
for atomic and 𝐶, 𝐷 for (possibly) complex concepts, and 𝑟 for an atomic and 𝑅 for a (possibly)
non-atomic role.
   A TBox is a set of concept inclusion axioms 𝐶 ⊑ 𝐷. An ABox is a set of (concept and
role) assertions of the form 𝐶(𝑎) and 𝑅(𝑎, 𝑏), respectively. A knowledge base (or ontology)
𝒦 = 𝒯 ∪ 𝒜 consists of a TBox 𝒯 and an ABox 𝒜. We use 𝐶 ≡ 𝐷 to abbreviate 𝐶 ⊑ 𝐷 and
𝐷 ⊑ 𝐶. With cons(𝒦), rols(𝒦), and inds(𝒦), we denote the sets of atomic concepts, atomic
roles, and individuals occurring in 𝒦, respectively. Interpretations and models are defined in
the standard way (see e.g. [4]).
   For a knowledge base 𝒦 = 𝒯 ∪ 𝒜, we say that 𝒦 is (concept) materialized if 𝒦 |= 𝐴(𝑎)
implies 𝐴(𝑎) ∈ 𝒦 for each 𝐴 ∈ cons(𝒦) ∪ {⊤} and 𝑎 ∈ inds(𝒦); 𝒜 is reduced if there is no
𝒜′ ⊂ 𝒜 with {𝑟(𝑎, 𝑏) | 𝑟(𝑎, 𝑏) ∈ 𝒜} ⊂ 𝒜′ such that 𝒜′ ∪ {𝐵(𝑎) | 𝐴(𝑎) ∈ 𝒜 and 𝒦 |= 𝐴 ⊑
𝐵, 𝐴, 𝐵 ∈ cons(𝒦)} is materialized, i.e., a reduced ABox is materialized with the most specific
atomic concepts.
   An 𝒜ℒ𝒞 knowledge base 𝒦 = 𝒯 ∪ 𝒜 is Horn and in normalized form if 𝐶 ∈ NC for every
𝐶(𝑎) ∈ 𝒦, and every 𝐶 ⊑ 𝐷 ∈ 𝒦 is in one of the forms ⊤ ⊑ 𝐴, 𝐴 ⊑ 𝐵, 𝐴 ⊑ ⊥, 𝐴 ⊓ 𝐵 ⊑
𝐴′ , ∃𝑟.𝐴 ⊑ 𝐵, 𝐴 ⊑ ∃𝑟.𝐵, 𝐴 ⊑ ∀𝑟.𝐵, where 𝐴, 𝐴′ , 𝐵 ∈ NC and 𝑟 ∈ NR . We use 𝒦∃ to
denote the set {∃𝑟.𝐵 | 𝐴 ⊑ ∃𝑟.𝐵 ∈ 𝒯 } and 𝒦∀ to denote {∀𝑟.𝐵 | 𝐴 ⊑ ∀𝑟.𝐵 ∈ 𝒯 }. W.l.o.g.,
we assume in the remainder that Horn 𝒜ℒ𝒞 knowledge bases are normalized by applying a
structural transformation (see e.g. [5]) and that the ABox is reduced.
   Each consistent Horn 𝒜ℒ𝒞 knowledge base 𝒦 has a so-called universal model 𝒰 which is
minimal and unique, and contains all the implied facts. In particular, the universal model has
a tree-like form of role-connected (anonymous) individuals with named individuals as roots
where individuals are only made equal if it is necessarily entailed by the knowledge base. For
query answering, it suffices to consider this universal model [3].

2.2. Concept Referring Expressions
Principally, referring expressions serve the purpose of uniquely identifying an object in a certain
context through its properties, that also include relations to other objects [6]. In DLs, this can
be realized by a conjunction of concepts with relations modeled as existential restrictions over
inverse roles, which relate an anonymous individual to a named one (expressed as nominal):
Definition 1. Let 𝒦 be a normalized ontology, 𝐶 = 𝐴1 ⊓. . .⊓𝐴𝑛 with 𝐴𝑖 ∈ cons(𝒦), 𝑟 ∈ rols(𝒦),
and 𝑎 ∈ inds(𝒦), then a concept referring expression 𝐸 is defined as
                              𝐸 ::= {𝑎}       𝐸 ::= 𝐶 ⊓ ∃𝑟− .(𝐸)
and we call 𝑎 the base individual of 𝐸.
  The reason for describing referring expressions this way lies in the tree model property of
DLs, which allows us to identify an anonymous object in terms of a named individual (the base
individual) and the (inverse) role path that connects the former to the latter [3]. Consider the
example taken from Toman and Weddell [3]:
Example 1. Let 𝒦 = 𝒯 ∪ 𝒜 consist of 𝒯 = {𝐴 ⊑ ∃𝑟.𝐶, 𝐴 ⊑ ∃𝑟.𝐷, 𝐴 ⊑ ∀𝑟.𝐵} and
𝒜 = {𝐴(𝑎)}, with the three (tree) models of 𝒦:

                      𝐴 𝑎                           𝐴 𝑎                    𝐴 𝑎
                     𝑟 𝑟 𝑟                          𝑟 𝑟                     𝑟
               𝐵, 𝐶 𝐵, 𝐶 𝐵, 𝐷                   𝐵, 𝐶    𝐵, 𝐷              𝐵, 𝐶, 𝐷

   The model in the middle is the universal model as it can be embedded into any other model of 𝒦.
When we consider the generalized instance query for the concept 𝐵, the universal model makes
it reasonable to consider the 𝑟-successor of 𝑎 labeled 𝐶 and the 𝑟-successor of 𝑎 labeled 𝐷 as
singular certain answers to the query. We can describe these answers as the CREs 𝐶 ⊓ ∃𝑟− .{𝑎}
and 𝐷 ⊓ ∃𝑟− .{𝑎}, respectively. Note that we use an 𝒜ℒ𝒞ℐ𝒪 concept to describe the CRE, whereas
𝒦 is in Horn 𝒜ℒ𝒞.
 For a CRE to qualify as an answer to a generalized instance query, we impose some require-
ments, following the definition of Toman and Weddell [3] for singularity and certainty:
Definition 2. A generalized instance query is an atomic concept 𝑄 ∈ NC . A set ans(𝑄) of CREs
is an answer to 𝑄 over a consistent ontology 𝒦 if, for each 𝐸, 𝐸 ′ ∈ ans(𝑄),
certainty 𝒦 |= 𝐸 ⊑ 𝑄 and |𝐸 ℐ | > 0 for all models ℐ of 𝒦,

singularity |𝐸 𝒰 | = 1 in the universal model 𝒰 of 𝒦, and

uniqueness 𝐸 𝒰 ̸= 𝐸 ′ 𝒰 in the universal model 𝒰 of 𝒦

completeness for every CRE 𝐹 with 𝒦 |= 𝐹 ⊑ 𝑄 there exists some 𝐸 ∈ ans(𝑄) s.t. 𝐸 ≡ 𝐹 .

   Here, the additional uniqueness property ensures that we do not obtain any duplicate answers,
since we are only interested in the individual (semantically) represented by some CRE rather
than the actual (syntactic) form of the latter. Besides, note that the above definition of singularity
is a weakening of the property defined by Borgida et al. [2], where a CRE was required to denote
a singleton set in all models of the knowledge base. This weakening, however, is essential in
DLs that do not support counting (e.g., through number restrictions or functional roles) such as
𝒜ℒ𝒞ℐ𝒪. Note also that unreachable objects cannot be certain answers. Furthermore, a complex
concept may still be considered as query if it can be represented by means of a new atomic
concept and additional appropriate axioms in the ontology, like ⊤ ⊑ 𝐴, for instance.

Example 2 (Ex. 1 cont.). Consider again the knowledge base 𝒦 of Example 1. Formally, the
set {𝐶 ⊓ ∃𝑟− .{𝑎}, 𝐷 ⊓ ∃𝑟− .{𝑎}} is an answer to the generalized instance query 𝐵 as both
concept expressions are singular certain answers that identify different anonymous individuals.
The CRE ∃𝑟− .{𝑎} does not satisfy the singularity requirement and the CRE 𝐶 ⊓ 𝐷 ⊓ ∃𝑟− .{𝑎}
violates the certainty requirement. Note that if we were to add 𝐶 ≡ 𝐷 to 𝒯 , the universal
model would be the right-most model of Example 1. In addition to the two CREs from above, also
𝐶 ⊓ 𝐷 ⊓ ∃𝑟− .{𝑎} becomes a certain singular answer. All three CREs, however, identify the same
anonymous individual in the universal model (in different syntactic variants) and our proposed
uniqueness criterion requires that ans(𝑄) consists of only one of them.


3. Answering Generalized Instance Queries
We propose an algorithm for computing CREs for a generalized instance query given by an
atomic concept 𝑄 over a (normalized) Horn 𝒜ℒ𝒞 ontology 𝒦 = 𝒯 ∪ 𝒜 with reduced ABox 𝒜.
An important aspect of the algorithm is that it employs an OWL reasoner as a black box as only
standard reasoning tasks (e.g., as foreseen in the OWL API [7]) are required and the concrete
approach being applied to answer generalized instance queries is not known to the reasoner.
For example, we retrieve super-concepts of a concept or the most specific concepts (w.r.t. to the
subsumption hierarchy) that an individual is an instance of (corresponding to those concepts in
a reduced ABox). This provides great flexibility concerning the choice of the applied reasoner
and allows for using optimized strategies for different ontologies.
   To construct CREs serving as answers for 𝑄 we start with a CRE 𝐸 = {𝑎} for each 𝑎 ∈ inds(𝒦)
and a corresponding current concept 𝐶𝑎 = 𝐴1 ⊓ . . . ⊓ 𝐴𝑛 using every 𝐴𝑖 (𝑎) ∈ 𝒜. We then look
for suitable existential restrictions ∃𝑟.𝐷 which satisfy 𝒦 |= 𝐶𝑎 ⊑ ∃𝑟.𝐷 and, thus, allow us to
extend the current CRE to 𝐸 ′ = 𝐷 ⊓ ∃𝑟− .(𝐸). This procedure is repeated and each time the
newly related 𝐷 is chosen as next current concept until no more appropriate restrictions can be
found to further extend the generated CREs. Here, a current concept 𝐶 does not just enable us
Algorithm 1 Answering generalized instance queries
 procedure GeneralizedInstanceQuery(𝒦, 𝑄)
    input: 𝒦 = 𝒯 ∪ 𝒜: an ontology, 𝑄: a generalized instance query
    output: ans(𝑄)
 1: ans ← ∅
 2: for all 𝑎 ∈ inds(𝒦) do
            d
 3: 𝐶𝑎 ← 𝐴(𝑎)∈𝒜 𝐴
 4: ans ← ans ∪ getCREs(𝒦, 𝑄, 𝐶𝑎 , {𝑎}, ∅)
 5: return ans


to further expand a CRE, but moreover serves as an indicator if the latter represents an answer
for the query 𝑄, which is the case if 𝒦 |= 𝐶 ⊑ 𝑄 as shown later in Lemma 1.

Initialization: Algorithm 1 describes the main algorithm that constructs, for each individual
𝑎 occurring in the knowledge base, the initial current concept and then calls the algorithm to
generate CREs w.r.t. this (base) individual.

Constructing Concept Referring Expressions: Algorithm 2 uses five steps to construct
CREs for a given base individual that serve as answers for the considered query:
   Step 1: At first, in Line 2, we look for suitable existential restrictions ∃𝑟.𝐵 that allow us to
relate the current concept 𝐶 to the concept 𝐵 in order to establish a link to a new anonymous
individual, thus requiring 𝒦 |= 𝐶 ⊑ ∃𝑟.𝐵. Since we are interested in producing singular CREs,
a restriction ∃𝑟.𝐵 should only be considered if there is no ∃𝑟.𝐴 (using the same role 𝑟) such
that 𝒦 |= 𝐴 ⊑ 𝐵. We capture this by introducing reduced (sets of) existential restrictions:

Definition 3 (Reduced Existential Restrictions). Let 𝒦 be a normalized Horn 𝒜ℒ𝒞 ontology
and 𝐶 a concept, then 𝒦∃ (𝐶) = {∃𝑟.𝐵 | 𝒦 |= 𝐶 ⊑ ∃𝑟.𝐵, 𝐵 ∈ NC , 𝑟 ∈ NR }. We denote with
𝒦∃min (𝐶) a smallest subset of 𝒦∃ (𝐶) such that, for each ∃𝑟.𝐵 ∈ 𝒦∃ (𝐶) ∖ 𝒦∃min (𝐶), there is some
∃𝑟.𝐴 ∈ 𝒦∃min (𝐶) s.t. 𝒦 |= 𝐴 ⊑ 𝐵.

   Note that an instance of ∃𝑟.𝐵 ∈ 𝒦∃ (𝐶) ∖ 𝒦∃min (𝐶) is connected to more than one instance
of 𝐵, which means that a CRE using this existential restriction is non-singular as it represents
more than one individual. Moreover, if there are two candidates ∃𝑟.𝐴, ∃𝑟.𝐵 ∈ 𝒦∃ (𝐶) such that
𝒦 |= 𝐴 ≡ 𝐵, only one of them should be chosen in order to prevent duplicate answers.
   Step 2: For each selected existential restriction that induces a successor for an instance of the
current concept 𝐶, we next consider universal restrictions that further specify these successors
(see Lines 4–5) and we add these concepts to the set of successor concepts for the role in the
sc relation. After this step, each (𝑟, 𝑆) ∈ sc is such that 𝒦 |= 𝐶 ⊑ ∃𝑟.(𝐵1 ⊓ . . . ⊓ 𝐵𝑛 ) for
𝑆 = {𝐵1 , . . . , 𝐵𝑛 }.
   Step 3: In this step of the algorithm, we determine those existential restrictions that can
actually be applied to further construct CREs leading to singular, unique answers of the query
and collect them in the set next. If we encounter            d 𝑆) ∈ sc for which we already have
                                                 d an entry (𝑟,
another entry (𝑟, 𝑆 ′ ) ∈ next such that 𝒦 |= 𝐵∈𝑆 𝐵 ≡ 𝐵 ′ ∈𝑆 ′ 𝐵 ′ , we do not consider (𝑟, 𝑆)
Algorithm 2 Computing CREs for a base individual
 procedure getCREs(𝒦, 𝑄, 𝐶, 𝐸, used)
    input: 𝒦 = 𝒯 ∪ 𝒜: an ontology, 𝑄: a query, 𝐶: the current concept, 𝐸: the current CRE,
    used: a set of already applied existential restrictions
    output: CREs from ans(𝑄) that build upon 𝐸
 1: // Step 1: find suitable existential restrictions
 2: sc ← {(𝑟, {𝐵}) | ∃𝑟.𝐵 ∈ 𝒦∃      min (𝐶)}

 3: // Step 2: find related universal restrictions
 4: for all (𝑟, 𝑆) ∈ sc do
 5: 𝑆 ← 𝑆 ∪ {𝐵 | ∀𝑟.𝐵 ∈ 𝒦∀ and 𝒦 |= 𝐶 ⊑ ∀𝑟.𝐵}
 6: // Step 3: filter found existential restrictions
 7: next ← ∅
 8: for all (𝑟, 𝑆) ∈ sc do
 9: // check for potential duplicates
10: sc′ ← {(𝑟, 𝑆 ′ ) ∈ next | 𝒦 |= 𝐵∈𝑆 𝐵 ≡ 𝐵 ′ ∈𝑆 ′ 𝐵 ′ }
                                       d             d
11: if sc′ = ∅ then
12:    if 𝐸 = {𝑎} then
13:      if {𝑏 | 𝑟(𝑎, 𝑏) ∈ 𝒜, ∀𝐵 ∈ 𝑆 : 𝒦 |= 𝐵(𝑏)} = ∅ then
14:        next ← next ∪ {(𝑟, 𝑆)}
15:    else
16:      // look for cycle in current CRE
17:      if (𝑟, 𝑆) ∈ used then
18:        𝐸 ← markCycle(𝐸, 𝑟, 𝑆)
19:      else
20:        next ← next ∪ {(𝑟, 𝑆)}
21: // Step 4: check if current CRE is an answer
22: ans ← ∅
23: if 𝒦 |= 𝐶 ⊑ 𝑄 then
24: ans ← ans ∪ {𝐸}
25: // Step 5: extend CRE recursively
26: for all (𝑟, 𝑆) ∈ next do
27: 𝐶 ′ ← 𝐵∈𝑆 𝐵
              d
28: 𝐸 ′ ← 𝐶 ′ ⊓ ∃𝑟 − .(𝐸)
29: ans ← ans ∪ getCREs(𝒦, 𝑄, 𝐶 ′ , 𝐸 ′ , used ∪ {(𝑟, 𝑆)})
30: return ans


any further to prevent duplicate answers, i.e., if the check in Line 11 fails, the entry (𝑟, 𝑆) is
not added to the set next. Even though we already consider only the reduced set of existential
restrictions in Step 1, this check is still necessary. Consider, for example, that 𝒦 |= 𝐶 ⊑ ∃𝑟.𝐴
and 𝒦 |= 𝐶 ⊑ ∃𝑟.𝐵 for the current concept 𝐶 and 𝒦 ̸|= 𝐴 ≡ 𝐵. Hence, we have two entries
(𝑟, {𝐴}) and (𝑟, {𝐵}) ∈ sc. Assume, furthermore, that 𝒦 |= 𝐶 ⊑ ∀𝑟.𝐴 and 𝒦 |= 𝐶 ⊑ ∀𝑟.𝐵.
This means, however, that for both (𝑟, {𝐴}), (𝑟, {𝐵}) ∈ sc, we have 𝒦 |= 𝐶 ⊑ ∃𝑟.(𝐴 ⊓ 𝐵).
   To guarantee the uniqueness property, an existential restriction should also be ignored for
the initial extension of a CRE only consisting of a nominal {𝑎} if the existential restriction is
already satisfied through a (named) individual 𝑏. This situation is handled in Line 13. Note that
due to the tree model property this situation can only occur for the initial CREs.
   For cyclic knowledge bases, it may be the case that for two, possibly equal, current concepts 𝐶
and 𝐶 ′ that occur during the algorithm processing, the same existential restriction is applicable.
This may lead to an arbitrarily long repetition of the same sequence of existential restrictions
that originally led from 𝐶 to 𝐶 ′ , hence, giving rise to an infinitely large number of possible CREs
(of increasing length). Analogous to blocking in tableau algorithms [4], we ensure termination
of the algorithm by detecting such cycles and by preventing the reuse of an already processed
existential restriction. Instead, we compactly represent such CREs using a cycle notation in
form of surrounding square brackets "[...]+ " to mark the sequence that may occur several times
repeatedly (indicated by a call to the procedure markCycle in Line 18). For an example, consider
𝒦 = 𝒯 ∪ 𝒜 with 𝒯 = {𝐴 ⊑ ∃𝑟.𝐴} and 𝒜 = {𝐴(𝑎)}, where [𝐴 ⊓ ∃𝑟− .(]+ {𝑎}) is an answer
for the generalized instance query 𝐴 and serves as single representative for the infinitely many
CREs of the form 𝐴 ⊓ ∃𝑟− .(𝐴 ⊓ ∃𝑟− .(...{𝑎}).
   Step 4: In this step, we check if the current CRE already represents an answer for the query
𝑄. For a standard instance query, this would usually require to check 𝒦 |= 𝑄(𝑎) for a named
individual 𝑎, but since we are considering anonymous individuals represented by some CRE 𝐸,
we want to know whether 𝒦 |= 𝐸 ⊑ 𝑄. This is actually realized by checking 𝒦 |= 𝐶 ⊑ 𝑄 in
Line 23 for the related current concept 𝐶 based on the following lemma.

Lemma 1. Given a Horn 𝒜ℒ𝒞 ontology 𝒦, a generalized instance query 𝑄, a CRE 𝐸 and its
associated (Horn 𝒜ℒ𝒞) current concept 𝐶, where 𝐶 = 𝐴1 ⊓ . . . ⊓ 𝐴𝑛 using every 𝐴𝑖 (𝑎) ∈ 𝒜 if
𝐸 = {𝑎}, or 𝐶 = 𝐷 if 𝐸 = 𝐷 ⊓ ∃𝑟− .(...), then 𝒦 |= 𝐸 ⊑ 𝑄 ⇔ 𝒦 |= 𝐶 ⊑ 𝑄.

Proof sketch. (⇒) 𝒦 |= 𝐶 ⊑ 𝑄 requires that 𝐶 is at least as specific as 𝑄. Therefore, we
show that the current concept 𝐶 is actually the most specific (Horn 𝒜ℒ𝒞) concept such that
𝒦 |= 𝐸 ⊑ 𝐶 and that for any other most specific candidate 𝐷 with 𝒦 |= 𝐸 ⊑ 𝐷, we have
𝒦 |= 𝐶 ≡ 𝐷, which is mainly based on the fact that we only work with reduced existential
restrictions (see Algorithm 2, Line 2 and Definition 3).
(⇐) Per definition, a current concept 𝐶 of some CRE 𝐸 always satisfies 𝒦 |= 𝐸 ⊑ 𝐶.

   Step 5: Even if an answer has been identified, the processing of the CRE does still proceed,
because it may be possible that the continuing construction leads to another answer later on.
Therefore, the algorithm is eventually called recursively using appropriately updated arguments,
like an extended CRE 𝐸 ′ and the new current concept 𝐶 ′ .

3.1. Properties
In the following, we discuss why the described algorithm works properly in the way that
for a generalized instance query, only certain, singular, and unique answers are produced
w.r.t. Definition 2. Additionally, we show that the algorithm returns every such answer and,
furthermore, always terminates. Due to space limitations, we mainly provide proof sketches,
while more details are given in an online appendix.1

Certainty. In Line 23 of Algorithm 2, a CRE 𝐸 is selected as answer if 𝒦 |= 𝐶 ⊑ 𝑄, which
implies 𝒦 |= 𝐸 ⊑ 𝑄 according to Lemma 1. In addition, a CRE basically describes a chain of
linked individuals where the existence of one individual ensures the presence of the next one
being referenced through an existential restriction. Since we start with an explicitly present
individual as base for 𝐸, there is always at least one element in 𝐸 ℐ for each model ℐ.

Singularity. For an initial CRE 𝐸 = {𝑎}, we directly get |𝐸 𝒰 | = 1 for the universal model
𝒰. In the more general case 𝐸 = 𝐶 ⊓ ∃𝑟− .(𝐸 ′ ) with 𝐸 ′ as the (recursive) part leading to the
base individual, we show that the non-singular situation |𝐸 𝒰 | > 1 is never achieved: This
would require that there is some part 𝐶 ′ ⊓ ∃𝑟′− .(𝐸 ′′ ) in 𝐸 where one individual from 𝐸 ′′𝒰
has 𝑟′ -relations to (at least) two different individuals in 𝐶 ′𝒰 . The necessary conditions for this
are described in Lemma 2 below (with 𝐶 ′ as 𝐷), but since the algorithm only selects reduced
existential restrictions w.r.t. Definition 3, i.e., some ∃𝑟.𝐵 is only chosen if there is no candidate
∃𝑟.𝐴 with 𝒦 |= 𝐴 ⊑ 𝐵, this situation never occurs.

Lemma 2. Let 𝒦 be a Horn 𝒜ℒ𝒞 ontology, 𝒰 the universal model of 𝒦, and assume that
⟨𝑐, 𝑎⟩, ⟨𝑐, 𝑏⟩ ∈ 𝑟𝒰 for some role 𝑟, and (anonymous individuals) 𝑎, 𝑏 ∈ 𝐷𝒰 for some concept
𝐷. We have 𝑎 ̸= 𝑏 iff there exist some concepts 𝐴, 𝐵, 𝐶 such that 𝑐 ∈ 𝐶 𝒰 , 𝒦 |= 𝐶 ⊑ ∃𝑟.𝐴,
𝒦 |= 𝐶 ⊑ ∃𝑟.𝐵, 𝒦 |= 𝐴 ⊑ 𝐷, 𝒦 |= 𝐵 ⊑ 𝐷, and 𝒦 ̸|= 𝐴 ≡ 𝐵.

Proof sketch. This basically follows from the characteristics of the universal model 𝒰.

Uniqueness. Considering the tree-like universal model 𝒰, having two different CREs 𝐸, 𝐸 ′
with 𝐸 𝒰 = 𝐸 ′𝒰 means that i) they both describe the same path in the tree using different
concepts or ii) one refers to a sub-path of the other leading to the same anonymous individual:
i) Because an edge in a tree path relates to some ∃𝑟.𝐵, 𝐸 ′ might describe the same path as
𝐸 if it uses some ∃𝑟.𝐵 ′ with 𝐵 ⊑ 𝐵 ′ (including 𝐵 ≡ 𝐵 ′ ) for the associated edge instead.
In Algorithm 2, this is prevented in Lines 2 and 11. ii) Assuming that 𝑎 and 𝑎′ are the base
individuals of 𝐸 and 𝐸 ′ , respectively, there must be some 𝑟(𝑎, 𝑎′ ) ∈ 𝒜 such that 𝐸 ′ refers to a
sub-path of 𝐸. If 𝑎′𝒰 ∈ 𝐵 𝒰 for some 𝐵, some ∃𝑟.𝐵 would describe the same edge as 𝑟(𝑎, 𝑎′ ),
given that 𝑎𝒰 ∈ (∃𝑟.𝐵)𝒰 , which is why such existential restrictions are not chosen (Line 13).

Completeness. It is not required to construct every possible CRE that represents an answer
for the stated query, but rather to find one unique, singular CRE for every, possibly anonymous,
individual that serves as an answer. For that, we assume there may exist some CRE 𝐸 describing
a correct, singular and unique answer, but which cannot be constructed by the algorithm and
prove that this is not possible: Since the considered 𝐸 is not generated by the algorithm, it
must possess a unique subpart that does not occur in any of the constructed answers. As
we already consider all individuals during the initialization, this part must be of the form
"𝐶 ′ ⊓ ∃𝑟− .(𝐶 ⊓ . . .)", where the existential restriction ∃𝑟.𝐶 ′ was applied for the concept 𝐶. By

1
    https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2022/IlGl22a_appendix.pdf
considering all the cases in the algorithm where 𝐶 is not used as current concept or ∃𝑟.𝐶 ′ is
not selected (or constructed), respectively, we can see that either the certainty, singularity or
uniqueness property would be violated by regarding 𝐸 as an answer. Besides, the employed
cycle notation may be seen as a compromise to implicitly return a possibly infinite number of
CREs in form of just one compact instance in order to ensure the termination of the algorithm.

Termination. As the given ontology always consists of a finite number of axioms and concepts,
all the applied search and iteration processes come to a halt. Therefore, non-termination may
only be realized by the repeated usage of an existential restriction during a recursive call, which,
however, is prevented by the cycle detection in Line 17 of Algorithm 2.


4. Implementation and Evaluation
A prototypical Java implementation of our algorithm is available online on GitHub2 and also
includes some optimizations. One of them refers to the ordering of existential and universal
restrictions by means of separate subsumption hierarchies. This allows us to reduce the number
of performed subsumption tests in the way that if, for example, 𝒦 ̸|= 𝐶 ⊑ ∃𝑟.𝐵, we do not
need to further check 𝒦 |= 𝐶 ⊑ ∃𝑟′ .𝐴 for any ∃𝑟′ .𝐴 that is below ∃𝑟.𝐵 in the hierarchy,
i.e., for which 𝒦 |= ∃𝑟′ .𝐴 ⊑ ∃𝑟.𝐵. Usually, reasoners are only concerned with computing
subsumption hierarchies for atomic concepts, referred to as classification (see e.g. [4]). Therefore,
we introduce a new atomic concept for each existential (or universal) restriction such that the
reasoner can (internally) compute the hierarchies for those new atomic concepts, based on
which the actual hierarchies for existential (or universal) restrictions can then be derived. Due
to the associated additional overhead, we also implemented the (explicit) Enhanced Traversal
Method [8] to efficiently deal with smaller number of elements.
   Another improvement is achieved by combining base individuals into one set if they share an
equivalent initial current concept and furthermore possess analogous given role assertions. Since
these properties result in the same computations for each individual, we can avoid unnecessary
repetitions by calling the algorithm only once for such a combined set and just generate different
versions of the constructed CRE for each base individual in the end.
   For a general performance assessment, the implementation was tested on different ontologies
listed in Table 1 with codinteraction-A and the separate ore_ont_2608/4516/3313 being part of
the ORE 2015 Reasoner Competition Corpus [9], while HAO (v2021-03-05), VO (v1.1.171) and
DTO (v1.1.1) were taken from BioPortal3 . If necessary, axioms not adhering to Horn 𝒜ℒ𝒞 were
removed and ontologies merged with their imports to obtain one complete ontology.
   Tests showed that subsumption checking has a huge influence on the performance, which
is why we considered two different reasoners, namely HermiT4 (v1.3.8) and JFact5 (v5.0.3). In
general, HermiT achieved better runtime results than JFact, except for the larger ontologies VO
and DTO, where JFact was faster in determining the earlier mentioned subsumption hierarchies.

2
  https://github.com/M-Illich/Computing-CREs.git
3
  https://bioportal.bioontology.org/ontologies
4
  http://www.hermit-reasoner.com/
5
  http://jfact.sourceforge.net/
Table 1
Overview of adapted ontologies with their number of atomic concepts (#con), individuals (#ind), com-
bined individual sets (#sets), considered existential/universal restrictions (#∃/#∀), average runtime in
ms for ⊤ as query, number of answers (#ans) and their percentage distribution w.r.t. their depth, i.e.,
number of contained inverse existential restrictions (* no subsumption hierarchies)
Ontology              #con #ind #sets        #∃ #∀ Runtime #ans          depth (%)
                                                      [ms]          0 1 2-4 5-7 8-10 11-12
codinteraction-A          6    21     13     3   0       71    30 70 30   -   -    -     -
ore_ont_2608            453 212      212    10 10       265 279 76 24     -   -    -     -
ore_ont_4516            509 217      217    10 10       185 284 76 24     -   -    -     -
ore_ont_3313            865 2,070    858 114     0   57,966 9,734 21 8 34 27       9     1
HAO                   2,548 2,764    687 522     1   37,965 2,764 100 -   -   -    -     -
VO                    6,828 167        4 1,513 237    460* 176 95 5       -   -    -     -
DTO                  10,075     3      1 7,958 114    738*      3 100 -   -   -    -     -


Since both VO and DTO, however, possess many existential restrictions but only few individuals
(especially in form of combined sets), the performance was actually best if no subsumption
hierarchies are computed. Table 1 shows the obtained runtime measurements (average of five
runs) for computing all CREs, i.e., using ⊤ as query, with HermiT as reasoner, based on an AMD
Ryzen 7 3700X 3.59 GHz processor with 16 GB RAM on Windows 10 (64-Bit).


5. Related Work
Krahmer and van Deemter [6] provide a survey on referring expressions and their computa-
tional generation, given by a historic overview of research developments. Here, the problem
of generating referring expressions is defined as finding a description in form of combined
properties that uniquely identify a given individual in a certain context, which differs from
our work in that we intend to describe unknown, anonymous individuals rather than explicitly
named ones.
   A related approach that works with DL is provided by Areces et al. [1] introducing an
algorithm that takes as input a model ℳ and tries to find formulas (concepts) that represent
the individuals in ℳ. The basic idea here is that, starting with ⊤ as formula for which the
interpretation contains every domain element, new formulas are created by successively refining
the already given ones through appending new conjuncts with the intention to reduce the
number of elements in the formulas’ interpretations. At first, only atomic concepts are added as
conjuncts, before existential restrictions relating to already computed formulas are considered
until the formulas’ interpretations are singular or no further adaptations are possible.
   Unlike in our work, the individuals to be described are already stated and the occurrence
of cycles in referring expressions is not considered. However, both approaches make use of
relations between individuals, but with the distinction that Areces et al. start from the individual
𝑎 described by the referring expression and go to another one 𝑏, while we utilize the inverse
case where another (present) individual 𝑏 refers to 𝑎, the (anonymous) one being described.
   The work that comes closest to ours is given by Toman and Weddell [3] dealing with (gen-
eralized) instance retrieval queries on (Horn 𝒜ℒ𝒞) ontologies, based on a tree automaton for
which a state 𝑆 is given by a set of atomic concepts, while transitions are defined by so-called
matching tuples (𝑆, 𝑆0 , ..., 𝑆𝑘 ) stating that some 𝑆𝑖 with 0 ⩽ 𝑖 ⩽ 𝑘 can be reached when
in the current state 𝑆 a certain existential restriction ∃𝑟𝑖 .𝐶𝑖 is applied. Starting with a set
𝑆𝑎 = {𝐴 | 𝐴(𝑎) ∈ 𝒜} for some individual 𝑎, a tree can be unfolded using those matching
tuples. In order to answer a query  d 𝐵, this tree is traversed beginning with some 𝑆𝑎 until a
state 𝑆𝑘 is reached where 𝒦 |= 𝐴∈𝑆𝑘 𝐴 ⊑ 𝐵, for which the sequence 𝑟1 𝐴1 ...𝑟𝑘 𝐴𝑘 (called
certain path) referring to the applied existential restrictions is then transformed into a CRE
𝐴𝑘 ⊓ ∃𝑟𝑘− .(... 𝐴1 ⊓ ∃𝑟1− .{𝑎}) serving as answer for 𝐵.
   Like in our algorithm, the tree automaton starts the construction of CREs with a given
individual and also takes care of occurring cycles. Furthermore, both approaches only use
minimal existential restrictions to ensure singularity, although the definitions for minimality are
different: While Toman and Weddell rely on the general subsumption of the whole restriction
∃𝑟.𝐶, we consider subsumption for the inner concept 𝐶 instead w.r.t. Definition 3, because only
then singularity can be guaranteed (based on Lemma 2). In this respect, the tree automaton
approach does not fulfill the completeness property due to only working with the most specific
existential restrictions, even though some other ones might lead to singular CREs, too, as
illustrated in Example 3 below. Besides, we are only interested in producing unique CREs, which
is not explicitly handled by Toman and Weddell.
Example 3. Let 𝒦 = 𝒯 ∪ 𝒜 consist of 𝒜 = {𝐴(𝑎)} and 𝒯 = {𝐴 ⊑ ∃𝑟.𝐶, ∃𝑟.𝐶 ⊑
𝐵, 𝐵 ⊑ ∃𝑟.𝐷, 𝐶 ⊑ 𝑄, 𝐷 ⊑ 𝑄}. For the generalized instance query 𝑄, we get ans(𝑄) =
{𝐶 ⊓ ∃𝑟− .{𝑎}, 𝐷 ⊓ ∃𝑟− .{𝑎}}, even though ∃𝑟.𝐷 is not minimal w.r.t. subsumption due to
𝒦 |= ∃𝑟.𝐶 ⊑ ∃𝑟.𝐷.


6. Conclusion
We presented an algorithm that generates concept referring expressions to identify both named
and anonymous individuals serving as certain, singular and unique answers for an instance
retrieval query on a Horn 𝒜ℒ𝒞 ontology. For that, we start with a named individual and
recursively determine appropriate existential restrictions to create a chain of relations that
defines an implicitly given individual based on its connection to an explicit one. A crucial factor
here is the selection based on reduced existential restrictions (cf. Definition 3), enabling us
to construct every desired singular CRE. Besides, the black box consideration of the applied
reasoner provides more flexibility in choosing optimal reasoning approaches for different
situations.

Future Research. In general, the question which reasoner should be selected for the consid-
ered ontologies is not an easy one and requires further investigations. On the other side, there
may be some advantages of directly integrating the algorithm into a particular reasoner as the
algorithm can then utilize the reasoner’s internal data structures and be optimized accordingly.
Moreover, it may be of interest to consider extensions of Horn 𝒜ℒ𝒞, too. While some features
might be already supported with none or only small adaptations in the algorithm, others prob-
ably require more examination, especially since we might lose the existence of the tree-like
universal model and thus can no longer make use of our original singularity definition.
References
[1] C. Areces, A. Koller, K. Striegnitz, Referring Expressions as Formulas of Description Logic,
    in: Proceedings of the Fifth International Natural Language Generation Conference, 2008,
    pp. 42–49. doi:https://doi.org/10.3115/1708322.1708332.
[2] A. Borgida, D. Toman, G. Weddell, On Referring Expressions in Query Answering over First
    Order Knowledge Bases, in: Proceedings of the 15th International Conference on Principles
    of Knowledge Representation and Reasoning (KR’16), AAAI Press, 2016, pp. 319–328. URL:
    https://www.aaai.org/ocs/index.php/KR/KR16/paper/viewFile/12860/12488.
[3] D. Toman, G. Weddell, Finding ALL Answers to OBDA Queries Using Referring Expressions,
    in: AI 2019: Advances in Artificial Intelligence, Springer International Publishing, Cham,
    2019, pp. 117–129. doi:https://doi.org/10.1007/978-3-030-35288-2_10.
[4] F. Baader, D. Calvanese, D. McGuinness, P. Patel-Schneider, D. Nardi, et al., The Description
    Logic Handbook: Theory, implementation and applications, Cambridge University Press,
    2003.
[5] Y. Kazakov, Consequence-Driven Reasoning for Horn 𝒮ℋℐ𝒬 Ontologies, in: Proc. of
    the 21st Int. Joint Conf. on Artificial Intelligence, IJCAI 2009, 2009, pp. 2040–2045. URL:
    https://www.ijcai.org/Proceedings/09/Papers/336.pdf.
[6] E. Krahmer, K. van Deemter, Computational Generation of Referring Expressions: A Survey,
    Computational Linguistics 38 (2012) 173–218. doi:https://doi.org/10.1162/COLI_
    a_00088.
[7] M. Horridge, S. Bechhofer, The OWL API: A Java API for OWL ontologies, Semant. Web 2
    (2011) 11–21. doi:https://doi.org/10.3233/SW-2011-0025.
[8] F. Baader, B. Hollunder, B. Nebel, H.-J. Profitlich, E. Franconi, An Empirical Analysis of
    Optimization Techniques for Terminological Representation Systems, Applied Intelligence
    4 (1994) 109–132. doi:https://doi.org/10.22028/D291-24994.
[9] N. Matentzoglu, B. Parsia, ORE 2015 Reasoner Competition Corpus, 2015. URL: https:
    //doi.org/10.5281/zenodo.18578. doi:10.5281/zenodo.18578.