Computing Least Common Subsumers in Description Logics with Existential Restrictions

1 Introduction

Knowledge representation systems based on description logics (DL) can be used to describe the knowledge of an application domain in a structured and formally well­ understood way. Traditionally, the knowledge base of a DL system is built in a "top-down" fashion by first formalizing the relevant concepts of the domain (its ter­ minology) by concept descriptions , i.e., expressions that are built from atomic concepts (unary predicates) and atomic roles (binary predicates) using the concept con­ structors provided by the DL language. In a second step, the concept descriptions are used to specify prop~r­ ties of objects and individuals occurring in the domam. DL systems provide their users with inference services that support both steps: classification of concepts and of individuals. Classification of concepts determines sub­ conceptjsuperconcept relationships (called subsumption relationships) between the concepts of a given terminol­ ogy, and thus allows one to structure the terminology in the form of a subsumption hierarchy. Classification of individuals (or objects) determines whether a given in­ dividual is always an instance of a certain concept (i.e. , whether this instance relationship is implied by the de­ scriptions of the individual and the concept).

*This work was partially supported by the EC Work­ ing Group CCL II, the Studienstiftung des deutschen Volkes , and the Deutsche Forschungsgemeinschaft Grant No. GRK 185/3-98.

This traditional "top-down" approach for construct­ ing a DL knowledge base is not always adequate, how­ ever. On the one hand, it need not be clear from the outset which are the relevant concepts in a par­ ticular application. On the other hand, even if it is clear which (intuitive) concepts should be introduced, it is sometimes difficult to come up with formal defi­ nitions of these concepts within the available descrip­ tion language. For example, in one of our applica­ tions in chemical process engineering [Sattler, 1998; Baader and Sattler, 1996], the process engineers prefer to construct the knowledge base (which consists of de­ scriptions of standard building blocks of process models, such as reactors) in the following "bottom-up" fashion: first , they introduce several "typical" examples of the standard building block as individuals , and then they generalize (the descriptions of) these individuals into a concept description that (i) has all the individuals as in­ stances, and (ii) is the most specific description satisfying property (i). The task of computing a description satis­ fying (i) and (ii) can be split into two subtasks: comput­ ing the most specific concept of a single individual , and computing the least common subsumer of a given fini te number of concepts. The most specific concept (msc) of an individual b is the most specific concept descrip­ tion C (expressible in the given DL) that has b as an instance, and the least common subsumer (lcs) of n con­ cept descriptions C1 , ... , Cn is the most specific concept description in the given DL that subsumes C1, ... , Cn·

The present paper investigates the second subtask for the sub-language ACt' of the DL employed in our process engineering application. This language allows both for value restrictions and existential restrictions, but not for full negation and disjunction (since the lcs operation is trivial in the presence of disjunction, and thus does not provide useful information) . It can, e.g., be used to in­ troduce the concept of a reactor with cooling jacket by the description Reactor n :Jconnected-to.Cooling-Jacket n \ffunctionality.-Naporize, where Vaporize is a primitive concept (i.e., not further defined). Previous work on how to compute the lcs [Cohen and Hirsh, 1994; Frazier and Pitt, 1996] has concentrated on sub-languages of the DL used by the system CLASSIC [Brachman et al., 1991], which allows (among other constructors) for value re­ strictions, but not for existential restrictions. Thus, the main new contribution of the present paper is the treat­ ment of existential restrictions.

For didactic reasons, we will start by showing how to compute the lcs in the small language EC, which allows for conjunction and existential restrictions only and ex­ tend our treatment in two steps to :FLE by adding value restrictions, and then to .ALE by further adding prim­ itive negation. For all three languages, we proceed in the following manner. First, we introduce an appropri­ ate data structure for representing concept descriptions (so-called description trees), and show that subsumption can be characterized by the existence of homomorphisms between description trees. From this characterization we then deduce that the lcs operation on concept descrip­ tions corresponds to the product operation on descrip­ tion trees, which can easily be computed. We will also comment on the complexity of subsumption and the lcs for the languages under consideration. Because of the space limitation, we cannot give all the technical details. These details as well as complete proofs can be found in [Baader et al., 1998].

