Open Knowledge Base Connectivity 2.0.31
-- Proposed --

Vinay K. Chaudhri
Artificial Intelligence Center
SRI International

Adam Farquhar
Knowledge Systems Laboratory
Stanford University



Richard Fikes
Knowledge Systems Laboratory
Stanford University



Peter D. Karp
Artificial Intelligence Center
SRI International



James P. Rice
Knowledge Systems Laboratory
Stanford University

April 9, 1998


Contents

Introduction

This document specifies a protocol for accessing knowledge bases (KBs) stored in knowledge representation systems (KRSs). By KRS we mean both systems that would traditionally be considered KRSs, as well as can be viewed as a KRS, for example, an object-oriented database. The protocol, called the Open Knowledge Base Connectivity (OKBC), provides a set of operations for a generic interface to underlying KRSs. The interface layer allows an application some independence from the idiosyncrasies of specific KRS software and enables the development of generic tools (e.g., graphical browsers and editors) that operate on many KRSs. OKBC implementations exist for several programming languages, including Java, C (client implementation only), and Common Lisp, and provide access to KBs both locally and over a network.

OKBC is complementary to language specifications developed to support knowledge sharing. KIF [4], the Knowledge Interchange Format, provides a declarative language for describing knowledge. As a pure specification language, KIF does not include commands for knowledge base query or manipulation. Furthermore, KIF is far more expressive than most KRSs. OKBC focuses on operations that are efficiently supported by most KRSs (e.g., operations on frames, slots, facets -- inheritance and slot constraint checking). OKBC is intended to be well impedance-matched to the sorts of operations typically performed by applications that view or manipulate object-oriented KRSs.

The Need for a Standard KRS Access Library

There are several motivations for creating a generic access and manipulation layer for KRS services. An application programmer may wish to use more than one KRS during the life of an application. An application that initially used the representation services of KRS1might later use KRS2 because KRS2 is faster, more expressive, cheaper, or better supported. Or, an application might use KRS2in addition to KRS1 -- KRS2 might be more expressive for a subset of tasks, or the application might later require access to a KB that was implemented using KRS2. In addition, OKBC supports reuse and composition of multiple ontologies and KBs. OKBC also allows users to reuse tools and utilities across various KRSs and applications, such as graphical knowledge editors or machine-learning programs.

Although there are significant differences among KRS implementations, there are enough common properties that we can describe a common knowledge model and an API for KRSs. An application or tool written to use these operations has the potential of portability over a variety of KRSs and knowledge bases.

Overview of the Protocol

OKBC specifies a knowledge model of KRSs (with KBs, classes, individuals, slots, and facets). It also specifies a set of operations based on this model (e.g., find a frame matching a name, enumerate the slots of a frame, delete a frame). An application uses these operations to access and modify knowledge stored in a OKBC-compliant KRS.

The current implementations of OKBC is object-oriented: methods in the appropriate object-oriented programming language for an application are used to implement OKBC operations. We refer to the set of methods that implement the protocol for a particular KRS as a back end. Many OKBC operations have default implementations written in terms of other OKBC operations; therefore, the programmer need define only a core subset of all OKBC operations in order to implement a compliant back end. These OKBC operations are called mandatory, and they comprise the OKBC kernel. The default implementations can be overridden within a given back end to improve efficiency.


  
Figure 1.1: The architecture of the Common Lisp implementation of OKBC.
\begin{figure}\centerline{\psfig{figure=clos.idraw,height=2in}} \end{figure}

Design Objectives

The design objectives for OKBC are as follows.

Simplicity: It is important to have a relatively simple specification that can be implemented quickly, even if that means sacrificing theoretical considerations or support for idiosyncrasies of a particular KRS.

Generality: The protocol should apply to many KRSs, and support all the most common KRS features. For example, it should support all the knowledge access and modification functionality that will be required by a graphical KB editor.

No legislation: The protocol should not require numerous changes to an KRS for which the protocol is implemented. That is, the protocol should not legislate the behavior of an underlying KRS, but should serve as an interface between an existing KRS and an application.

Performance: Inserting the protocol between an application and a KRS should not introduce a significant performance cost.

Consistency: The protocol should exhibit consistent behavior across different KRSs. That is, a given sequence of operations within the protocol should yield semantically equivalent results over a range of KRSs.

Precision: The specification of the protocol should be as precise and unambiguous as possible.

Extensibility: The protocol must support the variability in capabilities of KRSs, and the need to add new KRS features over time without penalizing users of less powerful systems.

Satisfying all of these objectives simultaneously is impossible because many of them conflict, such as simplicity and precision, simplicity and generality, and generality and performance. The deepest conflicts, however, exist simultaneously between generality, no-legislation, performance, consistency, and precision, as the following example shows. To specify the behavior of the operation that retrieves the values of a slot precisely and completely, we would have to specify exactly how the local values of a slot are combined with the inherited values of a slot (which may be inherited from multiple parent classes). That is, we would have to specify the exact inheritance mechanism that the protocol expects. Yet, different KRSs use a variety of different inheritance mechanisms [7]. For a KRS to conform to a precise specification of inheritance, it might be required either to alter its inheritance mechanism (violating no-legislation), or to emulate the desired inheritance mechanism within the implementation of the protocol (violating high performance and generality, since the inheritance method used by that KRS would then be inaccessible through the protocol).

The preceding quandary is central throughout the protocol, and we know of no simple solution to the problem. Our approach is for each OKBC implementation to advertise programmatically the capabilities that it provides. Each KB manipulated by the protocol is serviced directly by a single underlying KRS. The OKBC implementation for that KRS must declare what set of OKBC behaviors the implementation can support, and under what set of behaviors it is operating currently. For example, the implementation might declare that it can support only one of the two semantics for the behavior :inheritance, which we call :when-consistent and :override. (If it can support only the :when-consistent behavior, for example, then it must be currently operating under that behavior.) OKBC predefines alternative KRS behaviors, based on the properties of existing KRSs. The application can interrogate the implementation at any time it feels appropriate to determine which of several actions the application might take, or whether it needs to change the current behavior of the underlying KRS.

Many operations in the protocol use language such as, ``The operation returns at least the values derivable from the definition of direct assertions.'' This language defines a lower bound on the capability of any compliant OKBC implementation. An implementation is at liberty to deliver more results as long as they are logically consistent with the documentation of the operation. In this example, we are saying that the server must be aware of the class-subclass and class-instance relationships in the KB, and must perform logically correct taxonomic inferences. The same OKBC implementation is at liberty to perform arbitrary theorem proving as well as the minimal specified inferences. Such theorem proving may well derive other values in addition to those derived by taxonomic inference.

On Terminology

The goal of OKBC is to serve as an interface to many different KRSs. In a review of KRSs, Karp identified more than 50 of these systems [7]. He also observed that there is a lack of agreement regarding terminology in the field of knowledge representation because different researchers often use different terms to mean the same thing, and use the same term to mean different things. For example, there are 10 different terms for the notion of a class, 4 terms for an individual, 4 terms for the relationship between a concept and an individual, 3 terms for the notion of slot values, and 2 terms for the slot and for the slot frame.

The operations within OKBC require names. It is clearly impossible to choose a set of names for the protocol operations that will be considered ideal by the developers of every KRS. We ask readers of this document who are considering adapting the OKBC to their KRS to recognize these facts, and to be tolerant of the terminology herein.

OKBC History

OKBC is a successor of Generic Frame Protocol (GFP) which was primarily aimed at systems that can be viewed as frame representation systems. GFP was originally motivated by a review of KRSs authored by Peter Karp [7], by related earlier work by Barnett and colleagues [1], and by specifications used at the Stanford Knowledge Systems Laboratory for accessing Cyc [11], KEE [10], and Epikit. Karp and Tom Gruber began developing OKBC in 1993 for use with the EcoCyc [6], GKB Editor [9], and Ontolingua projects [3]. In 1995 Karp et al. authored a publication describing the version of OKBC in use at that time [8]. The protocol has undergone many revisions, based on input from many people, including Fritz Mueller, Karen Myers, Suzanne Paley, and Robert MacGregor.

   
The OKBC Knowledge Model

The Open Knowledge Base Connectivity provides operations for manipulating knowledge expressed in an implicit representation formalism called the OKBC Knowledge Model, which we specify in this chapter. The OKBC Knowledge Model supports an object-oriented representation of knowledge and provides a set of representational constructs commonly found in object-oriented knowledge representation systems (KRSs) [7]. Knowledge obtained from an KRS using OKBC or provided to an KRS using OKBC is assumed in the specification of the OKBC operations to be expressed in the Knowledge Model. The OKBC Knowledge Model therefore serves as an implicit interlingua for knowledge that is being communicated using OKBC, and systems that use OKBC translate knowledge into and out of that interlingua as needed.

