A Scheme for Integrating Concrete Domains into Concept Languages

1 Introduction

Concept languages based on KL-ONE [Brachman and Schmolze, 1985] are used to represent the taxonomical and conceptual knowledge of a particular problem do­ main on an abstract logical level. To describe this kind of knowledge, one starts with atomic concepts and roles, and defines new concepts using the operations provided by the language. Examples for atomic concepts may be Human and Female, and for roles child. If the log­ ical connective conjunction is present as language con­ struct, one may describe the concept Woman as "hu­ mans who are female", and represent it by the expres­ sion Human n Female. Many languages provide quan­ tification over role fillers which allows for example to describe the concept Mother by the expression Woman n 3child.Human.

*Supported by the BMFT research project AKA-WINO

fSupported by the BMFT research project ARC-TEC

KL-ONE was first developed for the purpose of natural language processing [Brachman et al., 1979], and some of the existing systems are still mostly used in this context (see e.g., SB-ONE [Kobsa, 1989]). However, its success in this area has also led to applications in other fields (see e.g., MESON [Edelmann and Owsnicki, 1986] which is used for computer configuration tasks, CLASSIC [Borgida et al., 1989] which is e.g. used in the area of CAD/CAM, or K-Rep [Mays et al., 1988] which is used in a financial marketing domain).

A drawback which pure KL-ONE languages have is that all the terminological knowledge has to be defined on the abstract logical level. In many applications, one would like to be able to refer to concrete domains and predi­ cates on these domains when defining concepts. An ex­ ample for such a concrete domain could be the set of non­ negative integers. In the above example, one might think that being human and female is not enough to make a woman. As an additional property one could require that she should be old enough, e.g., at least 21. Thus one would like to introduce a new role age, and define Woman by an expression of the form HumannFemalen~2l(age). Here ~21 stands for the unary predicate { n; n ~ 21} of all nonnegative integers greater or equal 21. Stating such properties directly with reference to a given concrete do­ main seems to be easier and more natural than encod­ ing them somehow into abstract concept expressions.1 Though this drawback already appears in natural lan­ guage processing, it becomes even more important if one has other applications in mind. For example, in a technical application the adequate representation of geometrical concepts requires to relate points in a co­ ordinate system. For that purpose one would e.g. like to have access to real arithmetic. Similar motivations have already led to extensions of KL-ONE in the above mentioned systems MESON, CLASSIC, and K-Rep. The MESON system provides "a separate hierarchy for describing non-concepts (e.g., integer ranges and strings)" ([Patel-Schneider et al., 1990], p. 8) which are given as user-defined or machine-defined predicates. Similar fea­ tures are provided by the "test" construct in CLASSIC. In K-Rep "the roles of concepts may in turn be other (complex) concepts, as well as numbers, strings and ... arbitrary Lisp objects" ([Mays et al., 1988], p. 62).

1 See e.g. [Brachman and Schmolze, 1985], Section 9.2, where so-called Structural Descriptions are used to encode the concrete predicate "less than one hour". From a compu­ tational point of view, Structural Descriptions are as bad as Role Value Maps which cause undecidability of subsumption [Schmidt-SchauB, 1989].

For similar reasons, Logic Programming has been ex­ tended to Constraint Logic Programming (CLP). The constraints in CLP languages "state properties directly in the domain of discourse as opposed to having these properties encoded into Prolog terms" ([Lassez, 1987], p. 2).

Before describing our approach for extending a con­ cept language by concrete domains we shall state some of the properties which such an extension should satisfy:

• The extension should still have a formal declarative semantics which is as close as possible to the usual semantics employed for concept languages.
• It should be possible to combine existing inference al­ gorithms for concept languages with well-known rea­ soning algorithms in the concrete domain in order to get the appropriate algorithms for the extension.
• One should provide a scheme for extending concept languages by various concrete domains rather than constructing a single ad hoc extension for a specific concrete domain. The formal semantics as well as the combination of the algorithms should already be treated on this scheme level.

