Reifying Concepts in Description Logics

1 Introduction

Description logics (DLs) are descendants of the famous KL-ONE system [Brachman and Schmolze, 1985] and can be viewed as formalizations of the frame-based knowledge representation languages.

Systems based on DLs are hybrid systems which sepa­ rate the described knowledge in two distinct categories: terminological and assertional knowledge. The termino­ logical knowledge is generic and refers to classes of ob­ jects and their relationships , while the assertional knowl­ edge describes particular instances (individuals) of these classes. These two levels are completely disjoint since a given object cannot be at the same time a concept and an instance. (Description logics further distinguish between two kinds of terminological knowledge, namely concepts and roles. Concepts are essentially unary pred­ icates interpreted as sets of individuals, while roles represent binary predicates interpreted as (binary) relations between individuals.)

An important limitation of current description logics is the clear-cut separation between the terminological (intensional) and the assertional (extensional) level. For example, concepts (representing intensional descriptions of sets of individuals) and their instances are stored at different levels and cannot be mixed under any circum­ stances.

In certain applications, however, it may be useful to be able to regard a given ·concept (class) as the instance of a higher level meta-concept (meta-class). This would allow us to reuse terminologies by constructing a unique generic terminology which could then be instantiated to produce several particular terminologies.

This paper presents an extension of description logics in which a given concept can be regarded as an individ­ ual (i .e. an instance of some other meta-level concept) . This process, called concept reification, has not been ex­ tensively studied in the framework of description logics 1 , mainly since it mixes the terminological and assertional levels and therefore spoils the simplicity of the currently used reasoning techniques. Also, reification introduces a form of higher-order constructs in description logics thereby complicating the issue of defining a proper se­ mantics of the logic as well as the associated inference services.

In spite of these difficulties, reification is absolutely necessary whenever we want to achieve reusability in a knowledge-based system. The following example, taken from [Badea and Tilivea, 1996], deals with allocating the staff of some research institution. In such a setting we may want to introduce concepts like manager, secretary , researcher and instances like Tom, Joan, Mary , Peter , Fred , etc: TomE manager, Joan E secretary, Mary E secretary, Peter E researcher, FredE researcher.

But now note that the concepts manager, secre­ tary and researcher represent positions in the re­ search institute. They are therefore not only con­ cepts, but also instances of the (metal-level) concept position : manager E position, secretary E position, researcher E position.

1 The CLASSIC system [Brachman et al., 1991] already in­ cluded meta-individuals (a pre-theoretic form of concept reifi­ cation), but these are not taken into account in DL inferences.

The concept position should not be confused with the concept employee, which is a super-concept of man­ ager, secretary and researcher: manager C employee, secretary C employee, researcher C employee.

Now consider an employee allocation problem. In a typical knowledge-based system, we would have to write separate inferences for instance for retrieving managers, secretaries and researchers. This would amount to writ­ ing three separate pieces of code that are extremely sim­ ilar (though not identical, as at least the positions of the employees to be retrieved would be different) .

If we would like to avoid writing three separate pieces of code (inferences), we would have to write a generic inference that would be parametrized by the position of the employee we would like to choose. This can be ac­ complished by using an input parameter, called type, linked to the concept position and which is supposed to specify the position of the person to be chosen. Figure 1 is a graphical representation of such a generic inference in the KADS-based ExClaim system (see [Badea, 1996] for more details on Ex Claim). Note that we are making use of the built-in membership role E, which links an instance X with a concept C whenever X is an instance of C.

The predefined role E links a concept (employee) with a meta-concept (position) and allows therefore a kind of generic inferences which are essential for developing domain-independent and reusable models . 2

Note that domain-independence and reusability of models could not have been achieved without concept reification and the role E.

In order to be usable in real-life applications, descrip­ tion logics will also have to allow for an individual (in­ stance) to represent a collection (set) of other individu­ als. However, existing (implemented) DL systems usually lack constructors for sets or lists of objects 3 and we therefore have to represent such collections outside the DL thereby affecting the completeness of the DL reason­ ing services.

2 Not only is it cumbersome to have three identical pieces of code, but these pieces of code would depend on the do­ main level (the types of positions - director, secretary and researcher are domain-dependent; we cannot change the do­ main level, for example by introducing a new position, with­ out having to modify the inference level too, since we would have to add a new inference for the new position type).

