The EL subsumption hierarchy consists of all EL concept descriptions and is partially ordered by subsumption. In order to navigate within this hierarchy, one can go up to subsumers and down to subsumees. We analyze how smallest steps can be made. Specifically, we show how all upper neighbors as well as all lower neighbors of a given EL concept description can be eficiently computed, where two concepts are neighbors if one subsumes the other and there is no third concept in between. We further show that the hierarchy contains very long chains: there is a sequence of concepts Cn with size linear in n such that each chain of neighbors from ⊤ to Cn has at least n-fold exponential length. As applications, we provide a template for determining upper complexity bounds for deciding whether a concept is maximally general or maximally specific w.r.t. a property, we construct a metric on the set of all EL concept descriptions, we introduce a similarity measure that fulfills the triangle inequality, and we conclude that an uninformed search for a target concept by subsequently computing neighbors or, equivalently, along an ideal refinement operator is not feasible in practical applications.
The EL subsumption hierarchy consists of all EL concept descriptions and is partially ordered by subsumption. In order to navigate within this hierarchy, one can go up to subsumers and down to subsumees. We analyze how smallest steps can be made. Specifically, we show how all upper neighbors as well as all lower neighbors of a given EL concept description can be eficiently computed, where two concepts are neighbors if one subsumes the other and there is no third concept in between. The complexity for both computation tasks is determined: while all upper neighbors can be computed in polynomial time, computation of all lower neighbors needs exponential time.
Secondly, we employ a standard construction from Lattice Theory [
Thirdly, we devise some consequences and applications. We provide a
template for determining upper complexity bounds for deciding whether a concept
description is maximally specific or maximally general w.r.t. a given property.
We construct a similarity measure on EL concept descriptions that fulfills the
triangle inequality. We conclude that an uninformed search for a target concept
by subsequently computing neighbors or, equivalently, along an ideal refinement
operator is not feasible in practical applications. The latter applies, in particular,
to an approach that tries to learn a target concept [
In addition to citing and rephrasing existing results on the enumeration of
upper neighbors as well as a construction of the distance measure, this article
provides as new contributions an eficient approach to computing lower neighbors
and an asymptotic analysis of the distance measure. Specifically, a contained
result is a previously unpublished, new contribution if and only it is followed
only by a reference to [
The EL Subsumption Hierarchy. We assume basic knowledge of the description logic EL. For a signature Σ := Σ C ∪ Σ R consisting of concept names and role names, EL concept descriptions are built from Σ by means of the constructors ⊤, ⊓, and ∃, and the set of all concept descriptions is denoted as EL(Σ ). We treat (nested) conjunctions like sets, i.e., nestings, order, and repetitions are not relevant. Concept names and existential restrictions are also called atoms. Each concept C is a conjunction of atoms, the top-level conjuncts of C, and we denote the set of all these atoms as Conj(C). ⊤ is the empty conjunction. The role depth of a concept is the maximal number of nestings of existential restrictions.
Given two concept descriptions C and D, we say that C is subsumed by D,
written C ⊑∅ D, if CI ⊆ DI for each interpretation I. We use the subscript ∅ to
indicate that we consider subsumption w.r.t. the empty TBox. It is well-known
that the subsumption relation ⊑∅ is a partial order — a reflexive, transitive binary
relation — on the set EL(Σ ). Consequently, the quotient of EL(Σ ) w.r.t. the
induced equivalence relation ≡ ∅ is a partially ordered set. In what follows, we
will not distinguish between the equivalence classes and their representatives,
with the consequence that ⊑∅ becomes a partial order — a reflexive, transitive,
antisymmetric binary relation. As representatives we usually take the reduced
concepts, where a concept is reduced if none of its conjunctions contains atoms
that are comparable w.r.t. ⊑∅. According to [
Upper and Lower Neighbors. For a partially ordered set (P, ≤ ), its neighborhood relation1 consists of all pairs (p, q) where p < q and there exists no x such that p < x < q. Usually, if p ≺ q, then one calls p a lower neighbor of q and, vice versa, q is called an upper neighbor of p.2 We say that ≤ is neighborhood generated if the transitive closure ≺ + equals the irreflexive part <. Obviously, this is the case if and only if, for each pair p ≤ q, there is a finite chain of neighbors from p to q, i.e., there are elements x0, . . . , xn such that p = x0 ≺ x1 ≺ · · · ≺ xn = q.
Clearly, if the underlying set P is finite, then each partial order on P is neighborhood generated. However, there are infinite posets where this does not hold true; even worse, there are cases where ≺ and thus also ≺ + are both empty. For instance, consider the set R of real numbers with their usual ordering ≤ . It is well known that R is dense in itself, i.e., for each pair x < y, there is another real number z in between, i.e., such that x < z < y — thus, there are no neighboring real numbers. Another example of a partially ordered set that is not neighborhood generated is the set N of all natural numbers augmented with a greatest element ∞, which then does not have any neighbors.
As an alternative formulation, a partial order ≤ is not neighborhood generated if and only if there exists a pair p < q such that every finite chain 3 p = x0 < x1 < · · · < xn = q can be refined, i.e., there is some index i and an element y such that xi < y < xi+1. It follows that ≤ is neighborhood generated if ≤ is bounded, i.e., for each element p, there is a finite upper bound on the lengths of chains starting with p. Although boundedness is suficient for neighborhoodgeneratedness, it is not necessary: the following result immediately implies that each unbounded poset can be order-embedded4 into a neighborhood generated poset, which must be unbounded as well.
Proposition 1. [
Proof sketch. Let (P, ≤ ) be a poset. Firstly, we define the poset (Q, ⊑) by adding
a fresh element between each two ≤ -comparable elements of P . It is easy to see
that (Q, ⊑) must be neighborhood generated. Secondly, we can map each element
of P to itself in Q in order to obtain an order-embedding.
⊔⊓
1 While in [
This section is concerned with the questions whether the subsumption relation is
neighborhood generated and how upper and lower neighbors can be enumerated.
Definition 2. Let C and D be concept descriptions. We call C a lower neighbor
of D and D an upper neighbor5 of C, written C ≺ ∅ D and D ≻ ∅ C, respectively,
if6 C ⊏∅ D and there does not exist a concept E such that C ⊏∅ E ⊏∅ D.
Here, we only consider the empty TBox — other types of TBoxes
(cyclerestricted, acyclic, general) as well as two extensions of EL (with ⊥, with greatest
ifxed-points) are considered in [
In the proof of Proposition 3.5 in [
Next, we show how all upper and all lower neighbors of a given EL concept
description C can be computed. Recall that there is the following recursive
characterization of the subsumption relation [
Dealing with the existential restrictions is more involved. To construct an upper neighbor, we cannot simply remove an existential restriction ∃ r. D from Conj(C), since the resulting concept might be too general — according to the above characterization of ⊑∅ it holds true that ∃ r. D ⊏∅ d{ ∃ r. E | D ≺ ∅ E } and so we infer that7 the concept (C \ ∃ r. D) ⊓ d{ ∃ r. E | D ≺ ∅ E } is between C and C \ ∃ r. D. In fact, we can prove that the concept in the middle is always an upper neighbor of C and further that each upper neighbor is either of this form or of the form C \ A for some concept name A ∈ Conj(C).
Definition 4. For each reduced EL concept description C, we recursively define the set Upper(C) := { C↑G | G ∈ Conj(C) } where C↑A := C \ A and C↑∃r.D := (C \ ∃ r. D) ⊓ d{ ∃ r. E | E ∈ Upper(D) }.
Proposition 5. [15, Proposition 4], [3, Lemma 22], [16, Proposition 5.1.5]. For each reduced EL concept description C, the set Upper(C) consists of all upper neighbors of C (modulo equivalence), i.e., a concept description D is an upper neighbor of C if and only if there is some D′ ∈ Upper(C) such that D ≡ ∅ D′. 5 Alternative denotations could be “direct subsumee” and “direct subsumer.” 6 We write C ⊏∅ D to indicate that C ⊑∅ D and D ̸⊑∅ C. 7 For D ∈ Conj(C), we abbreviate by C \ D the concept description d(Conj(C) \ {D}).
The mapping G 7→ C↑G is a bijection from Conj(C) to Upper(C), cf.
Proposition 5.1.6 in [
Proposition 6. [16, Proposition 5.1.16]. Upper(C) can be computed in quadratic time (w.r.t. C), each neighbor in Upper(C) has quadratic size (w.r.t. C), Upper(C) consists of linearly many neighbors (w.r.t. C), and each two diferent neighbors in Upper(C) are not equivalent.
An immediate consequence of Proposition 6 is the following result. Proposition 7. [16, Theorem 5.1.17]. decided in polynomial time.
The neighborhood relation ≺ ∅ can be Example 8. Consider the concept C := A⊓∃ r. (B1⊓B2⊓B3). The upper neighbor induced by the first top-level conjunct A is ∃ r. (B1⊓B2⊓B3). In order to compute the upper neighbor induced by the second top-level conjunct ∃ r. (B1 ⊓ B2 ⊓ B3), we remove that atom and in its stead add the existential restrictions ∃ r. D where D ranges over all upper neighbors of B1 ⊓B2 ⊓B3 — we obtain A⊓∃ r. (B1 ⊓B2)⊓ ∃ r. (B1 ⊓ B3) ⊓ ∃ r. (B2 ⊓ B3) as the second upper neighbor of C.
It remains to investigate how lower neighbors can be obtained by adding an existential restriction. The above characterization of upper neighbors provides a first hint: a lower neighbor of a concept C can be obtained by adding an existential restriction ∃ r. D for which all ∃ r. E for all upper neighbors E of D are already present in C (in a certain sense). More specifically, we observe that C ⊓ ∃ r. D is a lower neighbor of C if and only if (L1) C ̸⊑∅ ∃ r. D and (L2) C ⊑∅ ∃ r. E for each upper neighbor E of D, since the concept C ⊓ ∃ r. D is a lower neighbor of C ⊓ d{ ∃ r. E | E ∈ Upper(D) }, cf. Proposition 5.
According to the recursive characterization of ⊑∅ and using the notation Succ(C, r) := { F | ∃ r. F ∈ Conj(C) }, the above Condition (L2) is satisfied if and only if there is a function ψ : Upper(D) → Succ(C, r) such that ψ (E) ⊑∅ E for each upper neighbor E of D. This function ψ is injective. (Assume there would be two diferent upper neighbors U and V of D such that ψ (U ) = ψ (V ). We would obtain ψ (U ) ⊑∅ U ⊓ V . Since U ⊓ V is equivalent to D, we would obtain a contradiction to the above condition (L1).)
By means of the above bijection between Conj(D) and Upper(D) we can
transform ψ to an injective function ϕ : Conj(D) → Succ(C, r) where ϕ (G) ⊑∅
D↑G for each G ∈ Conj(D). Since ϕ is injective, we can invert it and so obtain
a surjective partial mapping8 χ : Succ(C, r) →7 Conj(D) such that F ⊑∅ D↑χ (F )
for each F ∈ Dom(χ ). Since χ is surjective, we conclude that D must be the
conjunction of all atoms in Ran(χ ). Furthermore, it is not hard to prove that
F ⊓ χ (F ) is a lower neighbor of F 9 for each F ∈ Dom(χ ) and further that
F ′ ⊑∅ χ (F ) for each two diferent F, F ′ ∈ Dom(χ ). We call χ a lowering function
8 For each partial function f : A →7 B, its domain is Dom(f ) := { a | f (a) is defined }
and its range is Ran(f ) := { f (a) | a ∈ Dom(f ) }.
9 That’s why χ (F ) could be called a lowering atom of F as in [
Definition 9. Let C be a reduced EL concept description. We define the following by mutual recursion on the role depth of C. Firstly, define the set Lower(C) := { C ⊓ A | A ∈ Σ C and A ̸∈ Conj(C) }
∪ { C ⊓ ∃ r. d Ran(χ ) | r ∈ Σ R and χ is a lowering function for r } .
Secondly, a lowering function for a role name r is a partial mapping
χ : Succ(C, r) →7 EL(Σ ) such that (1) F ⊓χ (F ) ∈ Lower(F ) for each F ∈ Dom(χ ),
(2) F ′ ⊑∅ χ (F ) for each two diferent F, F ′ ∈ Dom(χ ), and (3) C ̸⊑∅ ∃ r. d Ran(χ ).
Proposition 10. [16, Corollary 5.1.13]. For each reduced EL concept C, the set
Lower(C) consists of all lower neighbors of C (modulo equivalence), i.e., a
concept D is a lower neighbor of C if and only if D ≡ ∅ D′ for some D′ ∈ Lower(C).
Note that in [
Proposition 11. [16, Propositions 5.1.19 and 5.1.21]. Lower(C) can be computed in exponential time (w.r.t. C and Σ ), each neighbor in Lower(C) has quadratic size (w.r.t. C), Lower(C) consists of at most exponentially many neighbors (w.r.t. C and Σ ), and each two diferent neighbors in Lower(C) are not equivalent.
The following example shows that the exponential blow-up cannot be avoided. Example 12. Fix the signature Σ consisting only of two role names r and s. Define the concept Cn := d{ ∃ r. Dni | i ∈ {1, . . . , n} } for each n ≥ 2 where Dni := d{ Ej , Fj | j ∈ {1, . . . , n} \ {i} } ⊓ ∃ rn. ⊤ ⊓ ∃ sn. ⊤, and Ej := ∃ rj . ∃ s. ⊤, and Fj := ∃ sj . ∃ r. ⊤. There are exponentially many lowering functions for r, namely the partial functions χ : Succ(Cn, r) →7 EL(Σ ) where Dom(χ ) := Succ(Cn, r) and χ (Dni) ∈ {Ei, Fi} for each index i ∈ {1, . . . , n}, and these induce the lower neighbors Cn ⊓ ∃ r. (G1 ⊓ · · · ⊓ Gn) where each Gi is either Ei or Fi. 4
Using the results from the previous section on neighbors of EL concept descriptions, we are now able to introduce a natural distance measure (metric) on the set EL(Σ ), namely where the distance between two EL concepts C and D is the length of a shortest path between C and D in the undirected graph with vertex set EL(Σ ) and in which two concepts are connected by an edge if they are neighbors of each other.10 This distance measure fulfills all conditions of a metric, i.e., the distance between two concepts is never negative, two concepts have distance 0 if and only if they are equivalent, the distance from C to D equals the distance from D to C, and the distance between two concepts never exceeds the sum of the distances with a third concept in the middle (triangle inequality ).
In what follows, we will first explore some lattice-theoretic properties of the
partially ordered set (EL(Σ ), ⊑∅) and then utilize a well-known construction
from Lattice Theory [
First of all, the binary conjunction ⊓ is the infimum operation in the poset
(EL(Σ ), ⊑∅), i.e., for each two concepts C and D, it holds true that C ⊓ D ⊑∅ C
and C ⊓ D ⊑∅ D, and further E ⊑∅ C and E ⊑∅ D implies E ⊑∅ C ⊓ D for each
concept E. The dual notion is the supremum operation; for each two concepts C
and D, the supremum (or least common subsumer ) C ∨ D satisfies C ⊑∅ C ∨ D
as well as D ⊑∅ C ∨ D, and further C ⊑∅ E and D ⊑∅ E implies C ∨ D ⊑∅ E
for each concept E. According to [
⊓ d{ ∃ r. (E ∨ F ) | ∃ r. E ∈ Conj(C) and ∃ r. F ∈ Conj(D) }.
The existence of the infimum and the supremum operation turns the poset (EL(Σ ), ⊑∅) into a lattice. In [16, Proposition 5.2.1] it is shown that this lattice is distributive, i.e., the equivalences C ⊓ (D ∨ E) ≡ ∅ (C ⊓ D) ∨ (C ⊓ E) and C ∨ (D ⊓ E) ≡ ∅ (C ∨ D) ⊓ (C ∨ E) hold true for each three concepts C, D, E.
Recall that, for each concept C, there is a finite upper bound on the lengths
of chains starting with C [5, proof of Proposition 3.5]. We conclude that, for each
two concepts C and D, every chain from C to D has finite length. According
to [
As shown in [16, Proposition 5.4.4], the distance d(C, D) coincides with the length of a shortest path from C to D in the undirected graph (V, E) with vertex set V := EL(Σ ) and with edge set E := { {C, D} | C ≺ ∅ D }. Specifically, it follows that the distance d(C, D) equals the sum of the lengths of a chain of neighbors from C to C ⊓ D and of another from D to C ⊓ D.
We close this section with an asymptotic analysis. As a simple example, consider the concept description ∃ r. (A1 ⊓ · · · ⊓ Ak). Let X1, . . . , Xℓ be an enumerak tion of the exponentially many subsets of {A1, . . . , Ak} with ⌊ 2 ⌋ elements, and further let Dm := d{ ∃ r. d Xi | i ∈ {m, . . . , ℓ} } for each index m ∈ {1, . . . , ℓ}. It follows that ∃ r. (A1 ⊓ · · · ⊓ Ak) ⊏∅ D1 ⊏∅ D2 ⊏∅ · · · ⊏∅ Dℓ ⊏∅ ⊤ is an exponentially long chain of strict subsumptions, which implies that the distance from ∃ r. (A1 ⊓ · · · ⊓ Ak) to ⊤ must be at least exponential. Even worse, the following proposition shows that there exists a sequence of concept descriptions Cn such that Cn has role depth n (and size linear in n) and the distance from Cn to ⊤ is n-fold exponential.
Proposition 14. [16, Corollary 5.6.9]. Fix a natural number k ≥ 3 and let A1, . . . , Ak be diferent concept names from Σ . Further let ri be a role name in Σ for each natural number i. The distance from ∃ r1. · · · ∃ rn. (A1 ⊓ · · · ⊓ Ak) to ⊤, where n ranges over the natural numbers, is asymptotically bounded from below by12 the iterated exponential 12 A function f : N → R is asymptotically bounded from below by a function g : N → R if there is a constant c ∈ R+ and a number n0 ∈ N such that c · g(n) ≤ f (n) for each n ≥ n0.
Deciding Minimality and Maximality for a Property. [2, Section 5], [16, Section 5.1.2]. Let P ⊆ EL (Σ ) be a decision problem that is closed under subsumees, i.e., C ∈ P and C ⊒∅ D implies D ∈ P. Further consider the problem Max(P) that consists of all maximally general concepts in P, i.e., C ∈ Max(P) if and only if C ∈ P and there is no D such that C ⊏∅ D and D ∈ P.
A deterministic, polynomial time procedure that decides Max(P) is as follows: (1) On input C, check whether C ∈ P. If not, then reject C. (2) Compute the set Upper(C) from Proposition 5. (3) If there exists an upper neighbor D ∈ Upper(C) such that D ∈ P, then reject C; otherwise accept C.
We conclude that P ∈ C implies Max(P) ∈ PC for each complexity class C,
which specifically yields that P ∈ P implies Max(P) ∈ P and that P ∈ Σ nP
implies Max(P) ∈ ∆ nP+1 for each number n ∈ N. Furthermore, P ∈ P Space
implies Max(P) ∈ P Space, since PP Space ⊆ P Space [
Dually, let P ⊆ EL (Σ ) be a decision problem that is closed under subsumers, i.e., C ∈ P and C ⊑∅ D implies D ∈ P, and consider the problem Min(P) that consists of all maximally specific concepts in P, i.e., C ∈ Min(P) if and only if C ∈ P and there is no D such that C ⊐∅ D and D ∈ P.
A non-deterministic, polynomial time procedure that decides the complement of Min(P) is the following: (1) On input C, check if C ∈ P. If not, then accept C. (2) Guess a concept D the size of which is quadratic in C. (3) Check if C is an upper neighbor of D. If not, then accept C. (4) Check if D ∈ P. If yes, then accept C; otherwise reject C.
It follows that P ∈ C implies Min(P) ∈ co (NPC) for each complexity class C.
In particular, we infer that P ∈ P implies Min(P) ∈ co NP, and that P ∈ Σ nP
implies Min(P) ∈ Π nP+1 for each n ∈ N. As co (NPP Space) ⊆ P Space [
Diferent kinds of similarity measures have also been employed in the
development of novel DLs. For instance, [
In the following, we explain how the distance measure d in Proposition 13
can be transformed into a similarity measure. Firstly, we convert d into a metric
with range [0, 1) and, secondly, we twist the range (i.e., value x becomes 1 − x).
Formally, if f : [0, ∞) → [0, 1) is an order-preserving, sub-additive function, then
the mapping s defined by s(C, D) := 1 − f (d(C, D)) is a similarity measure. For
instance, suitable functions are f (x) := ( 1+xx )y for each y > 0 and f (x) := 1 − yx
for each y ∈ (0, 1). Such a similarity measure s fulfills all properties listed in [
In [20, Section 2.2] it is stated that “refinement operators are used to structure
a search process for concepts”. While this argument holds true in theory, we
show in the following that utilizing the ideal downward refinement operator, as
introduced in [
Given a TBox T , a downward refinement operator is a function ρ that maps each concept description to a set of concept descriptions such that D ∈ ρ (C) implies D ⊑T C.13 Furthermore, ρ is ideal if it additionally fulfills the following conditions: (1) ρ is finite , i.e., ρ (C) is finite for each C, (2) ρ is proper, i.e., D ∈ ρ (C) implies D ̸≡ T C, and (3) ρ is complete, i.e., D ⊏T C implies the existence of concept descriptions E1, . . . , En such that E1 ∈ ρ (C), E2 ∈ ρ (E1), . . . , En ∈ ρ (En− 1), and En ≡ T D.
There is a connection between the notion of neighbors of concept
descrip13 By C ⊑T D we indicate that CI ⊆ DI for each model I of T .
tions and ideal downward refinement operators. In what follows, we consider
the particular downward refinement operator ρ ∗ in [21, Theorem 1]. Firstly, ρ ∗
is defined with respect to TBoxes that may only contain axioms of the
following forms: concept inclusions A ⊑ B, concept disjointness axioms A ⊓ B ≡ ⊥ ,
role inclusions r ⊑ s, domain restrictions Dom(r) ⊑ A, and range restrictions
Ran(r) ⊑ A, where A and B are concept names and where r and s are role
names. Secondly, ρ ∗ is defined by means of another refinement operator ρ , which
constructs refinements by applying one of four operations to the syntax tree of
the concept description to be refined: (1) add a concept name as label to some
node, (2) refine a concept name that labels a node (i.e., if A ⊑ B is in T , then
a label B can be replaced by A), (3) refine a role name that labels an edge,
and (4) attach a new subtree to some node (see [
For the case where the TBox T is empty, it follows from Proposition 14 that the search for a particular EL concept description may need a non-elementary number of consecutive refinement steps with ρ ∗ . More specifically, constructing the target concept ∃ r1. · · · ∃ rn. (A1 ⊓ · · · ⊓ Ak) starting from ⊤ by means of ρ ∗ needs a number of steps that is asymptotically bounded from below by
Computing Maximally Strong Weakenings for Gentle Repairs. In order
to resolve inconsistency or to remove an unwanted consequence, the classical
approach to repairing an ontology is deleting enough axioms from it. More
finegrained repairs can be obtained by weakening axioms instead of removing them
completely [
A general framework for computing gentle repairs by axiom weakening is
developed in [
According to Proposition 18 in [
We have analyzed the EL subsumption hierarchy and, in particular, we have showed how smallest steps can be made when navigating within this hierarchy. Such a smallest step is either going up to an upper neighbor or going down to a lower neighbor. We have explained how all neighbors of a given concept can be computed and we have determined the computational complexity: all upper neighbors can be obtained in polynomial time, while enumerating all lower neighbors needs exponential time. By employing a standard construction from Lattice Theory, we have devised a distance measure (metric) on the set of all EL concepts. We have further seen that the EL subsumption hierarchy contains very long chains, since the distance between supposedly simple concepts can easily be multi-exponential — specifically, the distance between ⊤ and ∃ r1. · · · ∃ rn. (A1 ⊓ · · · ⊓ Ak) is n-fold exponential if k ≥ 3 — which directly prohibits its practical usage. Additionally, we have given some applications and consequences of the aforementioned results.
In this article, we have looked at subsumption w.r.t. the empty TBox only.
Other types of TBoxes (cycle-restricted, acyclic, general) as well as two
extensions of EL (with ⊥, with greatest fixed-points) are considered in [
Acknowledgements. The author gratefully thanks both Franz Baader and Bernhard Ganter for helpful discussions. The author further greatly appreciates Franz Baader’s valuable comments that helped to improve this article. Also, the author thanks the anonymous reviewers for their comments and questions.