In order to satisfy these properties it is important to choose an appropriate interface between the concept lan­ guage and the concrete domain. The interface which we shall use in the present paper was inspired by a construct which is e.g. present in the CLASSIC sys­ tem, namely coreference constraints (also called agree­ ments) between chains of single-valued roles (also called features) . 2 With such a coreference constraint one can for example express the concept of all women whose fa­ ther and husband are of the same age by the expression Woman n (father age) ! (husband age). But one cannot express that the husband is even older than the father . This becomes possible if we take the set of nonnega­ tive integers as concrete domain. Then we can sim­ ply write Woman n ~(husband age , father age) where ~ stands for the binary predicate {(n,m);n ~ m} on non­ negative integers. More general, our extension will al­ low to state that feature chains satisfy a ( nonnecessarily binary) predicate which is provided by the concrete do­ main in question.

The next section will contain a formal definition of what we mean by the notion "concrete domain". Section 3 describes our scheme for extending a concept language by an arbitrary concrete domain. As a starting point for this extension we use the language A.CC of [Schmidt­ Schau6 and Smolka, 1991]. The reason for choosing this language was that it is large enough to exhibit most of the problems connected with such an extension. Taking a larger language (e.g., including number restrictions) would only mean more work without bringing new in­ sights. Section 4 describes how an assertional component for such an extended concept language can be defined. For both the terminological and the assertional part of our formalism we shall introduce the important infer­ ence problems. Because of the space limitations it is not possible to present the algorithm which can be used to decide all of these problems. A complete presentation of the algorithm, and a proof of its correctness can be found in [Baader and Hanschke, 1991]. It is important to note that this algorithm is not only sound but also complete. 3

2 Agreements on feature chains are just the restriction of Role Value Maps to single-valued (i.e., functional) roles; but unlike Role Value Maps they usually do not cause undecid­ ability of subsumption [Hollunder and Nutt, 1990].

2 Concrete Domains

The following definition formalizes the notion "concrete domain" which has until now only been used in an intu­ itive sense.

Definition 2.1 A concrete domain V consists of a set dom(V) , the domain o/V, and a set pred(V), the pred­ icate names ofV. Each predicate name P is associated with an arity n, and an n-ary predicate p'D ~ dom(V)n .

We shall now give some examples of concrete domains.

• In the examples of the introduction we have considered the concrete domain N which has the set of nonneg­ ative integers as its domain. We have also used the binary predicate name ~. and one of the unary pred­ icate names ~n·
• The concrete domain 'R is defined as follows. The domain of 'R is the set of all real numbers, and the predicates of 'R are given by formulae which are built by first order means (i .e., by using logical connectives and quantifiers) from equalities and inequalities be­ tween integer polynomials in several indeterminates. 4 For example, x + z 2 = y is an equality between the polynomials p(x, z) = x + z 2 and q(y) = y; and x > y is an inequality between very simple poly­ nomials . From these equalities and inequalities one can e.g. build the formulae 3z(x + z 2 = y) and 3z(x + z 2 = y) V (x > y) . The first formula yields a predicate name of arity 2 (since it has two free vari­ ables), and it is easy to see that the associated predi­ cate is {(r,s) ; rands are real numbers and r ~ s} . Consequently, the predicate associated to the sec­ ond formula is { ( r, s); r and s are real numbers} = dom('R) x dom('R).
• The concrete domain Z is defined as 'R with the only difference that dom( Z) is the set of all integers instead of all real numbers.
• Our next example leaves the realm of numbers and arithmetic. Assume that VB is an arbitrary rela­ tional database equipped with an appropriate query

3 All the above mentioned systems employ sound but in­ complete algorithms.

4 For the sake of simplicity we assume here that the for­ mula. itself is the predicate name.

language. Then VB can be seen as a concrete do­ main where dom(VB) is the set of atomic values in the database. The predicates of VB are the relations which can be defined over VB with the help of the query language.

As mentioned in the introduction, we want to com­ bine inference algorithms for the given concept language with reasoning algorithms for the concrete domain in or­ der to get inference algorithms for the extended concept language. This is only possible if the concrete domain satisfies some additional properties.

For technical reasons we shall have to push negation into concept terms. To make this possible we have to require that the set of predicate names of the concrete domain is closed under negation, i.e., if P is an n-ary predicate name in pred(V) then there has to exist a pred­ icate name Q in pred(V) such that Q'D = dom(V)n \ p'D. In addition, we need a unary predicate name which de­ notes the predicate dom(V) . The domain N from above does not satisfy these properties. We should have to add the predicate names <, <n · The domains Rand Z sat­ isfy the properties. Whether a domain of the form VB satisfies these properties depends on the query language.

The property which will be formulated now clarifies what kind of reasoning mechanisms are required in the concrete domain. Let P1, ... , P1: be k (not necessarily different) predicate names in pred(V) of arities n1, ... , n1:. We consider the conjunction

Here £(i) stands for an n;-tuple (x~i), ... , x~l} of variables. It is important to note that neither all variables in one tuple nor those in different tuples are assumed to be distinct. Such a conjunction is said to be satisfiable iff there exists an assignment of elements of dom(V) to the variables such that the conjunction becomes true in V.