The OKBC Knowledge Model includes constants, frames, slots, facets, classes, individuals, and knowledge bases. We describe each of these constructs in the sections below. To provide a precise and succinct description of the OKBC Knowledge Model, we use the Knowledge Interchange Format (KIF) [4] as a formal specification language. KIF is a first-order predicate logic language with set theory, and has a linear prefix syntax.

   
Constants

The OKBC Knowledge Model assumes a universe of discourse consisting of all entities about which knowledge is to be expressed. Each OKBC knowledge base may have a different universe of discourse. However, OKBC assumes that the universe of discourse always includes all constants of the following basic types:

Classes are sets of entities2.1, and all sets of entities are considered to be classes. OKBC also assumes that the domain of discourse includes the logical constants true and false.

   
Frames, Own Slots, and Own Facets

A frame is a primitive object that represents an entity in the domain of discourse. Formally, a frame corresponds to a KIF constant. A frame that represents a class is called a class frame, and a frame that represents an individual is called an individual frame.

A frame has associated with it a set of own slots, and each own slot of a frame has associated with it a set of entities called slot values. Formally, a slot is a binary relation, and each value V of an own slot S of a frame F represents the assertion that the relation S holds for the entity represented by F and the entity represented by V (i.e., (S F V)2.2). For example, the assertion that Fred's favorite foods are potato chips and ice cream could be represented by the own slot Favorite-Food of the frame Fred having as values the frame Potato-Chips and the string ``ice cream''.

An own slot of a frame has associated with it a set of own facets, and each own facet of a slot of a frame has associated with it a set of entities called facet values. Formally, a facet is a ternary relation, and each value V of own facet Fa of slot S of frame Fr represents the assertion that the relation Fa holds for the relation S, the entity represented by Fr, and the entity represented by V (i.e., (Fa S Fr V)). For example, the assertion that the favorite foods of Fred must be edible foods could be represented by the facet :VALUE-TYPE of the Favorite-Food slot of the Fred frame having the value Edible-Food.

Relations may optionally be entities in the domain of discourse and therefore representable by frames. Thus, a slot or a facet may be represented by a frame. Such a frame describes the properties of the relation represented by the slot or facet. A frame representing a slot is called a slot frame, and a frame representing a facet is called a facet frame.

   
Classes and Individuals

A class is a set of entities. Each of the entities in a class is said to be an instance of the class. An entity can be an instance of multiple classes, which are called its types. A class can be an instance of a class. A class which has instances that are themselves classes is called a meta-class.

Entities that are not classes are referred to as individuals. Thus, the domain of discourse consists of individuals and classes. The unary relation class is true if and only if its argument is a class and the unary relation individual is true if and only if its argument is an individual. The following axiom holds:2.3 

   (<=> (class ?X) (not (individual ?X)))

The class membership relation (called instance-of) that holds between an instance and a class is a binary relation that maps entities to classes. A class is considered to be a unary relation that is true for each instance of the class. That is,2.4 

   (<=> (holds ?C ?I) (instance-of ?I ?C))

The relation type-of is defined as the inverse of relation instance-of. That is, 

   (<=> (type-of ?C ?I) (instance-of ?I ?C))

The subclass-of relation for classes is defined in terms of the relation instance-of, as follows. A class Csub is a subclass of class Csuper if and only if all instances of Csub are also instances of Csuper. That is,2.5 

   (<=> (subclass-of ?Csub ?Csuper)
        (forall ?I (=> (instance-of ?I ?Csub)
                       (instance-of ?I ?Csuper))))

Note that this definition implies that subclass-of is transitive. (I.e., If A is a subclass of B and B is a subclass of C, then A is a subclass of C.)

The relation superclass-of is defined as the inverse of the relation subclass-of. That is, 

   (<=> (superclass-of ?Csuper ?Csub) (subclass-of ?Csub ?Csuper))

   
Class Frames, Template Slots, and Template Facets

A class frame has associated with it a collection of template slots that describe own slot values considered to hold for each instance of the class represented by the frame. The values of template slots are said to inherit to the subclasses and to the instances of a class. Formally, each value V of a template slot S of a class frame C represents the assertion that the relation template-slot-value holds for the relation S, the class represented by C, and the entity represented by V (i.e., (template-slot-value S C V)). That assertion, in turn, implies that the relation S holds between each instance I of class C and value V (i.e., (S I V)). It also implies that the relation template-slot-value holds for the relation S, each subclass Csub of class C, and the entity represented by V (i.e., (template-slot-value S Csub V)). That is, the following slot value inheritance axiom   holds for the relation template-slot-value: 
   (=> (template-slot-value ?S ?C ?V)
       (and (=> (instance-of ?I ?C) (holds ?S ?I ?V))
            (=> (subclass-of ?Csub ?C)
                (template-slot-value ?S ?Csub ?V))))

Thus, the values of a template slot are inherited to subclasses as values of the same template slot and to instances as values of the corresponding own slot. For example, the assertion that the gender of all female persons is female could be represented by template slot Gender of class frame Female-Person having the value Female. Then, if we created an instance of Female-Person called Mary, Female would be a value of the own slot Gender of Mary.

A template slot of a class frame has associated with it a collection of template facets that describe own facet values considered to hold for the corresponding own slot of each instance of the class represented by the class frame. As with the values of template slots, the values of template facets are said to inherit to the subclasses and instances of a class. Formally, each value V of a template facet F of a template slot S of a class frame C represents the assertion that the relation template-facet-value holds for the relations F and S, the class represented by C, and the entity represented by V (i.e., (template-facet-value F S C V)). That assertion, in turn, implies that the relation F holds for relation S, each instance I of class C, and value V (i.e., (F S I V)). It also implies that the relation template-facet-value holds for the relations S and F, each subclass Csub of class C, and the entity represented by V (i.e., (template-facet-value F S Csub V)).

In general, the following facet value inheritance axiom   holds for the relation template-facet-value: 

   (=> (template-facet-value ?F ?S ?C ?V)
       (and (=> (instance-of ?I ?C) (holds ?F ?S ?I ?V))
            (=> (subclass-of ?Csub ?C)
                (template-facet-value ?F ?S ?Csub ?V))))

Thus, the values of a template facet are inherited to subclasses as values of the same template facet and to instances as values of the corresponding own facet.

Note that template slot values and template facet values necessarily inherit from a class to its subclasses and instances. Default values and default inheritance are specified separately, as described in Section 2.8.

Primitive and Non-Primitive Classes

Classes are considered to be either primitive or non-primitive by OKBC. The template slot values and template facet values associated with a non-primitive class are considered to specify a set of necessary and sufficient conditions for being an instance of the class. For example, the class Triangle could be a non-primitive class whose template slots and facets specify three-sided polygons. All triangles are necessarily three-sided polygons, and knowing that an entity is a three-sided polygon is sufficient to conclude that the entity is a triangle.

The template slot values and template facet values associated with a primitive class are considered to specify only a set of necessary conditions for an instance of the class. For example, all classes of ``natural kinds'' - such as Horse and Building - are primitive concepts. A KB may specify many properties of horses and buildings, but will typically not contain sufficient conditions for concluding that an entity is a horse or building.

Formally: 

   (=> (and (class ?C) (not (primitive ?C)))
       (=> (and (=> (template-slot-value ?S ?C ?V) (holds ?S ?I ?V))
                (=> (template-facet-value ?F ?S ?C ?V)
                    (holds ?F ?S ?I ?V)))
           (instance-of ?I ?C)))

   
Associating Slots and Facets with Frames

Each frame has associated with it a collection of slots, and each frame-slot pair has associated with it a collection of facets. A facet is considered to be associated with a frame-slot pair if the facet has a value for the slot at the frame. A slot is considered to be associated with a frame if the slot has a value at that frame or there is a facet that is associated with the slot at the frame. For example, if the template facet :NUMERIC-MINIMUM of template slot Age of frame Person had a value 0, then facet :NUMERIC-MINIMUM would be associated with the frame Person slot Age pair and the slot Age would be associated with the frame Person. In addition, OKBC contains operations for explicitly associating slots with frames and associating facets with frame-slot pairs, even though there are no values for the slots or facets at the frame.