Using concept reification, we can obtain individuals representing sets of other individuals by reifying con­ cepts of the form one_of(il; ... , in)· This observation allows us to concentrate in the following on "concept reification" .

Note that the role E allows us to regard the assertional component of the DL (the ABox) as consisting of role tuples only, since instance assertions of the form X : C can be viewed as tuples of the role E.

Concept reification, as studied in this paper, is dif­ ferent from Kobsa's role reification implemented in SB­ ONE [Kobsa, 1991] . More precisely, while the reification of a concept is an individual, Kobsa's reification of a role is a concept . (Kobsa's approach has been motivated by natural language applications in which a verb, f?r example, is regarded in some contexts as a role and m other contexts as a concept.) Therefore, while we are concerned with mixing the TBox and the ABox of a DL, Kobsa has dealt with mixing concepts and roles within the TBox (while keeping TBox and ABox disjoint) .

As previously mentioned, concept reification involves a form of higher-order logic since the interpretations of value and existential restrictions on the E-role employ a form of quantification over concept-valued variables. Therefore whereas in ordinary DLs concepts exist only as named: terminological ( TBox) level elements, in rei­ fled DLs concepts may be individuals ("data") as well.

Reification and the related higher-order features are also essential in object oriented databases (OODBs) [Beeri, 1990]. In classical database systems there are two distinct levels: data and schema (similar to ABox and respectively TBox in description logics) .

In OODBs, meta-data (such as classes and functions), are frequently treated as data. Class objects acquire thereby a dual nature: on the one hand they are data and can be manipulated by the system; on the other hand, they are schema-level objects and thus part of the schema.

This situation is similar to concept reification as in­ troduced in this paper. In fact , it is our opinion that the lack of a unified approach to description logics and OODBs is mainly due to the clear-cut separation of TBox and ABox (i.e. to the absence of reification) in DLs.

However, introducing concept reification in DLs is sig­ nificantly harder than in OODBs since we have to modify the D L inference services (consistency and subsumption tests) to cope with the new construct. Since no ana­ log inference services exist in OODBs and as long as we deal with reification in an explicit manner alone, there seem to be no complications in reasoning with the new construct in OODBs.

3 Some description logics provide the one_of(i!, ... , in) construct which denotes the concept whose extension is given by the set of instances {iJ, . . . ,in}. However, what w~ need is a concept construct whose instances denote sets or lists of other instances.

Another somewhat related formalism is F-logic [Kifer et a/., 1995], which attempts to provide sound logical foundations of object-oriented as well as frame-based languages and can be considered as a declarative ap­ proach to deductive object-oriented databases.

F-logic provides a form of explicit reification, but it lacks the E-role and the related DL inference ser­ vices. Therefore, we can easily represent F-logic object models in reified DLs. For instance, an F-logic non­ inheritable property objectfproperty ---+ value] would be represented in reified DLs as a tuple of the role prop­ erty involving the individual object: (object, value) : property, while an inheritable property of the form objectfproperty ·- value] would be captured by a DL terminological axiom imposing a restriction on the fillers of the role property for the instances of bbject: object C 3property. {value} . F -logic signature (typing) expressions of the form object [property=> type] can also be represented in DLs as value restrictions object C Vproperty.type . Of course, set-valued attributes in F­ logic correspond to DL roles, while normal F-logic at­ tributes would be represented in DLs as functional roles (attributes) . It is our opinion that the DL representa­ tion makes the distinction between the assertional and terminological properties of objects clearer.

It is worth noting that many frame-based knowledge representation systems (for example KEE) allow a class to be at the same time an instance, but this feature has usually no associated formal semantics.

2 Reifying concepts in description logics - semantical considerations

Traditional description logics separate the terminologi­ cal (TBox) and assertional (ABox) levels completely by not allowing a concept to be regarded at the same time as an individual. This simplifies the semantics and cor­ responding reasoning algorithms.

In this paper we consider an extension to DLs that eliminates this restriction. Concept reification amounts to associating with each concept C an individual C'.

Additionally, we allow the membership role E and its inverse 3 . The role E links an individual X with some other reified concept C' whenever X is an instance of C (regarded as a concept) .

