An Overview of a Procedural Approach to Semantic Networks

AN OVERVIEW OF A PROCEDURAL APPROACH TO SEMANTIC NETWORKS

Hector J. Levesque John Mylopo}llos Department of Computer Science University of Toronto

The purpose of this short paper is to summarize the salient features of a formal­ ism for the construction and use of a model representing knowledge of some domain. For a much more detailed exposition, including examples and motivation, see [Levesque 77] where, among other things, portions of the formalism are represented using the formal­ ism itself.

Although the underlying ideas used in the development of the formalism are adaptations from diverse sources, our starting point is the work on semantic net­ works. A major problem in many semantic network proposals is the lack of a semantic theory [Hayes 74] in terms of which one can explain what a semantic network means. We are attempting to deal with this problem by using a "procedural semantics" approach based on [Abrial 74] in contrast to the more declarative approach of classical Predicate Logic.

. The most primitive construct provided by the formalism is the object represent­ ing any single relevant conceptual unit. A fundamental kind of object is the class which is a collection of objects sharrng­ common properties. These objects are said to be instances of the class and may them­ selves be classes. A very important kind of class is the binary relation represent­ ing a mapping from one class to another. Instances of a relation represent assert­ ions made regarding two objects, one from each class.

There are four basic operations defined on classes: create or destroy an instance of a class, test whether an object is an instance-or-a class and fetch all instances of a class. Similarly, ~operations are defined for each rela­ tion: assert or deny that a relation holds between two objects, test whether a rela­ tion holds and fetch arr-objects that are mapped by a relation from a given object. These basic operations can be combined and parametrized to form programs which are classes whose instances are called ~rocesses. Programs can be decomposed 1nto a prerequisite, a main body, an effect and a complaint.--x-program can fa1l 1f its prerequisite is not satisfied. Otherwise, the main body is executed and if this execution is successful, the effect part is executed next, else the complaint part of the program is executed.

default programs supplied by the formalism. In addition, to refine or extend the beha­ viour of a class under its defined opera­ tions, only a part of a program (e.g. a prerequisite) need be given and the rest can default to the standard operation.

The objects constituting a model can be organized in terms of two orthogonal abstraction facilities called respectively the ISA and PARTOF hierarchies.

-xpart from the conceptual gains offer­ ed by having a taxonomy of classes, the main purpose of the ISA hierarchy is the inheritance of definitional properties which is a generalization of the default mechanism that capitalizes on the expected similarity between a subclass and a super­ class. The PARTOF hierarchy, on the other hand, involves the composition of groups of objects into functional units. Such units are called structures and the objects that constitute them, their parts. For classes, the parts are variables (slots) which are bound to objects (slot fiTiers) whenever the class is instantia­ ted. The slots may have default values and relations called dependencies attach­ ing them to other objects and having many possible procedural interpretations such as determining the acceptability of a slot filler or inferring its value. Whereas relations represent the assertional proper­ ties of a class, slots represent the definitional properties. Consequently, the PARTOF hierarchy determines the inher­ itable properties of a class while the ISA hierarchy specifies the inheritance paths.

The metaclass "program" (the class of all programs) can be thought of as a structure having prerequisite,effect etc. as slots and each program fills these slots by providing particular prerequisites etc. This allows programs to be integrated into the two hierarchies and benefit from the organization (e.g. inheritance) like any other class. Similarly, the metaclass "class" is a structure whose slots repre­ sent the four basic programs for classes and the semantics of each class are defined by filling these slots by specific programs. The default values for these slots (and the:four similar ones in "relation") constitute the standard behaviour of classes and relations providing the primi­ tives in terms of which everything else can be defined and linking the formalism to a physical implementation.