S-Net: A Foundation for Knowledge Representation Languages

1. INTRODUCTION

In this paper, we discuss a graphical notation called S-Net, which results in a foundation for recently developed AI languages. S-Net is a descendant of both semantic networks and recent­ ly developed AI languages. Semantic networks have been developed since the mid-sixties as a formalism for the representation of knowledge. Though the original idea of semantic networks is intuitively attractive, the recent formalisms of networks seem to lose the advantages which the researchers initially conceived. G. Hendrix [1975), L. Schubert[l976) and others have tried to formalize their networks based on predicate logic. As a result, their notations have become graphical analogues of logical formula. On the other hand, since the appearance of 'Frame' [Minsky 1975], great efforts have been made to develop programming languages and systems which realize the frame idea [Winograd 1977, Bobrow 1976, Goldstein 1977, Davis 1978). They all have a certain data structure into which various sorts of knowledge, including both pro~dural and declarative ones, are integrated. ·However, their data structures are based only on the vague idea 'Frame', and, more seriously, lack rigidly defined semantics. Especially, the technique 'procedural attachment', though it is powerful tool for describing knowledge, makes the situa­ tion chaotic. There are no general mechanisms for managing the attached procedures appropriate­ ly. In most languages, the programmer must spec­ ify explicitly when an attached procedure should be invoked. Moreover, most aspects concerning the control of the interactions among the attach­ ed procedures are also left to the programmer. As a result, the programmer must always pay at­ tention to the overall control issues during the coding of his procedures. We present in this paper a framework called S-Net on which descrip­ tions and operations of these languages can be appropriately founded.

2. RELATED RESEARCH WORKS

Among others, FRL [Goldstein 1978) and KRL [Bobrow 1977) are the better known examples of recent AI languages. Because these two have both the advantages and disadvantages of recent attempts, we will consider them as typical exam­ ples and compare them with the S-Net notations throughout this paper.

As Goldstein said, FRL is a programming syster. rather than a language. It lacks the overall control mechanisms. It only provides a data structure and a programming package for manipu­ lating it. The data structure, a frame system, consists of a set of mutually related knowledge units called 'frame'. A frame, in turn, is an aggregation of descriptive data and procedures. The core of a FRL frame is a property list. FRL generalizes the LISP property list in the follow­ ing ways:

1. FRL supplies a mechanism for inheritance of properties through a generalization hierarchy.
2. The property value in a frame can be a procedure which knows how to get the actual value.
3. Procedures can be associated directly with frames. The programmer is required to specify explicitly, by using facet indicators such as $IF-ADDED, $IF-REMOVED, $IF-NEEDED etc., what sorts of operations on the frames will invoke the associated procedures.
4. In short, the essential features of FRL are 1. lnheritance of prope rties through a hierarchy.
5. Procedural attachment.

Though these two ideas are intuitively attractive, there remain a lot of difficult problems before they can be realized. We will consider these problems in this section. Note that because we restrict the discussion in this paper to the topic of problem solving mechanisms and their foundations, we will neglect many characteristic features of FRL or KRL which are very interesting in their own right.

2.1 Property Inheritance Through~ Hierarchy

Fig. 1 shows an example in [Goldstein 1977]. The frame MINSKY inherits the properties STREET, CITY, STATE and ZIP from the frame MIT-AI. In FRL, 1 the AKO (A Kind OF) link establishes a mapping by which properties of one frame may be distributed to related frames. Semantically, the mapping can represent a set/subset, part/ whole, or other relationships[Goldstein 1977 ]'.

This approach seems very promising and appropri­ ate. However, some properties can be inherited through set/subset relations but not through part/whole relations and vice versa. From the view point of logic, property inheritance is a specific mode of inference associated with a predicate. In a extreme case, for example, children may inherit their second names from their parents but not any other properties. This inheritance rule is assoc iated with a pred­ icate, say, CHILD-OF. In FRL, there are no ex­ plic it provisions for representing such a kind of restricted property inheritance. The only possible solution is to embed such a rule in a procedure (Fig. 2). This solution is not a real solution of the problem. The programmer should do all things in his procedures. Because prop­ erty inheritance through hierarchy provides only a very restricted inference mechanism, we need additional frameworks for supporting other kinds of inheritance mechanisms.

2.2 Procedural Attachment

One of the difficult problems in procedural attachment is how to decide when a procedure is evaluated. In most of the AI languages, the programmer should explicitly specify this.

Fig. 3. Description for 'Day' in KRL.