As already mentioned, concept reification involves a form of higher-order logic. For example, in defining the interpretation of V 3 .C :

we quantify over all concepts y, not just the ones that are explicitly given. Since higher-order logics lack even a sound a complete axiomatization and in order to preserve the desired computational properties , we will restrict the semantics of the logic to a first-order semantics. This amounts to interpreting quantified concept variables as ranging over (explicitly given) reified individuals, or in­ tensions , rather than over all concepts that potentially exist (or their extensions) . Therefore, we will allow reifi­ cation of concept names only.

Actually, we can drop the explicit reification construct .' (and use C instead of C' for all concept names C) be­ cause we can determine the type of an object (whether it is a concept or an individual) from the context in which it is used. For example, C in the concept term V R .C is regarded as a concept, while if we use it in the as­ sertional axiom C : D , then C represents the reification of the corresponding concept (i.e. an individual). As previously mentioned, since we don't have an explicit reification operator, we will allow reification of concept names only. For instance, we will not allow ABox asser­ tions like (VR.C): D.

Also, since we interpret concept-valued variables over intensions rather than extensions, it may be that the reified counterparts of two equivalent concepts, C and D, represent two different individuals.

We can use the membership role E to express all in­ stance assertions X : C (for concept names C) as tuple assertions of X E C . Therefore, we can regard the ABox as consisting of tuple assertions only.

Reified description logics are quite expressive.

For example, it is easy to check that V 3 .C represents, roughly speaking, the power-set P(C) of C (the set of subset of C), while 3 E .C denotes the union U C of the instances of C, regarded as sets.

Although reified DLs are capable of representing con­ cepts like V 3 . T denoting "the set of all sets" , we do not run into logical paradoxes, since V 3 .Tis equivalent ,.as expected, to the top concept T.

Since the union of all subsets of a set C is equal to C, UP( C) = C, we obtain the identity 3 E .V 3 .C = C which could be regarded as an axiom in reified DLs. However , only the "+--" direction is specific to E, the " ---+" direction being an instance of the axiom for role mverses.

Additionally, note that C is an instance of 3 3 .D iff C n D is consistent, and that C is an instance of V 3 .D iff C C D. In reified DLs, subsumption is therefore reducible (within the language) to instance checking.

The following identities specific to reified DLs can also be easily checked 4 :

Also, since Cis an instance of 3 3 .{X} iff X E C, we can regard 3 3 . {X} as denoting the set of concepts C for which X is an instance. This observation shows that the "realization problem" 5 for X has a solution expressible in the language, namely 3 3 .{X} .

4 {X} is the singleton concept whose extension has only one element, X .

5 retrieving the set of concepts C that admit a given indi­ vidual X as an instance.

The examples and observations above give a flavour of the intricate ways in which reification and the E-role interact with one another and the other DL constructors.

