Completion algorithms for subsumption are investigated for many extensions of the description logic EL. While for several of them subsumption is tractable, this is no longer the case, if inverse roles are admitted. In this paper we present an optimized version of the completion algorithm for ELHIfR+ [11], which is implemented in jCel. The completion sets computed during classification are a good substrate for implementing other reasoning services such as generalizations. We report on an extension of jCel that computes role-depth bounded least common subsumers and most specific concepts based on completion sets.
The lightweight Description Logic (DL) E L and many of its extensions enjoy the
nice property that computing concept subsumption and classification of
ontologies written in these Description Logics is tractable [
Recently, the completion sets computed during classification have been employed to compute (approximations for) generalization inferences such as the least common subsumer (lcs) or most specific concept (msc). The lcs generalizes a collection of concept descriptions into a single concept description that is the least w.r.t. subsumption. The msc generalizes a description of an individual into a concept description. Intuitively, the msc delivers the most specific concept description that the input individual belongs to. Both of these services are useful for the building of knowledge bases. In the bio-medical field in particular the lcs is employed to define similarity measures between concept descriptions. Since for conjunction existential restr. C u C ∃r.C
Semantics
CI ∩ DI
{d ∈ ΔI | ∃e ∈ ΔI : (d, e) ∈ rI ∧ e ∈ CI }
general E L-TBoxes neither the lcs nor the msc need to exist, an algorithm for
role-depth bounded lcs and -msc was devised in [
Starting from two disjoint sets NC and NR of concept and role names, respectively, E LHIfR+ -concept descriptions are built using concept and role constructors shown in Table 1 and the top-concept (>). The DL E L is the E LHIfR+ fragment that only allows for the concept constructors conjunction and existential restrictions. E LH extends E L by role inclusion statements.
The semantics of E LHIfR+ is defined by interpretations I = (ΔI , ·I ) consisting of a non-empty domain ΔI and an interpretation function ·I that assigns binary relations on ΔI to role names and subsets of ΔI to concepts. The interpretation function is extended to complex concept descriptions and roles as described in the last column of Table 1.
A TBox is a set of concept inclusion axioms of the form C v D, where C, D are concept descriptions. An interpretation I satisfies the concept inclusion C v D, denoted as I |= C v D iff CI ⊆ DI . I is a model of a TBox T if it satisfies all axioms in T . A concept C is subsumed by a concept D w.r.t. T (denoted C vT D) if, for every model I of T it holds that I |= C v D.
Let NI be a set of individual names. An E L-ABox is a set of assertions of the form C(a), r(a, b), where C is an E L-concept description, r ∈ NR, and a, b ∈ NI. A knowledge base K = (T , A) consists of a TBox T and an ABox A.
Finally, an individual a ∈ NI is an instance of a concept description C w.r.t. K (written K |= C(a)) if I |= C(a) for all models I of K. ABox realization is to compute for each individual a in A the set of named concepts from K that have a as an instance. 3
Completion algorithm for E LHI fR+
Classification of TBoxes is the computation of all subsumption relations between
all named concepts of a TBox. For several extensions of E L classification can be
performed in polynomial time [
NR-1 C ≡ D C v D, D v C NR-2 C1 u · · · u Cˆ u · · · u Cn v D Cˆ v A, C1 u · · · u A u · · · u Cn v D NR-3 ∃r0.Cˆ v D Cˆ v A, ∃r0.A v D NR-4 Cˆ v ∃r0.D Cˆ v A, A v ∃r0.D NR-5 B v ∃r0.Cˆ B v ∃r0.A, A v Cˆ NR-6 D v C1 u C2 D v C1, D v C2 NR-7 C v ∃r−.D C v ∃u.D, u v r−, r− v u NR-8 ∃r−.C v D ∃u.C v D, u v r−, r− v u where r: role; r0: (inverse) role; C, Ci, D: concept descriptions; Cˆ, Dˆ : complex concept descriptions; B: concept name; A: fresh concept name; u: fresh role name.
2. apply completion rules to the completion graph 3. read off subsumptions relations from the saturated completion graph The basic completion algorithm represents the completion graph by two kinds of completion sets: S(C) and S(C, r) for each concept name C and role name r from the TBox. The sets contain concept names from the TBox and > . The sets S(C) represent the labelled nodes, while the sets S(C, r) represent the edges of the completion graph. The idea of the classification algorithm is that completion rules make implicit subsumption relationships explicit. In fact, the following invariants hold: – D ∈ S(C) implies that C vT D, – D ∈ S(C, r) implies that C vT ∃r.D.
For extensions of E L that also offer inverse roles, testing subsumption is not
polynomial, but it is ExpTime-complete [
A1 u . . . u An v B,
A1 v ∃r.A2 or ∃r.A1 v B.
Each E LHIfR+ -TBox can be transformed into this normal form by applying the rules shown Table 2, where the axioms on the left-hand side are replaced by the axiom(s) on the right-hand side. The implicit information on (functional) roles is made explicit by applying the following saturation rules to the TBox: r v s r ◦ r v r r− v s− r− ◦ r− v r− r v s , s v t r v s , f (s) In addition, auxiliary role names are added to NR to allow a mapping where each role s has an inverse role r− such that s ≡ r−. In this way, the algorithm applies the completion rules to role names and inverse roles.
Completion rules. Once the TBox is normalized and saturated, the completion sets are initialized and the completion rules are applied. Based on the two sets Ξ := {∃r.A | r ∈ NR, A ∈ NC} and Ω := {(A, ψ) | A ∈ NC, ψ ⊆ Ξ} the completion sets are defined as – V ⊆ Ω – S ⊆ {(x, A) | x ∈ Ω, A ∈ NC} – R ⊆ {(r, x, y) | r ∈ NR, x, y ∈ Ω}.
For the completion graph, the set V is the set of nodes, S is a node labeling and Ω is the set of edges. The elements in S are called S-entries, the elements in R are called R-entries, the elements in V are referred to as nodes. The completion process satisfies the following invariants: – if ((A, ϕ), C) ∈ S, then (A u d E) vT C
E∈ϕ – if (r, (A, ϕ), (B, ψ)) ∈ R, then (A u d E) vT ∃r.(B u E∈ϕ d E) E∈ψ A vT follows: where each E is of the form ∃r.X. Furthermore, after completion we have that
B if and only if ((A, ∅), B) ∈ S. The algorithm initializes the sets as – V := {(A, ∅) | A ∈ NC}, – S := {((A, ∅), A) | A ∈ NC} ∪ {((A, ∅), >) | A ∈ NC}, – R := ∅ and applies the completion rules. The optimized completion rules for E LHIfR+ are presented in Table 3. The underlined elements are membership checks for S and R. These conditions are relevant for the strategy of completion.
As a consequence of the normal form presented here, CR-2 may have several conjuncts on the left-hand side of a normalized GCI. This simple optimization reduces the number of auxiliary symbols.
In [
To prepare Q the initialization of the algorithm is slightly modified: CR-1 if A v B ∈ T , (x, A) ∈ S then S0 := S ∪ {(x, B)} CR-2 if A1 u . . . u Ai u . . . u An v B ∈ T ,
(x, A1) ∈ S, . . ., (x, Ai) ∈ S, . . ., (x, An) ∈ S then S0 := S ∪ {(x, B)} CR-3 if A v ∃r.B ∈ T , (x, A) ∈ S then if f (r) then v := (>, {∃r−.A}) if v ∈/ V then V := V ∪ {v}, S0 := S ∪ {(v, B)} ∪ {(v, >)},
R0 := R ∪ {(r, x, v)} else y := (B, ∅)
R0 := R ∪ {(r, x, y)} CR-4 if ∃s.A v B ∈ T , (r, x, y) ∈ R, (y, A) ∈ S, r vT s
then S0 := S ∪ {(x, B)} CR-5 if s ◦ s v s ∈ T , (r1, x, y) ∈ R, (r2, y, z) ∈ R, r1 vT s, r2 vT s
then R0 := R ∪ {(s, x, z)} CR-6 if ∃s−.A v B ∈ T , r vT s, (r, x, y) ∈ R, (x, A) ∈ S, (y, B) ∈/ S, y = (B0, ψ) then v := (B0, ψ ∪ {∃r−.A}) if v ∈/ V then V := V ∪ {v}, S0 := S ∪ {(v, k) | (y, k) ∈ S}
S0 := S ∪ {(v, B)}, R0 := R ∪ {(r, x, v)} CR-7 if ∃s−.A v B ∈ T , (r2, x, y) ∈ R, x = (A0, ϕ), y = (B0, ψ),
r ◦ r v r ∈ T , r1 vT r, r2 vT r, ∃r1−.A ∈ ϕ, r vT s then v := (B0, ψ ∪ {∃r−.A}) if v ∈/ V then V := V ∪ {v}, S0 := S ∪ {(v, k) | (y, k) ∈ S}
S0 := S ∪ {(v, B)}, R0 := R ∪ {(r2, x, v)} CR-8 if A v ∃r2−.B ∈ T , (r1, x, y) ∈ R, (y, A) ∈ S, r1 vT s, r2 vT s, f (s−) then S0 := S ∪ {(x, B)} CR-9 if (r1, x, y) ∈ R, (r2, x, z) ∈ R, r1 vT s, r2 vT s,
y = (>, ψ), z = (>, ϕ), y 6= z, f (s) then v := (>, ψ ∪ ϕ) if v ∈/ V then V := V ∪ {v} S0 := S ∪ {(v, k) | (y, k) ∈ S} ∪ {(v, k) | (z, k) ∈ S}, R0 := R ∪ {(r1, x, v)} The sets S0 and R0 represent the next step of sets S and R, respectively. Their new elements are added to Q0 in the algorithm shown in Table 4.
We say a completion rule is sensitive to changes in a set, if the precondition of that rule mentions that set. In Table 3 the relevant entries are underlined. For example, CR-1 is sensitive to changes in S only, CR-7 is sensitive to changes in R only, and CR-4 is sensitive to changes in S and R. According to the kind of entry they are sensitive to, the completion rules are members of the chain of rules the process S-entries or R-entries.
A conceptual scheme of the algorithm is presented in Table 4. The processor takes entries from Q, changes sets S and R, and informs the corresponding chain of rules of these changes. This procedure is repeated until Q is empty, i.e. no rules are applicable. 3.1
Implementation in jCel
jCel1 is implemented in Java. The object-oriented design of the completion
algorithm brings a very low coupling, since each rule can be changed separately. Thus
jCel can easily be adapted to new sets of completion rules. For
implementationdependant technical details (e.g. data structures) see [
Besides classification for E LHIfR+ -TBoxes, jCel also implements realization of E LH-ABoxes. Experiments classifying ELHIfR+ ontologies. The full version of GALEN is still one of the most challenging ontologies, since hardly any reasoner can classify it. Two GALEN ontologies were considered: the original version of GALEN (GALEN-A), and the newer version of GALEN (GALEN-B), which were used in [?] to test Cel. Table 6 lists their sizes in terms of concepts etc.
For GALEN-A, jCel took 1093 s and the reasoner CB less than 1 s. In case of GALEN-B, the current version of jCel could not finish classification due to lack of memory. CB classified this ontology in 5 s. 1 The reasoner jCel and its source code is available at http://jcel.sourceforge.net. ontology NCI EL GO ELR+ FMA ELR+ SNOMED CT ELH NotGalen CELGalen
Experiments in ELHR+ . In Table 6 we compare the sizes of the different test ontologies to be classified with the polynomial completion algorithm (with static node set).
The execution times of jCel were compared with the Cel system. Cel is
one of the fastest reasoners for reasoning in the EL-family of DLs and is known
to deliver correct results [
To sum up, jCel’s performance is comparable to state of the art reasoners and, in case of Cel sometimes even better. 4
The classification and the realization algorithm of jCel can be employed to compute generalizations. We define these inferences now.
Definition 1. Let K =(T , A) be a ELH-KB and C1, . . . , Cn ELH-concept descriptions and k ∈ IN. Then the ELH-concept description C is the role-depth bounded ELH-least common subsumer of C1, . . . , Cn w.r.t. T and role-depth k (written k-lcs(C1, . . . , Cn)) iff
2. Ci vT C for all 1 ≤ i ≤ n, and
Let a be an individual in A and again k ∈ IN. The E LH-concept description C is the role-depth bounded E LH-most specific concept of a w.r.t. K and role-depth k (written k-msc(a)) iff
2. K |= C(a), and 3. for each E LH-concept description D with role-depth(D) ≤ k holds: K |= D(a) implies C vT D.
Completion-based subsumption algorithms classify E LH-TBoxes by explicitly deriving all subsumptions relationships between named concept and storing them in completion sets. The latter can be used to compute the k-lcs of concept descriptions. A completion-based realization algorithm can be used to compute the k-msc of an individual from its completion sets.
The algorithm for computing k-lcs and k-msc from completion sets is given
in [
2. classify the augmented TBox 3. for the subgraph of the completion graph reachable from the nodes representing the newly introduced names by paths of length ≤ k: do cross-product construction w.r.t. the node labels and edges.
The proof of the correctness for the k-lcs-algorithm for relies on the invariants discussed in Section 3.
If the completion sets for ABox realization are computed, one can compute the k-msc of an individual a simply by traversing the subgraph of the completion graph reachable from a by paths of length up to k and conjoining the node labels.
Since the completion sets are containing all subsumers of a named concept,
the concept descriptions resulting from traversing subgraphs of the completion
graph and collecting the node labels are very redundant. For a person editing
the resulting concept description this is clearly undesirable. We devise a
simplification heuristic that is similar to the (equivalent) minimal rewritings proposed
in [
Algorithm 1 Simplification of the resulting concept description. Procedure simplify (C, S) Input: C: EL concept description; S: set of completion sets Output: simplify(C): a simplified concept description equivalent to C
Our system Gel is available as a plug-in for the ontology editor Prote´ge´
and an API for the role-depth bounded lcs and -msc is planned. The former
system sonic [
Evaluation. For the evaluation of the generalization algorithms, we used two different ontologies. The earlier mentioned NotGalen described in Table 6 is a version of the medical ontology Galen stripped-down to E LH. This ontology does not contain individuals, but its deep concept hierarchy makes it a good test ontology for the k-lcs. As test concepts for the k-lcs we selected sibling concepts from the concept hierarchy with common ancestors other than > and with many (comparable) existential restrictions. In total, we selected 20 such concept tuples from NotGalen.
We also used the Sweet2 ontology, the Semantic Web for Earth and Environmental Terminology by NASA. This ontology was converted to E LH by replacing all value restrictions with existential restrictions and dropping all axioms not expressible in E LH. Sweet does contain individuals and a rich relational structure and was used as a test ontology for the k-msc. It has 4276 concept names and 2069 individuals. We selected those individuals from Sweet that appear in many role assertions. In total, we selected 18 individuals from Sweet.
All tests were run on an Intel(R) Core(TM) i5-2400 under Oracle Java 6SE 64bit. For each computation of the k-lcs or k-msc we measured the concept size 2 http://sweet.jpl.nasa.gov/sweet/
k = 1 k = 2 k = 3 k = 4 k = 5 k 2-ary lcs 3-ary lcs 4-ary lcs 5-ary lcs of the resulting concept description and after simplification and the run-time (after classification / realization) for construction of the k-lcs or k-msc and of its simplification. The Table 8 and 10 show the results for the k-msc and klcs, respectively. The concept construction time and expanded concept size for different numbers of input concepts to the k-lcs are shown in Table 9.
For the k-lcs the resulting run-times were quite high, whereas classification of NotGalen took only around 670 ms. Computation of the k-msc was always quite fast—especially compared to the realization time of 5.7 s for the Sweet ontology.
For both k-lcs and k-msc we found the expanded concept size (and thus the construction time) to grow exponentially with the role-depth bound k. The concept size of the simplified concepts, however, is growing much slower.
Interestingly, for the k-msc the resulting concept was the exact most specific concept for most individuals for a role-depth of only 2 or 3 — the resulting concept did not change for higher k. Only 3 of the 18 individuals had a msc with maximum role-depth of 5.