$IF-ADDED in FRL and WHEN-FILLED in KRL indicat­ ors are used to indicate that the attached pro­ cedure should be invo~ed when a certain value is stored in the slot. However, this ; tyl e of specification is often inadequate. Some proce­ dures should be triggered when more than one slot is filled. Fig. 3 is an example by Winograd [1975]. The procedure Check-Relation, which checks the consistency between the Day-Number and the Month, will be triggered when the Day-Number slot is filled. If the Month slot has not been filled when the Day-Number is filled, the execu­ tion of the procedure should be suspended, and resumed again when the Month slot is filled. The control of such suspension and resumtng of procedures may become very complicated, if it is implemented without any clear formalization. Moreover, the specification of TO-FILL and WHEN­ FILLED indicators results in the restriction of the system's abilities. Consider a simple example in which we have two procedures which compute the slot-B's value from the slot-A's value, and the slot-C's value from slot-B's value respectively. There ·are four possibilities to embed such proce­ dures by using TO-FILL and WHEN-FILLED indicators [Fig. 4]. In the first three, the slot-C's value can be obtained when the slot-A's value is given. However, it is not the case in the last represen­ tation.

To avoid this, we should carefully distinguish the two different kinds of knowledge: what logic­ al or conceptual relationships the attached procedure embodies, and when the procedure will be invoked. It is often known beforehand that the evaluation of a certain procedure requires much more resources (time or space) than the others or that a certain direction of searching often leads us to success. These sorts of knowl­ edge are called 'heuristics' and the programmers have been encouraged to embed them in their rep­ resentation. However, it is our contention that such heuristics are only heuristics, i.e., they may be reflected on the problem solving process only to the extent that they will not restrict the system's abilities. TO-FILL (WHEN-FILLED) indicators not only recommend the backward (forward) usages of the attached procedures but also inhibit their forward (backward) usages.

In short, the pre-specification of the usages of attached procedures is too restrictive.

Our problem solver based on the S-Net alternate­ ly performs backward and forward reasonings. In that process, an attached procedure will be utilized either in forwards or backwards, accord ing to the problem solving situations. In order to accomplish such mechanism, we introduce the concept of 'partially instantiated relationships in the S-Net, which are dynamically created during the problem solving process [See 4.1 and 4.2].

3. S-NET REPRESENTATION

S-Net consists of several types of nodes and links. The node types which are used in the S-Net are shown in Fig. 5. The Disjoint node and the Condition node play the role of logical connectives. They are used for augmenting the generalization hierarchy (3.1). A property or a slot is represented in the S-Net by a node called Property node. All variable nodes in the S-Net are typed by certain data types. The def­ inition of a type plays a central role in the S-Net.

A Type Definition node describes the basic behaviour of a data type. It corresponds to an atom in LISP. In LISP, an arbitrary character string identifies an atom, and all occurrences of the same character string in LISP programs and data are represented internally by a pointer which points to the atom. The behaviour of an atom is described by the property list attached to the atom. According to this convention, a data type in the S-Net is identified uniquely by its name, and there is one type definition node for each data type.

3.1 Augmentation of Generalization Hierarchy

Data types can be organized in a hierarchical structure. We use the term SORT, instead of AKO or ISA, to refer to the link. In our problem solving procedure, the hierarchy of data types plays the central role for distributing proper­ ties, though explicit path specification (See 3.3) will further augment the inheritance mecha­ nisms. When a problem description is given, the instance nodes of the corresponding data types are created. Because each instance in a problem description has its own data type name, the ini­ tial position of the instance in the hierarchy is determined by its name. However, the posi­ tion should be determined not only by its type name but also its whole descriptions. For exam­ ple, the instance

(OBJECT-I NAME = ALCOHOL

(! TEMPARATURE) = 28°C) )

is identified with the data type ALCOHOL by its type name. Moreover, because ALCOHOL is a sub­ sort of .MATERIAL and because an instance of MATERIAL whose temparature is between the boiling point and the congelation point is an instance of LIQUID, it should be identified as an instance of LIQUID. All properties of LIQUID should be distributed to this instance. In order to accom­ plish such an identification process, we need a framework in the S-Net for specifying when an instance is located lower in the hierarchy. For this purpose we introduce in the S-Net a new link SUBSORT and a new type of node Condition Node (See Fig. 6). A SUBSORT link is a link from a higher data type to a lower one. A Condition Node holds a condition when the transition from the higher to the lower data type is permitted. Moreover, because new information about an instance may be derived during the problem solv­ ing process or accumulated through the dialogue with the user, the position identification may be performed during the problem solving process.

