Introduction
In Description Logics the inference most specific concept (msc) constructs a concept
description that generalizes an individual into a concept description. For the Description
Logic EL the msc needs not exist [
Many practical applications that need to represent probabilistic information, such as
medical applications or context-aware applications, need to characterize that
observations only hold with certain probability. Furthermore, these applications face the
problem that information from different sources does not coincide or that different diagnoses
yield differing results. These applications need to “integrate” differing observations for
the same state of affairs. A way to determine what the different information sources
agree upon is to represent this information as ABox individuals and to find a common
generalization of these individuals. A description of such a generalization of a group
of ABox individuals can be obtained by applying the so-called bottom-up approach for
constructing knowledge bases [
The second step, i.e., a computation procedure for the approximative lcs has been
investigated for EL and Prob-E Lc01 in [
c . The so-called k-msc obtained by the algorithm is
still a generalization of the input, but not necessarily the least one – in this sense it
is only an approximation of the msc. Moreover, our algorithms are based upon the
completion algorithms for EL and Prob-E Lc01 and thus can be easily implemented on
top of reasoners of these DLs. Due to space limitations the proofs can be found in [
We introduce the DL EL and its probabilistic variant Prob-E Lc01. Let NI , NC and NR be disjoint sets of individual-, concept- and role names, respectively. Prob-E Lc01-concept descriptions are built using the syntax rule
C ::= ⊤ | A | C ⊓ D | ∃r.C | P>0C | P=1C, where A ∈ NC , and r ∈ NR. EL-concept descriptions are Prob-E Lc01-concept description that do not contain the constructors P>0 or P=1.
A knowledge base K = (T , A) consists of a TBox T and an ABox A. An EL- (ProbE Lc01-)TBox is a finite set of concept inclusions (CIs) of the form C ⊑ D, where C, D are EL- (Prob-E L01
c -)concept descriptions. An EL-ABox is a set of assertions of the form C(a), r(a, b), where C is an EL-concept description, r ∈ NR, and a, b ∈ NI . A Prob-E Lc01-ABox is a set of assertions of the form C(a), r(a, b), P>0r(a, b), P=1r(a, b), where C is a Prob-E L01
c -concept description, r ∈ NR, and a, b ∈ NI .
The semantics of EL is defined by means of 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, subsets of ΔI to concepts and elements of ΔI to individual
names. For a more detailed description of this semantics, see [
An interpretation I satisfies a concept inclusion C ⊑ D, denoted as I |= C ⊑ D if CI ⊆ DI ; it satisfies an assertion C(a) (r(a, b)), denoted as I |= C(a) (I |= r(a, b)) if aI ∈ CI ((aI , bI ) ∈ rI ). It is a model of a knowledge base K = (T , A) if it satisfies all CIs in T and all assertions in A.
The semantics of Prob-E Lc01 generalizes the semantics of EL. A probabilistic interpretation is of the form
I = (ΔI , W, (Iw)w∈W , μ), where ΔI is the (non-empty) domain, W is a set of worlds, μ is a discrete probability distribution on W , and for each world w ∈ W , Iw is a classical EL interpretation with domain ΔI , where aIw = aIw′ for all a ∈ NI , w, w′ ∈ W . The probability that a given element of the domain d ∈ ΔI belongs to the interpretation of a concept name A is pdI (A) := μ({w ∈ W | d ∈ AIw }).
The functions Iw and pdI are extended to complex concepts in the usual way for the classical EL constructors, where the extension to the new constructors P∗ is defined as (P>0C)Iw := {d ∈ ΔI | pdI (C) > 0}, (P=1C)Iw := {d ∈ ΔI | pdI (C) = 1}.
A probabilistic interpretation I satisfies a concept inclusion C ⊑ D, denoted as I |= C ⊑ D if for every w ∈ W it holds that CIw ⊆ DIw . It is a model of a TBox T if it satisfies all concept inclusions in T . Let C, D be two Prob-E Lc01 concepts and T a TBox. We say that C is subsumed by D w.r.t. T (C ⊑T D) if for every model I of T it holds that I |= C ⊑ D. The probabilistic interpretation I satisfies the assertion P>0r(a, b) if μ({w ∈ W | Iw |= r(a, b)}) > 0, and analogously for P=1r(a, b). I satisfies the ABox A if there is a w ∈ W such that Iw |= A.
Finally, an individual a ∈ NI is an instance of a concept description C w.r.t. K (K |= C(a)) if I |= C(a) for all models I of K. The ABox realization problem is to compute for each individual a in A the set of named concepts from K that have a as an instance and that are least (w.r.t. ⊑). In this paper we are interested in computing most specific concepts.
Definition 1 (most specific concept). Let L be a DL, K = (T , A) be a L-KB. The most specific concept (msc) of an individual a from A is the L-concept description C s. t. 1. K |= C(a), and 2. for each L-concept description D holds: K |= D(a) implies C ⊑T D. The msc depends on the DL in use. For the DLs with conjunction as concept constructor the msc is, if it exists, unique up to equivalence. Thus it is justified to speak of the msc. 3
Completion-based Instance Checking Algorithms
Now we briefly sketch the completion algorithms for instance checking in EL [
Assume we want to test for an EL-KB K = (T , A) whether K |= D(a) holds. The completion algorithm first augments the knowledge base by introducing a concept name for the complex concept description D from the instance check, i.e., it sets K = (T ∪ {Aq ≡ D}, A), where Aq is a new concept name not appearing in K. The instance checking algorithm for EL works on normalized knowledge bases. The normalization is done in two steps: first the ABox is transformed into a simple ABox. An ABox is a simple ABox, if it only contains concept names in concept assertions. An EL-ABox A can be transformed into a simple ABox by first replacing each complex assertion C(A) in A by A(a) with a fresh name A and, second, introduce A ≡ C in the TBox.
After this step the TBox is normalized. For a concept description C let CN(C) denote the set of all concept names and RN(C) denote the set of all role names that appear in C. The signature of a concept description C (denoted sig(C)) is CN(C) ∪ RN(C). Similarly, the set of concept (role) names that appear in a TBox are denoted by CN(T ) (RN(T )). The signature of a TBox T (denoted sig(T )) is CN(T ) ∪ RN(T ). The signature of an ABox A (denoted sig(A)) is the set of concept (role / individual) names CN(A) (RN(A)/IN(A) resp.) that appear in A. The signature of a KB K = (T , A) (denoted sig(K)) is sig(T ) ∪ sig(A).
Now, an EL-TBox T is in normal form if all concept axioms have one of the following forms, where C1, C2 ∈ sig(T ) and D ∈ sig(T ) ∪ {⊥}:
C1 ⊑ D,
Any EL-TBox can be transformed into normal form by introducing new concept names and by applying the normalization rules displayed in Figure 1 exhaustively. These rules replace the GCI on the left-hand side of the rules with the set of GCIs on the right-hand NF1 C ⊓ Dˆ ⊑ E −→ { Dˆ ⊑ A, C ⊓ A ⊑ E } NF2 ∃r.Cˆ ⊑ D −→ { Cˆ ⊑ A, ∃r.A ⊑ D } NF3 Cˆ ⊑ Dˆ −→ { Cˆ ⊑ A, A ⊑ Dˆ } NF4 B ⊑ ∃r.Cˆ −→ { B ⊑ ∃r.A, A ⊑ Cˆ } NF5 B ⊑ C ⊓ D −→ { B ⊑ C, B ⊑ D } where Cˆ, Dˆ 6∈ BCT and A is a new concept name. side. Clearly, for a KB K = (T , A) the signature of A may be changed only during the first of the two normalization steps and the signature of T may be extended during both of them. The normalization of the KB can be done in linear time.
The completion algorithm for instance checking is based on the one for classifying
EL-TBoxes introduced in [
SK denotes the set of all completion sets of a normalized K. The completion sets are
initialized for each a ∈ IN(A) and each C ∈ CN(K) as follows:
– S(C) := {C, ⊤} for each C ∈ CN(K),
– S(C, r) := ∅ for each r ∈ RN(K),
– S(a) := {C ∈ CN(A) | C(a) appears in A} ∪ {⊤}, and
– S(a, r) := {b ∈ IN(A) | r(a, b) appears in A} for each r ∈ RN(K).
Then these sets are extended by applying the completion rules shown in Figure 2 until
no more rule applies. In these rules X and Y can refer to concept or individual names,
while C, C1, C2 and D are concept names and r is a role name. After the completion
has terminated, the following relations hold between an individual a, a role r and named
concepts A and B:
– subsumption relation between A and B from K holds iff B ∈ S(A)
– instance relation between a and B from K holds iff B ∈ S(a),
which has been shown in [
CR1 If C ∈ S(X), C ⊑ D ∈ T , and D 6∈ S(X)
then S(X) := S(X) ∪ {D} CR2 If C1, C2 ∈ S(X), C1 ⊓ C2 ⊑ D ∈ T , and D 6∈ S(X)
then S(X) := S(X) ∪ {D} CR3 If C ∈ S(X), C ⊑ ∃r.D ∈ T , and D 6∈ S(X, r)
then S(X, r) := S(X, r) ∪ {D} CR4 If Y ∈ S(X, r), C ∈ S(Y ), ∃r.C ⊑ D ∈ T , and
D 6∈ S(X) then S(X) := S(X) ∪ {D}
To describe the completion algorithm for Prob-E L, we need the notion of basic concepts. The set BCT of Prob-E Lc01 basic concepts for a KB K is the smallest set that contains (1) ⊤, (2) all concept names used in K, and (3) all concepts of the form P∗A, where A is a concept name in K. A Prob-E Lc01-TBox T is in normal form if all its axioms are of one of the following forms
C ⊑ D, where C, C1, C2, D ∈ BCT and A is a concept name. The normalization rules in Figure 1 can also be used to transform a Prob-E L01 c -TBox into this extended notion of normal form. We further assume that for all assertions C(a) in the ABox A, C is a concept name. We denote as P0T , P1T and R0T the set of all concepts of the form P>0A, P=1A, and P>0r(a, b) respectively, occurring in a normalized knowledge base K.
The completion algorithm for Prob-E Lc01 follows the same idea as the algorithm for EL, but uses several completion sets to deal with the information of what needs to be satisfied in the different worlds of a model. We define the set of worlds V := {0, ε, 1} ∪ P0T ∪ R0T , where the probability distribution μ assigns a probability of 0 to the world 0, and the uniform probability 1/(|V | − 1) to all other worlds. For each individual name a, concept name A, role name r and world v, we store the completion sets S0(A, v), Sε(A, v), S0(A, r, v), Sε(A, r, v), S(a, v), and S(a, r, v).
The algorithm initializes the sets as follows for every A ∈ BCT , r ∈ RN(K), and a ∈ IN(A): – S0(A, 0) = {⊤, A} and S0(A, v) = {⊤} for all v ∈ V \ {0}, – Sε(A, ε) = {⊤, A} and Sε(A, v) = {⊤} for all v ∈ V \ {ε}, – S(a, 0) = {⊤} ∪ {A | A(a) ∈ A}, S(a, v) = {⊤} for all v 6= 0, – S0(A, r, v) = Sε(A, r, v) = ∅ for all v ∈ V , S(a, r, v) = ∅ for v 6= 0, – S(a, r, 0) = {b ∈ IN(A) | r(a, b) ∈ A}.
These sets are then extended by exhaustively applying the rules shown in Figure 3, where X ranges over BCT ∪ IN(A), S∗(X, v) stands for S(X, v) if X is an individual and for S0(X, v), Sε(X, v) if X ∈ BCT , and γ : V → {0, ε} is defined by γ(0) = 0, and γ(v) = ε for all v ∈ V \ {0}.
PR1 If C′ ∈ S∗(X, v), C′ ⊑ D ∈ T , and D 6∈ S∗(X, v)
then S∗(X, v) := S∗(X, v) ∪ {D} PR2 If C1, C2 ∈ S∗(X, v), C1 ⊓ C2 ⊑ D ∈ T , and D 6∈ S∗(X, v)
then S∗(X, v) := S∗(X, v) ∪ {D} PR3 If C′ ∈ S∗(X, v), C′ ⊑ ∃r.D ∈ T , and D ∈/ S∗(X, r, v)
then S∗(X, r, v) := S∗(X, r, v) ∪ {D} PR4 If D ∈ S∗(X, r, v), D′ ∈ Sγ(v)(D, γ(v)), ∃r.D′ ⊑ E ∈ T ,
and E ∈/ S∗(X, v) then S∗(X, v) := S∗(X, v) ∪ {E} PR5 If P>0A ∈ S∗(X, v), and A ∈/ S∗(X, P>0A)
then S∗(X, P>0A) := S∗(X, P>0A) ∪ {A} PR6 If P=1A ∈ S∗(X, v), v 6= 0, and A ∈/ S∗(X, v)
then S∗(X, v) := S∗(X, v) ∪ {A} PR7 If A ∈ S∗(X, v), v 6= 0, P>0A ∈ P0T , and P>0A ∈/ S∗(X, v′)
then S∗(X, v′) := S∗(X, v′) ∪ {P>0A} PR8 If A ∈ S∗(X, 1), P=1A ∈ P1T , and P=1A ∈/ S∗(X, v)
then S∗(X, v) := S∗(X, v) ∪ {P=1A} PR9 If r(a, b) ∈ A, C ∈ S(b, 0), ∃r.C ⊑ D ∈ T ,
and D 6∈ S(a, 0) then S(a, 0) := S(a, 0) ∪ {D} PR10 If P>0r(a, b) ∈ A, C ∈ S(b, P>0r(a, b)), ∃r.C ⊑ D ∈ T , and D 6∈ S(a, P>0r(a, b)) then S(a, P>0r(a, b)) := S(a, P>0r(a, b)) ∪ {D} PR11 If P=1r(a, b) ∈ A, C ∈ S(b, v) with v 6= 0, ∃r.C ⊑ D ∈ T and D 6∈ S(a, v) then S(a, v) := S(a, v) ∪ {D}
This algorithm terminates in polynomial time. After termination, the completion
sets store all the information necessary to decide subsumption of concept names, as
well as checking whether an individual is an instance of a given concept name [
The msc was first investigated for EL-concept descriptions and w.r.t. unfoldable TBoxes
and possibly cyclic ABoxes in [
C ⊓ ∃r.(C ⊓ ∃r.(C ⊓ ∃r.(C ⊓ · · ·
and cannot be expressed by a finite concept description. For cyclic TBoxes it has been
shown in [
To avoid infinite nestings in presence of cyclic ABoxes it was proposed in [
The role-depth of a concept description C (denoted rd(C)) is the maximal number of nested quantifiers of C. Now we can define the msc with limited role-depth for EL. Definition 2 (role-depth bounded EL-msc). Let K =(T , A) be an EL-KB and a an individual in A and k ∈ IN. Then the EL-concept description C is the role-depth bounded EL-most specific concept of a w.r.t. K and role-depth k (written k-mscK(a)) iff 1. rd(C) ≤ k, 2. K |= C(a), and 3. for all EL-concept descriptions E with rd(E) ≤ k holds: K |= E(a) implies
C ⊑T E.
Please note that in case the exact msc has a role-depth less than k the role-depth bounded msc is the exact msc. 4.1
The computation of the msc relies on a characterization of the instance relation. While
in earlier works this was given by homomorphism [
Definition 3 (traversal concept). Let K be an EL-KB, K′′ be its normalized form, SK the completion set obtained from K and k ∈ IN. Then the traversal concept of a named concept A (denoted k-CSK (A)) with sig(A) ⊆ sig(K′′) is the concept obtained from executing the procedure call traversal-concept-c(A, SK, k) shown in Algorithm 1.
The traversal concept of an individual a (denoted k-CSK (a)) with a ⊆ sig(K) is the concept description obtained from executing the procedure call traversal-concept-i(a, SK, k) shown in Algorithm 1.
The idea is that the traversal concept of an individual yields its msc. However, the traversal concept contains names from sig(K′′) \ sig(K), i.e., concept names that were introduced during normalization – we call this kind of concept names normalization names in the following. The returned msc should be formulated w.r.t. the signature of the original KB, thus the normalization names need to be removed or replaced. Algorithm 1 Computation of a role-depth bounded EL-msc.
Procedure k-msc (a, K, k) Input: a: individual from K; K =(T , A) an EL-KB; k ∈ IN Output: role-depth bounded EL-msc of a w.r.t. K and k. 1: (T ′, A′) := simplify-ABox(T , A) 2: K′′ := (normalize(T ′), A )
′ 3: SK := apply-completion-rules(K) 4: return Remove-normalization-names ( traversal-concept-i(a, SK, k))
Input: a: individual name from K; S: set of completion sets; k ∈ IN Output: role-depth traversal concept (w.r.t. K) and k. 1: if k = 0 then return dA ∈ S(a) A 2: else return dA ∈ S(a) A ⊓
d d r∈RN(K′′) A ∈ CN(K′′)∩S(a,r)
d d ∃r. traversal-concept-i (b, S, k − 1) r∈RN(K′′) b ∈ IN(K′′)∩S(a,r) ∃r. traversal-concept-c (A, S, k − 1) ⊓ 3: end if
Input: A: concept name from K′′; S: set of completion sets; k ∈ IN Output: role-depth bounded traversal concept. 1: if k = 0 then return dB∈S(A) B 2: else return d B ⊓ d d
B∈S(A) r∈RN(K′′) B∈S(A,r) 3: end if ∃r.traversal-concept-c (B, S, k − 1) Lemma 1. Let K be an EL-KB, K′′ its normalized version, SK be the set of completion sets obtained for K, k ∈ IN a natural number and a ∈ IN(K). Furthermore let C = kCSK (a) and Cb be obtained from C by removing the normalization names. Then
K′′ |= C(a) iff K |= Cb(a).
This lemma guarantees that removing the normalization names from the traversal
concept preserves the instance relationships. Intuitively, this lemma holds since the
construction of the traversal concept conjoins exhaustively all named subsumers and all
subsuming existential restrictions to a normalization name up to the role-depth bound.
Thus removing the normalization name does not change the extension of the
conjunction. The proof can be found in [
The procedure k-msc has an individual a from a knowledge base K, the knowledge base K itself and number k for the role depth-bound as parameter. It first performs the two normalization steps on K, then applies the completion rules from Figure 2 to the normalized KB K′′ and stores the set of completion sets in SK. Afterwards it computes the traversal-concept of a from SK w.r.t. role-depth bound k. In a post-processing step it applies Remove-normalization-names to the traversal concept.
Obviously, the concept description returned from the procedure k-msc has a roledepth less or equal to k. Thus the first condition of Definition 2 is fulfilled. We prove next that the concept description obtained from k-msc fulfills the second condition from Definition 2.
Lemma 2. Let K = (T , A) be an EL-KB and a an individual in A and k ∈ IN. If C = k-msc(a, K, k), then K |= C(a).
The claim can be shown by induction on k. Each name in C is from a completion set of
(1) an individual or (2) a concept, which is connected via existential restrictions to an
individual. The full proof can be found in [
Lemma 3. Let K = (T , A) be an EL-KB and a an individual in A and k ∈ IN. If C = k-msc(a, K, k), then for all EL-concept descriptions E with rd(E) ≤ k holds: K |= E(a) implies C ⊑T E.
Again, the full proof can be found in [
Theorem 1. Let K = (T , A) be an EL-KB and a an individual in A and k ∈ IN. Then k-msc(a, K, k) ≡ k-mscK(a).
The k-msc can grow exponential in the size of the knowledge base. 4.2
c In order to compute the msc, we simply accumulate all concepts to which the individual a belongs, given the information in the completion sets. This process needs to be done recursively in order to account for both, the successors of a explicitly encoded in the ABox, and the nesting of existential restrictions masked by normalization names. In the following we use the abbreviation S>0(a, r) := Sv∈V \{0} S(a, r, v). We then define traversal-concept-i(a, S, k) as
l B∈S(a,0)
B ⊓
l ` l r∈RN(K′′) r(a,b)∈K′′ l l l B∈CN(K′′)∩S(a,r,0) B∈CN(K′′)∩S(a,r,1) B∈CN(K′′)∩S>0(a,r)
∃r.traversal-concept-i(b, S, k − 1) ⊓ ∃r.traversal-concept-c(B, S, k − 1) ⊓ P=1(∃r.traversal-concept-c(B, S, k − 1)) ⊓
P>0(∃r.traversal-concept-c(B, S, k − 1))´, where traversal-concept-c(B, S, k + 1) is
l C∈S0(B,0)
B ⊓ l ` l r∈RN C∈S0(B,r,0)
∃r.traversal-concept-c(C, S, k) ⊓ C∈S0(B,r,1) l l C∈S0>0(B,r)
P=1(∃r.traversal-concept-c(C, S, k)) ⊓
P>0(∃r.traversal-concept-c(C, S, k))´
and traversal-concept-c(B, S, 0) = dC∈S0(B,0) B. Once the traversal concept has been
computed, it is possible to remove all normalization names preserving the instance
relation, which gives us the msc in the original signature of K. The proof can be found
in [
Theorem 2. Let K a Prob-E Lc01-knowledge base, a ∈ IN(A), and k ∈ IN; then Remove-normalization-names(traversal-concept-i(a, S, k)) ≡ k-mscK(a). 5 In this paper we have presented a practical method for computing the role-depth bounded msc of EL concepts w.r.t. a general TBox. Our approach is based on the completion sets that are computed during realization of a KB. Thus, any of the available implementations of the EL completion algorithm can be easily extended to an implementation of the (approximative) msc computation algorithm. We also showed that the same idea can be adapted for the computation of the msc in the probabilistic DL Prob-E L01 c .
Together with the completion-based computation of role-depth limited (least)
common subsumers given in [
c -KBs. This approach yields a practical method to compute commonalities for differing observations regarding individuals. To the best of our knowledge this has not been investigated for DLs that can express uncertainty.