We formalize the association of slots with frames and facets with frame-slot pairs by defining the relations slot-of, template-slot-of, facet-of, and template-facet-of as follows: 

   (=> (exists ?V (holds ?Fa ?S ?F ?V)) (facet-of ?Fa ?S ?F))

   (=> (exists ?V (template-facet-value ?Fa ?S ?C ?V))
       (template-facet-of ?Fa ?S ?C))

   (=> (or (exists ?V (holds ?S ?F ?V))
           (exists ?Fa (facet-of ?Fa ?S ?F)))
       (slot-of ?S ?F))

   (=> (or (exists ?V (template-slot-value ?S ?C ?V))
           (exists ?Fa (template-facet-of ?Fa ?S ?C)))
       (template-slot-of ?S ?C))

So, in the example given above, the following sentences would be true: (template-slot-of Age Person) and (template-facet-of :NUMERIC-MINIMUM Age Person).

As with template facet values and template slot values, the template-slot-of and template-facet-of relations inherit from a class to its subclasses and from a class to its instances as the slot-of and facet-of relations. That is, the following slot-of inheritance axioms hold.   

   (=> (template-slot-of ?S ?C)
       (and (=> (instance-of ?I ?C) (slot-of ?S ?I))
            (=> (subclass-of ?Csub ?C) (template-slot-of ?S ?Csub))))

   (=> (template-facet-of ?Fa ?S ?C)
       (and (=> (instance-of ?I ?C) (facet-of ?Fa ?S ?I))
            (=> (subclass-of ?Csub ?C)
                (template-facet-of ?Fa ?S ?Csub))))

Collection Types for Slot and Facet Values

OKBC allows multiple values of a slot or facet to be interpreted as a collection type other than a set. The protocol recognizes three collection types: set, bag, and list. A bag is an unordered collection with possibly multiple occurrences of the same value in the collection. A list is an ordered bag.

The OKBC Knowledge Model considers multiple slot and facet values to be sets throughout because of the lack of a suitable formal interpretation for (1) multiple slot or facet values treated as bags or lists, (2) the ordering of values in lists of values that result from multiple inheritance, and (3) the multiple occurrence of values in bags that result from multiple inheritance. In addition, the protocol itself makes no commitment as to how values expressed in collection types other than set are combined during inheritance. Thus, OKBC guarantees that multiple slot and facet values of a frame stored as a bag or a list are retrievable as an equivalent bag or list at that frame. However, when the values are inherited to a subclass or instance, no guarantees are provided regarding the ordering of values for lists or the repeating of multiple occurrences of values for bags. The collection types supported by a KRS can be specified by a behavior (see Section 4.1.7) and the collection type of a slot of a specific frame can be specified by using the :COLLECTION-TYPE facet (see Section 2.10.2).

   
Default Values

The OKBC knowledge model includes a simple provision for default values for slots and facets. Template slots and template facets have a set of default values associated with them. Intuitively, these default values inherit to instances unless the inherited values are logically inconsistent with other assertions in the KB, the values have been removed at the instance, or the default values have been explicitly overridden by other default values. OKBC does not require a KRS to be able to determine the logical consistency of a KB, nor does it provide a means of explicitly overriding default values. Instead, OKBC leaves the inheritance of default values unspecified. That is, no requirements are imposed on the relationship between default values of template slots and facets and the values of the corresponding own slots and facets. The default values on a template slot or template facet are simply available to the KRS to use in whatever way it chooses when determining the values of own slots and facets. OKBC guarantees that, unless the value of the :default behavior is :none, default values for a template slot or template facet asserted at a class frame will be retrievable at that frame. However, no guarantees are made as to how or whether the default values are inherited to a subclass or instance.

   
Knowledge Bases

A knowledge base (KB) is a collection of classes, individuals, frames, slots, slot values, facets, facet values, frame-slot associations, and frame-slot-facet associations. KBs are considered to be entities in the universe of discourse and are represented by frames. All frames reside in some KB. The frames representing KBs are considered to reside in a distinguished KB called the meta-kb, which is accessible to OKBC applications.

   
Standard Classes, Facets, and Slots

The OKBC Knowledge Model includes a collection of classes, facets, and slots with specified names and semantics. It is not required that any of these standard classes, facets, or slots be represented in any given KB, but if they are, they must satisfy the semantics specified here.

The purpose of these standard names is to allow for KRS- and KB-independent canonical names for frequently used classes, facets, and slots. The canonical names are needed because an application cannot in general embed literal references to frames in a KB and still be portable. This mechanism enables such literal references to be used without compromising portability.

   
Classes

Whether the classes described in this section are actually present in a KB or not, OKBC guarantees that all of these class names are valid values for the :VALUE-TYPE facet described in Section 2.10.2.


:THING   class
:THING is the root of the class hierarchy for a KB, meaning that :THING is the superclass of every class in every KB.


:CLASS   class
:CLASS is the class of all classes. That is, every entity that is a class is an instance of :CLASS.


:INDIVIDUAL   class
:INDIVIDUAL is the class of all entities that are not classes. That is, every entity that is not a class is an instance of :INDIVIDUAL.


:NUMBER   class
:NUMBER is the class of all numbers. OKBC makes no guarantees about the precision of numbers. If precision is an issue for an application, then the application is responsible for maintaining and validating the format of numerical values of slots and facets. :NUMBER is a subclass of :INDIVIDUAL.


:INTEGER   class
:INTEGER is the class of all integers and is a subclass of :NUMBER. As with numbers in general, OKBC makes no guarantees about the precision of integers.


:STRING   class
:STRING is the class of all text strings. :STRING is a subclass of :INDIVIDUAL.


:SYMBOL   class
:SYMBOL is the class of all symbols. :SYMBOL is a subclass of :SEXPR.


:LIST   class
:LIST is the class of all lists. :LIST is a subclass of :INDIVIDUAL.

   
Facets

The standard facet names in OKBC have been derived from the Knowledge Representation System Specification (KRSS) [13] and the Ontolingua Frame Ontology. KRSS is a common denominator for description logic systems such as LOOM[12], CLASSIC [2], and BACK [14]. The Ontolingua Frame Ontology defines a frame language as an extension to KIF. KIF plus the Ontolingua Frame Ontology is the representation language used in Stanford University's Ontolingua System [5]. Both KRSS and Ontolingua were developed as part of DARPA's Knowledge Sharing Effort.


:VALUE-TYPE   facet
The :VALUE-TYPE facet specifies a type restriction on the values of a slot of a frame. Each value of the :VALUE-TYPE facet denotes a class. A value C for facet :VALUE-TYPE of slot S of frame F means that every value of slot S of frame F must be an instance of the class C. That is, 

   (=> (:VALUE-TYPE ?S ?F ?C)
       (and (class ?C)
            (=> (holds ?S ?F ?V) (instance-of ?V ?C))))

   (=> (template-facet-value :VALUE-TYPE ?S ?F ?C)
       (and (class ?C)
            (=> (template-slot-value ?S ?F ?V) (instance-of ?V ?C))))

The first axiom provides the semantics of the :VALUE-TYPE facet for own slots and the second provides the semantics for template slots. Note that if the :VALUE-TYPE facet has multiple values for a slot S of a frame F, then the values of slot S of frame F must be an instance of every class denoted by the values of :VALUE-TYPE.

A value for :VALUE-TYPE can be a KIF term of the following form: 

   <value-type-expr> ::= (union <OKBC-class>*) | (set-of <OKBC-value>*) |
                         OKBC-class

A OKBC-class is any entity X for which (class X) is true or that is a standard OKBC class described in Section 2.10.1. A OKBC-value is any entity. The union expression allows the specification of a disjunction of classes (e.g., either a dog or a cat), and the set-of expression allows the specification of an explicitly enumerated set of possible values for the slot (e.g., either Clyde, Fred, or Robert).


:INVERSE   facet
The :INVERSE facet of a slot of a frame specifies inverses for that slot for the values of the slot of the frame. Each value of this facet is a slot. A value S2 for facet :INVERSE of slot S1 of frame F means that if V is a value of S1 of F, then F is a value of S2 of V. That is, 

   (=> (:INVERSE ?S1 ?F ?S2)
       (and (:SLOT ?S2)
            (=> (holds ?S1 ?F ?V) (holds ?S2 ?V ?F))))

   (=> (template-facet-value :INVERSE ?S1 ?F ?S2)
       (and (:SLOT ?S2)
            (=> (template-slot-value ?S1 ?F ?V)
                (template-slot-value ?S2 ?V ?F))))


:CARDINALITY   facet
The :CARDINALITY facet specifies the exact number of values that may be asserted for a slot on a frame. The value of this facet must be a nonnegative integer. A value N for facet :CARDINALITY on slot S on frame F means that slot S on frame F has N values. That is,2.6 

   (=> (:CARDINALITY ?S ?F ?N)
       (= (cardinality (setofall ?V (holds ?S ?F ?V))) ?N))

   (=> (template-facet-value :CARDINALITY ?S ?F ?C)
       (=< (cardinality (setofall ?V (template-slot-value ?S ?F ?V)) 
           ?N)))