We often find the following type of declarative sentences.

Acid which dissolves copper is either Hydrochloric-Acid, Nitric-Acid or Sulphuric-Acid.

These statements describe mutually exclusive relationships among sets. A data type and a set do not necessarily correspond but they are close­ ly related.

We call a set of data types 'Disjoint Set', if the data types in the set satisfy the following conditions:

1. If an instance is a certain data type in the set, it can never be other data types in the set.
2. We can determine the data type of an in­ stance by determining which data type it is not equal to, i.e. by elimination.

In the S-Net, we represent a disjoint set by a node called Disjoint Node (Fig. 7). Disjoint nodes are often useful to ·inhibit semantically irrelevant information from entering into the search space. By combining the Condition nodes and Disjoint nodes, the generalization hierarchy in the S-Net becomes very powerful.

3.2 Relation Nodes

A relation node in the S-Net expresses a certain dependency relationship among the slots, and also functions as entrance to some external procedures from the S-Net. Based on the dependency rela­ tionships, the S-Net problem solver determines how to solve a problem. For each relation node, a bunch of procedures is internally defined. The procedures embody how to utilize the relation in the problem solving. The problem solver decides which internal procedures is invoked, is a simple example of such descriptions. We treat an occurrance of a data type in the defini­ tion of another type as a variable typed by the data type. Thus, (DT NAME = Water) in the above example is represented as a typed variable>. Since the variable is typed as Water, all infor­ mation attached to Water is applicable to the variable. For example, we will have the value H20 when we retrieve the value of the property Chemical-Formula of the Solvent of a certain Aqueous-Solution. Moreover, a specific knowl­ edge, which can be applied only to the water that is the solvent of a certain solution, but not to Water in general, is also attached to the variable.

(DT NAME = Aqueous - Solution

(! Solvent) = (DT NAME = Water)

(ADD/SUB (! MASS) (! Solvent MASS)

(! Solute Mass)))

The S-Net for the above description is shown in Fig. 9. Retrieval of a value through a path description such as (FGET Aqueous - Solution Solvent Mass) will cause the evaluation of a procedure which is defined as the 'internal' procedure of the relation node ADD/SUB that computes the Solvent's mass from those of the Solution and the Solute. Moreover, if the procedure fails to compute it, more general procedures which are attached to the data type Water or more general data types than Water will be invoked. Thus, unlike in FRL, a path descrip­ tion in the S-Net is augmented automatically by the system.

Such a path description can be emplyed not only in the query expression but also in the S-Net descriptions as follows. The general statement

'If a researcher is a member of an organtzation, he inherits the address from the organization'

can be expressed by

