We propose an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the knowledge base and by a domain expert. The use of techniques from Formal Concept Analysis ensures that, on the one hand, the interaction with the expert is kept to a minimum, and, on the other hand, we can show that the extended knowledge base is complete in a certain, well-defined sense.
Description Logics (DLs) [
A DL knowledge base (nowadays often called ontology) usually consists of two parts, the terminological part (TBox), which denfies concepts and also states ? Supported by DFG (GRK 334/3) and the EU (IST-2005-7603 FET project TONES and NoE 507505 Semantic Mining). additional constraints (so-called general concept inclusions, GCIs) on the interpretation of these concepts, and the assertional part (ABox), which describes individuals and their relationship to each other and to concepts. Given an application domain and a DL knowledge base (KB) describing it, we can ask whether the KB contains all the relevant information about the domain: Are all the relevant constraints that hold between concepts in the domain captured by the TBox? Are all the relevant individuals existing in the domain represented in the ABox?
As an example, consider the OWL ontology for human protein phosphatases
that has been described and used in [
Such questions cannot be answered by an automated tool alone. Clearly, to check whether a given relationship between concepts—which does not follow from the TBox—holds in the domain, one needs to ask a domain expert, and the same is true for questions regarding the existence of individuals not described in the ABox. The roˆle of the automated tool is to ensure that the expert is asked as few questions as possible; in particular, she should not be asked trivial questions, i.e., questions that could actually be answered based on the represented knowledge. In the above example, answering a non-trivial question regarding human protein phosphatases may require the biologist to study the relevant literature, query existing protein databases, or even carry out new experiments. Thus, the expert may be prompted to acquire new biological knowledge.
Attribute exploration is an approach developed in Formal Concept Analysis
(FCA) [
Although this sounds very similar to what is needed in our context, we
cannot directly use this approach. The main reason is the open-world semantics of
description logic knowledge bases. In DLs, if we cannot deduce from the
knowledge base that an individual i is an instance of the concept C, we do not assume
that i belongs to ¬C. In contrast classical FCA assumes complete knowledge in
the sense that, whenever it is not explicitly mentioned that an object o has a
property p, we assume that o does not have p. There has been some work on how
to extend FCA and attribute exploration from complete knowledge to the case
of partial knowledge [
Due to space limitation, we introduce our variant of FCA that can deal
with the open-world semantics of DL knowledge bases only briefly. For a more
comprehensive description, we refer the reader to the long version of this paper
[
In this section, we extend the classical approach to Formal Concept Analysis
(FCA), as described in detail in [
Definition 1. A partial object description (pod) is a tuple (A, S) where A, S ⊆ M are such that A ∩ S = ∅. We call such a pod a full object description (fod) if A ∪ S = M . A set of pods is called a partial context and a set of fods a full context.
Intuitively, the pod (A, S) says that the object it describes satisfies all attributes from A and does not satisfy any attribute from S. For the attributes not contained in A ∪ S, nothing is known w.r.t. this object.
Definition 2. We say that the pod (A0, S0) extends the pod (A, S), and write this as (A, S) ≤ (A0, S0), if A ⊆ A0 and S ⊆ S0. Similarly, we say that the partial context K0 extends the partial context K, and write this as K ≤ K 0, if every pod in K is extended by some pod in K0. If K is a full context and K ≤ K, then K is called a realizer of K. If (A, S) is a fod and (A, S) ≤ (A, S), then we also say that (A, S) realizes (A, S).
The following notion of implication formalizes the informal notion “relationship between properties” used in the introduction.
Definition 3. An implication is of the form L → R where L, R ⊆ M . This implication is refuted by the pod (A, S) if L ⊆ A and R ∩ S 6= ∅. It is refuted by the partial context K if it is refuted by at least one element of K. The set of implications that are not refuted by a given partial context K is denoted by Imp(K). The set of all fods that do not refute a given set of implications L is denoted by Mod (L).
For a set of implications L and a set P ⊆ M , the implicational closure of P with respect to L, denoted by L(P ), is the smallest subset Q of M such that – P ⊆ Q, and – L → R ∈ L and L ⊆
Q imply R ⊆
Q.
A set P ⊆
M is called L-closed if L(P ) = P .
Definition 4. The implication L → R is said to follow from a set J of implications if R ⊆ J (L). The set of implications J is called complete for a set of implications L if every implication in L follows from J . It is called sound for L if every implication that follows from J is contained in L. A set of implications J is called a base for a set of implications L if it is both sound and complete for L, and no strict subset of J satisfies this property.
The following is a trivial fact regarding the connection between partial contexts and the implications they do not refute.
Proposition 1. For a given set P ⊆ M and a partial context K, K(P ) := M \ S{S | (A, S) ∈ K, P ⊆ A} is the largest subset of M such that P → K(P ) is not refuted by K.
Attribute exploration with partial contexts The classical attribute
exploration algorithm of FCA assumes that there is a domain expert that can
answer questions regarding the validity of implications in the application
domain. Accordingly, our approach requires an expert that can decide whether an
implication is refuted in the application domain or not. In contrast to existing
work on extending FCA to the case of partial knowledge [
To be more precise, we consider the following setting. We are given an initial (possibly empty) partial context K, an initially empty set of implications L, and a full context K that is a realizer of K. The expert answers implication questions “L → R?” w.r.t. the full context K. More precisely, if the answer is “yes,” then K does not refute L → R. The implication L → R is then added to L. Otherwise, the expert extends the current context K such that the extended context refutes L → R and still has K as a realizer. Consequently, the following invariant will be satisfied by K, K, L: K ≤ K ⊆ Mod (L). Our aim is to enrich K and L such that eventually L is not only sound, but also complete for Imp(K), and K refutes all other implications (i.e., all the implications refuted by K). As in the classical case, we want to do this by asking as few as possible questions to the expert. Definition 5. Let L be a set of implications and K a partial context. An implication is called undecided w.r.t. K and L if it neither follows from L nor is refuted by K. It is decided w.r.t. K and L if it is not undecided w.r.t. K and L. In principle, our attribute exploration algorithm tries to decide each undecided implications by either adding it to L or extending K such that it refutes the implication. If all implications are decided, then our goal is achieved. Proposition 2. Assume that K ≤ K ⊆ Mod (L) and that all implications are decided w.r.t. K and L. Then L is complete for Imp(K) and K refutes all implications not belonging to Imp(K).
How can we find—and let the expert decide—all undecided implications without considering all implications? The following proposition motivates why it is sufficient to consider implications whose left-hand sides are L-closed. Proposition 3. Let L be a set of implications and L → R an implication. Then, L → R follows from L iff L(L) → R follows from L.
Concerning right-hand sides, Proposition 1 says that the largest right-hand
side R such that L → R is not refuted by K is R = K(L). Putting these
two observations together, we only need to consider implications of the form
L → K(L) where L is L-closed. In order to enumerate all relevant left-hand sides,
we can thus use the well-known approach from FCA for enumerating closed sets
in the lectic order [
Definition 6. Assume that M = {m1, . . . , mn} and fix some linear order m1 < m2 < · · · mn on M . The lectic order < is defined as follows: for mi ∈ M and A, B ⊆ M we define A <i B iff mi ∈ B \ A and A ∩ {m1, . . . , mi− 1} = B ∩ {m1, . . . , mi− 1}. The order < is the union of the orders <i. Obviously, < extends the strict subset order, and thus ∅ is the smallest and M the largest set w.r.t. <.
Proposition 4. Given a set of implications L and an L-closed set A ( M , the
next L-closed set following A in the lectic order is L((A∩{m1, . . . , mj− 1})∪{mj })
where j is maximal such that A <j L((A ∩ {m1, . . . , mj− 1}) ∪ {mj }.
In [
In order to represent knowledge about an application domain using Description
Logics (DLs) (see [
¬C Δ I \ CI
C u D CI ∩ DI general concept inclusion C v D CI ⊆ DI
NR of role names (binary predicates), and builds complex concept descriptions out of them by using the concept constructors provided by the particular description language being used. In addition, a set NI of individual names is used to refer to domain elements. In this paper, we do not fix a specicfi set of constructors, we only assume that the constructors conjunction and negation (see the upper part of Table 1) are available. A TBox is a finite set of general concept inclusions (GCIs), and an ABox is a nfiite set of concept and role assertions (see the lower part of Table 1). A knowledge base (KB) consists of a TBox together with an ABox. The semantics of concept descriptions, TBoxes, and ABoxes is given in terms of an interpretation I = (Δ I , · I ), where Δ I (the domain) is a nonempty set, and · I (the interpretation function) maps each concept name A ∈ NC to a set AI ⊆ Δ I , each role name r ∈ NR to a binary relation rI ⊆ Δ I × Δ I , and each individual name a ∈ NI to an element aI ∈ Δ I . Concept descriptions C are also interpreted as sets CI ⊆ Δ I , which are defined inductively, as seen in the semantics column of Table 1 for the constructors conjunction and negation. An interpretation I is a model of the TBox T (the ABox A) if it satisfies all its GCIs (assertions) in the sense shown in the semantics column of the table. In case I is a model of both T and A, it is also called a model of the knowledge base (T , A). If there is such a model, we call the KB consistent.
Given a KB (T , A), concept descriptions C, D, and an individual name a, the inference problems subsumption and instance are denfied as follows: C is subsumed by D w.r.t. T (C vT D) if CI ⊆ DI holds for all models I of T ; and a is an instance of C w.r.t. T and A (T , A |= C(a)) if aI ∈ CI holds for all models of (T , A). For most DLs, these problems are decidable, and there exist highly optimized DL reasoners such as FaCT, Racer, and Pellet that can solve these problems for very expressive DLs on large practical KBs.
Our approach for completing DL knowledge bases applies to arbitrary DLs, provided that the description language allows at least for conjunction and negation, the TBox formalism for GCIs, the ABox formalism for concept assertions, and the subsumption and the instance problem are decidable.
DLs and partial contexts Let (T , A) be a consistent DL knowledge base, and M be a nfiite set of concept descriptions. An individual name a occurring in A gives rise to the partial object description pod T ,A(a, M ) := (A, S) where A := {C ∈ M | T , A |= C(a)} and S := {C ∈ M | T , A |= ¬C(a)}, and the whole ABox induces the partial context KT ,A(M ) := {pod T ,A(a, M ) | a an individual name in A}. Note that pod T ,A(a, M ) is indeed a pod since (T , A) was assumed to be consistent. Similarly, any element d ∈ Δ I of an interpretation I gives rise to the full object description fod I (d, M ) := (A, S) where A := {C ∈ M | d ∈ CI } and S := {C ∈ M | d ∈ (¬C)I }, and the whole interpretation induces the full context KI (M ) := {fod I (d, M ) | d ∈ Δ I }. KT 0,A0 (M ) ≤ K I (M ).
Proposition 5. Let (T , A), (T 0, A0) be DL KBs such that T ⊆ T 0 and A ⊆ A 0, M a set of concept descriptions, and I a model of (T 0, A0). Then KT ,A(M ) ≤ Next, we straightforwardly transfer the notion of refutation of an implication from partial (full) contexts to knowledge bases (interpretations). Definition 7. The implication L → R over the attributes M is refuted by the knowledge base (T , A) if it is refuted by KT ,A(M ), and it is refuted by the interpretation I if it is refuted by KI (M ). If an implication is not refuted by I, then we say that it holds in I. In addition, we say that L → R follows from T if uL vT uR, where uL and uR respectively stand for the conjunctions dC∈L C and dD∈R D.
Obviously, the implication L → R holds in I iff ( uL)I ⊆ (uR)I . As an immediate consequence of this fact, we obtain: Proposition 6. Let T be a TBox and I be a model of T . If L → R follows from T , then it holds in I.
Completion of DL KBs: formal definition and algorithm We are now ready to define what we mean by a completion of a DL knowledge base. Intuitively, the knowledge base is supposed to describe an intended model. For a xfied set M of “interesting” concepts, the knowledge base is complete if it contains all the relevant knowledge about implications between these concepts. To be more precise, if an implication holds in the intended interpretation, then it should follow from the TBox, and if it does not hold in the intended interpretation, then the ABox should contain a counterexample.
Definition 8. Let (T , A) be a consistent DL knowledge base, M a finite set of concept descriptions, and I a model of (T , A). Then (T , A) is M -complete (or complete if M is clear from the context) w.r.t. I if the following three statements are equivalent for all implications L → R over M : 1. L → R holds in I; 2. L → R follows from T ; 3. L → R is not refuted by (T , A).
A0 ⊆ A .
Let (T0, A0) be a DL knowledge base and I a model of (T0, A0). Then (T , A) is a completion of (T0, A0) if it is complete and extends (T0, A0), i.e., T0 ⊆ T and
We can now describe an instance of attribute exploration for partial contexts that computes a completion of a given knowledge base (T0, A0) w.r.t. a fixed model I. We assume that the expert has or can obtain enough information Algorithm 1 Completion of DL knowledge bases {attribute set; KB with model I} 1: Input: M = {m1, . . . , mn}, (T0, A0) 2: T := T0, A := A0 3: L := ∅ 4: P := ∅ 5: while P 6= M do 6: Compute KT ,A(P ) 7: if P 6= KT ,A(P ) then {check whether the implication follows from T } 8: if uP vT uKT ,A(P ) then 9: L := L ∪ {P → KT ,A(P ) \ P } 10: Pnew := L((P ∩ {m1, . . . , mj− 1}) ∪ {mj}) for the max. j that satisfies P <j L((P ∩ {m1, . . . , mj− 1}) ∪ {mj})
{initial empty set of implications} {lectically smallest L-closed subset of M } {extend the ABox} {P not changed} about this model to be able to answer questions of the form “Is L → R refuted by I?”. If the answer is “no,” then L → R holds according to the expert’s opinion, and is thus added to the implication base computed by the algorithm. In addition, the GCI uL v uR is added to the TBox. Since L → R is not refuted by I, the interpretation I is still a model of the new TBox obtained this way. If the answer is “yes,” then the expert is asked to extend the current ABox (by adding appropriate assertions on either old or new individual names) such that the extended ABox refutes L → R and I is still a model of this ABox. Because of Proposition 6, before actually asking the expert whether the implication L → R is refuted by I, we can first check whether uL v uR already follows from the current TBox. If this is the case, then we know that L → R cannot be refuted by I. This completion algorithm for DL knowledge bases is described in more detail in Algorithm 1.
Theorem 1. Let (T0, A0) be a consistent knowledge base, M a finite set of concept descriptions, and I a model of (T0, A0), and let (T , A) be the knowledge base computed by Algorithm 1. Then (T , A) is a completion of (T0, A0). 4
We have extended the attribute exploration algorithm from FCA to partial
contexts, and have shown how the extended algorithm can be used to complete
DL knowledge bases, using both DL reasoning and answers given by a domain
expert. This algorithm inherits its complexity from “classical” attribute
exploration [
Based on the results presented in the previous two sections, we have
implemented a rfist experimental version of a tool for completing DL knowledge bases
as an extension of the ontology editor Swoop [
From a theoretical point of view, we will also look at extensions of our
definition of a complete KB. As a formalization of what “all relationships between
interesting concepts” really means, we have used subsumption relationships
between conjunctions of elements of the set of interesting concepts M . One could
also consider more complex relationships by fixing a specicfi DL D, and then
taking, as attributes, all D-concept descriptions over the concept “names” from
M . The immediate disadvantage of this extension is that, in general, the set of
attributes becomes infinite, and thus termination of the exploration process is
no longer guaranteed. An extension of classical attribute exploration (i.e., for
full contexts) in this direction is described in [