For example, one could represent the assertion that Fred has exactly four brothers by asserting 4 as the value of the :CARDINALITY own facet of the Brother own slot of frame Fred. Note that all the values for slot S of frame F need not be known in the KB. That is, a KB could use the :CARDINALITY facet to specify that Fred has 4 brothers without knowing who the brothers are and therefore without providing values for Fred's Brother slot.

Also, note that a value for :CARDINALITY as a template facet of a template slot of a class only constrains the maximum number of values of that template slot of that class, since the corresponding own slot of each instance of the class may inherit values from multiple classes and have locally asserted values.


:MAXIMUM-CARDINALITY   facet
The :MAXIMUM-CARDINALITY facet specifies the maximum number of values that may be asserted for a slot of a frame. Each value of this facet must be a nonnegative integer. A value N for facet MAXIMUM-CARDINALITY of slot S of frame F means that slot S of frame F can have at most N values. That is, 

   (=> (:MAXIMUM-CARDINALITY ?S ?F ?N)
       (=< (cardinality (setofall ?V (holds ?S ?F ?V))) ?N))

   (=> (template-facet-value :MAXIMUM-CARDINALITY ?S ?F ?C)
       (=< (cardinality (setofall ?V (template-slot-value ?S ?F ?V)) 
           ?N)))

Note that if facet :MAXIMUM-CARDINALITY of a slot S of a frame F has multiple values N1,$\ldots$,Nk, then S in F can have at most (min N1 $\ldots$ Nk) values. Also, it is appropriate for a value for :MAXIMUM-CARDINALITY as a template facet of a template slot of a class to constrain the number of values of that template slot of that class as well as the number of values of the corresponding own slot of each instance of that class since an excess of values for a template slot of a class will cause an excess of values for the corresponding own slot of each instance of the class.


:MINIMUM-CARDINALITY   facet
The :MINIMUM-CARDINALITY facet specifies the minimum number of values that may be asserted for a slot of a frame. Each value of this facet must be a nonnegative integer. A value N for facet MINIMUM-CARDINALITY of slot S of frame F means that slot S of frame F has at least N values. That is, 2.7 

   (=> (:MINIMUM-CARDINALITY ?S ?F ?N)
       (>= (cardinality (setofall ?V (holds ?S ?F ?V))) ?N))

Note that if facet :MINIMUM-CARDINALITY of a slot S of a frame F has multiple values N1,$\ldots$,Nk, then S of F has at least (max N1 $\ldots$ Nk) values. Also, as is the case with the :CARDINALITY facet, all the values for slot S of frame F do not need be known in the KB.

Note that a value for :MINIMUM-CARDINALITY as a template facet of a template slot of a class does not constrain the number of values of that template slot of that class, since the corresponding own slot of each instance of the class may inherit values from multiple classes and have locally asserted values. Instead, the value for the template facet :MINIMUM-CARDINALITY constrains only the number of values of the corresponding own slot of each instance of that class, as specified by the axiom.


:SAME-VALUES   facet
The :SAME-VALUES facet specifies that a slot of a frame has the same values as other slots of that frame or as the values specified by slot chains starting at that frame. Each value of this facet is either a slot or a slot chain. A value S2 for facet :SAME-VALUES of slot S1 of frame F, where S2 is a slot, means that the set of values of slot S1 of F is equal to the set of values of slot S2 of F. That is, 

   (=> (:SAME-VALUES ?S1 ?F ?S2)
       (= (setofall ?V (holds ?S1 ?F ?V))
          (setofall ?V (holds ?S2 ?F ?V))))

A slot chain is a list of slots that specifies a nesting of slots. That is, the values of the slot chain S1,$\ldots$,Sn of frame F are the values of the Sn slot of the values of the Sn-1 slot of $\ldots$ of the values of the S1 slot in F. For example, the values of the slot chain (parent brother) of Fred are the brothers of the parents of Fred. Formally, we define the values of a slot chain recursively as follows: Vn is a value of slot chain S1,$\ldots$,Sn of frame F if there is a value V1 of slot S1 of F such that Vn is a value of slot chain S2,$\ldots$,Sn of frame V1. That is,2.8 

   (<=> (slot-chain-value (listof ?S1 ?S2 @Sn) ?F ?Vn)
        (exists ?V1 (and (holds ?S1 ?F ?V1)
                         (slot-chain-value (listof ?S2 @Sn) ?V1 ?Vn))))

   (<=> (slot-chain-value (listof ?S) ?F ?V) (holds ?S ?F ?V))

A value (S1 $\ldots$ Sn) for facet :SAME-VALUES of slot S of frame F means that the set of values of slot S of F is equal to the set of values of slot chain (S1 $\ldots$ Sn) of F. That is, 

   (=> (:SAME-VALUES ?S ?F (listof @Sn))
       (= (setofall ?V (holds ?S ?F ?V))
          (setofall ?V (slot-chain-value (listof @Sn) ?F ?V))))

For example, one could assert that a person's uncles are the brothers of their parents by putting the value (parent brother) on the template facet :SAME-VALUES of the Uncle slot of class Person.


:NOT-SAME-VALUES   facet
The :NOT-SAME-VALUES facet specifies that a slot of a frame does not have the same values as other slots of that frame or as the values specified by slot chains starting at that frame. Each value of this facet is either a slot or a slot chain. A value S2 for facet :NOT-SAME-VALUES of slot S1 of frame F, where S2 is a slot, means that the set of values of slot S1 of F is not equal to the set of values of slot S2 of F. That is, 

   (=> (:NOT-SAME-VALUES ?S1 ?F ?S2)
       (not (= (setofall ?V (holds ?S1 ?F ?V))
               (setofall ?V (holds ?S2 ?F ?V)))))

A value (S1 $\ldots$ Sn) for facet :NOT-SAME-VALUES of slot S of frame F means that the set of values of slot S of F is not equal to the set of values of slot chain (S1 $\ldots$ Sn) of F. That is, 

   (=> (:NOT-SAME-VALUES ?S ?F (listof @Sn))
       (not (= (setofall ?V (holds ?S ?F ?V))
               (setofall ?V (slot-chain-value (listof @Sn) ?F ?V)))))


:SUBSET-OF-VALUES   facet
The :SUBSET-OF-VALUES facet specifies that the values of a slot of a frame are a subset of the values of other slots of that frame or of the values of slot chains starting at that frame. Each value of this facet is either a slot or a slot chain. A value S2 for facet :SUBSET-OF-VALUES of slot S1 of frame F, where S2 is a slot, means that the set of values of slot S1 of F is a subset of the set of values of slot S2 of F. That is, 

   (=> (:SUBSET-OF-VALUES ?S1 ?F ?S2)
       (subset (setofall ?V (holds ?S1 ?F ?V))
               (setofall ?V (holds ?S2 ?F ?V))))

A value (S1 $\ldots$ Sn) for facet :SUBSET-OF-VALUES of slot S of frame F means that the set of values of slot S of F is a subset of the set of values of the slot chain (S1 $\ldots$ Sn) of F. That is, 

   (=> (:SUBSET-OF-VALUES ?S ?F (listof @Sn))
       (subset (setofall ?V (holds ?S ?F ?V))
               (setofall ?V (slot-chain-value (listof @Sn) ?F ?V))))


:NUMERIC-MINIMUM   facet
The :NUMERIC-MINIMUM facet specifies a lower bound on the values of a slot whose values are numbers. Each value of the :NUMERIC-MINIMUM facet is a number. This facet is defined as follows: 

   (=> (:NUMERIC-MINIMUM ?S ?F ?N)
       (and (:NUMBER ?N)
            (=> (holds ?S ?F ?V) (>= ?V ?N))))

   (=> (template-facet-value :NUMERIC-MINIMUM ?S ?F ?N)
       (and (:NUMBER ?N)
            (=> (template-slot-value ?S ?F ?V) (>= ?V ?N))))


:NUMERIC-MAXIMUM   facet
The :NUMERIC-MAXIMUM facet specifies an upper bound on the values of a slot whose values are numbers. Each value of this facet is a number. This facet is defined as follows: 

   (=> (:NUMERIC-MAXIMUM ?S ?F ?N)
       (and (:NUMBER ?N)
            (=> (holds ?S ?F ?V) (=< ?V ?N))))

   (=> (template-facet-value :NUMERIC-MAXIMUM ?S ?F ?N)
       (and (:NUMBER ?N)
            (=> (template-slot-value ?S ?F ?V) (=< ?V ?N))))


