For EL the least common subsumer (lcs) need not exist, if computed w.r.t. general TBoxes. In case the role-depth of the lcs concept description is bounded, an approximate solution can be obtained. In this paper we extend the completion-based method for computing such approximate solutions to ELI and EL+. For ELI the extension needs to be able to treat complex node labels. For EL+ a naive method generates highly redundant concept descriptions for which we devise a heuristic that produces smaller, but equivalent concept descriptions. We demonstrate the usefulness of this heuristic by an evaluation.
The approach to compute the k-lcs is to employ the completion method that
is used to classify the TBox. This method builds a graph structure, which is
saturated by completion rules [
For both methods we show that the obtained concept is a common subsumer and that it is minimal w.r.t. subsumption for the given role-depth bound k. Thus, the obtained concept description is the exact lcs, if the exact lcs exists for a role-depth n and the k-lcs is computed for a maximal role-depth of k ≥ n.
The concept descriptions obtained in this way turn out to be highly redundant. In order to obtain concise and readable concept descriptions, we devise a heuristic to obtain smaller, equivalent concept descriptions.
This paper is organised as follows: next, we introduce the basic notions. In Section 3 we recall the completion algorithm for E L+ and devise the computation algorithms for the k-lcs in E L+. The computation algorithm for E LI is presented in Section 4. In Section 5 we present the simplification heuristic to obtain smaller E L+-concept descriptions. We end with conclusions and remarks on future work. 2
We assume that the reader is familiar with the basic notions of DLs, for an
introduction see [
The concept constructors and axioms are interpreted in the standard way. We denote by NC,T and NR,T the sets of concept names and role names that occur in a TBox T . For a concept description C we denote by rd(C) its roledepth, i.e., its maximal nesting of quantifiers. We define the central reasoning services of this paper.
Definition 1 ((Role-depth bounded) least common subsumer). Let L be a DL, T be a L-TBox and C1, . . . , Cn be L-concept descriptions. Then the L-concept description D is the least common subsumer of C1, . . . , Cn w.r.t. T iff (1) Ci vT D for all i ∈ {1, . . . , n}, and (2) for all L-concept descriptions E: Ci vT E for all i ∈ {1, . . . , n} implies D vT E.
Let k ∈ N. Then the L-concept description D is the role-depth bounded least common subsumer of C1, . . . , Cn w.r.t. T and the role-depth k (k−lcs(C1, . . . , Cn)) iff (1) rd(D) ≤ k, (2) Ci vT D for all i ∈ {1, . . . , n}, and (3) for all L-concept descriptions E with rd(E) ≤ k: Ci vT E ∀i ∈ {1, . . . , n} implies D vT E. For the DLs considered in this paper the (k-)lcs is unique up to equivalence, thus we speak of the (k-)lcs. 3
Computing the k-lcs in E L+ The algorithms to compute the role-depth bounded lcs rely on completion graphs produced by completion-based subsumption algorithms. Completion algorithms work on normalized TBoxes and for which they build a completion graph and exhaustively apply completion rules. After this step, the completion graph contains all subsumption relations from the TBox explicitly. 3.1
Completion Algorithm for EL+
An E L+-TBox T is in normal form, if all concept inclusions in T are of the form
A v B, A1 u A2 v B, A v ∃r.B, or ∃r.A v B with A, A1, A2, B ∈ NC and r ∈
NR; and all role inclusions are of the form s v r or s ◦ t v r with {r, s, t} ⊆ NR.
All E L+-TBoxes can be normalized by applying a set of normalization rules [
The completion graph for a normalized TBox T 0 used by the completion
algorithm is of the form (V, E, S), where V = NC,T 0 ∪{>} is the set of nodes, E ⊆
V ×NR,T ×V is the set of role name labeled edges and S : V → 2NC,T 0 ∪{>} is the
node-labeling. The completion algorithms starts with an initial graph (V, E, S)
with E = ∅ and S(A) = {A, >} for each A ∈ NC,T 0 ∪ {>} and exhaustively
applies a set of completion rules from [
Once the rule-applications finished, all subsumption relations can be directly
be read off the completion graph. This completion algorithm is sound and
complete as shown in [
Procedure k-lcs (C, D, T , k) Input: C, D: EL+-concept descriptions; T : EL+-TBox; k: natural number Output: k-lcs(C, D): role-depth bounded EL+-lcs of C, D w.r.t. T and k 1: T 0 := normalize(T ∪ {A ≡ C, B ≡ D}) 2: (V, E, S) := apply-completion-rules(T 0) 3: L := k-lcs-r(A, B, (V, E, S), k) 4: return remove-normalization-names(L) Procedure k-lcs-r(A, B, (V, E, S), k) Input: A, B: concept names; (V, E, S): completion graph; k: natural number Output: k-lcs(A, B): role-depth bounded EL+-lcs of A, B w.r.t. T and k 1: common-names := S(A) ∩ S(B) 2: if k = 0 then 3: return l P 4: else 5: return
P ∈common-names
l P ∈common-names l
P u
l r∈NR (A,r,C)∈E,(B,r,D)∈E
∃r.k-lcs-r(C, D, (V, E, S), k − 1)
The resulting completion graph can be used to compute the role-depth bounded
lcs. All RIAs from the E L+-TBox are explicitly captured in the completion graph
in the following sense: for each edge in the completion graph labeled with some
role r, the completion algorithm also creates edges for all its super-roles. This
means that for computing the k-lcs for an E L+-TBox the same algorithm can
be used as for E L, which was introduced in [
Procedure simplify(C, (V, E, S), T ) Input: C: EL+-concept description; (V, E, S): completion graph; T : EL+-TBox Output: simplify(C): simplified concept description The highly redundant E LH-concept descriptions obtained from the k-lcs algorithm, need to be simplified, in order to make the resulting concept description readable. The general idea for the simplification is to remove those subtrees from the syntax tree which are subsumers of any of their sibling subtrees. For a conjunction of concept names, this results in the least ones (w.r.t. vT ).
Algorithm 2 computes the simplification of an E L+-concept description. Note, that the algorithm needs to be applied after the normalization names were removed, otherwise it might remove names from the original TBox that subsume normalization names, which get removed later during denormalization.
For the soundness of the simplification procedure simplify, it is only necessary
to ensure that the procedure ‘subsumes-H’ is sound. However, for our purpose
this procedure does not have to be complete. This might result in simplifications
that are correct k-lcs, but that are still redundant. This heuristic is given in [
Obviously, it would be desirable to avoid the generation of highly redundant
concept descriptions, instead of reducing them in a post-processing step. Due
to interactions with denormalization, such optimizations need to be
conservative. Such optimizations have been investigated in [
Evaluation. The k-lcs algorithm and the simplification algorithm are
implemented in our system GEL1, which is implemented on top of the jCEL
rea1 GEL is freely available from http://sourceforge.net/p/gen-el.
soner2 [
Computing the k-lcs in E LI
To handle inverse roles correctly, the completion algorithm needs to be adapted
in several ways. The normal form for TBoxes is the same as before.
The E L-completion algorithm has been extended to E LI in [
The node set V is defined as V ⊆ NC,T × 2{∃r.X|r is a role,X∈NC,T }. A node A with A ∈ NC,T from the node set for E L+ would then correspond to the node (A, ∅) from the node set for E LI. We will formalize the meaning of nodes in the node set V by defining the concept descriptions that these nodes correspond to: 2 jCEL is freely available from http://jcel.sourceforge.net.
Definition 2 (Concept descriptions for nodes). Let T be a normalized ELI-TBox and (V, E, S) its completion graph. Then we define for each node u = (A, φ) ∈ V : vconcept(u) = A u d∃r.X∈φ ∃r.X The graph (V, E, S) for the completion algorithm for ELI starts with V = {(A, ∅) | A ∈ NC,T }, E = ∅ and S((A, ∅)) = {A, >} for all A ∈ NC,T . The completions rules for ELI are the following: CI1 If A1 ∈ S(v) and A1 v B ∈ T and B 6∈ S(v),
then S(v) := S(v) ∪ {B} CI2 If A1, A2 ∈ S(v) and A1 u A2 v B ∈ T and B 6∈ S(v),
then S(v) := S(v) ∪ {B}
CI3 If A1 ∈ S(u), v = (B, ∅) and A1 v ∃r.B ∈ T and (u, r, v) 6∈ E,
then E := E ∪ {(u, r, v)}
CI4 If (u, r, v) ∈ E, B1 ∈ S(v) and ∃r.B1 v C ∈ T and C 6∈ S(u),
then S(u) := S(u) ∪ {C}
CI5 If (u, r, v) ∈ E, v = (B, ψ), A1 ∈ S(u), ∃r−.A1 v B1 ∈ T and B1 6∈ S(v),
then
v0 := (B, ψ ∪ {∃r−.A1})
if v0 6∈ V then V := V ∪ {v0}, E := E ∪ {(u, r, v0}), S(v0) := S(v) ∪ {B1}
else E := E ∪ {(u, r, v0}), S(v0) := S(v0) ∪ {B1}
The completion algorithm for ELI defined this way is again sound. For
completeness one needs to consider only those edges that do not point to nodes, which
have an ‘extended copy’ generated by rule CI5, i.e., edges (u, r, v) for which there
is no ∃r−.A v B ∈ T with A ∈ S(u) and B 6∈ S(v). We call those edges bad
edges and collect them in the bad edge set Ebad. However, since for each edge
(u, r, v) in Ebad there is (u, r, v0) ∈ E \ ebad with vconcept(v0) vT vconcept(v),
completeness for good edges is sufficient to show that the concept description
obtained by Algorithm 1 is a common subsumer [
A B r r−
C
r > Now, traversing this completion graph to compute the lcs of A and B without going backwards, we would get the result > u ∃r.> and then get stuck in the > node. However, the lcs of A and B is ∃r.∃r−.A, therefore the algorithm must to go backwards from > to A using the edge (A, r, >) as (>, r−, A), which yields the correct lcs. To see that the algorithm may not go backwards along arbitrary edges consider to go from A to C using the edge (C, r−, A) as (A, r, C). This would clearly be wrong, since we don’t have A vT ∃r.C. Thus the algorithm may only traverse backwards on those edges that led to the current node.
Therefore, the recursive algorithm needs to know not only the current nodes, but also the whole path from the start to the current node. This path is given in the form [u0, r1, u1, r2, . . . , rn, un] where u0 is the starting node, un the current node, and (ui−1, ri, ui) ∈ E are edges of the completion graph that have been traversed. For each path [u0, r1, u1, r2, . . . , rn, un] we will define the concept description they correspond to.
Definition 3 (Concept descriptions for paths). Let T be a normalized ELI-TBox and (V, E, S) its completion graph. Then we define for each path l = [u0, r1, u1, r2, . . . , rn, un] lconcept(l) =
vconcept(un) u ∃rn−.(vconcept(un−1) u ∃rn−−1.(. . . u ∃r1−.vconcept(u0) . . .)) Algorithm 1 depicted below computes the role-depth bounded lcs for two ELIconcept descriptions C and D w.r.t. a general ELI-TBox. This algorithm differs from the Algorithm 3.2 for EL+ mainly only in the following aspects: – Algorithm 1 uses the whole path to the current node instead of the node itself. – While in Algorithm 3.2 the nodes to visit from the current node are computed implicitly, Algorithm 1 stores all successors of the paths p1 and p2 explicitly in the sets S1 and S2. – Both algorithms traverse all edges (u, r, v) from the current node u, but Algorithm 1 additionally traverses the last edge backwards, if it is the inverse of r.
We give a proof sketch that Algorithm 1 indeed computes the k-lcs. Condition (1) from the Definition of the role-depth bounded lcs is obviously given. Common Subsumer. The fact that Algorithm 1 yields a common subsumer follows directly from the following lemma: Lemma 1. Let L = k-lcs-r(p1, p2, (V, E, S), k) for the two given paths p1 = [u0, r1, u1, r2, . . . , rn, un] and p2 = [v0, s1, v1, s2, . . . , sm, vm]. Then lconcept(p1) vT L and lconcept(p2) vT L.
Proof. This lemma can be proven by induction on the role-depth k of L. For k = 0, L = A1 u A2 u . . . u Al must be a conjunction of concept names Ai ∈ S(un) ∩ S(vm), 0 ≤ i ≤ l. Then soundness of the completion algorithm yields that for each Ai, we have lconcept(p1) vT vconcept(un) vT Ai and similarly lconcept(p2) vT Ai; therefore lconcept(p1) vT L and lconcept(p2) vT L.
For k ≥ 1, L is a conjunction of concept names and existential restrictions. For concept names, the same argument as above holds. All existential restrictions are of the form ∃r.k-lcs-r(l1, l2, (V, E, S), k − 1) where l1 is either Algorithm 1 Computation of a role-depth bounded ELI-lcs.
Procedure k-lcs(C, D, T , k) Input: C, D: ELI-concept descriptions; T : ELI-TBox; k: natural number Output: k-lcs(C, D): role-depth bounded ELI-lcs of C and D w.r.t. T and k 1: T 0 := normalize(T ∪ {A ≡ C, B ≡ D}) 2: (V, E, S) := apply-completion-rules(T 0) 3: L := k-lcs-r([(A, ∅)], [(B, ∅)], (V, E, S), k) 4: return remove-normalization-names(L) 11: return result-concept 1: result-concept := Procedure k-lcs-r(p1, p2, (V, E, S), k) Input: p1 = [(A0, ∅), r1, . . . , rn, (An, φn)] and p2 = [(B0, ∅), s1, . . . , sn, (Bm, ψm)]: two paths in the completion graph; (V, E, S): completion graph; k: natural number Output: role-depth bounded ELI-lcs of lconcept(p1) and lconcept(p2) w.r.t. T and k l
C
C∈S((An,φn))∩S((Bm,ψm)) 2: if k > 0 then 3: for all r ∈ NR do 4: S1 := {[(A0, ∅), r1, . . . , rn, (An, φn), r, (A, φ)] | ((An, φn), r, (A, φ)) ∈ E} 5: if n > 0 ∧ r = rn− then 6: S1 := S1 ∪ {[(A0, ∅), r1, (A1, φ1), r2, . . . , (An−2, φn−2), rn−1, (An−1, φn−1)]} 7: S2 := {[(B0, ∅), s1, . . . , sn, (Bm, ψm), r, (B, ψ)] | ((Bm, ψm), r, (B, ψ)) ∈ E} 8: if n > 0 ∧ r = s−m then 9: S2 := S2∪{[(B0, ∅), s1, (B1, ψ1), s2, . . . , (Bm−2, ψm−2), sm−1, (Bm−1, ψm−1)]} 10: result-concept := result-concept u l ∃r.k-lcs-r(l1, l2, (V, E, S), k − 1) l1∈S1 l2∈S2 p1 extended by one more edge (un, r, u) ∈ E or shorted by the last edge if rn = r−. In the first case soundness of completion for (un, r, u) ∈ E yields vconcept(un) vT ∃r.vconcept(u) and thus lconcept(p1) vT ∃r.(vconcept(u) u ∃r−.lconcept(p1)) = ∃r.lconcept(l1). In the second case we have lconcept(p1) = vconcept(un) u ∃rn−.lconcept(l1) vT ∃r.lconcept(l1). Then the induction hypothesis yields that lconcept(p1) vT ∃r.k-lcs-r(l1, l2, (V, E, S), k − 1), therefore lconcept(p1) vT L holds and by the same argument lconcept(p2) vT L holds. Minimality. To show that Algorithm 1 yields the least common subsumer w.r.t. the role-depth bound k, we show the following lemma.
Lemma 2. Let p1 and p2 be two paths in the completion graph (V, E, S) with p1 = [u0, r1, . . . , rn, un] and p2 = [v0, s1, . . . , sm, vm], such that (ui−1, ri, ui) ∈ E \ Ebad for all 1 ≤ i ≤ n and (vj−1, sj, vj) ∈ E \ Ebad for all 1 ≤ j ≤ m, u0 = (A, ∅) and v0 = (B, ∅). Let k ∈ N and F an ELI-concept description with rd(F ) ≤ k. If lconcept(p1) vT F and lconcept(p2) vT F then L = k-lcs-r(p1, p2, (V, E, S), k) vT F .
Proof. We prove this claim by induction on the role-depth bound k. For k = 0, F = A1u. . .uAn must be a conjunction of concept names. Since lconcept(p1) vT F and lconcept(p2) vT F , we have lconcept(p1) vT Ai and lconcept(p2) vT Ai for all 1 ≤ i ≤ n. Since p1 and p2 only traverse edges over E\Ebad, all possible rule applications of CI5 during that path were applied, and we have vconcept(un) vT Ai and vconcept(vm) vT Ai. Then completeness of the completion algorithm yields Ai ∈ S(un) and Ai ∈ S(vm) for all 1 ≤ i ≤ n. Thus, L vT F .
For k ≥ 1, F is a conjunction of concept names and existential restrictions. The concept names in F must appear in L by the same argument as in the base case. For each existential restriction ∃r.F 0 of F , we can again use the fact that p1 and p2 only traverse edges over E \ Ebad to derive that there must be nodes u and v with vconcept(u) vT F 0, vconcept(v) vT F 0, such that vconcept(un) vT ∃r.vconcept(u) and vconcept(vm) vT ∃r.vconcept(v). Then completeness of completion yields that there are u0 and v0 with (un, r, u0) ∈ E \ Ebad or u0 = un−1, r = rn− and similarly (vm, r, v0) ∈ E \ Ebad or v0 = vm−1, r = s−m, such that vconcept(u0) vT vconcept(u) and vconcept(v0) vT vconcept(v). Therefore, there are new paths l1 ∈ S1 and l2 ∈ S2, such that lconcept(l1) vT F 0 and lconcept(l2) vT F 0 which still only traverse edges in E \ Ebad, so the induction hypothesis yields k-lcs-r(l1, l2, (V, E, S), k − 1) vT F 0, and thus L = k-lcs-r(p1, p2, (V, E, S), k) vT F .
This shows that the Algorithm 1 computes the role-depth bounded least common subsumer for ELI. In contrast to subsumption, the computation of klcs does not increase complexity-wise when going from EL to ELI– it remains exponential in the size of k. 5
In this paper we have extended the computation algorithm for the k-lcs in EL w.r.t. general TBoxes to two members of the EL-family and showed that the proposed methods indeed compute the k-lcs. In cases where the exact lcs exists, our algorithms compute the exact lcs for a big enough k.
For ELI the extension of the EL algorithm for computing the k-lcs required traversal of the completion graph w.r.t. paths and the correct handling of complex node labels.
In case of EL+, the extension of the computation method for EL turned out to be trivial, here our contribution rather lies in the simplification procedure devised. This procedure turned out to be extremely helpful, when reducing the concept size. For the NotGalen ontology the the result concepts were reduced by several orders of magnitude. It would be desirable to obtain the simplified EL+-concept descriptions directly, instead of in the generate and then reduce kind of fashion employed so far. Besides this, we want to extend our results on EL+ and ELI to the computation of most specific concepts by completion.