2 Preliminaries

Concept descriptions are inductively defined with the help of a set of constructors, starting with a set Nc of primitive concepts and a set N R of primitive roles. The constructors determine the expressive power of the DL. In this paper, we consider concept descriptions built from the constructors shown in Table 1. In the descrip­ tion logic ££, concept descriptions are formed using the constructors top-concept (T), conjunction (C n D) and existential restriction (:Jr.C). The description logic :FLE additionally provides us with value restrictions (Vr.C), and .ALE allows for all the constructors shown in Table 1.

The semantics of a concept description is defined in terms of an interpretation I= (.6., .I). The domain .6. of I is a non-empty set of individuals and the interpretation function .I maps each primitive concept P E Nc to a set pi ~ .6. and each primitive role r E N R to a binary relation ri ~ .6. x .6.. The extension of .I to arbitrary concept descriptions is inductively defined, as shown in the third column of Table 1.

One of the most important traditional inference ser­ vices provided by DL systems is computing the subsump­ tion hierarchy. The concept description C is subsumed by the description D ( C ~ D) iff CI ~ DI holds for all interpretations I. The concept descriptions C and D are equivalent ( C = D) iff they subsume each other.

In this paper, we are interested in the non-standard inference task of computing the least common subsumer (lcs) of concept descriptions. Given n ;:::: 2 concept de­ scriptions C1, ... , Cn in a description logic £, a concept description C of £ is an lcs of C1, ... , Cn (for short, C = lcs(C1, ... , Cn)) iff (i) Ci ~ C for all1 ~ i ~ n, and (ii) C is the least concept description with this property, i.e., if C' satisfies Ci ~ C' for all 1 ~ i ~ n, then C ~ C'.