:SOME-VALUES   facet
The :SOME-VALUES facet specifies a subset of the values of a slot of a frame. This facet of a slot of a frame can have any value that can also be a value of the slot of the frame. A value V for own facet :SOME-VALUES of own slot S of frame F means that V is also a value of own slot S of F. That is, 

   (=> (:SOME-VALUES ?S ?F ?V) (holds ?S ?F ?V))


:COLLECTION-TYPE   facet
The :COLLECTION-TYPE facet specifies whether multiple values of a slot are to be treated as a set, list, or bag. No axiomatization is provided for treating multiple values as lists or bags because of the lack of a suitable formal interpretation for the ordering of values in lists of values that result from multiple inheritance and the multiple occurrence of values in bags that result from multiple inheritance.

The protocol itself makes no commitment as to how values expressed in collection types other than set are combined during inheritance. Thus, OKBC guarantees that multiple slot and facet values stored at a frame as a bag or a list are retrievable as an equivalent bag or list at that frame. However, when the values are inherited to a subclass or instance, no guarantees are provided regarding the ordering of values for lists or the repeating of multiple occurrences of values for bags.


:DOCUMENTATION-IN-FRAME   facet
:DOCUMENTATION-IN-FRAME is a facet whose values at a slot for a frame are text strings providing documentation for that slot on that frame. The only requirement on the :DOCUMENTATION facet is that its values be strings.

Slots


:DOCUMENTATION   slot
:DOCUMENTATION is a slot whose values at a frame are text strings providing documentation for that frame. Note that the documentation describing a class would be values of the own slot :DOCUMENTATION on the class. The only requirement on the :DOCUMENTATION slot is that its values be strings. That is, 

   (=> (:DOCUMENTATION ?F ?S) (:STRING ?S))

Slots on Slot Frames

The slots described in this section can be associated with frames that represent slots. In general, these slots describe properties of a slot which hold at any frame that can have a value for the slot.


:DOMAIN   slot
:DOMAIN specifies the domain of the binary relation represented by a slot frame. Each value of the slot :DOMAIN denotes a class. A slot frame S having a value C for own slot :DOMAIN means that every frame that has a value for own slot S must be an instance of C, and every frame that has a value for template slot S must be C or a subclass of C. That is, 

   (=> (:DOMAIN ?S ?C)
       (and (:SLOT ?S)
            (class ?C)
            (=> (holds ?S ?F ?V) (instance-of ?F ?C))
            (=> (template-slot-value ?S ?F ?V)
                (or (= ?F ?C) (subclass-of ?F ?C))))

If a slot frame S has a value C for own slot :DOMAIN and I is an instance of C, then I is said to be in the domain of S.

A value for slot :DOMAIN can be a KIF expression of the following form: 

   <domain-expr> ::= (union <OKBC-class>*) | OKBC-class
A OKBC-class is any entity X for which (class X) is true or that is a standard OKBC class described in Section 2.10.1.

Note that if slot :DOMAIN of a slot frame S has multiple values C1,$\ldots$,Cn, then the domain of slot S is constrained to be the intersection of classes C1,$\ldots$,Cn. Every slot is considered to have :THING as a value of its :DOMAIN slot. That is, 

   (=> (:SLOT ?S) (:DOMAIN ?S :THING))


:SLOT-VALUE-TYPE   slot
:SLOT-VALUE-TYPE specifies the classes of which values of a slot must be an instance (i.e., the range of the binary relation represented by a slot). Each value of the slot :SLOT-VALUE-TYPE denotes a class. A slot frame S having a value V for own slot :SLOT-VALUE-TYPE means that the own facet :VALUE-TYPE has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-VALUE-TYPE ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:VALUE-TYPE ?S ?F ?V))))

As is the case for the :VALUE-TYPE facet, the value for the :SLOT-VALUE-TYPE slot can be a KIF expression of the following form: 

   <value-type-expr> ::= (union <OKBC-class>*) | (set-of <OKBC-value>*) |
                         OKBC-class

A OKBC-class is any entity X for which (class X) is true or that is a standard OKBC class described in Section 2.10.1. A OKBC-value is any entity. The union expression allows the specification of a disjunction of classes (e.g., either a dog or a cat), and the set-of expression allows the specification of an explicitly enumerated set of values (e.g., either Clyde, Fred, or Robert).


:SLOT-INVERSE   slot
:SLOT-INVERSE specifies inverse relations for a slot. Each value of :SLOT-INVERSE is a slot. A slot frame S having a value V for own slot :SLOT-INVERSE means that own facet :INVERSE has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-INVERSE ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:INVERSE ?S ?F ?V))))


:SLOT-CARDINALITY   slot
:SLOT-CARDINALITY specifies the exact number of values that may be asserted for a slot for entities in the slot's domain. The value of slot :SLOT-CARDINALITY is a nonnegative integer. A slot frame S having a value V for own slot :SLOT-CARDINALITY means that own facet :CARDINALITY has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-CARDINALITY ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:CARDINALITY ?S ?F ?V))))


:SLOT-MAXIMUM-CARDINALITY   slot
:SLOT-MAXIMUM-CARDINALITY specifies the maximum number of values that may be asserted for a slot for entities in the slot's domain. The value of slot :SLOT-MAXIMUM-CARDINALITY is a nonnegative integer. A slot frame S having a value V for own slot :SLOT-MAXIMUM-CARDINALITY means that own facet :MAXIMUM-CARDINALITY has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-MAXIMUM-CARDINALITY ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:MAXIMUM-CARDINALITY ?S ?Csub ?V))))


:SLOT-MINIMUM-CARDINALITY   slot
:SLOT-MINIMUM-CARDINALITY specifies the minimum number of values for a slot for entities in the slot's domain. The value of slot :SLOT-MINIMUM-CARDINALITY is a nonnegative integer. A slot frame S having a value V for own slot :SLOT-MINIMUM-CARDINALITY means that own facet :MINIMUM-CARDINALITY has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-MINIMUM-CARDINALITY ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:MINIMUM-CARDINALITY ?S ?F ?V))))


:SLOT-SAME-VALUES   slot
:SLOT-SAME-VALUES specifies that a slot has the same values as either other slots or as slot chains for entities in the slot's domain. Each value of slot :SLOT-SAME-VALUES is either a slot or a slot chain. A slot frame S having a value V for own slot :SLOT-SAME-VALUES means that own facet :SAME-VALUES has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-SAME-VALUES ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:SAME-VALUES ?S ?F ?V)))


:SLOT-NOT-SAME-VALUES   slot
:SLOT-NOT-SAME-VALUES specifies that a slot does not have the same values as either other slots or as slot chains for entities in the slot's domain. Each value of slot :SLOT-NOT-SAME-VALUES is either a slot or a slot chain. A slot frame S having a value V for own slot :SLOT-NOT-SAME-VALUES means that own facet :NOT-SAME-VALUES has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-NOT-SAME-VALUES ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:NOT-SAME-VALUES ?S ?F ?V)))


:SLOT-SUBSET-OF-VALUES   slot
:SLOT-SUBSET-OF-VALUES specifies that the values of a slot are a subset of either other slots or of slot chains for entities in the slot's domain. Each value of slot :SLOT-SUBSET-OF-VALUES is either a slot or a slot chain. A slot frame S having a value V for own slot :SLOT-SUBSET-OF-VALUES means that own facet :SUBSET-OF-VALUES has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-SUBSET-OF-VALUES ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:SUBSET-OF-VALUES ?S ?F ?V)))


:SLOT-NUMERIC-MINIMUM    slot
:SLOT-NUMERIC-MINIMUM specifies a lower bound on the values of a slot for entities in the slot's domain. Each value of slot :SLOT-NUMERIC-MINIMUM is a number. A slot frame S having a value V for own slot :SLOT-NUMERIC-MINIMUM means that own facet :NUMERIC-MINIMUM has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-NUMERIC-MINIMUM ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:NUMERIC-MINIMUM ?S ?F ?V)))


:SLOT-NUMERIC-MAXIMUM   slot
:SLOT-NUMERIC-MAXIMUM specifies an upper bound on the values of a slot for entities in the slot's domain. Each value of slot :SLOT-NUMERIC-MAXIMUM is a number. A slot frame S having a value V for own slot :SLOT-NUMERIC-MAXIMUM means that own facet :NUMERIC-MAXIMUM has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-NUMERIC-MAXIMUM ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:NUMERIC-MAXIMUM ?S ?F ?V)))


