;; All people have exactly one nose
(forall ?x (=> (person ?x)
(= (cardinality (setofall ?y (nose ?x ?y))) 1)))

;; Noses are unique
(forall (?x ?y)
(=> (and (person ?x) (person ?y))

Axioms are usually viewed in one of 4 ways.

· As Documentation. In this view, theories aren't checked for consistency. Axioms serve to record the intent of the knowledge base's creators.
· As Weak Constraints. In this view, theories are assumed to be consistent until they can be proven false. If an instance of person is created and the nose slot does not have a value, the axiom that all people have exactly one nose has not been violated (and the theory is not inconsistent). If, on the other hand, the nose slot has two provably distinct values, then the axiom has been violated and the theory is inconsistent.
· As Strong Constraints. This view is similar to adopting the closed-world assumption. If an instance of person exists, and the nose slot has no declared value, then the axiom has been violated and something must be done. One strategy might be to signal an error
· As Value-Propagation Devices. The first three interpretations in this list concerned whether a given proposition (the axiom) is true or not. In this fourth view of the world, the axiom must hold (and the system will try to make it hold). This is much less common than the first three (what happens when the nose slot has no value? Having the system create a default nose seems a tad extreme).

Typically, a system will use some combination of these approaches. For example, a typical system might make the following decisions: Most axioms will be interpreted as weak constraints, but not checked (due to the run-time difficulties associated with undecidable algorithms); most facets will be interpreted as strong constraints; and some facets (for example, an inverse-slot facet) will be interpreted as value-propagation devices.

3. THE PROTÉGÉ PROJECT

This section illustrates two of the main design choices in the Protégé toolset. We will look carefully at these decisions and illustrate their impact on the Protégé knowledge model.

3.1. Full Support for Building Knowledge Bases

There are at least three stages to the construction and use of a knowledge base: an ontology must be defined, reasonably static and long-lasting instances must be acquired, and run-time data must be entered (often when an application is running). For example, in the medical domain, these steps might correspond to gathering a medical vocabulary, acquiring specific protocols for patient care, and getting the details of a patient visit.

In many cases, it is unreasonable to expect the people building the knowledge base to be familiar with the sophisticated and subtle issues that pervade the literature on knowledge representation. Knowledge acquisition is frequently done by humans, as part of a job that requires no previous knowledge based systems experience. Protégé takes this into account and is explicitly designed to allow domain experts to build knowledge bases without constantly referring to an expert in knowledge representation.

How Protégé Takes Knowledge Base Construction into Account

The Protégé toolset takes a similar approach to that used by description logics. That is, we strongly distinguish between classes ("concepts" in description logics) and instances. This enables us to establish the following user-interface paradigm:

· Classes are concepts, related hierarchically. Protégé provides an easy to use, Windows-based ontology editor.
· Associated to each concept is a graphical prototype of a form. Protégé will automatically generate default versions of these forms which can then be customized.
· Prototype forms have user-interface controls that allow information to be easily entered and validated.
· Creating an instance involves filling out a blank form of the appropriate type. Filling out forms is a time-honored and well understood, if slightly bureaucratic, way of entering information. As such, it provides users with an easy-to-understand and easy-to-follow way of performing what often is an ancillary task for the human expert.

By including these tools inside the Protégé toolset, we have substantially lowered the barrier to knowledge base development for users, made the development of applications much simpler (since we provide almost all of the knowledge base construction code), and established a uniform look and feel across knowledge-acquisition programs.

Consequences for the Knowledge Model

The above benefits come at a price. By focusing on users and on providing easy-to-use tools for designing ontologies and forms, we have deliberately chosen not to include some of the more baroque knowledge representations within our knowledge model. To do otherwise would needlessly complicate what is a fairly straightforward task in most cases. It would also have a bad effect on the user interface: when a slot is also a facet and a class, both the "class is a concept" and the "create an instance by filling out a form" metaphors break down completely.

3.2. Use of PSMs as Inference Engines

The Protégé toolset also has an explicit code-reuse model, based on the idea of separating out reasoning mechanisms. Given a knowledge base, there are many different tasks that can be performed using the information in it, and many different types of inference that could be appropriate. Rather than build the inference engine into the knowledge base management system, Protégé supports the problem-solving method model, where in which reasoning is done by specialized components that can be reused in many different applications.

This model has many benefits:

· It enables easier adaptation of existing knowledge-based systems and methods of inference. Developers can use the Protégé tools for ontology design and knowledge acquisition without making any commitment to a particular PSM.
· It enables the use of various shells and libraries that have already been developed. For example, many Protégé applications include at least one CLIPS-based PSM.
· It enables collaborative development-Protégé provides a base environment and then problem-solving methods and knowledge bases developed for one application can be reused in others.
· It enables the production of lightweight knowledge acquisition tools.

Reuse of PSMs and Knowledge via Mapping Relations

The question then arises: How do we reuse a problem-solving method ? One possible answer is: through the use of mediators (Gennari, et al. 1994; Gennari, Grosso, and Musen, 1998; Park, Gennari and Musen, 1998). In the Protégé methodology, mediators define a transformation of the domain ontology into a domain-independent ontology that the problem-solving method uses (frequently referred to as the "method ontology"). The map on ontologies induces a map on the entire knowledge base and thus provides the problem-solving method with data.

Consequences for the Protégé Knowledge Model

The use of mediators limits the knowledge model in much the same way that knowledge acquisition did. To see this, we once again consider the illustrative example of description logics.

Suppose that the ontologies are all expressed in one of the more tractable description-logics. And that the mediators are defined as a sequence of the following simple operations:

· Eliminating a slot
· Collapsing the distinction between a parent and a direct child if the child does not define additional slots,
· Combining two classes related by a has-a style relationship into a single class.
· Renaming a slot or class.
· Combining several slots using arithmetic operations (where appropriate).

Then, verifying that the mediator is sound and complete reduces to subsumption and is well-known to be decidable in polynomial time (Borgida and Patel-Schnedier, 1994).

If, on the other hand, if the knowledge model is a multi-sorted second order logic, decidability is a hopeless endeavor. This is yet another instance of the classical tension between expressiveness and tractability (Levesque and Brachman, 1985): We want the knowledge model to be sufficiently expressive for good modeling and we want to be able to easily create and verify mediators that are both sound and complete. Work towards reconciling these two aims is ongoing.

4. Open Knowledge Base Connectivity

In the early 1990's, DARPA funded a series of projects aimed at reusing declarative knowledge. Among the standards developed were the Knowledge Interchange Format (KIF) and the Generic Frame Protocol (GFP). KIF was intended to be an interlingua: a way to transmit declarative knowledge between components. In this view of interoperability, knowledge-based systems would use their own representation internally, but would be able to translate their declarative knowledge into KIF statements (and create internal representations from KIF statements).

The Generic Frame Protocol (GFP) was an attempt, by researchers at SRI and Stanford KSL, to define a unified API for frame representation systems (Karp et al, 1995) and grew out of Karp's study of frame representation systems (Karp, 1993). GFP aimed at reusing procedural code. As one paper (Karp et al, 1995) put it, "Just as knowledge reuse is extremely important, so is the ability to reuse, and to mix and match, the software components of a large AI system." GFP defined a universal API for knowledge-base management systems in the hope that client-software (in particular, knowledge management utilities) would then be reusable across frame representation systems.

OKBC expands the GFP API by defining a knowledge model and behaviors, in an attempt to guarantee the semantics of commonly used API calls (Chaudhri et al, 1997). The goal of OKBC is thus explicitly to reuse knowledge bases inside a knowledge base management system (and not the KIF approach of creating an "interlingua"). The current version of OKBC explicitly incorporates KIF as an underlying representation language and thus incorporating a solid model-theoretic notion of semantics.

The goal of this section is to illustrate three of the main design choices in the OKBC specification. We will look carefully at these decisions and illustrate their impact on the OKBC knowledge model. In section 5, we will compare this knowledge model to the Protégé knowledge model.

4.1. Use KIF as an Underlying Logical Language

One of the main goals of the OKBC specification is to provide a solid semantics for frame-based representations (see Hayes, 1979; Gruber, 1991; Gruber, 1993). To provide solid semantics, one must choose a logical formalism and restrict all definitions to those that can be expressed in this language.
KIF was chosen as the underlying logical language for OKBC. This choice necessitates translating frame-based intuitions into logical and/or set-theoretic notions. Thus, in the history of frame-based systems, we have gone from "A frame is a data-structure for representing a stereotyped situation..." (Minsky, 1985) to "Formally, a frame corresponds to a KIF constant" (Chaudhri et al, 1997).

OKBC continues in this vein, defining classes to be sets (alternatively, the unary relations that define a set), instances to be elements of the set, slots to be binary relations, and facets to be ternary relations. Moreover, classes, slots, instances, and facets are all frames and any valid KIF sentence can be asserted about them. OKBC thus gives a very clean and precise set of logical definitions, but it's unclear that common intuitions about frame-based knowledge representations have been adequately captured.

For example, a KIF symbol can be both a class and a slot. There is no explicit "slot" predicate in OKBC, but instead "slot-of" and "template-slot-of." That S is a slot of F taking value V is implied by the assertion (S F V). Since KIF allows predicates to have variable arity, there is nothing to prevent S from also being a class (in the OKBC specification, a class is simply a relation with arity 1). This multiplicity of meanings can be confusing for people who have dealt with frame-based representations but not with explicit logical formulations of them.

4.2. Avoid Formalisms that aren't Widely Supported

OKBC deliberately avoids some of the more esoteric things that frame representations do. For example, it makes no commitment to either an axiom language or to any inference mechanisms within the knowledge base management server.

It's hard to see how the OKBC designers could have done otherwise; they certainly couldn't have legislated a universal axiom language for all frame representation systems. On the other hand, researchers developing client applications are either going to restrict themselves to a subset of the OKBC-compliant servers (partially defeating the purpose of OKBC) or avoid axiomatic representations.

4.3. Use "Behaviors" to Represent System Differences

In order for a KBMS to be OKBC compliant, it must be compatible with the OKBC knowledge model. However, it need not support every nuance of the OKBC knowledge model. Behaviors are the mechanism by which a KBMS can signal that it only supports some subset of the OKBC knowledge model. The function get-behavior takes, as argument, the name of a behavior and returns the defined value of the behavior in the knowledge base. For example, (get-behavior :are-frames) might return {:class, :instance}. This means that neither slots nor facets are frames. Which in turn implies that neither can be either a class or an instance or have slots.

The OKBC specification defines many behaviors. Each behavior can be viewed as a set of additional axioms on top of the knowledge model. For example, the are-frames behavior allows a system to tell clients what gets treated as a frame (what elements of the knowledge model correspond to KIF constants). And the return value {:class, :instance} is logically equivalent to adding axioms asserting that neither slots nor facets can be frames.
Behaviors are convenient and allow for a large number of systems to quickly become OKBC compliant, at the cost of defining many different knowledge models, all of which are consistent with the general OKBC knowledge model (since all they do is add in additional constraints on what can be expressed).
This is reasonable-after all, the goal of OKBC is to provide a common API for a wide variety of frame representation systems. On the other hand, it means that researchers developing client applications are either going to restrict themselves to a subset of the OKBC-compliant servers (partially defeating the purpose of OKBC) or use a fairly limited style of modeling.

5. COMPARING THE PROTÉGÉ AND OKBC KNOWLEDGE MODELS

This section is a description of some of the differences between the Protégé and OKBC knowledge models. As we describe in Section 6, our aim is to share knowledge across these models: to publish Protégé knowledge bases into OKBC, and to read OKBC knowledge bases into Protégé. To achieve this interoperation, we must understand all the differences between the knowledge models.

These differences can be divided into three types: fundamental, structural, and procedural.

· Fundamental Differences. Fundamental differences involve the types of constructions that are supported by the frame language (for example, whether slots can have slots) and what can be explicitly reasoned about (whether slots are reified into frames).
· Structural Differences. Structural differences involve the structures that the KBMS creates as side-effects of a creation operation. For example, when a frame (a knowledge-base, a class, whatever) is created, what else is created as a consequence. In many cases, a given structural difference is implied by a fundamental difference.
· Procedural Differences. Procedural differences involve the minor niggling details of communication with the KBMS (e.g. things like how frame handles are obtained and whether they are unique).

Of these, fundamental differences are the most interesting and come close to determining the entire knowledge model. Thus, for brevity, we have restricted this section to a table of the fundamental differences, along with explanations (Table 1). In many ways, the explanations provide capsule summaries of the discussion in previous sections.

Issue	Protégé	OKBC	Explanation
What is a frame ?	Only classes and instances can be frames	Classes, instances, slots, and facets are all frames.	Because of its focus on knowledge-acquisition, Protégé strongly enforces "slots are attributes of concepts." Thus they have values but are not reified.
Are Meta-class Relationships allowed?	No	Yes.	This difference is rooted in both knowledge acquisition and the desire to build mediators: knowledge acquisition because end-users find the idea of meta-classes confusing (thus potentially invalidating the data) and mediators because of the strong "pipe/data" focus in the Protégé project.
Are there own slots on classes?	Every class is created with 3 own slots. No others can be attached in any way.	Yes. Both by inheritance (meta-classes) and by direct attachment. Users can create arbitrary own slots.	The Protégé model has evolved due to engineering requirements. One own slot, role, came about in order to distinguish between classes that need forms and classes that don't (if no instance of the class is ever acquired, there is no need to design a form). There is also a documentation slot. And, recently, it has become obvious that a constraint slot, allowing axiomatic constraints on classes, is also necessary.
How are slots attached?	Slots can only be attached as template slots on classes. All other attachments are structural or by inheritance.	Arbitrary.	This is another example of a KA driven requirement. Allowing modelers to directly attach an own slot, while useful in some cases, may cause far more confusion than it is worth.
How are facets attached?	Each template slot has a predefined set of facets.	Arbitrary.	In Protégé, facets have a single role: they are constraints on slot values. This limits their utility but enforces a certain consistency on models (design choices appear in class definitions).
Which slots can have values?	Own slots.	Both own and template slots can have values.
Can facet values be over-ridden in subclasses?	Yes.	No. Additional values can be asserted, but values asserted for the superclass are asserted for the subclass as well.
Can axioms refer to anything?	Axioms can only directly refer to classes and slots.	OKBC makes no commitment to any notion of axioms (outside of a very limited tell/ask interface).	Protégé takes the point of view that an axiom which refers to an instance, or a group of instances which do not comprise a named class, is probably the result of a modeling error.

Table 1: Fundamental Differences in the Knowledge Models

6. MAKING PROTÉGÉ OKBC COMPLIANT

One of the fundamental truths of the knowledge-based systems field is this: knowledge is expensive. Building a knowledge-base requires domain experts, skilled ontologists, and a lot of hard work. If at all possible, we should reuse knowledge-bases, rather than rebuilding them.

This implies two things for the Protégé Project:

(1) Tools should be developed to export knowledge-bases built in Protégé to OKBC compliant knowledge base management systems.
(2) Tools should be developed to enable Protégé to use knowledge-bases residing in some OKBC compliant knowledge base management system.

6.1. Exporting to a Sufficiently Generic OKBC Server

The Protégé knowledge model is weakly compatible with the generic OKBC knowledge model. That is, we can write a set of axioms in KIF that are consistent with the OKBC knowledge model and thereby define a restricted knowledge model which is almost isomorphic to the Protégé knowledge model (as in Figure 2).

For example, we have taken the statement "Every class is created with three own slots. No others can be attached in any way" and modeled it by using a distinguished meta-class as follows:

The only known difficulty with this approach is the relationship between inheritance and template facet values. Protégé allows over-riding of template facet values and the OKBC knowledge model does not.

We plan, after testing and refining, to submit the specification for the Protégé Knowledge Model as a new behavior for OKBC. Exporting a knowledge-base built in Protégé to OKBC will then consist of the following three steps.

(1) Tell the OKBC-compliant server to create a new knowledge base
(2) Either the Protégé behavior flag is set (if the server supports the behavior) or the Protégé Constraint Set is asserted using the tell portion of the OKBC API.
(3) The knowledge base is copied over using the OKBC API and replacing :THING with :protege-thing (a direct subclass of :THING with the appropriate own slots from the Protégé knowledge model) in all inheritance relationships.

6.2. The Problems Involved In Importing

Using a knowledge base inside an OKBC server is more problematic because we anticipate most existing knowledge bases will be made available via OKBC in roughly the same way that Protégé knowledge bases will be. That is, the tools used to create the knowledge bases will have a rather idiosyncratic knowledge model. And these idiosyncracies will be preserved in the knowledge base available via OKBC.

Figure 3 illustrates the problem: two different knowledge models, each a restriction of the OKBC knowledge model, are not necessarily compatible (and thus reusing the knowledge may be difficult).

Unfortunately, the problem is more generic than Figure 3 might indicate. A knowledge base that is perfectly valid with the original OKBC knowledge model (e.g. doesn't constrain the OKBC knowledge model in any way) may not be valid in either of the restricted knowledge models. An application which implicitly relies on one of the more restricted knowledge models will not be able to use all the information in the knowledge base.

We believe that this scenario is still a significant improvement over prior scenarios for two reasons. The first reason is that the knowledge bases are consistent with the OKBC knowledge model. While they may further restrict the meaning of some of the relations defined by OKBC, they do not contradict anything stated by the OKBC specification. Which means that large portions of the OKBC API are still quite meaningful. Our hope is that in practice, this will prove sufficient.

The second reason is that both knowledge models will have formal specifications in similar terms (e.g. the formal specifications will both incorporate OKBC's frame ontology). If the knowledge base does need to be translated, having a formal specification in a common language will undoubtedly lower the cost of doing so.

7. DISCUSSION

In this paper, we have discussed formal specifications for knowledge models in great detail. We believe that knowledge models are important, and will continue to grow in importance as the community continues to focus on reuse and interoperability. We base this belief on three straightforward claims which, taken together, imply that sophisticated and logically correct use of a foreign knowledge base requires knowing the underlying knowledge model:

· Formal knowledge models are very useful in pinpointing knowledge base translation difficulties and are probably the only way to reliably do so.
· Some representational constructs do not have straightforward translations. Indeed, for some, the "right" translation depends on the ontology and the intended use (e.g. there is no logically equivalent translation).
· It may be better to strive for "taxonomic equivalence" rather than "logical equivalence." That is, the taxonomic structure of an ontology is crucial for use in applications (and for human understanding). Translators which preserve "intuitive semantics," even at the cost of logical equivalence, may be desirable.

Our analysis of Protégé and OKBC is a start toward verifying these claims. As we described in Section 6, the ability to relate the constraints of the Protégé knowledge model to the OKBC knowledge model allows us to both formally define a mapping from Protégé to OKBC (as presented in the appendix), and to better understand the relationship between OKBC and Protégé knowledge bases.

Although our analysis does not lead to completely automatic knowledge base translation, it clarifies which constructs and semantics are problematic for interoperation. This makes the job of developing reusable knowledge bases easier- authors will know which constructs are "safe"2 and which bind the knowledge base to a particular KBMS. Moreover, the analysis serves to underscore an important point- in order for a knowledge base to be truly generic, the authors need to adopt a restricted knowledge model.
If all knowledge base systems published formal knowledge models, as we have done for Protégé and as Chaudri et al. (1997) have done for OKBC, and if we can analyze and compare these knowledge models, then we will have greatly advanced the ability to share and interoperate across knowledge base systems.

Acknowledgements

This paper owes whatever clarity and insight it managed to achieve to the collective efforts of the (alas, anonymous) reviewers and the percipience of Samson Tu. Parts of this work were funded by the High Performance Knowledge Base Project of the Defense Advanced Research Projects Agency.

References

Borgida, A., Patel-Schneider P. (1994). A semantics and complete algorithm for subsumption in the CLASSIC description logic. Journal of Artificial Intelligence Research 1: 277-308

Brachman R, Levesque, H. (eds). (1985). Readings in Knowledge Representation. Morgan Kauffmann Publishers.

Chaudhri, V., Farquhar, A., Fikes, R., Karp, P., and Rice, J. (1997). The Generic Frame Protocol 2.0 [Online] Available http://www.ai.sri.com/~gfp/spec.html.

Davis, R., Shrobe H. , Szolovits P. (1993). What is a knowledge representation? AI Magazine 14(1): 17-33.

Finin, T., McKay, D., Fritzson, R., and McEntire, R., (1994). KQML-A language and protocol for knowledge and information exchange. In Kazuhiro Fuchi and Toshio Yokoi (Eds.), Knowledge Building and Knowledge Sharing, Ohmsha and IOS Press.

Genesereth, M., Fikes, R., et al (1992). Knowledge Interchange Format 3.0 [Online] Available http://logic.stanford.edu/kif/kif.html.

Gennari, J. H., Grosso, W., Musen, M. A. (1998). A method-description language: An initial ontology with examples. ). Proceedings of the Eleventh Banff Knowledge Acquisition for Knowledge-Bases Systems Workshop. Banff, Canada

Gennari, J. H., Tu, S. W., Rothenfluh, T. E., and Musen, M. A. (1994). Mapping domains to methods in support of reuse. International Journal of Human-Computer Studies, 41, 399-424.

Gruber, T.R. (1991). A translation approach to portable ontology specifications. Knowledge Acquisition, 5, 199-220.

Gruber, T.R. (1993). Ontolingua: A mechanism to support portable ontologies. Stanford KSL Technical Report 91-66

Hayes, P. (1979). The Logic of Frames. In Brachman and Levesque (Eds.), Readings in Knowledge Representation, Morgan Kauffman, pp. 287-295.

Karp, P, Chaudhri, V., and Paley, S. (1997) A collaborative environment for authoring large knowledge bases. submitted for publication.

Karp, P, Myers, K., and Gruber, T. (1995) The generic frame protocol. Proceedings of the 1995 International Joint Conference on Artificial Intelligence, pp. 768 - 774.

Karp, P. (1993) The design space of frame knowledge representation systems. SRI AI Center Technical Note #520

Levesque, H., and Brachman, R. (1984). A fundamental tradeoff in knowledge representation and reasoning (Revised Version). In Brachman and Levesque (Eds.), Readings in Knowledge Representation, Morgan Kauffman, pp. 41-71.

McCarthy, J. (1997). Formulas for the Blocks World. [Online] Available http://www-formal.stanford.edu/jmc/cs323/blocks-formulas.html

Minksy, M. (1981). A framework for representing knowledge. In Brachman and Levesque (Eds.), Readings in Knowledge Representation, Morgan Kauffman, pp. 245-263.

Musen, M.A., Tu, S.W. (1993). Problem-solving models for generation of task-specific knowledge-acquisition tools. In J. Cuena (Ed.), Knowledge-Oriented Software, Elsevier, pp. 23-50.

Neches, Fikes, Finin, Gruber, Patil, Senator, and Swartout (1991). Enabling technology for knowledge sharing. AI Magazine 13(3): 37-56.

Newell, A. (1982). The knowledge level, Artificial Intelligence, 18(2): 87-127

Woods, W. (1975). What's in a link: foundations for semantic networks. In Brachman and Levesque (Eds.), Readings in Knowledge Representation, Morgan Kauffman, pp. 217-243.

Appendix: A Draft Specification of the Protege Knowledge Model

This appendix contains a draft specification for the Protege knowledge model. The specification is written in KIF and is intended to be used in conjunction with an OKBC-enabled knowledge base management system. In particular, the specification is written to simplify procedural aspects of such an implementation. For example, there is no (logical) need to define :protege-thing or any of the "foundational meta-classes" (see below). But doing so makes it clearer what the procedural implementation ought to do in response to various requests and, we hope, enables a fair amount of error-checking to be "on-the-fly" (we certainly hope that servers which implement this knowledge model will enforce it as well).

The Axiomatization

1
Some authors do not think of is-a and instance-of as slots. Instead, they divide the set of binary relations into relations between classes, relations between a class and an instance, and slots.

2
A construct is "safe" to the extent that it is directly translatable into other knowledge models.