For example, let P1 ( x, y) be the predicate 3z( x + z 2 = y) in pred('R), and let P2(x,y) be the predicate x >yin pred('R). Obviously, neither the conjunction P1 (x, y) 1\ P2( x, y) nor P2 ( x, x) is satisfiable.

Definition 2.2 A concrete domain V is called admissi­ ble iff (i) the set of its predicate names is closed under negation and contains a name for dom(V), and (ii) the satisfiability problem for finite conjunctions of the above mentioned form is decidable.

The concrete domain R is admissible. This is a conse­ quence of Tarski's decidability result for real arithmetic [Tarski, 1951]. The concrete domain Z is not admis­ sible since Hilbert's Tenth Problem-one of the most prominent undecidable problems [Matijacevic, 1970]-is a special case of its satisfiability problem.

3 The Concept Language

We shall now present our scheme for integrating an arbi­ trary concrete domain V into the concept language A.CC. The result of this integration will be called A.CC(V).

3.1 Syntax and Semantics

In addition to the usual language constructs of A.CC, the language A.CC(V) allows features (i.e., functional roles) in value restrictions, and predicate names of V applied to feature chains. For a set F of feature names, a feature chain is just a nonempty word over F.

Definition 3.1 Let C, R, and F be disjoint sets of con­ cept, role, and feature names. The set of concept terms of A.CC(V) is inductively defined. As a starting point of the induction, any element of C is a concept term (atomic terms). Now let C and D be concept terms, let R be a role name or feature name, P E pred(V) be an n-ary predicate name, and u1 , ... , Un be feature chains. Then the following expressions are also concept terms:

1. CuD (disjunction), C n D (conjunction), and -,c (negation),

2. 3R.C (exists-in restriction) and VR.C (value restriction),

3. P(u1, ... ,un) (predicate restriction).

Let A be a concept name and let D be a concept term. Then A = D is a terminological axiom. A terminology (T-box) is a finite set T of terminological axioms with the additional restrictions that (i) no concept name ap­ pears more than once as a left hand side of a definition, and (ii) T contains no cyclic definitions. 5

Please note that the exists-in and the value restrictions are not only defined for roles but also for features.

The following is an example of a T-box in A.CC(N). Let Human, Female, Mother, Woman be concept names, let child be a role name, and let age be a feature name. The T-box-which proposes yet another definition of the concept woman-consists of the following axioms:

Mother Woman Humann Female n 3child.Human Humann Female n (Mother u ~21 (age))

The reason for choosing child as role and age as fea­ ture is that an individual can have more than one child, but (s)he has only one age. The next definition gives a model-theoretic semantics for the languages introduced in Definition 3.1.