Depending on the DL under consideration, the lcs of two or more descriptions need not always exist, but if it exists, then it is unique up to equivalence. In the follow­ ing, we will show that, for the DLs [£, :FLE, and .ACE, the lcs always exists and can effectively be computed. We will mostly restrict the attention to the problem of computing the lcs of two concept descriptions, since the lcs of n > 2 descriptions can be obtained by iterated application of the binary lcs operation.

3 Getting started - the lcs in ££

As mentioned in the introduction, our method for com­ puting the lcs is based on an appropriate representation of concept descriptions by trees. In the case of the small DL ££, these trees, called [£-description trees, are of the form g = (V, E, v0 , e), where g is a tree with root vo whose edges vrw E E are labeled with primitive roles r E N R, and whose nodes v E V are labeled with sets e(v) of primitive concepts from Nc. The empty label corresponds to the top-concept.

Intuitively, such a tree is merely a graphical represen­ tation of the syntax of the concept description. More formally, every ££-concept description C can be written (modulo equivalence) as C :::::: P1 n ... n Pn n :lr1.C1 n ... n :lrm.Cm with Pi E Nc U {T}. This descrip­ tion can now be translated into an ££-description tree 9c = (V, E, Vo, e) as follows. The set of all primitive con­ cepts occurring in the top-level conjunction of C yields the label e ( v0 ) of the root v0 , and each existential restric­ tion :lri.Ci in this conjunction yields an ri-successor that is the root of the tree corresponding to Ci. For example, the ££-concept description

yields the tree 9c depicted on the left-hand side of Fig. 1.

Conversely, every ££-description tree g = (V, E, Vo, e) can be translated into an ££-concept description Cg. In­ tuitively, the primitive concepts in the label of v0 yield the primitive concepts in the top-level conjunction of Cg, and each r-successor v of vo yields an existential restriction :Jr.C where C is the ££-concept description obtained by translating the subtree of g with root v. For a leaf v E V, the empty label is translated into the top-concept. For example, the ££-description tree g in Fig. 1 yields the [£-concept description

These translations preserve the semantics of concept de­ scriptions in the sense that C = Cgc.

Subsumption in [.C can be characterized using the fol­ lowing notion: a homomorphism from an [£-description tree 1i = (Vs,Es,wo,fs) to an [£-description tree 9 = (Va,Ea,vo,fa) is a mapping r.p: Vs--+ Va such that (1) r.p(wo) = vo, (2) fs(v) ~ fa(r.p(v)) for all v E Vs, and (3) r.p(v)rr.p(w) E Ea for all vrw E Es.

Theorem 1 Let C, D be [£-concept descriptions and 9c, 9n the corresponding [£-description trees. Then C [;;;; D iff there exists a homomorphism from 9 D to 9c.

In our example, the [£-concept description Cg subsumes C, because mapping v~ onto v; for all 0 ~ i ~ 4 yields a homomorphism from 9 = 9cc to 9c (see Fig. 1).

Theorem 1 is a special case of the characterization of subsumption between simple conceptual graphs in [Chein and Mugnier, 1992], and of the characterization of containment of conjunctive queries in [Abiteboul .et al., 1995]. In the more general setting of simple conceptual graphs and conjunctive queries, testing for the existence of a homomorphism is an NP-complete problem. In the restricted case of [£-description trees, however, testing for the existence of a homomorphism can be realized in polynomial time [Reyner, 1977; Baader et al., 1998], which shows that subsumption between [£-concept de­ scriptions is a tractable problem.

Least common subsumer in [.C

The characterization of subsumption by homomorphisms allows us to characterize the lcs by the product of [£-description trees. The product 9 x 1i of two [£-description trees 9 = (Va,Ea,vo,fa) and 1i = (Vs,Es,wo,fs) is defined by induction on the depth of the trees. Let 9(v) denote the subtree of 9 with root v. We define (v0 , w0 ) to be the root of 9 x 1i , labeled with fa(vo) n fs(wo). For each r-successor v of Vo in 9 and w of w0 in H, we obtain an r-successor (v,w) of (v0 , w0 ) in 9 x 1i that is the root of the product of 9(v) and 1-l(w).

For example, consider the [£-description tree 9c (Fig. 1) and the [£-description tree 9n (Fig. 2), where 9n corresponds to the [£-concept description D :=

3r.(P n 3r.P n 3s.Q). The product 9c X 9n is depicted on the right-hand side of Fig. 2.

Theorem 2 Let C, D be two [£-concept descriptions and 9c, 9n the corresponding [£-description trees. Then Cgc xQv is the lcs of C and D.

In our example, we thus obtain

The size of the lcs of two [£-concept descriptions C, D can be bounded by the size of 9c x 9n, which is poly­ nomial in the size of 9c and 9 D. Since the size of the description tree corresponding to a given description is linear in the size of the description, we obtain:

Proposition 3 The size of the lcs of two [£-concept descriptions C, D is polynomial in the size of C and D, and the lcs can be computed in polynomial time.

In our process engineering application, however, we are interested in the lcs of n > 2 concept descriptions C1 , ... , Cn. This lcs can be obtained from the product 9c 1 x · · · x 9c" of their corresponding [£-description trees. Therefore, the size of the lcs can be bounded by the size of this product. It has turned out [Baader et al., 1998] that, even for the small DL [£, this size cannot be polynomially bounded.

Proposition 4 The size of the lcs of n [£-concept de­ scriptions C1 , ... , Cn of size linear in n may grow expo­ nential in n .

4 Extending the results to :F.t:E

Our goal is to obtain a characterization of the lcs in F££ analogous to the one given in Theorem 2 for [£. To achieve this goal, we first extend the notion of a descrip­ tion tree from [£ to F££. In order to cope with value restrictions occurring in F££-concept descriptions, weal­ low for two types of edges, namely those labeled with a primitive role r E N R (corresponding to existential re­ strictions of the form 3r.C) and those labeled with \lr for r E N R (corresponding to value restrictions of the form \lr.D). Just as for E£, there is a 1- 1 correspondence between F££-concept descriptions and F££-description trees.

The notion of a homomorphism also extends to .Fa­ description trees in a natural way. A homomorphism from an FLE -description tree 1-l = (V H' E H' Wo' f H) into an F££-description tree 9 = (Va,Ea,vo,fa) is a map­ ping cp : VH --t Va that satisfies the conditions (1)- (3) on homomorphisms between [£-description trees, and additionally ( 4) cp( v) \lr cp( w) E Ea for all v \lr w E EH.

However, these straightforward extensions are not suf­ ficient to obtain a sound and complete characteriza­ tion of subsumption in FLE based on homomorphisms between F££-description trees. For example, consider the F££-concept descriptions and their translations into F££-description trees depicted in Fig. 3. It is easy to see that C ~ D and C' ~ D', but there exists neither a homomorphism from 9D to 9c nor one from 9D· to 9c·.

To avoid these problems, we must normalize the F££­ concept descriptions before· translating them into .Fa­ description trees. The normal form of an FLE -concept description C is obtained from C by exhaustively apply­ ing the following normalization rules:

Since each normalization rule preserves equivalence, the resulting normalized F££-concept description is equiva­ lent to the original one. The rules should be read modulo commutativity of conjunction; e.g., 3r.E n \lr.F is also normalized to 3r.(E n F) n \lr.F.

Now, the FLE -description tree 9c corresponding to C is obtained from C by first normalizing C, and then translating the resulting normalized F££-concept de­ scription into a tree. Each .F££-description tree 9 = (V, E, v0 , f) obtained this way satisfies the following properties [Baader et al., 1998]:

• For each node v E V and each primitive role r E N R, v has at most one outgoing edge labeled \lr.
• Let { vrw, v\lrw'} ~ E, and let C denote the F££­ concept description corresponding to the subtree of 9 with root w, and C' the one corresponding to the subtree of 9 with root w'. Then C ~ C'.
• Leaves in 9 labeled with the empty set cannot be reached via an edge labeled \lr for some r E N R, i.e., Cg does not contain a subconcept of the form \lr.T.

The proof of soundness and completeness of the char­ acterization of subsumption in FLE stated in the next theorem makes heavy use of these properties [Baader et al. , 1998].

Theorem 5 Let C, D be two FLE -concept descriptions and 9c, 9 D their corresponding FLE -description trees. Then C ~ D iff there exists a homomorphism from 9 D to 9c.

It should be noted that there is a close relation­ ship between the normalization rules introduced above and some of the so-called propagation rules employed by tableaux-based subsumption algorithms, as e.g. in­ troduced in [Donini et al., 1992]. The main idea un­ derlying our second normalization rule and the prop­ agation rule treating value restrictions is to make the knowledge implicitly given by a conjunction of the form \lr.En3r.F explicit by propagating E onto the existential restriction according to the equivalence \lr.E n 3r.F = \lr.En3r.(EnF). As shown in [Donini et al., 1992], this propagation rule may lead to an exponential blow-up of the tableau, and the same is true for our normalization rule. More precisely, applying the normalization rules introduced above to an F££-concept description C may lead to a normalized concept description, and hence a corresponding F££-description tree 9c, of size exponen­ tial in the size of C. This exponential blow-up cannot be avoided since (i) as for E£, existence of a homomor­ phism between F££-description trees can be tested in polynomial time; and (ii) subsumption in FLE is an NP­ complete problem [Donini et al., 1992].

Least common subsumer in FLE

Just as for E£, we can now use the characterization of subsumption in FLE by homomorphisms to charac­ terize the lcs of two FLE-concept descriptions by the product of F££-description trees. The product 9 x 1-l of two F££-description trees 9 = (Va, Ea, v0 , fa) and 1-l = (VH' EH' Wo, fH) is again defined by induction on the depth of the trees. As before, (v0 , w0 ) is the root of 9 x 1-l, and r-successors of (v0 , w0 ) are obtained in the same way as for E£. Additionally, we now obtain a Vr-successor ( v, w) of ( v0 , w0 ) in 9 x 1-l if v is the Vr­ successor of v0 in 9 and w the one of w0 in 1-l, and (v, w) is the root of the product of Q(v) and 1-l(w).

Theorem 6 Let C, D be two FLE -concept descriptions and 9c , 9D their corresponding FLE-description trees. Then Cg 0 x<;v is the lcs ofC and D.

As mentioned above, :FJ:E differs from ££ in that the :FJ:E-description tree 9c corresponding to an :FJ:E­ concept description C may be of size exponential in the size of C. Therefore, even for two :FJ:E-concept descrip­ tions C, D, the size of their lcs cannot be polynomially bounded by the size of C and D [Baader et al., 1998].

Proposition 7 The size of the lcs of two :FJ:E -concept descriptions C, D may be exponential in the size of C and D.

5 Extending the results to ACE

In order to characterize the lcs of two .A.C£-concept descriptions by the product of description trees, we must adapt the notions description tree, homomorphism, and product appropriately, taking into account the ad­ ditional constructors primitive negation and bottom­ concept.

First, we extend the notion of :FJ:E-description trees to .A.C£ -description trees by additionally allowing for negated primitive concepts -,p and the bottom-concept ..l in the labels of nodes. Again, as for ££ and :FJ:E, there is a 1- 1 correspondence between .A.C£ -concept de­ scriptions and .A.C£-description trees.

Since .A.C£ is an extension of :FJ:E, and since we are again interested in a characterization of subsumption by homomorphisms, we must normalize .A.C£-concept de­ scriptions before translating them into their correspond­ ing .A.C£-description trees. In addition to the normaliza­ tion rules for :FJ:E, we need three more rules, which deal with the fact that .A.C£-concept descriptions may con­ tain inconsistent sub-descriptions (i.e., ..l and P n ,p for P E Nc):

Starting with an .A.C£-concept description C, the exhaus­ tive application of these rules, together with the rules for :FJ:E, yields an equivalent .A.C£-concept description in normal form, which is used to construct the .A.C£­ description tree 9c corresponding to C.

In addition to the conditions for :FJ:E-description trees, the .A.C£-description trees obtained this way satisfy the following condition: if the labe' 8f a node contains ..l , then its label is { ..l} and it is a leaf that cannot be reached by an edge with label r E N R ·

Unfortunately, the straightforward adaptation of the notion of a homomorphism from :FJ:E-description trees to .A.C£-description trees does not yield a sound and com­ plete characterization of subsumption in .A.C£. As an ex­ ample, consider the following .A.C£-concept descriptions:

The description D is already in normal form, and the normal form of C is C' := Vr . ..l n 3s.(P n 3r.Q). The corresponding .A.C£-description trees 9c and 9D are de­ picted in Figure 4.

It is easy to see that there does not exist a homomor­ phism (in the sense of Section 4) from 9 D into 9c, al­ though we have C ~ D. In particular, the .A.C£-concept description 3r.P n 3r.-,P corresponding to the subtree with root w1 of 9D subsumes ..l, which is the concept description corresponding to the subtree with root v1 in 9c . Therefore, a homomorphism from 9 D into 9c should be allowed to map the whole tree corresponding to 3r.P n 3r.-,P, i.e., the nodes w1, w2, w3, onto the tree corresponding to ..l, i.e., onto v1 .

A homomorphism from an .A.C£-description tree 1{ = (VH,EH,Wo ,CH) into an .A.C£-description tree 9 = (Vc,Ec,vo,Cc) is a mapping <p: VH -----t Vc such that (1) <p(wo) = vo, (2) CH(v) ~ Cc(<p(v)) or Cc(<p(v)) = {..l} for all v E VH , (3) for all vrw E EH, either <p(v)r<p(w) E Ec, or <p(v) = <p(w) and Cc(<p(v)) = {..l}, and (4) for all v'r/rw E EH, either <p(v)Vr<p(w) E Ec, or <p(v) = <p(w) and Cc(<p(v)) = {..l}.

In our example, if we map wo onto Vo; Wt, w2, and w3 onto v1 ; W4 onto v2 ; and w5 onto v3, then the above conditions are satisfied, i.e., this mapping yields a ho­ momorphism from 9D into 9c.

With this new notion of a homomorphism between .A.C£-description trees, we can again characterize sub­ sumption in .A.C£ in a sound and complete way [Baader et al., 1998].1

Theorem 8 Let C, D be two .A.C£ -concept descriptions and 9c, 9 D the corresponding .A.C£ -description trees. Then C ~ D iff there exists a homomorphism from 9 D into 9c.

Least common subsumer in .A.C£

The definition of the product of .A.C£-description trees must be adapted to the modified notion of a homomor­ phism. In particular, this definition must treat leaves with label { ..l} in a special manner. In fact , such a leaf corresponds to the bottom-concept, and since ..l ~ C for all .A.C£-concept descriptions C, we have lcs(..l, C) = C . Thus, our product operation should be defined such that Cc;JJ, x9c =C.

More precisely, the product 9 x H of two .A.C£- description trees 9 (Vc, Ec, vo, Cc) and H (VH,EH,wo,CH) is defined as follows. If Cc(v0 ) = {..l} (e H ( w0 ) = { ..l}), then we define 9 x H by replacing each node win 1{ (v in 9) by (v0 , w) ( (v, wo) ). Otherwise, we define Q x H by induct ion on the depth of the trees anal­ ogous to the definition of the product of FL£-description trees.

1 Note that subsumption in .ACE is also an NP-complete problem [Donini et al., 1992].

In the example, 9c x QD can be obtained from 9D by replacing w0 by (v0 , w0 ), w; by (v1 , w;) fori= 1, 2, 3, w4 by (v2, w4), and W5 by (v3, w5) (see Fig. 4).

Theorem 9 Let C, D be two ACE -concept descriptions and 9c, Q D their corresponding ACE -description trees. Then Cgcx9o is the lcs ofC and D.

The proof of Proposition 7 also works if we view the FL£-concept descriptions used in this proof as special ACE-concept descriptions. Thus, we have:

Proposition 10 The size of the lcs of two ACE -concept descriptions C, D may be exponential in the size of C, D .

6 Conclusion and future work

We have described a method for computing the least common subsumer in the description logic ACE. In the worst case, the result of this computation may be expo­ nential in the size of the input descriptions. However, the examples that show this exponential behavior [Baader et al., 1998] are rather artificial, and thus we believe that this complexity will not pose a problem in practice.

Our method depends on the characterization of sub­ sumpt ion by homomorphisms on description trees, be­ cause this allows us to construct the lcs as the prod­ uct of the description trees. For sub-languages of CLAS­ SIC, a similar method has been used to construct the lcs [Cohen and Hirsh, 1994; Frazier and Pitt, 1996], even though the characterization of subsumption (via a structural subsumption algorithm [Borgida and Patel­ Schneider , 1994]) is not explicitly given in terms of ho­ momorphisms. The main difference is that these lan­ guages do not allow for existential restrictions. The re­ sults for simple conceptual graphs (conjunctive queries) mentioned below Theorem 1 characterize subsumption (resp. containment) with the help of homomorphisms , but they do not consider the lcs, and they cannot han­ dle value restrictions.

The language ACE is expressive enough to be quite use­ ful in our process engineering application. In fact, the descriptions of standard building blocks of process mod­ els that we current ly represent in our DL system can all be expressed within this language. However, in order to support the "bottom-up" approach for constructing knowledge bases outlined in the introduction, we must also be able to compute the most specific concept for individuals. Unfortunately, the msc need not always ex­ ist in ACE. For the DL .ACJV, it was shown in [Baader and Kiisters, 1998] that this problem can be overcome by allowing for cyclic concept descriptions, but .AC.Af does not allow for existential restrictions. Thus, we must ei­ ther extend the approach of [Baader and Kusters, 1998] to ACE, or resort to an approximation of the msc, as proposed in [Cohen and Hirsh, 1994]. In the process engineering application, we can also use the lcs opera­ tion directly to structure the existing knowledge base.

In fact , it has turned out that the subsumption hierar­ chy obtained from the knowledge base of standard build­ ing blocks is rather flat. To obtain a deeper hierarchy (which better supports search and hence reuse of build­ ing blocks) , we will try to construct intermediate levels of concepts by applying the lcs operation. Of course, this only makes sense if the lcs yields concepts that have an intuitive meaning in the application domain.