:SLOT-SOME-VALUES   slot
:SLOT-SOME-VALUES specifies a subset of the values of a slot for entities in the slot's domain. Each value of slot :SLOT-SOME-VALUES of a slot frame must be in the domain of the slot represented by the slot frame. A slot frame S having a value V for own slot :SLOT-SOME-VALUES means that own facet :SOME-VALUES has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-SOME-VALUES ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:SOME-VALUES ?S ?F ?V)))


:SLOT-COLLECTION-TYPE   slot
:SLOT-COLLECTION-TYPE specifies whether multiple values of a slot are to be treated as a set, list, or bag. Slot :SLOT-COLLECTION-TYPE has one value, which is either set, list or bag. A slot frame S having a value V for own slot :SLOT-COLLECTION-TYPE means that own facet :COLLECTION-TYPE has value V for slot S of any frame that is in the domain of S. That is, 

   (=> (:SLOT-COLLECTION-TYPE ?S ?V)
       (and (:SLOT ?S)
            (=> (forall ?D (=> (:DOMAIN ?S ?D) (instance-of ?F ?D)))
                (:COLLECTION-TYPE ?S ?F ?V)))

OKBC Operations

In presenting the functional interface of OKBC, we first describe concepts that are common to many operations, including common arguments and standard ways to signal errors. Then we give an overview of all the OKBC operations, based on the type of objects on which they operate. To facilitate the use of OKBC with multiple programming languages we describe language bindings for C, Lisp, and Java. Finally, we list all the OKBC operations, along with their input arguments, return values, and descriptions.

The concept of KB behaviors, common to many OKBC operations, is described in detail in Chapter 4. On the first reading of this chapter, any references to KB behaviors can be safely ignored.

OKBC Architecture

OKBC assumes a client-server architecture for application development. The client and server can be on different machines, on the same machine but in a different address space, or on the same machine and in the same address space. When the OKBC client and server are on different machines, they communicate via the OKBC transport layer. The OKBC transport layer can be implemented by direct procedure calls if the client and server are in the same address space, or any of the standard network protocols (e.g., CORBA or TCP/IP).

Using OKBC, a client application can access any KRS that supports a OKBC server. OKBC enables an application to access multiple OKBC servers, each of which may support multiple KRSs, which in turn may provide access to multiple KBs. For example, an application that merged multiple KBs could access a LOOM KB on one server, two Ontolingua KBs on a second server, and place the result in a Classic KB on a third server.

To access a KB, an application loads the OKBC client library for the appropriate programming language. For instance, an application written in the Java programming language would be compiled with the OKBC Java client library. The client library defines Java methods for all of the OKBC operations. It also defines Java classes to implement all of the OKBC entities, and conditions to implement all of the OKBC conditions.

To access a OKBC server, a client application typically undertakes the following steps. First, the application must establish a connection to a OKBC server (using   establish-connection3.1). Second, the application may find out the set of KRSs that the server supports on that connection (using   get-kb-types). Third, the application can get information about the KBs of a given type that can be opened on the connection (using   openable-kbs). Finally, the application can either open a specific KB (using   open-kb) or create a new one (using   create-kb). The application may now query and manipulate the KB by executing OKBC operations. For example, it can look for specific frames (using   get-frames-matching), find the root classes of the KB (using   get-kb-roots, create new frames (using   create-frame), and save changes (using   save-kb).

A back end implementor implements the OKBC operations by using the KRS's native API. Whenever there is no direct mapping between a OKBC operation and some operation in the native API, the back end may invoke multiple operations in the native API or perform some runtime translation between the constructs of OKBC and the constructs supported by underlying KRS. For example, LOOM supports a concept definition language but no facets. It is possible to translate the LOOM concept definition language into OKBC facets, for example, the :at-most concept constructor of LOOM is translated into the :maximum-cardinality facet.

There is considerable redundancy in OKBC operations -- some operations can be implemented in terms of others. For example, consider the operations   class-p and   individual-p that check whether an entity is a class or on individual. If we define either of these two operations, it can be used to define the other, because the domain of discourse is partitioned into classes and individuals. The minimal set of OKBC operations that must be implemented, also known as mandatory methods, is known as a kernel. Because of this redundancy, an implementor can choose a kernel that most closely matches the native API of a KRS.

It is possible to develop a system that implements the complete protocol using a set of kernel operations. At least two such system have been implemented. As a consequence, a KRS developer can implement a complete OKBC-compliant system by implementing only the kernel operations. This may lead to some loss in efficiency because some non-kernel operations may have more efficient implementation in terms of the native API of a KRS. For example, the operation   get-kb-classes can be implemented using   get-kb-frames and   class-p operations. Systems that store an explicit list of classes can return this result more efficiently.

KRS developers can also support subsets of OKBC behavior in their back ends, and then advertise this using the behaviors mechanism (see Section 4.1). For instance, a back end might only define read-only operations on a KB. This further reduces the initial effort required to implement OKBC.

Notation and Naming Conventions

Many OKBC operations, (for example,   slot-p) are predicates on their arguments, and the value returned by them is a boolean truth value. All of these operations are named consistently with ``-p'' as a suffix. For example,   slot-p is a predicate that is true for slots, and   class-p is a predicate that is true for classes. When we say that an operation returns a boolean result, we mean that it returns either the OKBC value false, which is to be interpreted as the boolean value false, or some non-false value is returned that is interpreted as the boolean true. Although such a truth-deciding value will frequently be the OKBC value true, the only guarantee is that it will not be false. In some language implementations, the OKBC values true and false may not be the same as the native language values for true and false.

We use a standard format for describing the OKBC operations in Section 3.7. To explain this format, we use an example description of the get-slot-values operation as shown in Figure 3.1.


   
Figure 3.1: Format for documentation of OKBC operations
\begin{figure}{\bf get-slot-values}{\index{get-slot-values}\index{operation!get-... ...ied slot has no values, {\em ()}\ is returned.\vspace{0.1in}\hrule\end{figure}

Name. The first element is the name of the operation.

Argument list. The arguments are specified using the Common Lisp conventions. The argument list is divided into two groups, separated by the ``&key'' indicator. Mandatory arguments precede ``&key''. These arguments must be provided in all language bindings. The keyword (named) arguments follow the ``&key'' indicator. In Section 3.6, we discuss language bindings that show how the keyword arguments should be interpreted for languages such as C that do not support keyword arguments. In some language bindings, the keyword arguments may be optional. In language bindings that support optional keyword arguments (for example, Java), default values will be supplied for the optional keyword arguments. The specification of an optional keyword argument is either (1) a list whose first element is the argument name and whose second element is the default value or (2) the argument name. Otherwise, the argument defaults to false.

For example, kb-local-only-p defaults to false, and inference-level defaults to :taxonomic.

Return values. Following `` $\Rightarrow$'' are the values returned by the operation or void if no value is returned. The operations may return more than one value. For example, get-slot-values returns three values -- a list containing the requested slot values, exact-p and more-status.

Flags. Each operation has a set of descriptive flags to indicate (1) whether there is a corresponding enumerator operation3.2 (E), (2) whether it is mandatory, optional or neither3.3 in the current implementations (M or O or I), and (3) if it is read-only or writes to the KB (R or W). For example,   get-slot-values has an enumerator, is read-only, and is optional in the current implementation.

Documentation. The documentation defines the meaning of the operations. For brevity, common arguments, such as inference-level, and common return values, such as more-status, are not described in the individual operation definitions, but in Sections 3.3 and 3.5. Arguments, return values, and OKBC operations are in this font.

   
Common Concepts

A comprehensive list of all arguments that are common to many OKBC operations, and their default and legal values, is shown in Table 3.1. Some of the common arguments are described later, when we present an overview of the OKBC operations (Sections 3.5).

   
Controlling Inference

  In many situations, it is necessary to control the inferences that should be performed while executing OKBC operations. For example, while retrieving the values of a slot, a user may wish to receive directly asserted values and perhaps inherited values as well. To provide such control, many OKBC operations support an inference-level argument that can take the following three values.

A value of :direct for inference-level is guaranteed to return at least directly asserted values, because in some systems, such as, forward chaining systems -- values in addition to the directly asserted values may also be returned. Some OKBC operations, for example, an operation returning superclasses of a class may eliminate redundant values from the result. To help an application determine when exactly the directly asserted values are returned, all operations taking an :inference-level argument will return a second value (the first value being the result of the operation), exact-p, which is true if it is known that exactly the :direct or :taxonomic values is returned. A OKBC implementation that always returns false as the value of exact-p is compliant, but implementors are encouraged to return true whenever possible.

Returning a List of Multiple Values

  For a OKBC operation that returns a list of values, it is often desirable to limit the size of the resulting list and the computation necessary to establish the elements of the list. The number-of-values argument, which is supported by many OKBC operations, allows the caller to limit the number of values returned. The legal values for this argument are :all, which is always the default, or any positive integer. A OKBC operation accepting the number-of-values argument returns at least three values. The first value is the result list for the request, the second is the value of exact-p (discussed in the Section 3.3.1), and the third is more-status, a value that reveals whether there are more results available.

When number-of-values is :all; the value of more-status is either false, which indicates that there are known to be no more results, or :more, which indicates that there may still theoretically be more results, but the KRS was unable to find any more. When number-of-values is :all, a more-status value of :more means that the system cannot guarantee that it can access all possible results requested by the OKBC operation.

If the number-of-values argument is a positive integer, then no more results than the specified number will be returned. The more-status will be one of the following three possible values.


 
Table 3.1: Commonly used arguments
Description Argument Name Default Value Constraint on a Legal Value X
Connection connection   okbc-local-connection (  connection-p X)
KB Type kb-type   KB-type object
KB reference kb (current-kb) (  kb-p X)
KB inclusion kb-local-only-p false X$\in${ true, false}
Frame reference frame   (  coercible-to-frame-p X)
Slot reference slot   (  slot-p X)
Facet reference facet   (  facet-p X)
Class reference class   (  class-p X)
Value value/thing   Any value corresponding to OKBC data types (portable) or any value corresponding to system-defined data types
Number of values to be returned number-of-values   X= :all or a positive integer
Inferences to be performed inference-level :taxonomic X $\in$ { :taxonomic, :all, :direct}
Test function test (kb-test-fn) X $\in$ { :eql, :equal, :equalp } or a function specifier on the two arguments to be compared, KB object and kb-local-only-p, and must return true or false
Choosing values value-selector :known-true X $\in$ { :known-true, :default-only, :either}
Controls whether error should be signaled error-p true X$\in${ true, false}
Chooses between template and own slots slot-type :own X $\in$ { :own, :template, :all }
Enumerator enumerator   An enumerator object
 

Selecting between Default and Asserted Values

  As discussed in the knowledge model, OKBC provides a facility to store and retrieve default values. Therefore, while adding a value to a slot or a facet, one may specify whether the value being added is a default value. Similarly, while retrieving values from a slot (or facet) of a frame, one may choose whether default values should be returned. This control is provided by the value-selector argument. The argument value-selector may take one of the following three values.

Test Functions

Many OKBC operations need to perform comparisons. For example, while removing a slot value, we need to compare the value to be removed with the existing slot values. OKBC operations requiring such comparisons support a test argument whose value is one of :eql, :equal, :equalp, or a procedure that should be used in the comparisons. The test argument defaults to :equal. The functions invoked for the values :eql, :equal, and :equalp are   eql-in-kb,   equal-in-kb, and   equalp-in-kb respectively. The arguments to a test procedure are the two entities to be compared, and the KB for which the comparison should be performed, and kb-local-only-p (discussed in Section 3.5.2). The test function should return either true or false. Supplying a function in the native programming language as a value of test is not portable especially in network applications.

Handling Errors

To support the development of robust applications, some standard means  for processing error conditions are desirable. Whenever possible, OKBC operations that experience erroneous conditions or arguments signal errors. OKBC uses condition signals that are analogous to COMMON LISP conditions or Java exceptions. Condition signals are defined for commonly occurring error situations. OKBC provides a user with some control over when the errors should be signaled. A comprehensive list of standard OKBC errors is available in Section 3.8.

The OKBC errors are said to be either continuable or not. An error is said to be continuable only if the state of the KB is not known to have been changed by the error in such a way that the behavior of subsequent OKBC operations becomes undefined. Thus, although the signaling of a continuable error will interrupt any processing currently being performed, subsequent OKBC calls will be unaffected. After a non-continuable error, the state of the KB and the behavior of the KRS and application are undefined. The operation   continuable-error-p returns true only for continuable error objects, and is false otherwise.

The error behavior of OKBC operations is specified in one of the following four ways: ``is an error'', ``error is signaled'', ``unspecified behavior'', ``is not portable''.

Whenever we say that ``it is an error'' for some situation to occur, it means that no valid OKBC program should cause that situation to occur; if it occurs, the effects and results are completely undefined. No OKBC-compliant implementation is required to detect such errors, but implementors are encouraged to detect such errors when possible. In some cases we also specify the condition that should be signaled if an implementation decides to signal one and has choice over which error is signaled.

When we say that an ``error is signaled'' in a situation, any OKBC-compliant implementation must signal an error of the specified type when that situation is encountered.

When we say that ``behavior is unspecified'' for a given situation, it means that a OKBC-compliant system may or may not treat that situation as an error.

An example of a situation where the behavior is unspecified is the function   replace-slot-value that replaces an existing slot value with another. The definition of   replace-slot-value does not specify whether an error should be signaled when the slot value to be replaced is not a current value of the slot, or if the new value to be added is already a value of the slot. This approach simplifies the implementation and speeds performance since each underlying KRS may make different assumptions about signaling behavior.

When we say that a particular usage is not portable, we mean that an application may legally operate in this state, but even if correct behavior is observed, it is not guaranteed to be the case if the application is directed at a different knowledge base (KB) of the same KRS, or the same KB with different behavior settings, or a KB resident in a different KRS (even with the same content), or a KB connected over a network. For example, many KBs uniquely identify frames by their names. For a KB with a value true for the behavior :frame-names-required, a frame name may be used as a valid argument for any operation that accepts a frame argument. Since the :frame-names-required behavior can be false for some KBs, such usage is not portable, because a frame name will not always be a valid argument for an operation that accepts a frame argument.

The general rule is that a standard OKBC error will be signaled when the documented exceptions occur. If, for example, the user attempts to retrieve slot values from a frame that does not exist, by using a call to the function   get-slot-values, the error not-coercible-to-frame is signaled. Errors can also be signaled when slot constraints are violated. When a constraint violation occurs, the KRS should signal one of the conditions defined for constraint violations.

In two situations, an application program needs explicit control of whether an error should be signaled. An example of the first situation is the function coerce-to-frame that coerces a given object to a frame. In general, coerce-to-frame signals an error if the input object cannot be coerced to a frame. But a user program may not wish an error to be signaled if it is not sure if the input object is indeed coercible to a frame. The second situation is encountered in functions such as copy-frame that perform multiple operations. For such functions, a user may wish to continue copying even if there is an error, in which case the copy-frame continues copying as much as possible.

  To provide such control, a few OKBC operations accept an error-p argument. The default value for error-p is true, in which case the errors are signaled as usual. If error-p is false, the operation catches at least the documented conditions and continues execution if possible.

The OKBC operations accepting the error-p argument return a second status value, in addition to the usual return value. When the second value is true, and error-p is false, it means that execution completed successfully.

Overview of OKBC operations

We categorize all the OKBC operations based on the type of objects in which they operate. We introduce here any new concepts that are necessary for understanding those operations, and list operations in each category. Detailed descriptions of all operations are in Section 3.7.  

   
Operations on Connections

OKBC has been designed to be easily used in both centralized and distributed environments. To permit this, we use an abstraction called a connection that encodes the actual location of a OKBC KB and mediates communication between a OKBC application and the KB. To communicate with a KRS, an application program first establishes a connection by using the establish-connection operation. With each OKBC operation, we need to indicate the connection that should be used in executing it. Some OKBC operations take an explicit connection argument, whereas others derive the connection from a KB argument (explained in Section 3.5.2). Thus, once a connection is established, a user need not be aware of the actual location of the KB or whether the KB is being accessed from the same address space as the application or over the network.

Depending on the nature of the communication and the security model involved, different types of connection are used to perform the mediation between a OKBC client and a server. For example, if a OKBC server requires user authentication, the client will have to fulfill the authentication requirement before being able to establish a connection. The OKBC specification does not provide a detailed definition of connections since the specific behavior of the connections will be a function of the communication, threading, locking, and security models used by the server. A provider of a OKBC server is required to make the definition of its supported connection types available to the authors of OKBC client programs.

The connection operations are:   all-connections,   close-connection,   connection-p,   establish-connection,   local-connection

   
Operations on KBs

Network OKBC operations take a kb argument that specifies the KB to which the operation applies. Multiple KBs may be open for access simultaneously by a OKBC application. Different KBs may be serviced by different KRSs. For example, a single application might simultaneously access both a LOOM and a THEO KB.

    With each KB in a KRS, we associate a OKBC KB-object and a KB-locator. A KB-object uniquely identifies a KB (discussed below) in a OKBC application. A KB-locator is a frame in the meta-KB and contains sufficient information to locate and open the KB. For example, for a KB residing in a file, a KB-locator may contain the name of the KB and its pathname. In effect, a kb-locator is to a KB as a filename is to a file. OKBC operations requiring a kb argument must be supplied with a KB-object. The kb argument defaults to the current KB, which is queried by the OKBC operation   current-kb and set by the operation   goto-kb.

  OKBC defines a taxonomy of KB-object types. A KRS may have several KB-object types defined for it. For example, one can imagine a type hierarchy in which the root class is ``KB'', with a subclass ``LOOM-KB'', which in turn has subclasses ``LOOM-FILE-KB'' and ``LOOM-ORACLE-KB.'' A back end implementor may define new KB types for her purpose, for example, ``CYC-KB''. Methods defined for KB types can be used to implement the type-specific KB operations. Certain OKBC operations must be performed before an application has created a KB or acquired a reference to a KB object. Such operations must be supplied a kb-type argument, which should be the type object for the KB class for which the operation is to be executed. A KB type object for a KB class can be obtained by using the OKBC operation   get-kb-type.

Our model of KB access allows KBs to reside on different types of secondary storage devices, including both flat files, and database systems on remote servers. We do not assume that the KB is read into memory in its entirety when the KB is opened for access. An existing OKBC KB can be opened using the OKBC operation open-kb. A new OKBC KB can be created using the OKBC operation create-kb. An open KB may be saved using save-kb or closed using close-kb.

The OKBC operation openable-kbs can determine which KBs are available on a given connection and return KB-locators for such KBs. Each such KB-locator can then be used as an argument to open-kb.

Many KRSs allow the creation of new KBs by including existing KBs. The semantics of KB inclusion vary widely amongst KRSs. It is often useful to limit the scope of an operation so that it is performed to exclude any frames belonging to KBs that were included in the current KB from some other KBs. For example, if a client application wants to display a class graph, it might want to select the roots of the graph by ignoring frames from any included KBs. To control such behavior, many OKBC operations take the argument kb-local-only-p,   which when set to true ignores, if possible, any information in the KB that was included from another KB. The kb-local-only-p argument always defaults to false.

  As was mentioned in Chapter 2, the entities in the domain of discourse of interest to OKBC exist within a knowledge base (KB). Because KBs themselves are of interest to us, every OKBC implementation must define a special KB, called meta-KB containing frames that represent KBs themselves. Such frames representing the KB are the same as KB-locators. A meta-kb can be accessed using the OKBC operation   meta-kb.

The meta-KB also contains classes corresponding to each kb-type. Each KB-locator is an instance of an appropriate kb-type in the meta-KB. For example, a KB-locator representing a LOOM KB may be an instance of loom-kb KB-type.

The meta-KB allows the use of the OKBC operations to manipulate KB-locators. For example, we could view the contents of a KB-locator using the OKBC operation (  print-frame kb-locator :kb (  meta-kb)). Similarly, we could use   get-class-instances to determine all the instances of the KB-type loom-kb as follows. 

    (get-class-instances (get-kb-type 'loom-kb) :kb (meta-kb)
                         :inference-level :taxonomic)

The KB operations are   close-kb,   copy-kb,   create-kb,   create-kb-locator,   current-kb,   expunge-kb,   find-kb,   find-kb-locator,   find-kb-of-type,   generate-individual-name,   get-kb-direct-children,   get-kb-direct-parents,   get-kb-type,   get-kb-types,   get-kbs,   get-kbs-of-type,   goto-kb,   individual-name-generation-interactive-p,   kb-modified-p,   kb-p,   meta-kb,   open-kb,   openable-kbs,   revert-kb,   save-kb,   save-kb-as

Operations on Frames

In OKBC, as many as four identifiers are associated with a frame: frame name, frame handle, frame object, and pretty-name. Many KRSs associate a name with each frame in a KB. The frame name can be of type symbol or string. When the :frame-names-required behavior is true, a frame name uniquely identifies a frame. Some KRSs do not use frame names. OKBC parameterizes this behavior of an KRS by setting the :frame-names-required behavior. When the value of :frame-names-required is true, it means that each frame is required to have a name, the frame name is unique in a KB, and the frame name supplied at the time of frame creation can be used at a later time to identify the frame. When the value of the :frame-names-required behavior is false, frame names are not required, and may not be unique in a KB even if supplied; one may not be able to locate a frame by using the name that was supplied when the frame was created.

A frame handle always uniquely identifies a frame in a KB. For some KRSs, a frame handle may be the same as the frame name or the same as the frame object. Frame handles are always supported by all the OKBC back ends. To ensure portability, OKBC application writers are encouraged always to refer to frames by frame handles.

A frame object is a reference to the actual data structure that encodes the information about the frame in a KRS. A frame object always uniquely identifies a frame in a KB. Some KRSs may not have a single data structure representing a frame. In such cases, the frame object is not distinguishable from the frame handle, and all frame-like properties of the frame are emergent from the context of the KB. For example, if we view an object-oriented database as a KRS, then object-identifiers (OIDs) could be viewed as frame handles. The information about an object identified by an OID does not all reside in one physical data structure in the database, but the contents of that object can still be viewed using OKBC.

Any OKBC operation that takes a frame argument must accept either a frame handle or a frame object as a valid value. A frame name is guaranteed to be a valid value for the frame argument only if the :frame-names-required behavior is set to true.

The frame pretty-name is a name for a frame that is meant for use in a user interface that needs to display a visually appealing but terse presentation for a frame. A pretty-name need not be unique or suitable for use in a program except for display purposes.

In Table 3.2, we summarize how different frame properties differ along several dimensions. These properties might differ in a complex implementation as follows. The frame name is a symbol unique in a KB, but not across different KBs (different KBs can contain different frames that happen to have the same frame name). The frame handle is a data structure used by a KRS to represent frames conveniently and efficiently. It is guaranteed to be unique only in a KB. The frame pretty-name is a string naming the frame in a pretty manner, that happens to be retrieved from a slot of the frame.


 
Table 3.2: The differences between the OKBC mechanisms for identifying individual frames. Type -- The data type of the identifier (e.g., the frame pretty-name must be a string). Unique in KB? -- Must the identifier be unique within a given KB? Unique across KBs? -- Must the identifier be unique across all KBs? Frame arg? -- Can the identifier be used as a frame argument to most OKBC functions? Slot value? -- Can the identifier be a slot value that records a relationship among frames? Pretty? -- Is the name suitable for display within a user interface?
  Type Unique Unique Frame arg? Slot value? Pretty?
    in KB? across KBs?      
Name symbol/ yes no yes KRS maybe
  string       dependent  
Handle any yes no yes yes no
Object any yes no yes yes no
Pretty-name string no no no not portably yes
 

The frame operations are:   allocate-frame-handle,   coerce-to-frame,   coercible-to-frame-p,   copy-frame,   create-frame,   delete-frame,   frame-in-kb-p,   get-frame-details,   get-frame-handle,   get-frame-in-kb,   get-frame-name,   get-frame-pretty-name,   get-frame-type,   get-frames-matching,   get-kb-frames,   print-frame,   put-frame-details,   put-frame-name,   put-frame-pretty-name

Operations on Classes

The class operations are:   add-class-superclass,   class-p,   coerce-to-class,   create-class,   get-class-instances,   get-class-subclasses,   get-class-superclasses,   get-kb-classes,   get-kb-roots,   instance-of-p,   primitive-p,   put-class-superclasses,   remove-class-superclass,   subclass-of-p,   superclass-of-p

Operations on Instances

The instance operations are:   add-instance-type,   get-instance-types,   put-instance-types,   remove-instance-type,   type-of-p

Operations on Individuals

The operations on individuals are:   coerce-to-individual,   create-individual,   get-kb-individuals,   individual-p

Operations on Slots

The OKBC knowledge model distinguishes between own slots, the slots that appear in frames, and template slots, slots that are defined in classes, but are expressed in the frames that are instances of those classes. Rather than having a different set of operations for each type of slot, OKBC has a single set of operations that applies to both own and template slots. Appropriate behavior of these operations is selected by the slot-type argument that can take one of the following three values.

For an operation that does not take a slot argument, slot-type defaults to :all. For all other operations taking a slot-type argument, the default is :own.

The slot operations are:   add-slot-value,   attach-slot,   coerce-to-slot,   create-slot,   delete-slot,   detach-slot,   follow-slot-chain,   frame-has-slot-p,   get-classes-in-domain-of,   get-frame-slots,   get-frames-with-slot-value,   get-kb-slots,   get-slot-type,   get-slot-value,   get-slot-values,   get-slot-values-