After having informally presented concept reification in DLs, let us now try to formalize it. For reasons of sim­ plicity, we are going to discuss reification in the A.CCOe;, language (A.CC of Schmidt-SchauB and Smolka [1991J extended with the one-of construct) , but the results are easily extensible to more expressive languages.

The syntax of reified A.CCOE deals with the following three sets of (syntactic) objects:

• Names denoted by X , Y, ... (including .l)
• Concept-Terms denoted by C, D, ...
• Role- Terms denoted by R, Q, .. .

The set Names contains individuals and concept names occurring in the DL knowledge base. Since we want to allow for the reification of concept names, in­ dividuals and concept names will have to belong to a single syntactic category (Names) (as opposed to tradi­ tional DLs where they fall under syntactically disjoint cat.egories) .

Concept- Terms are terms built from concept names (belonging to Names) using the following A.CCOE con­ cept constructors:

({X} is a singleton concept; general one_of(X 1, ... , Xn) concepts can be represented as {XI} U ... U {Xn} .)

Role-Terms are built from role names (which are not in Names, since we do not reify roles) using the spe­ cific DL role constructors. Since A.CCO admits only role names, A.CCOE will admit only the following roles:

The semantics of a DL allowing reification is also a bit different from the usual DL semantics.

Traditional DLs separate the terminological (TBox) and assertional (ABox) levels completely and define a polymorphic interpretation function .I which interprets concepts as sets of elements of some interpretation do­ main 6. and individuals as elements of 6.:

As long as individuals and concepts are distinct, this works fine. But as soon as we allow concept reification, a given object name X can play both the role of an individual and of a concept name and we cannot use the above polymorphic interpretation function any more (because we wouldn't know how to define XI: as an element of 6., or as a subset of 6. ?).

Therefore, we are forced to introduce two different in­ terpretation functions:

1. one that interprets object names as elements of the interpretation domain 6. (i.e. regards them as in­ dividuals) v : Names -+ 6. (the "name function") and
2. one that associates an extension with concept and role terms (the "extension function") :

The "name function" maps object names to elements of the interpretation domain 6.. Such elements x E 6. can be regarded either as individuals (if we use their names) or as concept names (if we use their extensions) .

In order to retrieve the extension of an element x E 6. regarded as a concept name, we need an additional function, the "value function" V : 6. -+ 2~.

V associates with each x E 6. the extension V( x) C 6. of the concept name denoted by x , and is therefore uniquely determined by the extension of the E-role:

(in fact , Vis a functional representation of the extension of the r?le 3). c:( E) must verify the following (first-order) constramt:

(i.e. Vx E 6..3y E 6. .V(y) = {x}) . This constraint says that each singleton { x} must have an intension y in 6. (this is needed, for example, to prove C-+ 3 E .V 3 .C). We also interpret the 3-role as the inverse of the E-role: c:(3)=c:(E)- 1 .

Using the "value function" and the "name function", we can now construct the extensions of concept names as

The extension of concept terms is defined as usual de­ pending on the particular DL concept constructors:

An interpretation I is uniquely determined by the "name function" v : Names -+ 6. and the "exten­ sion function" restricted to role names (including E) c : Role_Names U {E} -+ 2~x~. It can be extended to a full interpretation as follows :

• first, we extend c from role names to role terms
• then we use c:( E) to determine the "value function" V : 6.-+ 2~ according to (1)
• this in turn helps us define the extension of concept names according to (2)
• finally, c extends naturally to concept terms as in (3) .

Having two different interpretation functions v and c: applicable to a given object X allows us to talk about the interpretation xv of X as an individual and as a concept c:(X) at the same time! This wasn't possible in the old setting, where we had a single polymorphic interpretation function .I .

3 Reasoning in reified A.CCOE

Like in traditional description logics, the reasoning ser­ vices in reified ACCOE are reducible to the knowl­ edge base (KB) consistency test [Buchheit et a/. , 1993] . Therefore, we will concentrate in the following on check­ ing consistency in ACCOE knowledge bases . The al­ gorithm is a non-trivial extension of the algorithm for ACC and is based on a tableaux-like calculus operating on constraint systems.

Starting from an initial constraint system represent­ ing the KB, the calculus tries to construct a model of the knowledge base by applying a series of propagation rules. In doing so, it may discover obvious contradictions (clashes) and report the inconsistency of the original KB, or it may come up with a complete clash-free model, thus proving the satisfiability of the knowledge base.

The initial knowledge base to be tested for consistency is represented as a set of constraints of the form:

where X, Y and C N are names, C is a concept term and R a role term. We also assume that all the concepts and roles occurring in constraints have been previously brought to the negation normal form .

The KB consistency checking algorithm applies a se­ ries of propagation rules to a given constraint set S, until either an obvious contradiction (or clash) is generated (thereby proving the consistency of S), or no propaga­ tion rules are applicable any more (case in which the constraint system is called complete and can be used to construct an interpretation of S).

The propagation rules for ACCOE, presented in Fig­ ure 2, can take the following two forms :

Both forms fire only if the condition 1 holds · and if the current constraint system contains constraints match­ ing a. After execution, the first deletes the constraints matching a from the constraint system, while the second keeps them. Both forms add the constraints from f3 to the constraint system after firing.

The predicate individuai(X) succeeds on constant in­ dividuals, variables or singleton constructs {X}, while ro/e_name(R) succeeds only on role names (excluding E and 3) .

The rule ( --.{1.}) can be explained as follows : C : --.{ l.} holds iff C # 1. , i.e. Cis not the "empty" concept. C is therefore consistent and admits an instance X : C . The special case l. : --.{ l.} is avoided by this rule since it is dealt with by the (clash{}) rule.

Note that the (V E) rule asserts Y to be an instance (of C) only if it is an individual (since we allow reification of concept names only) .

Since X is an instance of the singleton concept {X}, rules ('v' E {}) and (V 3 {}) make sure that this is taken into consideration during constraint propagation.

Finally, rule (de!) deals with acyclic 6 definitions def(CN, C) of concept names CN (C being a concept term) . Such definitions are interpreted semantically as c(CN) C c(C) . We shall not address the issue of more complex definitions (like general concept inclusions or equations) in this setting, since ACCOE is "unstable" due to the presence of the 3 role (the inverse of E) . In­ stability amounts to the possibility that after having ex­ panded all the constraints for some individual X, at some point in the future new constraints involving X get dis­ covered. For example, if we apply the propagation rules to x : ( c n V E .V 3 .d) and expand all the constraints in­ volving x, we obtain the constraints (1)-(3) below. But subsequent applications of propagation rules eventually discover a new constraint involving x (namely (5)) , thus proving the instability of ACCOE .

The same kind of problem occurs if we allow role in­ verses and general inclusions, for which the results in [Buchheit et a/., 1993] are no longer applicable (because the stability lemma fails in the presence of role inverses) . The problems posed by role inverses are deep and will not be tackled in the present paper since they are orthogonal to the issue of interest here (namely reification) .

Note that the ABox assertion T : V 3 .Cis equivalent to the TBox axiom stating the validity of C and can therefore be used to express general concept inclusions or equations. In order to avoid the above-mentioned problems with general inclusions, we will not allow T to be used as a concept name. 7

6 Cycles "through" the E (or 3) role are anyhow problem­ atic from a semantical point of view. For example, since 3 should be well-founded (...,repeat(3) in repeat-PDL notation) , cycles involving 3 should be interpreted probably w.r.t . least fixpoint semantics.

Also, such cycles don't seem to occur in practical applica­ tions anyway.

The following sequence of constraints illustrates the consistency checking algorithm applied to the KB con­ sisting of constraints (1) and (2) below.

3.1 Soundness and completeness

The termination and soundness ofthe algorithm are easy to prove. Its completeness is established by construct­ ing a canonical interpretation Is for each clash-free and complete constraint system S. Note that the propaga­ tion rules deal with so-called "extended" constraints , i.e. constraints of the form X : Y and (X, Y) : R where X and Y can be not just names, but also "extended" individuals represented by arbitrarily nested singletons like{ ... {Z} ... } (if we disallow extended individuals, we loose the completeness of the algorithm) .

We can extend the "name function" v to the set N amesD of "extended" individuals and thus talk about the name (intension) {X}" of an "extended" individual {X} . The extended name function must satisfy the con­ straint V( {X}")= {Xv} .

The canonical interpretation Is is defined by

for X, Y E N amesD and R =j:. E, 3. The extension of concept names can thus be obtained as:

c extends naturally to concept terms according to (3) .

Testing the consistency of A.CCOE knowledge bases w.r.t. the proposed semantics is therefore decidable.

4 Conclusions

Extending description logics with concept reification is essential for developing domain-independent and reusable models. Nevertheless, it has not been exten­ sively studied, mainly due to the semantical problems posed by its inherent higher-order features and because of the complications in the reasoning algorithms. ·

7 We also disallow iff-definitions since these would enable us to define a concept nameD= Eu...,E equivalent toT, and the above problems with expressing valid concepts C using D: 'V 3 .C reappear.

The semantical problems related to the higher-order features implicit in reification are solved by defining a first-order semantics which ensures the decidability of the main inference services. We have also described sound and complete inference algorithms for the reified terminological language A.CCOE (but the algorithms can be extended to more expressive languages) .

In our view, concept reification represents an essential element for bridging the gap between description logics and (deductive) object-oriented databases.

It also makes description logics expressive enough to be used for developing generic problem solving models [Badea and 'filivea, 1996] and even libraries of such mod­ els.

Acknowledgments

Thanks are due to Doina Tilivea and Alon Levy for interest­ ing discussions as well as to anonymous reviewers for their helpful comments and especially for pointing out the paper [Franconi, 1993] (which also introduces an explicit member­ ship role, but does not provide a complete reasoning algo­ rithm) .