(DT NAME = Researcher

(! Organization) = (DT NAME

= Organization)

In the above examples, all path descriptions begin with !'s which show that the paths start from the current data type. A path which starts from a data type that is different from the current one is also allowed in the S-Net. Thus, the statement 'A MIT-Researcher inherits his address from MIT-Al-Lab' can be expressed direct­ ly by

(DT NAME = MIT - Researcher

(EQ (! Address) ( (DT NAME =

MIT-Al-Lab) Address)).

The S-Net for this is shown Ln Fig. 10. By using this mechanism, called 'explicit path specifica­ tion', property inheritance or distribution among different data types can be obtained in a very intuitive way. Because EQ is represented as a relation node, the above expression can be used not only for retrieving the researcher's address but also for checking the consistency when the address of a certain MIT-Researcher is given.

4. OPERATIONS ON THE S-NET

4.1 Creation of an Instance

A problem description may contain several in­ stances. The description contains three instances of different data types . They are instances of Solution(OBJECT-1), Water (OBJECT-2) and a data type without a name(OBJECT3).

The type definition node for Solution contains various relationships among the properties. These relationships are also instantiated. For example, there may exist a relation node ADD/SUB that expresses the relationship among Solution's mass, Solvent's mass and Solute's mass. When the solution's mass is filled by 100 gr, the relationship is also partially instantiated, and the partially instantiated relation node is creat­ ed (Fig. 11).

The instance OBJECT-2 is created as an instance of Water. Because the property Mass is filled by 98 gr, the relation nodes attached to Water's Mass are instantiated. Moreover, because OBJECT-· 2 is put in the property Solvent of OBJECT-I, the relation nodes attached to the Solvent's Mass are also instantiated. As a result, the instantiated relation node ADD/SUB is further instantiated, i.e., the arg-2 is bound to 98 gr . Since both arg-1 and arg-2 are known in this instantiated rela tion node, one of the procedures defined in this relation node which computes arg-3 becomes to be evaluable. The procedure is marked as evaluable and put into a list called EV-List (See 4.2). In the sequel, the final result will be such as shown in Fig. 12.

As described above, the instantiation of a data type recursively causes the instantiation of other data types. Some relation nodes are also instantiated during the process. The instantia­ tion of relation nodes is propagated upward through the SORT-hierarchy: If a property of a certain data type is filled, the relation nodes attached to the same property of the higher data types in the hierarchy are all instantiated.

4.2 Backward and Forward Reasonings

As we described earlier, after the initial instantiation of variables, a certain set of procedures are only marked as immediately evalu­ able and put into the EV-list, because the imme­ diate evaluation of these procedures will trig­ ger the unlimited forward reasoning which may invoke many irrelevant procedures.

The next stage is performed backward. The ini­ tial goal, which is to solve the problem posed by the user, will be tried, and if not fulfilled, the goal will be further expanded into a set of subgoals. The expansion of a goal will be per­ formed by utilizing the information attached to the instantiated data t ypes, especially the declaration parts of internal procedures in the instantiated relation nodes. Because the instantiated relation nodes have already been partially instantiated during the preceding for­ ward mode, it is reasonable to expect that these instantiated relationships are relevant to the current problem more than those which have not been instantiated. We illustrate this process by considering a simple example. Suppose the problem description in 4.1 has been given and that the following problem is posed.

'Retrieve the Density of OBJECT-!'

The initial goal will not be achieved, because the mass of OBJECT-3 is not explicitly given. The initial goal is expanded into subgoals. Since tl~ relation node which indicates the relation­ ship among Solution's Mass, Solute's Mass and Solution's Density has been partially instantiat­ ed and attached to the instance OBJECT-1, this instantiated relation node will be used to expand the goal. The subgoal is

'Retrieve the Mass of OBJECT-3'.

The reasoning mode will be changed from the back­ ward mode to the forward mode. In this mode, the procedures in the EV-list will be evaluated in turn. The evaluation will further instantiate some variables in the S-Net so that some other procedures will enter in the evaluable stage. They are also marked accordingly, and put in the EV-list. They will be evaluated in the next for­ ward mode.

In the above example, the internal procedure in the relation node ADD/SUB, which computes the Solute's(OBJECT-3's) Mass, is evaluated. The result of the evaluation fulfills the above sub­ goal. This will be checked in the next backward mode. The success of the subgoal will result in the success of the initial goal.

Thus, the whole process is performed forwards and backwards. If there are no procedures in the EV­ list, only the backward mode will be continued until a certain procedure will be entered in the EV-list. Note that an internal procedure in a relation node will be used in both directions, forwards and backwards. Moreover, the two mode works cooperatively in the sense that the back­ ward mode prefers to operating the partially in­ stantiated relation nodes proposed by the preced­ ing forward mode.

5. ~ SIMPLE EXAMPLE

In order to give the reader some idea about the operation of the problem solver, we will give an example in this section. Suppose the following problem is given.

(OBJECT-! NAME ,. Solution (! Solute) = ( OBJECT-2) (! Volume) 200 cc ) (OBJECT-2 NAME Sodium (! Mass) = 2 gr (RETRIEVE OBJECT-! Mol-Densit:z:) ?

In order to compute the Mol-Density, the pro­ blem solver should solve various subproblems such as computing the Solute's Mol-Number from the mass and the molecular-weight, retrieving the Molecular-Weight from the external data base, get­ ting Sodium's Chemical-Formula for accessing the data base etc. The problem solver works fairly well and selects relevant knowledge appropriately even if there is much irrelevant knowledge in the S-Net.

6. CONCLUSION

In this paper, we have proposed a graphical nota­ tion called S-Net which provides a framework and a foundation for some of the operations of recent AI languages and systems. Especially,it is shown that the problems, 'when an attched procedure to be invoked' and 'how to represent restricted pro­ perty inheritance in nonprocedural forms 1 , can be solved in the S Net representation. Moreover, various sorts of information about problem solv­ i.ng situations such as variable binding contexts etc. are distributively stored in the nodes(part­ ially instantiated relation nodes etc.) so that the global controller, the problem solver, can be easily implemented. The current version is only one of possible constructions. We are now de­ veloping different problem solving strategies.