A description graph is a directed graph that has labeled vertices and edges. This document proposes a method for extracting a knowledge base from a description graph. The technique is presented for the description logic ALEQRSelf, which allows for conjunctions, primitive negations, existential restrictions, value restrictions, qualified number restrictions, existential self restrictions, general concept inclusions, and complex role inclusions. Furthermore, also sublogics may be chosen to express the axioms in the knowledge base. The extracted knowledge base entails exactly all those statements that can be expressed in the chosen description logic and are encoded in the input graph.
There have been several approaches towards the combination of description logics
[
In the following text we provide a method to compute a knowledge base for concept and role inclusions holding in an ALEQRSelf -interpretation or description graph, respectively, which entails all knowledge that is encoded in the interpretation/graph and can be expressed in ALEQRSelf . For this purpose we need the notion of a model-based most-specific concept description. It is defined as a concept description which describes a given individual x, i.e., the individual is an instance of the concept, and is most specific w.r.t. this property, i.e., for all concept descriptions C that have x as an individual, the most-specific concept is subsumed by C. Since we do not want to use greatest fixpoint semantics here, we restrict the role-depth to ensure existence of most-specific concepts. The description logic ALEQRSelf is chosen for knowledge representation here, since it is an expressive description logic that does not allow for disjunctions (like ALC), and hence will not model the examples in the input graph too exactly.
We start with a short introduction of the description logic ALEQRSelf . Then we define description graphs, and show their equivalence to interpretations. Furthermore, we then present model-based most-specific concept descriptions, and their relationships to formal concept analysis. We then continue with induced concept contexts and induced role contexts, and eventually utilize them to construct the desired knowledge base.
Please note that many of the results on model-based most-specific concept
descriptions, induced concept contexts, and bases of general concept inclusions, have already
been observed and proven by Baader and Distel [
The Description Logic ALEQR
Self Let (NC, NR) be a signature, i.e., NC is a set of concept names, and NR is a set of role names, such that NC and NR are disjoint. We stick to the usual notations and hence concept names are written as upper-case latin letters, e.g., A and B, and role names are written as lower-case latin letters, e.g., r and s. An interpretation over (NC, NR) is a tuple I = (DI , I ) where DI is a non-empty set, called domain, and I is an extension function that maps concept names A 2 NC to subsets AI DI and role names r 2 NR to binary relations rI DI DI .
The set of all ALEQRSelf -concept descriptions is denoted by ALEQRSelf (NC, NR), and is inductively defined as follows. Every concept name A 2 NC, the bottom concept ?, and the top concept >, is an atomic ALEQRSelf -concept description. If A 2 NC is a concept name, r 2 NR is a role name, C, D 2 ALEQRSelf (NC, NR) are concept descriptions, and n 2 N+ is a positive integer, then :A, C u D, 9 r. C, 8 r. C, n. r. C, n. r. C, and 9 r. Self, are complex ALEQRSelf -concept descriptions. The extension function of an interpretation I is canonically extended to all ALEQRSelf -concept descriptions as shown in the semantics column of Figure 1.
Note that every individual without any r-successors in the interpretation I at all is an element of the extension of every value restriction 8 r. C for arbitrary concept descriptions C. We use the usual notation Xk for the set of all subsets of X with exactly k elements. It is well-known that X k = jXk j .
Furthermore, ALEQRSelf allows to express the following terminological axioms. If A is a concept name, and C, D are concept descriptions, then C v D is a (general) concept inclusion (abbr. GCI), and A C is a concept definition. Of course, every concept definition A C can be simulated by two concept inclusions A v C and C v A. If r, r1, . . . , rn, s are role names, then r v s is a simple role inclusion, and r1 . . . rn v s is a complex role inclusion, also called role inclusion axiom (abbr. RIA). We then say that an interpretation I is a model of an axiom a, denoted as I j= a, if the condition in the name bottom concept top concept primitive negation conjunction existential restriction value restriction qualified number
restriction self restriction syntax C ? > :A C u D semantics column of Figure 2 is satisfied. An axiom is generally valid if all interpretations are models of it. If C v D is generally valid, then we denote this by C v D, too, and say that C is subsumed by D, C is a subsumee of D, and D is a subsumer of C.
A TBox is a set of concept inclusions and concept definitions, and a RBox is a set of role inclusions. I is a model of a TBox T , denoted as I j= T , if I is a model of all axioms a 2 T , and analogously for RBoxes R. A knowledge base K is a pair (T , R) of a TBox T and a RBox R.
name concept inclusion concept definition simple role inclusion complex role inclusion syntax a C v D A
C r v s semantics I j= a
AI = CI CI rI
DI sI r1 r2 . . . rn v s rI rI . . . rI 1 2 n sI (sound) All axioms in K hold in I, i.e., I j= K. (complete) All axioms that hold in I, are entailed by K, i.e., I j= a ) K j= a. (irredundant) None of the axioms in K follows from the others, i.e., K n fag 6j= a for all a 2 K.
The semantics of ALEQRSelf can also be characterized by means of description graphs, which are cryptomorphic to interpretations. A description graph over (NC, NR) is a tuple G = (V, E, `), such that the following conditions hold. 1. (V, E) is a directed graph, i.e., V is a set of vertices, and E V V is a set of directed edges on V. For an edge (v, w) 2 E we say that v and w are connected, v is the source vertex, and w is the target vertex of (v, w). 2. ` = `V [˙ `E is a labeling function where `V : V ! 2NC maps each vertex v 2 V to a label set `V(v) NC, and `E : E ! 2NR maps each edge (v, w) 2 E to a label set `E(v, w) NR.
The vertices of the graph G are labeled with subsets of NC to indicate the concept names they belong to. Analogously, the edges are labeled with subsets of NR to allow multiple (named) relations between the same two vertices in the graph. Usually, one would also specify a root vertex v0 2 V for description graphs, but this is not necessary for our purposes here.
A description graph may also be called folksonomy or social network here. For example, the set NR of role names in the signature may contain a relation friend that connects friends in a social network (graph). Other relations are for example isMarriedWith, sentFriendrequestTo, likes, follows, and hasAttendedEvent, with their obvious meaning. The vertices in a social network are of course the users (and possibly other objects). The vertex labels in the set NC of concept names can be used to categorize the users in a social network, e.g., by nationality, sex, marital status, profession, etc.
For each description graph G = (V, E, `) we define a canonical interpretation IG that contains all information that is provided in G as follows. The domain is just the vertex set, i.e., DIG := V, and the extensions of concept names A 2 NC, and of role names r 2 NR, respectively, are given as follows.
AIG := `V1(A) = f v 2 V j A 2 `(v) g rIG := `E 1(r) = f (v, w) 2 E j r 2 `(v, w) g
Furthermore, we can easily construct a description graph GI from an interpretation I = (DI , I ) by setting GI := (V, E, `) where
V := DI E := [ rI r2NR
`V(v) := n A 2 NC v 2 AI o `E(v, w) := n r 2 NR (v, w) 2 rI o .
It can be readily verified that both transformations are mutually inverse, i.e., IGI = I for all interpretations I, and GIG = G for all description graphs G.
As a consequence, we do not have to distinguish between interpretations and description graphs, and we may also compute model-based most-specific concept descriptions (which are usually defined for individuals of an interpretation, cf. next section) for vertices in description graphs. In the following we want to propose a method to compute a knowledge base K = (T , R) from a given description graph G that entails all knowledge that is encoded in G and is expressible in the description logic ALEQRSelf .
The role depth rd(C) of a concept description C is defined as the greatest number of roles in a path in the syntax tree of C. Formally, we inductively define the role depth as follows. 1. Every atomic concept description A, ?, >, and every primitive negation :A, has role depth 0. 2. The role depth of a conjunction is the maximum of the role depths of the conjuncts, i.e., rd(C u D) := rd(C) _ rd(D) for all concept descriptions C and D. 3. The role depth of a restriction is the successor of the role depth of the concept description in the restriction’s body, i.e., rd(Q r. C) := 1 + rd(C) for all quantifiers Q 2 f9, 8, n, ng, role names r 2 NR, and concept descriptions C. 4. The role depth of a self restriction is just defined as 1, i.e., rd(9 r. Self) := 1. It is easy to see that the role-depth of a concept description is well-defined. However, equivalent concept descriptions do not necessarily have the same role depth. For example the concept description ? and 9r.? are equivalent, but the former concept description has role depth 0 and the latter has role depth 1.
Definition 2 (Model-Based Most-Specific Concept Description). Let (NC, NR) be a signature, I = (DI , I ) an interpretation over (NC, NR), d 2 N a role-depth bound, and X DI a subset of the interpretation’s domain. Then an ALEQRSelf -concept description C is called a model-based most-specific concept description (abbr. mmsc) of X w.r.t. I and d if it satisfies the following conditions.
CI .
DI it holds that C v D. ments hold for all subsets X, Y with a role-depth d.
Since all model-based most-specific concept descriptions of X w.r.t. I and d are unique up to equivalence, we speak of the mmsc, and denote it by XId . Lemma 3. Let I be an interpretation over the signature (NC, NR). Then the following stateDI , and concept descriptions C, D 2 ALEQRSelf (NC, NR)
5. C w CIId . 7. CI = CIIdI .
DI .
It then follows that IId is a closure operator on the concept description poset (ALEQRSelf (NC, NR), w) factorized by concept equivalence, and a concept inclusion C v D holds in I if, and only if, the implication C ! D holds in the closure operator IId . It follows that there is a (finite) canonical base of concept inclusions holding in a (finite) interpretation I. Definition 4 (Least Common Subsumer). Let C, D be ALEQRSelf -concept descriptions w.r.t. the signature (NC, NR). Then a concept description E 2 ALEQRSelf (NC, NR) is called a least common subsumer (abbr. lcs) of C and D if the following conditions are fulfilled.
2. Whenever F is a common subsumer of C and D, then F subsumes E, i.e., C v F and
D v F implies E v F for all concept descriptions F 2 ALEQRSelf (NC, NR).
It follows that least common subsumers are always unique up to equivalence. Hence, we can speak of the lcs of two concept descriptions, and furthermore we denote it by lcs(C, D) or C t D. The definition can be canonically extended to an arbitrary number of concept descriptions, and we then write lcs(C1, . . . , Cn) or Fn i=1 Ci for the least common subsumer of the concept descriptions C1, . . . , Cn.
C D v v
C t D v v v
E
Lemma 5. Let (Xt)t2T be a family of subsets Xt DI , and (Cs)s2S a family of concept descriptions Cs 2 ALEQRSelf (NC, NR). Then the following statements hold. 1. (St2T Xt)Id 2. (ds2S Cs)I = Ts2S CsI
F t2T
XId
t
d, then also
Beforehand we have observed a pair of mappings that has similar properties like the well-known galois connection which is induced by a formal context. More specifically, the pair ( Id , I ) is an adjunction. Consequently, we adapt the notions of a formal concept and a formal concept lattice as follows.
Definition 7 (Description Concept). Let I be a finite interpretation over the signature (NC, NR), and d 2 N a role-depth bound.
A description concept of I and d is a pair (X, C) that consists of a subset X DI , and an ALEQRSelf -concept description over (NC, NR), such that X is the extension CI , and C is the model-based most-specific concept description XId . Furthermore, we call X the extent, and C the intent of (X, C). The set of all description concepts of I and d is denoted as B(I, d). Analogously, Ext(I, d) and Mmsc(I, d) denote the sets of all extents and intents, respectively.
To ensure formal correctness, we require that B(I, d) only contains at most one description concept with the extent X. This is no limitation as we will see in the next lemma that all description concepts with the same extent have equivalent intents. Definition 8 (Subconcept, Superconcept, Description Concept Lattice). Let (X, C) and (Y, D) be two description concepts. Then (X, C) is a subconcept of (Y, D) if X Y holds. We then also write (X, C) (Y, D), and call (Y, D) a superconcept of (X, C).
Additionally, the pair B(I, d) := (B(I, d), ) is called description concept lattice of I and d.
Lemma 9 (Order on Description Concepts). Let I be a finite interpretation over the signature (NC, NR), and d 2 N a role-depth bound.
(X, C) (Y, D) , X Y , C v D.
is an order on B(I, d).
We may furthermore observe that the set of all description concepts with the given order is a complete lattice.
Definition 10 (Description Lattice). Let I be a finite interpretation over the signature (NC, NR), and d 2 N a role-depth bound. Then B(I, d) is a complete lattice whose infima and suprema are given by the following equations.
0 0
t2T [ Xt t2T l Ct t2T !IdI !IId 1
A 1 , G CtA t2T
A description lattice is a nice visualization of the information provided in a description graph or in an interpretation, respectively. Since interpretations and description graphs are cryptomorphically defined, we do not need to further distinguish between them. One can think of description lattices as a natural generalization of concept lattices which do not only allow conjunctions of attributes as intents, but also more complex concept descriptions that can be expressed in the underlying description logic. Of course, if the chosen description logic is L0, i.e., only allows for conjunctions u, then the concept lattices and description lattices w.r.t. L0 coincide. However, for more complex description logics like EL or FLE or extensions thereof, we can further involve roles in the intents of the description concepts which adds further expressivity.
There is also a strong correspondence to the pattern structures and their lattices that
have been introduced by Ganter and Kuznetsov [
Definition 11 (Induced Context). Let I be an interpretation, and M a set of concept descriptions, both over the signature (NC, NR). Then the induced context of I and M is defined as the formal context KI,M := DI , M, I , where the incidence I is defined via (x, C) 2 I if, and only, if x 2 CI . For a concept description C over (NC, NR) its projection (C) := f D 2 M j C v D g. A concept description C is expressible itno MtermissdoeffinMed aifsCpM d U for a subset U M. We have d Æ = > and d U = dC2U C for all subsets Æ 6= U M.
Lemma 12. Let I be an interpretation, and M a set of concept descriptions. Then the following statements hold for all subsets X, Y M, and all concept descriptions C, D.
Lemma 13. Let KI,M be an induced context. Then the following statements hold for all concept descriptions C over (NC, NR), all subsets U M, and X DI . 4. pM (d U)II
= UII 5. C d pM(C) if C is expressible in terms of M. 6. CI = pM(C)I if C is expressible in terms of M. 7. U = pM (d U) if U is an intent of KI,M.
The next lemma tells us that we can directly decide in the induced context K ,M, I whether a concept inclusion between conjunctions of concept descriptions of M holds in the given interpretation I.
Lemma 14 (Implications and concept inclusions). Let I be an interpretation, and M a set of concept descriptions, both over the signature (NC, NR). Then for all subsets X, Y M, the concept inclusion d X v d Y holds in I if, and only if, the implication X ! Y holds in Definition 15 (Approximation). Let I be an interpretation over the signature (NC, NR), d 2 N a role-depth bound, and C 2 ALEQRSelf (NC, NR) a concept description with its normal form dA2U A u d(Q,r,D)2P Q r. D. Then the approximation of C w.r.t. I and d is defined as the concept description bCcI,d := l A u A2U
l (Q,r,D)2P
Lemma 16. For all concept descriptions C, D, and role names r, the following statements hold. 1. (CIId u D)I = (C u D)I . 2. (Q r. CIId )I = (Q r. C)I for all quantifiers Q 2 f9, 8, n, ng.
CIId v bCcI,d v C.
Lemma 18. Let I be an interpretation, and d 2 N a role-depth bound. Define 8 >> 9 r. XId 1, > > >>> 8 r. XId 1, < > > > > > > > : 9 r. Self n. r. XId 1, m. r. XId 1,
MI,d := f ? g [ f A, :A j A 2 NC g [ context KCI,d := KI,MI,d of I and MI,d.
Then every model-based most specific concept description of I with role-depth d is expressible in terms of MI,d. Furthermore, the induced context of I and d is defined as the induced Lemma 19 (Intents and MMSCs). Let I be an interpretation over (NC, NR), and KI,d its induced context w.r.t. the role-depth bound d 2 N. Then the following statements hold for all subsets U MI,d, and concept descriptions C over (NC, NR). 1. (d U)IId d UII. 2. If U is an intent of KI,d, then d U is a mmsc of I with role-depth d. 3. If C is a mmsc of I with role-depth d, then pMI,d (C) is an intent of KI,d.
Consequently, the mapping d : MI,d ! ALEQRSelf (NC, NR) is an isomorphism from the intent-lattice (Int(KI,d), \) to the mmsc-lattice (Mmsc(I, d), t), and has the inverse pMI,d . This shows the strong correspondence between the formal concept lattice of KI,d and the description concept lattice of I w.r.t. role depth d. We can infer the following corollary from Lemmata 12 and 19.
Corollary 20. The intent lattice of KI,d is isomorphic to the mmsc lattice of I, d.
We can further observe that the concept inclusions holding in I and the implications holding in KI,d are also in a strong correspondence. We can show that whenever the implication U ! V holds in KI,d, then also the concept inclusion d U v d V holds in I. Furthermore, since every mmsc of I with a role depth d is expressible in terms of MI,d, and conjunctions of intents of KI,d are exactly the mmscs of I, and every concept inclusion C v D holding in I is entailed by the concept inclusion C v CII , we can deduce that indeed every concept inclusion holding in I is entailed by the transformation of the canonical implicational base of KI,d, which consists of all GCIs that have a conjunction of a pseudo-intent as premise and the conjunction of the closure of the pseudo-intent as conclusion.
Lemma 21. Let I be an interpretation over the signature (NC, NR), d 2 N a role-depth bound, and C v D a concept inclusion, such that both concepts C, D have a role-depth d. (id, I )
p1 ( I, id) I Int(KI,d)
Ext(KI,d) I
Id pM d
p1 (id, Id ) I
p2 Mmsc(I, d)
B(I, d) ( I , id) 1. If D is expressible in terms of MI,d, and the implication pMI,d (C) ! pMI,d (D) holds in KI,d, then the concept inclusion C v D holds in I. 2. If C is expressible in terms of MI,d, and the concept inclusion C v D holds in I, then the implication pMI,d (C) ! pMI,d (D) holds in KI,d.
Corollary 22 (Concept Inclusion Base). Let I be an interpretation over the signature (NC, NR), and d 2 N a role-depth bound. Then the following statements hold: 1. For all subsets X, Y MI,d, the implication X ! Y holds in KI,d if, and only if, the concept inclusion d X v d Y holds in I. 2. The intents of KI,d are exactly the model-based most-specific concept descriptions of I with role-depth bound d. 3. If L is an implicational base for KI,d, then d L := f d X v d Y j X ! Y 2 L g is a sound and complete TBox for all concept inclusions holding in I, d. Especially this holds for the following TBox.
n l P v l PII
P is a pseudo-intent of KI,d o 6
Role contexts have been introduced by Zickwolff [
Definition 23 (Induced Role Context). Let I be an interpretation over the signature (NC, NR), and d 2 N a role depth bound. Furthermore, assume that X = f x0, x1, . . . , xd g is a set of d + 1 variables. Then the induced role context for I and d is defined as KIR,d :=
DI
X , X
NR
X, J where ( f , (x, r, y)) 2 J if, and only if, ( f (x), f (y)) 2 rI .
Lemma 24 (Role Inclusions and Implications). Let I be an interpretation over (NC, NR), d 2 N a role-depth bound, and n d. Then the complex role inclusion r1 r2 . . . rn v s holds in I if, and only if, the implication f (x0, r1, x1), (x1, r2, x2), . . . , (xn 1, rn, xn) g ! f (x0, s, xn) g holds in the induced role context KIR,d.
In particular, we are only interested in implications whose premise contains a subset of the form f (x0, r1, x1), (x1, r2, x2), . . . , (xk 1, rk, xk) g. Hence, we define a constraining closure operator fR on the attribute set X NR X of the induced role context as follows.
fR(B) := 8 > > ><B > > >:B [ f (x0, r, x1) j r 2 NR g if 9k 2 N+9r1, r2, . . . , rk 2 NR
X 9 f x0, x1, . . . , xk g 2 k+1 : f (x0, r1, x1), . . . , (xk 1, rk, xk) g otherwise.
We shall now formulate a base of all complex role inclusions holding in an
interpretation. For this purpose, we refer to [
By means of the results of the previous Sections 5 and 6 we are now ready to formulate a knowledge base for an interpretation I, or for a description graph G, respectively. Beforehand, it is necessary to inspect the interplay of role and concept inclusions to ensure irredundancy of the knowledge base. First, we list some trivial concept inclusions that hold in all interpretations.
8 > > > > > > > < > > > > > > > : RI,d := r1 r2 . . . rk v s 9X ! Y 2 L 9r1, r2, . . . , rk, s 2 NR
X 9 f x0, x1, . . . , xk g 2 k+1 : X Y 3 (x0, s, xk) > > f (x0, r1, x1), (x1, r2, x2), . . . , (xk 1, rk, xk) g>>> > > ; Lemma 26. Let m, n 2 N+ be non-negative integers with n < m, r 2 NR a role name, and C a concept description. The following general concept inclusions hold in every interpretation I.
A u :A v ? 9 r. Self u 8 r. C v C
9 r. Self u C v 9 r. C 9 r. Self u C u
1. r. C v 8 r. C n. r. C u 8 r. D v 9 r. C u 8 r. D v 9 r. (C u D)
n. r. (C u D) n. r. C u 8 r. D v n. r. (C u D)
Please note that there are no direct subsumptions between existential restrictions 9 r. C and value restrictions 8 r. C, i.e., both 9 r. C v 8 r. C and 8 r. C v 9 r. C do not hold. There is also a crossover between both constructors existential restriction and value restriction. The constructor is denoted by 89, and has the semantics (89 r. C)I := (9 r. C)I \ (8 r. C)I , i.e., a domain element is in the extension of 89 r. C if, and only if, there is an r-successor in C, and all r-successors are in C.
The next two lemmata show us which concept inclusions can be inferred from known role inclusions.
Lemma 27. Let I be a model of the role inclusion axiom r v s, C an arbitrary concept description, Q1 2 f 9, n g, Q2 2 f 8, n g, and n 2 N+. Then I is also a model of the following general concept inclusions.
Q1 r. C v Q1 s. C 9 r. Self v 9 s. Self
Q2 s. C v Q2 r. C Lemma 28. Let I be a model of the complex role inclusion r1 r2 . . . rk v s, C an arbitrary concept description, Q1 2 f 9, n g, Q2 2 f 8, n g, and n 2 N+. Then I is also a model of the following concept inclusions.
9 r1. 9 r2. . . . Q1 rk. C v Q1 s. C
Q2 s. C v 8 r1. 8 r2. . . . Q2 rk. C
As final step we use the trivial concept inclusions and concept inclusions that are entailed by valid role inclusions to define some background knowledge for the computation of the canonical implicational base of the induced concept context which is trivial in terms of description logics, but not for formal concept analysis due to their different semantics.
Theorem 29 (Knowledge Base). Let I be an interpretation over the signature (NC, NR), and d 2 N a role-depth bound. Furthermore, assume that L is an implicational base of the induced concept context KCI,d w.r.t. the background knowledge SI := f C g ! f D g
C, D 2 MI,d,
C v D [ [ f f A, :A g ! MI,d j A 2 NC g 8 n > > > > <> n 9 r. XId 1, 8 r. YId 1 o ! n. r. XId 1, 8 r. YId 1 o ! n 9 r. ZId 1 o , n n n. r. ZId 1 o , m. r. ZId 1 o , 1 f 9 r. Self g ! f 9 s. Self g n. s. XId 1 o , m. r. XId 1 o , Æ 6= X
DI r, s 2 NR, r v s 2 R, 1 m < n
DI , 9 > > > > > > > > > > =
. > > > > > > > > > > ; [ >>>> n > : 8 > > > > > > > > > > < n > >>>> n > > > > > : Then KI,d = (TI,d, RI,d) is a knowledge base for I where TI,d := d L holds as in Corollary 22, and RI,d is defined as in Theorem 25. 8
If only a lower expressivity of the underlying description logic is necessary, then one could also use EL, FLE, or extensions thereof with role hierarchies H, or complex role inclusions R. All of the previous results are still valid, however one has to remove some of the used concept descriptions that are not expressible in the chosen description logic. Figure 5 gives an overview on description logics that have a lower expressivity than ALEQRSelf , and could also be used for knowledge acquisition. 8.1
Role Hierarchies H instead of Complex Role Inclusions R In the special case of simple role inclusions provided by the extension H it is not necessary to use the induced role context. We can directly extract the role hierarchy from the interpretation I, or the description graph G, respectively, as follows.
First, we want to extract a minimal RBox RI from the interpretation that entails all role inclusion axioms holding in I. We therefore define an equivalence relation
I on the role names as follows: r I s if, and only if, rI = sI . Then let NRI be a set of representatives of this equivalence relation, i.e., NRI \ [r] = 1 for all role I names r 2 NR. Then add the following role equivalence axioms to RI : For each constructor
EL FL0 FLE ALE
Q
Self
H
R representative role r 2 NRI , add the axioms r s for all s 2 [r]
n frg. Furthermore, I define an order relation vI on the representatives NRI by r vI s if, and only if, rI sI . Let I be the neighborhood relation of vI , then add the role inclusion axioms r v s for each pair r I s to the RBox RI . Obviously, the constructed RBox is minimal w.r.t. the property to entail all valid role inclusion axioms holding in the interpretation I. Eventually, the RBox in KI is defined as follows.
RI := f r s j r 2 NRI , s 2 [r]
I n f r g g [ f r v s j r, s 2 NRI , r
I s g 9
We have provided an extension of the results of Baader and Distel [