Definition 3.2 An interpretation I for A.CC(V) con­ sists of a set dom(I), the abstract domain of the inter­ pretation, and an interpretation function. The abstract domain and the given concrete domain have to be dis­ joint, i.e., dom(V) n dom(I) = 0. The interpretation function associates with each concept name A a subset AI of dom(I), with each role name R a binary rela­ tion RI on dom(I), i.e., a subset of dom(I) x dom(I), and with each feature name f a partial function ji from dom(I) into dom(I) U dom(V).

For such a partial function P the expression ji ( x) = y is sometimes written as (x,y) E ji. lfu = f1 .. .fn is a feature chain, then ui denotes the composition ff o .. . of!. of the partial functions If, ... , f!.. 6

5 See [Nebel, 1989; Baader, 1990] for a treatment of cyclic definitions in concept languages.

6 The composition should be read from left to right, i.e., Jf o ... o f~ means apply first f{, then Ji, and so on.

The interpretation function-which gives an interpreta­ tion for atomic terms-can be extended to arbitrary con­ cept terms as follows: Let C and D be concept terms, let R be a role name or feature name, P E pred(V) be an n-ary predicate name, and u1, ... , Un be feature chains. Assume that ci and Jii are already defined. Then

1. (C U D)I = CI U Jii, (C n D)I = CI n DI, and ( -.C)I = dom(I) \ CI,

2. (VR.C)I = {x E dom(I); Vy: (x, y) E RI--+ yE CI}, (3R.C)I = {x E dom(I); 3y: (x, y) E RI 1\ y E CI},

3. P}u1, ... , un)I = {x E dom(I);3rl, ... , rn E dom(V) : u1 (x) = r1, ... , u~(x) = rn 1\ (r1, ... , rn) E Pv}.

An interpretation I is a model of the T-box T iff it sat­ isfies AI = ni for all terminological axioms A = D in T.

The philosophy underlying this definition is that we assume that the concrete domain V is sufficiently struc­ tured by the predicates in pred(V). That means that we do not want to define new classes of elements of dom(V) or new relations between elements of dom(V) with the help of our concept language. Consequently, concept terms are always interpreted as subsets of the abstract domain, i.e. , an individual of the concrete domain cannot be element of a concept.

3.2 Terminological Reasoning

An important service terminological representation sys­ tems provide is computing the subsumption hierarchy, i.e., computing the subconcept-superconcept relation­ ships between the concepts of a T-box. Let T be a T-box and let A, B be concept names. Then B sub­ sumes A with respect to T (symbolically A ~T B) iff AI~ BI holds for all models I ofT.

In our example, it is very easy to see that Woman subsumes Mother. However, in general it is not at all trivial to determine such relationships. Until recently, sound and complete subsumption algorithms were only known for rather trivial concept languages (see [Levesque and Brachman, 1987]). Consequently, all the existing KL-ONE systems use only sound, but incomplete algo­ rithms. If such an algorithm gives a positive answer, a subsumption relationship really exists; but if its answer is negative, then we do not know anything. A subsump­ tion relationship may or may not exist. In [Schmidt­ SchauB and Smolka, 1991] a sound and complete sub­ sumption algorithm for A.CC is described. The underly­ ing method of constraint propagation was used in [Hol­ lunder et a/., 1990] to derive algorithms for various other concept languages . This method can- with appropri­ ate modifications-also be applied to the languages of the form A.CC(V) . As a subtask, such an algorithm for A.CC(V) will have to decide satisfiability of conjunctions of the form /\7= 1 P;(~(i)) in the concrete domain. Thus we shall have to require that V is admissible.

In [Baader and Hanschke, 1991] we do not directly give a subsumption algorithm for A.CC(V). Instead we reduce the subsumption problem to a problem which will be introduced in the next section: the consistency problem for A-boxes.

4 The Assertional Language

