Extracting ALEQRSelf -Knowledge Bases from Graphs Francesco Kriegel Institute of Theoretical Computer Science, TU Dresden, Germany francesco.kriegel@tu-dresden.de http://lat.inf.tu-dresden.de/˜francesco Abstract. 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 re- strictions, 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. Keywords: Description Logics · Formal Concept Analysis · Terminological Learning · Knowledge Base · General Concept Inclusion · Canonical Base · Most- Specific Concept Description · Interpretation · Description Graph · Folksonomy · Social Network 1 Introduction There have been several approaches towards the combination of description logics [5] and formal concept analysis [12] for knowledge acquisition, knowledge exploration, and knowledge completion. Rudolph [19] invented a method for the exploration of con- cept inclusions holding in an FLE -interpretation. Baader, Ganter, Sattler, and Sertkaya, [3, 4, 20] provided a technique for completion of knowledge bases. Furthermore, Baader and Distel [1, 2, 9] gave a method for computing a finite base of all concept inclusions holding in a finite EL-interpretation by means of the Duquenne-Guiges-base [13] of a so-called induced formal context. Finally, Borchmann [6–8] extended the results by defining the notion of confidence for concept inclusions, and utilized the Luxenburger-base [16–18] of the induced formal context to formulate a base for the concept inclusions whose confidence exceeds a given threshold. 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, re- spectively, 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 spe- cific 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 2 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 de- fine 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 descrip- tions, induced concept contexts, and bases of general concept inclusions, have already been observed and proven by Baader and Distel [1, 2, 9] for the light-weight descrip- tion logic EL⊥ w.r.t. greatest fixpoint semantics, which allows for the bottom concept, conjunctions, existential restrictions, and general concept inclusions. Their results are extended to the additional concept constructors of ALEQRSelf , and furthermore we also take complex role inclusions into account. 2 The Description Logic ALEQRSelf 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 = (∆I , ·I ) where ∆I is a non-empty set, called domain, and ·I is an extension function that maps concept names A ∈ NC to subsets AI ⊆ ∆I and role names r ∈ NR to binary relations rI ⊆ ∆I × ∆I . The set of all ALEQRSelf -concept descriptions is denoted by ALEQRSelf ( NC , NR ), and is inductively defined as follows. Every concept name A ∈ NC , the bottom concept ⊥, and the top concept >, is an atomic ALEQRSelf -concept description. If A ∈ NC is a concept name, r ∈ NR is a role name, C, D ∈ ALEQRSelf ( NC , NR ) are concept descriptions, and n ∈ N+ is a positive integer, then ¬ A, C u D, ∃ r. C, ∀ r. C, ≥ n. r. C, ≤ n. r. C, and ∃ 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  ∀ 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 Xk = |Xk | . 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 α, denoted as I |= α, if the condition in the 3 name syntax C semantics CI bottom concept ⊥ ∅ top concept > ∆I primitive negation ¬A ∆I \ AI conjunction CuD CI ∩ DI existential restriction ∃ r. C { x ∈ ∆I | ∃y ∈ ∆I : (x, y) ∈ rI ∧ y ∈ CI } value restriction ∀ r. C { x ∈ ∆I | ∀y ∈ ∆I : (x, y) ∈ rI → y ∈ CI } { x ∈ ∆I | ∃Y ∈ ∆n : { x } × Y ⊆ rI ∧ Y ⊆ CI }  I qualified number ≥ n. r. C { x ∈ ∆I | ∀Y ∈ n∆+1 : { x } × Y ⊆ rI → Y 6⊆ CI }  I restriction ≤ n. r. C self restriction ∃ r. Self { x ∈ ∆I | (x, x) ∈ rI } Fig. 1. Concept Constructors of ALEQRSelf 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 |= T , if I is a model of all axioms α ∈ T , and analogously for RBoxes R. A knowledge base K is a pair (T , R) of a TBox T and a RBox R. name syntax α semantics I |= α concept inclusion CvD CI ⊆ DI concept definition A≡C AI = C I simple role inclusion rvs r I ⊆ sI complex role inclusion r1 ◦ r2 ◦ . . . ◦ rn v s r1I ◦ r2I ◦ . . . ◦ rnI ⊆ sI Fig. 2. Axiom Constructors of ALEQRSelf ◦ denotes the product operator where R ◦ S := { (x, z) | ∃y : (x, y) ∈ R ∧ (y, z) ∈ S }. Definition 1 (Knowledge Base). Let I be an interpretation. A knowledge base for I is a knowledge base K that has the following properties. (sound) All axioms in K hold in I , i.e., I |= K. (complete) All axioms that hold in I , are entailed by K, i.e., I |= α ⇒ K |= α. (irredundant) None of the axioms in K follows from the others, i.e., K \ {α} 6|= α for all α ∈ K. 4 3 Graphs 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) ∈ 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 ∈ V to a label set `V (v) ⊆ NC , and `E : E → 2NR maps each edge (v, w) ∈ 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 ∈ 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., ∆IG := V, and the extensions of concept names A ∈ NC , and of role names r ∈ NR , respectively, are given as follows. AIG := `V −1 ( A) = { v ∈ V | A ∈ `(v) } rIG := `−1 E (r) = { (v, w) ∈ E | r ∈ `(v, w) } Furthermore, we can easily construct a description graph GI from an interpretation I = (∆I , ·I ) by setting GI := (V, E, `) where V := ∆I n o `V (v) := A ∈ NC v ∈ AI rI [ E := n I o r∈ N ` E (v, w ) := r ∈ NR (v, w) ∈ r . R 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 descrip- tion 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 com- pute 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 . 5 4 Model-Based Most-Specific Concept Descriptions 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 ∈ {∃, ∀, ≥ n, ≤ n}, role names r ∈ NR , and concept descriptions C. 4. The role depth of a self restriction is just defined as 1, i.e., rd(∃ 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 ∃r.⊥ 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 = (∆I , ·I ) an interpretation over ( NC , NR ), δ ∈ N a role-depth bound, and X ⊆ ∆I 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 δ if it satisfies the following conditions. 1. C has a role depth of at most d, i.e., rd(C) ≤ δ. 2. All elements of X are in the extension of C w.r.t. I , i.e., X ⊆ CI . 3. For all concept descriptions D with rd(D) ≤ δ and X ⊆ DI it holds that C v D. Since all model-based most-specific concept descriptions of X w.r.t. I and δ are unique up to equivalence, we speak of the mmsc, and denote it by XIδ . Lemma 3. Let I be an interpretation over the signature ( NC , NR ). Then the following state- ments hold for all subsets X, Y ⊆ ∆I , and concept descriptions C, D ∈ ALEQRSelf ( NC , NR ) with a role-depth ≤ δ. 1. X ⊆ CI if, and only if, XIδ v C. 2. X ⊆ Y implies XIδ w YIδ . 3. C v D implies CI ⊆ DI . 4. X ⊆ XIδ I . 5. C w CIIδ . 6. XIδ ≡ XIδ IIδ . 7. CI = CIIδ I . It then follows that ·IIδ 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 ·IIδ . It follows that there is a (finite) canonical base of concept inclusions holding in a (finite) interpretation I . 6 Definition 4 (Least Common Subsumer). Let C, D be ALEQRSelf -concept descriptions w.r.t. the signature ( NC , NR ). Then a concept description E ∈ ALEQRSelf ( NC , NR ) is called a least common subsumer (abbr. lcs) of C and D if the following conditions are fulfilled. 1. E subsumes both C and D, i.e., C v E and D v E. 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 ∈ 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 F an arbitrary number of concept descriptions, and we then write lcs(C1, . . . , Cn ) or in=1 Ci for the least common subsumer of the concept descriptions C1, . . . , Cn . C v v v CtD E v v D Fig. 3. The least common subsumer is a pullback in the category, whose objects are concept descriptions and whose morphisms are subsumptions. Lemma 5. Let (Xt )t∈T be a family of subsets Xt ⊆ ∆I , and (Cs )s∈S a family of concept descriptions Cs ∈ ALEQRSelf ( NC , NR ). Then the following statements hold. I 1. ( t∈T Xt )Iδ ≡ t∈T Xt δ S F 2. ( s∈S Cs )I = s∈S CsI d T Lemma 6. If C v D holds in I , and both C and D have a role depth ≤ δ, then also C v CIIδ holds in I , and C v D follows from C v CIIδ . 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 (·Iδ , ·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 δ ∈ N a role-depth bound. A description concept of I and δ is a pair (X, C) that consists of a subset X ⊆ ∆I , 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 XIδ . Furthermore, we call X the extent, and C the intent of (X, C). The set of all description concepts of I and δ is denoted as B(I , δ). Analogously, Ext(I , δ) and Mmsc(I , δ) denote the sets of all extents and intents, respectively. 7 To ensure formal correctness, we require that B(I , δ) 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 , δ) := (B(I , δ), ≤) is called description concept lattice of I and δ. Lemma 9 (Order on Description Concepts). Let I be a finite interpretation over the signature ( NC , NR ), and δ ∈ N a role-depth bound. 1. For two description concepts (X, C) and (Y, D) it is true that (X, C) ≤ (Y, D) ⇔ X ⊆ Y ⇔ C v D. 2. The relation ≤ is an order on B(I , δ). 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 δ ∈ N a role-depth bound. Then B(I , δ) is a complete lattice whose infima and suprema are given by the following equations.  !IIδ  ^ \ l (Xt , Ct ) =  Xt , Ct  t∈T t∈T t∈T  !Iδ I  _ [ G (Xt , Ct ) =  Xt , Ct  t∈T t∈T t∈T A description lattice is a nice visualization of the information provided in a descrip- tion 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 [11]. Of course, the set of patterns consists of all concept descriptions that are expressible in the underlying description logic w.r.t. the given signature ( NC , NR ). The similarity operation is simply given by the least common subsumer mapping t which is the infimum in the lattice of all concept descriptions. 8 5 Induced Concept Contexts 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 := ∆I , M, I , where the incidence I is defined via (x, C) ∈ I if, and only, if x ∈ CI . For a concept description C over ( NC , NR ) its projection to M is defined as πM (d C) := { D ∈ M | C v D }. A concept d descriptiond C is expressible in terms of M if C ≡ U for a subset U ⊆ M. We have ∅ = > and U = C∈U C d 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. d 1. X ⊆ πM (C) if, and only if, C v X. d d 2. X ⊆ Y implies d X w Y. 3. C v d D implies πM (C) ⊇ πM (D). 4. dX ⊆ πM d ( X )d 5. C v πM (C). d 6. X ≡ πM ( X). 7. πM (C) = πM ( πM (C)). 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 ⊆ ∆I . 1. πM (XI ) = X I 2. ( U )I = U I d 3. CI ⊆ πM (C) I 4. πM ( U)II = U II d d 5. C ≡ πM (C) if C is expressible in terms of M. 6. CI = πM (dC) I if C is expressible in terms of M. 7. U = πM ( U ) if U is an intent of KI ,M . The next lemma tells us that we can directly decide in the induced context KI ,M , 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 d bothdover the signature ( NC , NR ). Then for all subsets X, Y ⊆ M, set of concept descriptions, the concept inclusion X v Y holds in I if, and only if, the implication X → Y holds in KI ,M . Definition 15 (Approximation). Let I be an interpretation over the signature ( NC , NR ), Self δ ∈ N a role-depth d d and C ∈ ALEQR ( NC , NR ) a concept description with its bound, normal form A∈U A u (Q,r,D)∈Π Q r. D. Then the approximation of C w.r.t. I and δ is defined as the concept description l l bCcI ,δ := Au Q r. DIIδ . A∈U (Q,r,D)∈Π Lemma 16. For all concept descriptions C, D, and role names r, the following statements hold. 9 1. (CIIδ u D)I = (C u D)I . 2. (Q r. CIIδ )I = (Q r. C)I for all quantifiers Q ∈ {∃, ∀, ≥ n, ≤ n}. Lemma 17. For every interpretation I , and every concept description C it holds that CIIδ v bCcI ,δ v C. Lemma 18. Let I be an interpretation, and δ ∈ N a role-depth bound. Define Iδ−1    ∃ r. X  ,   r ∈ N    I  ∀ r. X δ−1 ,  R ,        I MI ,δ := { ⊥ } ∪ { A, ¬ A | A ∈ NC } ∪ ≥ n. r. X δ−1 , 1 ≤ m < n ≤ ∆ , . I   ≤ m. r. XIδ−1 , ∅ 6= X ⊆ ∆I             ∃ r. Self   Then every model-based most specific concept description of I with role-depth ≤ δ is expressible in terms of MI ,δ . Furthermore, the induced context of I and δ is defined as the induced context KCI ,δ := KI ,MI ,δ of I and MI ,δ . Lemma 19 (Intents and MMSCs). Let I be an interpretation over ( NC , NR ), and KI ,δ its induced context w.r.t. the role-depth bound δ ∈ N. Then the following statements hold for all subsets U ⊆ MI ,δ , and concept descriptions C over ( NC , NR ). 1. ( U )IIδ ≡ U II . d d 2. If U is an intent of KI ,δ , then U is a mmsc of I with role-depth ≤ δ. d 3. If C is a mmsc of I with role-depth ≤ δ, then πMI ,δ (C) is an intent of KI ,δ . Consequently, the mapping : MI ,δ → ALEQRSelf ( NC , NR ) is an isomorphism d from the intent-lattice (Int(KI ,δ ), ∩) to the mmsc-lattice (Mmsc(I , δ), t), and has the inverse πMI ,δ . This shows the strong correspondence between the formal concept lattice of KI ,δ and the description concept lattice of I w.r.t. role depth ≤ δ. We can infer the following corollary from Lemmata 12 and 19. Corollary 20. The intent lattice of KI ,δ is isomorphic to the mmsc lattice of I , δ. We can further observe that the concept inclusions holding in I and the implications holding in KI ,δ are also in a strong correspondence. We can show that d whenever the implication U → V holds in KI ,δ , then also the concept inclusion U v V holds d in I . Furthermore, since every mmsc of I with a role depth ≤ δ is expressible in terms of MI ,δ , and conjunctions of intents of KI ,δ 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 ,δ , 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 ), δ ∈ N a role-depth bound, and C v D a concept inclusion, such that both concepts C, D have a role-depth ≤ δ. 10 (id, · I ) π1 B(KI ,δ ) Ext(KI ,δ ) B(I , δ) π1 (id, ·Iδ ) (· I , id) · I ·I π2 π2 ·I ·Iδ (·I , id) πM Int(KI ,δ ) Mmsc(I , δ) d Fig. 4. Overview on the isomorphisms between the extent lattice, intent lattice, and mmsc lattice of KI ,δ and I , δ, respectively. Note that Ext(KI ,δ ) = Ext(I , δ) holds. 1. If D is expressible in terms of MI ,δ , and the implication πMI ,δ (C) → πMI ,δ (D) holds in KI ,δ , then the concept inclusion C v D holds in I . 2. If C is expressible in terms of MI ,δ , and the concept inclusion C v D holds in I , then the implication πMI ,δ (C) → πMI ,δ (D) holds in KI ,δ . Corollary 22 (Concept Inclusion Base). Let I be an interpretation over the signature ( NC , NR ), and δ ∈ N a role-depth bound. Then the following statements hold: d ⊆ Md 1. For all subsets X, Y I ,δ , the implication X → Y holds in KI ,δ if, and only if, the concept inclusion X v Y holds in I . 2. The intents of KI ,δ are exactly the model-based most-specific concept descriptions of I with role-depth bound ≤ δ. 3. If L is an implicational base for KI ,δ , then L := { X v Y | X → Y ∈ L } is a d d d sound and complete TBox for all concept inclusions holding in I , δ. Especially this holds for the following TBox. nl l o Pv P II P is a pseudo-intent of KI ,δ 6 Induced Role Contexts Role contexts have been introduced by Zickwolff [21], and have been used by Rudolph [19] for gaining knowledge on binary relations or roles (that are interpreted as binary relations). We use their definition here for the deduction of complex role inclusions holding in an interpretation. Definition 23 (Induced Role Context). Let I be an interpretation over the signature ( NC , NR ), and δ ∈ N a role depth bound. Furthermore, assume that X = { x0, x1, . . . , xδ } is a set of δ + 1 variables. Then the induced role context for I and δ is defined as    X R I KI ,δ := ∆ , X × NR × X, J where ( f , (x, r, y)) ∈ J if, and only if, ( f (x), f (y)) ∈ rI . 11 Lemma 24 (Role Inclusions and Implications). Let I be an interpretation over ( NC , NR ), δ ∈ N a role-depth bound, and n ≤ δ. Then the complex role inclusion r1 ◦ r2 ◦ . . . ◦ rn v s holds in I if, and only if, the implication { (x0, r1, x1 ), (x1, r2, x2 ), . . . , (xn−1, rn , xn ) } → { (x0, s, xn ) } holds in the induced role context KIR,δ . In particular, we are only interested in implications whose premise contains a subset of the form { (x0, r1, x1 ), (x1, r2, x2 ), . . . , (xk−1, rk , xk ) }. Hence, we define a constrain- ing closure operator φR on the attribute set X × NR × X of the induced role context as follows. if ∃k ∈ N+ ∃r1, r2, . . . , rk ∈ NR     X B ∃ { x0, x1, . . . , xk } ∈ k+ 1 : φR (B) :=    { (x0, r1, x1 ), . . . , (xk−1, rk , xk ) } ⊆ B, B ∪ { (x0, r, x1 ) | r ∈ NR } otherwise.  We shall now formulate a base of all complex role inclusions holding in an inter- pretation. For this purpose, we refer to [15] for the notions of constrained implications and their bases. A φ-constrained implication over M is an implication X → Y over M such that both premise X and conclusion Y are φ-closed. A φ-constrained implicational base for a formal context K is a set of φ-constrained implications that is valid in K, and furthermore entails all φ-constrained implications that hold in K. Theorem 25 (Role Inclusion Base). Let I be an interpretation over ( NC , NR ). If L is a φR -constrained implicational base of KI ,R , then the following RBox RI ,δ is sound, complete, and irredundant, for all complex role inclusions holding in I , δ.     ∃X → Y ∈ L         ∃r1, r2, . . . , rk , s ∈ NR         X RI ,δ := r1 ◦ r2 ◦ . . . ◦ rk v s ∃ { x0, x1, . . . , xk } ∈ k+ 1 :     X ⊇ { (x0, r1, x1 ), (x1, r2, x2 ), . . . , (xk−1, rk , xk ) }          Y 3 (x0, s, xk )   7 Construction of the Knowledge Base 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. 12 Lemma 26. Let m, n ∈ N+ be non-negative integers with n < m, r ∈ NR a role name, and C a concept description. The following general concept inclusions hold in every interpretation I . A u ¬A v ⊥ ∃ r. Self u ∀ r. C v C ∃ r. Self u C v ∃ r. C ∃ r. Self u C u ≤ 1. r. C v ∀ r. C ∃ r. C u ∀ r. D v ∃ r. (C u D) ≥ n. r. C u ∀ r. D v ≥ n. r. (C u D) ≤ n. r. C u ∀ r. D v ≤ n. r. (C u D) ∃ r. C v ≥ 1. r. C ≥ n. r. C v ∃ r. C ≤ n. r. C v ≤ m. r. C ≥ m. r. C v ≥ n. r. C ≥ ∆I . r. C v C u ∀ r. C u ∃ r. Self > v ≤ ∆I . r. C Please note that there are no direct subsumptions between existential restrictions ∃ r. C and value restrictions ∀ r. C, i.e., both ∃ r. C v ∀ r. C and ∀ r. C v ∃ r. C do not hold. There is also a crossover between both constructors existential restric- tion and value restriction. The constructor is denoted by ∀∃, and has the semantics (∀∃ r. C)I := (∃ r. C)I ∩ (∀ r. C)I , i.e., a domain element is in the extension of ∀∃ 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 ∈ { ∃, ≥ n }, Q2 ∈ { ∀, ≤ n }, and n ∈ N+ . Then I is also a model of the following general concept inclusions. Q1 r. C v Q1 s. C ∃ r. Self v ∃ 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 ∈ { ∃, ≥ n }, Q2 ∈ { ∀, ≤ n }, and n ∈ N+ . Then I is also a model of the following concept inclusions. ∃ r1. ∃ r2. . . . Q1 rk . C v Q1 s. C Q2 s. C v ∀ r1. ∀ 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. 13 Theorem 29 (Knowledge Base). Let I be an interpretation over the signature ( NC , NR ), and δ ∈ N a role-depth bound. Furthermore, assume that L is an implicational base of the induced concept context KC I ,δ w.r.t. the background knowledge C, D ∈ MI ,δ ,   SI := {C} → {D} CvD ∪ { { A, ¬ A } → MI ,δ | A ∈ NC } r ∈ NR ,  n o n o  Iδ−1 Iδ−1 Iδ−1   ∃ r. X , ∀ r. Y → ∃ r. Z ,   ∅ 6= X, Y, Z ⊆ ∆I ,       n o n o   Iδ−1 Iδ−1 Iδ−1 ∪ ≥ n. r. X , ∀ r. Y → ≥ n. r. Z ,   ZIδ−1 ≡ XIδ−1 u YIδ−1 ,   n o n o  ≤ m. r. XIδ−1 , ∀ r. YIδ−1 → ≤ m. r. ZIδ−1 , 1 ≤ m < n ≤ ∆I         n o n o     ∃ r. XIδ−1 → ∃ s. XIδ−1 ,    r, s ∈ N ,   R  n o n o   I I    ∀ s. X δ−1 → ∀ r. X δ−1 ,      n o n o r v s ∈ R ,    ∪ ≥ n. r. X Iδ−1 → ≥ n. s. X Iδ−1 , 1 ≤ m < n ≤ ∆ ,. I      n o n o   I I I ≤ m. s. X → ≤ m. r. X ∅ ∆  δ−1 δ−1     , 6 = X ⊆        { ∃ r. Self } → { ∃ s. Self }   d Then KI ,δ = (TI ,δ , RI ,δ ) is a knowledge base for I where TI ,δ := L holds as in Corol- lary 22, and RI ,δ is defined as in Theorem 25. 8 Other Description Logics 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]≡I = 1 for all role names r ∈ NR . Then add the following role equivalence axioms to RI : For each 14 REFERENCES constructor EL FL0 FLE ALE Q Self H R ⊥ × > × × × × ¬A × CuD × × × × ∃ r. C × × × × ∀ r. C × × × ≥ n. r. C × ≤ n. r. C × ∃ r. Self × CvD × × × × C≡D × × × × rvs × × r1 ◦ . . . ◦ rn v s × Fig. 5. Overview on various Description Logics below ALEQRSelf representative role r ∈ NRI , add the axioms r ≡ s for all s ∈ [r]≡I \ {r}. Furthermore, 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 := { r ≡ s | r ∈ NRI , s ∈ [r]≡I \ { r } } ∪ { r v s | r, s ∈ NRI , r ≺I s } 9 Conclusion We have provided an extension of the results of Baader and Distel [1, 2, 9] for the deduction of knowledge bases from interpretations in the more expressive description logic ALEQRSelf w.r.t. descriptive semantics and role-depth bounds. Since role-depth- bounded model-based most-specific concept descriptions always exist, this technique can always be applied. Furthermore, the construction of knowledge bases has been reduced to the computation of implicational bases of formal contexts, which is a well-understood problem that has several available algorithms – for example the stan- dard NextClosure algorithm from Ganter [10], or the parallel algorithm that has been introduced in [15] and implemented in [14]. The presented methods are prototypically implemented in Concept Explorer FX [14]. References [1] Franz Baader and Felix Distel. “A Finite Basis for the Set of EL-Implications Holding in a Finite Model”. In: Formal Concept Analysis, 6th International Con- ference, ICFCA 2008, Montreal, Canada, February 25-28, 2008, Proceedings. Ed. by REFERENCES 15 Raoul Medina and Sergei A. Obiedkov. Vol. 4933. Lecture Notes in Computer Science. Springer, 2008, pp. 46–61. [2] Franz Baader and Felix Distel. “Exploring Finite Models in the Description Logic ELgfp”. In: Formal Concept Analysis, 7th International Conference, ICFCA 2009, Darmstadt, Germany, May 21-24, 2009, Proceedings. Ed. by Sébastien Ferré and Sebastian Rudolph. Vol. 5548. Lecture Notes in Computer Science. Springer, 2009, pp. 146–161. [3] Franz Baader and Bariş Sertkaya. “Applying Formal Concept Analysis to De- scription Logics”. In: Concept Lattices, Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings. Ed. by Peter W. Eklund. Vol. 2961. Lecture Notes in Computer Science. Springer, 2004, pp. 261–286. [4] Franz Baader et al. Completing Description Logic Knowledge Bases using Formal Concept Analysis. LTCS-Report 06-02. Dresden, Germany: Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, 2006. [5] Franz Baader et al., eds. The Description Logic Handbook: Theory, Implementation, and Applications. New York, NY, USA: Cambridge University Press, 2003. [6] Daniel Borchmann. “Learning Terminological Knowledge with High Confidence from Erroneous Data”. PhD thesis. Dresden, Germany: Technische Universität Dresden, 2014. [7] Daniel Borchmann. “Towards an Error-Tolerant Construction of EL⊥ -Ontologies from Data Using Formal Concept Analysis”. In: Formal Concept Analysis, 11th International Conference, ICFCA 2013, Dresden, Germany, May 21-24, 2013. Proceed- ings. Ed. by Peggy Cellier, Felix Distel, and Bernhard Ganter. Vol. 7880. Lecture Notes in Computer Science. Springer, 2013, pp. 60–75. [8] Daniel Borchmann and Felix Distel. “Mining of EL-GCIs”. In: Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on, Vancouver, BC, Canada, December 11, 2011. Ed. by Myra Spiliopoulou et al. IEEE Computer Society, 2011, pp. 1083–1090. [9] Felix Distel. “Learning Description Logic Knowledge Bases from Data using Methods from Formal Concept Analysis”. PhD thesis. Dresden, Germany: Technische Universität Dresden, 2011. [10] Bernhard Ganter. “Two Basic Algorithms in Concept Analysis”. In: Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010. Proceedings. Ed. by Léonard Kwuida and Baris Sertkaya. Vol. 5986. Lecture Notes in Computer Science. Springer, 2010, pp. 312–340. [11] Bernhard Ganter and Sergei O. Kuznetsov. “Pattern Structures and Their Projec- tions”. In: Conceptual Structures: Broadening the Base, 9th International Conference on Conceptual Structures, ICCS 2001, Stanford, CA, USA, July 30-August 3, 2001, Proceedings. Ed. by Harry S. Delugach and Gerd Stumme. Vol. 2120. Lecture Notes in Computer Science. Springer, 2001, pp. 129–142. [12] Bernhard Ganter and Rudolf Wille. Formal Concept Analysis - Mathematical Foundations. Springer, 1999. [13] Jean-Luc Guigues and Vincent Duquenne. “Familles minimales d’implications informatives résultant d’un tableau de données binaires”. In: Mathématiques et Sciences Humaines 95 (1986), pp. 5–18. 16 REFERENCES [14] Francesco Kriegel. Concept Explorer FX. Software for Formal Concept Analysis. 2010-2015. URL: https://github.com/francesco-kriegel/conexp-fx. [15] Francesco Kriegel. Next Closures – Parallel Exploration of Constrained Closure Operators. LTCS-Report 15-01. Dresden, Germany: Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, 2015. [16] Michael Luxenburger. “Implications partielles dans un contexte”. In: Mathéma- tiques, Informatique et Sciences Humaines 29.113 (1991), pp. 35–55. [17] Michael Luxenburger. “Implikationen, Abhängigkeiten und Galois-Abbildung- en”. PhD thesis. TH Darmstadt, 1993. [18] Michael Luxenburger. “Partielle Implikationen und partielle Abhängigkeiten zwischen Merkmalen”. Diploma Thesis. TH Darmstadt, 1988. [19] Sebastian Rudolph. “Relational Exploration - Combining Description Logics and Formal Concept Analysis for Knowledge Specification”. PhD thesis. Dresden, Germany: Technische Universität Dresden, 2006. [20] Bariş Sertkaya. “Formal Concept Analysis Methods for Description Logics”. PhD thesis. Dresden, Germany: Technische Universität Dresden, 2007. [21] Monika Zickwolff. “Rule Exploration: First Order Logic in Formal Concept Analysis”. PhD thesis. Germany: Technische Hochschule Darmstadt, 1991.