The terminological formalism introduced in the previ­ ous section allows to describe knowledge about classes of objects (the concepts) and relationships between these classes (e.g., subsumption relationships which are conse­ quences of the descriptions). Many applications, how­ ever, require that one can also say something about ob­ jects in the world. For this reason, most KL-ONE sys­ tems provide additional assertional capabilities. This assertional part of the system uses the concept terms for making statements about parts of a given world. The ex­ pressiveness of this component varies between the rather weak formalism employed in the original KL-ONE sys­ tem [Brachman and Schmolze, 1985] to full first order predicate logic as used in KRYPTON [Brachman et a/., 1985] . We shall now show how to integrate a concrete domain into an assertional language which is similar to the ones used in KANDOR [Patel-Schneider, 1984], ME­ SON [Edelmann and Owsnicki, 1986], CLASSIC [Borgida eta/., 1989], or BACK [Nebel and von Luck, 1988].

4.1 Syntax and Semantics

Let V be an arbitrary concrete domain . We have seen in Section 3 that we have to deal with two different kinds of objects: the individuals of the concrete domain and the individuals in the abstract domain (see Definition 3.2). The names for objects of the concrete domain will come from a set OC of object names, and the names for objects of the abstract domain from a set OA.

Definition 4.1 Let OC and OA be two disjoint sets of object names. The set of all assertional axioms is defined as follows. Let C be a concept term of A.CC(V), R be a role name, f be a feature name, P be an n-ary predicate name ofV, and let a, b be elements ofOA andy, y1 , ... , Yn be elements ofOC. Then the following are assertional axwms:

An A-box is a finite set of such assertional axioms.

The assertional language can for example be used to express the facts that the woman Lolita, the daughter of Humbert, is married to Vladimir, a man older than Humbert, by the assertional axioms

LOLITA : Woman, (LOLITA, HUMBERT): father, (LOLITA, VLADIMIR) : husband, (HUMBERT , Al) : age, (VLADIMIR,A2): age , (A2,Al) : >.

Here LOLITA, HUMBERT, and VLADIMIR are elements of OA, and Al and A2 are elements of OC.

It may seem to be a drawback of the above defined as­ sertionallanguage that it disallows the use of specific el­ ements of dom(V) in the assertions. For example, we are not allowed to write the axiom (LOLITA, 12) : age. How­ ever, if we have a predicate name for the singleton set {12}, say =12 , then we can express the same fact by the two axioms (LOLITA, A3) : age and = 12(A3). In A-boxes of A.CC(R) one can use algebraic numbers such as V2 be­ cause the corresponding singleton set { V'i.} corresponds to a predicate name in J?, namely (x 2 = 2) 1\ X ~ 0.

Definition 4.2 An interpretation for the assertional language is simply an interpretation for, A.CC(V) which, in addition assigns an object ai E dom(I) to each ob-' . I ) ject name a E OA, and an obJect x E dom(V to each object name x E OC. Such an interpretation satisfies an assertional axiom

An interpretation is a model of an A-box A iff it satisfies all the assertional axioms of A, and it is a model of an A-box A together with aT-box T iff it is a model ofT and a model of A.

The definition shows that we do not require unique names for the objects occurring in an A-box? For exam­ ple, assume that we have the abstract names VLADIMIR and LOLITA'S_FATHER in our A-box. As our knowledge about the world increases, we may learn that Vladimir is in fact Lolita's father. Similarly, if we introduce con­ crete names Al, A2 for the ages of two persons PERSON I, PERSON2 into the A-box, we do not want to assume au­ tomatically that these two numbers are different.

4.2 Assertional Reasoning

In the following, A will always denote an A-box, T a T-box, C, D concept terms, a, bE OA names of abstract objects, and x, y E OC names of concrete objects.

An obvious requirement on the represented knowledge is that it should not be contradictory. Otherwise, it would be useless to deduce other facts from this knowl­ edge since logically, everything follows from an incon­ sistent set of assumptions. However, a given A-box to­ gether with a given T-box need not have a model. For ex­ ample, an A-box containing the axioms a : C and a : ..,~, or the axioms (a, b):/, (a,y): f for a feature name f ts contradictory, and thus cannot have a model.

We say that an A-box together with aT-box is con­ sistent iff it has a model. Otherwise, it is called incon­ sistent.

For the above mentioned reason it is important to have an algorithm which decides consistency of a given A-box together with aT-box. In addition, it will turn out that such an algorithm can also be used to solve the other important inference problems, namely subsumption be­ tween concepts and the so-called instantiation problem.

This last problem is defined as follows. The abstract object a is an instance of C with respect to A together with Tiff ai E cr for all models of A together with T.

As an example, we consider the T-box defining the concepts Mother and Woman of Section 3, and an A-box containing the axioms (LOLITA, A3) : age, =12(A3) and LOLITA :Woman. Then LOLITA is an instance of Mother with respect to the A-box together with the T-box.

The instantiation problem can be reduced to the con­ sistency problem as follows: a is an instance of C with respect to A together with T iff the A-box AU {a : ..,C} together with T is inconsistent.

7 Many KL-ONE based systems have a unique name as­ sumption for their A-box individuals; but for example KL­ TWO [Vilain, 1985] does not assume unique names.

Finally, the subsumption problem can also be r~duced to the instantiation problem, and thus to the conststency problem for A-boxes. In fact, Cis subsumed by D with respect toT iff the abstract object a is an instance of D with respect to the A-box {a : C} together with T .

In [Baader and Hanschke, 1991] a sound and com­ plete algorithm is described which decides the consis­ tency problem for A.CC(V), provided that the concrete domain V is admissible. Such an algorithm for A.CC without concrete domain and features can be found in [Hollunder, 1990]. Since the other inference problems in­ troduced above can be reduced to the consistency prob­ lem, we thus have

Theorem 4.3 Let V be an admissible concrete domain. Then there exists a sound and complete algorithm which is able to decide the following problems for A.CC(V): the subsumption problem w. r. t. a T-box, the instantiation problem w.r.t. an A-box together with a T-box, and the consistency problem for an A-box together with a T-box.

5 Conclusion

We have proposed a KL-ONE based knowledge represen­ tation and reasoning system which is hybrid in two re­ spects. On the one hand, it makes the usual distinction between two epistemological different kinds of knowl­ edge, the terminological knowledge and the assertional knowledge. On the other hand, the terminological and assertional language, which usually describes the knowl­ edge on an abstract logical level, is extended by allowing to refer to concrete domains and predicates on these do­ mams.

The different parts of the system are integrated with the help of a unified model-theoretic semantics. Reason­ ing in the terminological and the assertional part can be done with the help of a single basic reasoning algorithm. This algorithm creates subtasks which have to be solved by the special purpose reasoner of the concrete domain. But there is no other interaction necessary between our basic reasoning algorithm and the reasoner on the con­ crete domain.

Our approach differs from other extensions of KL-ONE which were done for similar reasons in several respects . Firstly, we have proposed a scheme for such an extension, and not a particular extension by some specific concrete domains. The formal semantics and the algorithm are given on this scheme level. Secondly, the basic reas~n­ ing algorithm is not only sound but also complete wtth respect to this semantics. In addition, we can utilize spe­ cial purpose reasoners which may already exist for the concrete domain in question. This shows another differ­ ence to e.g. the MESON system where the important re­ lationships between the user-defined or machine-defined predicates have to be explicitely supplied by the user.

An advantage other systems have compared to our approach is that their incomplete algorithms are usu­ ally polynomial, whereas our complete algorithm is of complexity at least PSPACE (depending on the concrete domain). However, one should keep in mind that ~hese complexity results are worst case results. The algonthm may behave much better for "typical" knowledge bases.

Our main motivation for developing the presented KL­ ONE extension was to represent knowledge in a mechan­ ical engineering domain. In particular, we wanted to describe both geometric and other attributes of lathe work pieces in a unified framework. For that purpose we intend to use the language .A.CC('R.) where geometric properties can be described with the help of predicates over real numbers. Currently, we are experimenting with a prototypical implementation which uses a relatively small fragment of real arithmetics as its concrete do­ main.