ABOUT A FRAME IN A PLURALITY OF CONTEXTS

IN A FRAME-BASED SEMANTIC NETWORK

TECHNICAL FIELD

This invention- relates to methods and apparatus for storing information about a frame in a plurality of contexts in a frame-based semantic network, for example, in the field of artificial intelligence.

BACKGROUND ART

Artificial intelligence (Al) technology is a discipline with an ultimate goal of providing a machine that is capable of reasoning, making references and following rules in a manner believed to model the human mind. Artificial intelligence provides relatively untrained users with sophisticated computer power to solve practical problems such as to assist in the analysis of massive amounts of relatively unprocessed data to aid in decision-making processes.

As Al technology begins to demonstrate potential and practical uses, tools are needed to speed development of practical computational systems. Al specialists have developed a number of Al-dedicated computer languages to assist in this development. Among the languages are LISP and PROLOG. However, these languages are not particularly easy for either skilled Al researchers or minimally-trained user/programmers to use to develop sophisticated and complex knowledge bases necessary to solve the problems related to artificial intelligence applications.

Over the years, various attempts have been made to develop commercially useful knowledge

representation languages. Among the efforts have been FRL (Frame Representation Language), KRL (Knowledge Representation Language), KL-ONE, NIKL, SMALLTALK, STROBE, UNITS, KEE, ART, Knowledge Craft and Laser.

In the field of artificial intelligence

"knowledge" is a combination of data structures and interpretive procedures which, if suitably manipulated, will lead to what might best be termed "knowledgeable" behavior. A knowledge base is a set of knowledge representations which describes a domain of knowledge. A knowledge base is to an artificial intelligence environment what a database is to a conventional computer program. Unlike a database, however, a knowledge base can include executable program material within a defined record called a slot and complex interrelationships between frames as described below.

One type or category of representing knowledge is descriptive knowledge. This category is the collection and classification of facts and categorizations about an idea or entity which might be acted upon. The basic units of descriptive knowledge are generally called frames. A frame contains one or more slots.

Many commercial systems have a context mechanism, sometimes referred to as "worlds", "alternate worlds" or "perspectives". Contexts are a mechanism for representing alternative or duplicate worlds (i.e. a complete copy of the knowledge base) in a frame-based semantic network. Contexts are used to perform what-if reasoning by allowing several, potentially diverse sets of modifications to a knowledge base to proceed independently. Conceptually, therefore, each frame in the knowledge base potentially corresponds to several

versions of the frame, one for each context in which that frame exists. In other words, each frame can exist in several different versions of the knowledge base.

Knowledge Craft employs a copy-on-access strategy. When a frame is accessed in a context, it is copied into that context whether or not it is modified.

This strategy requires substantial memory, however, to represent alternative worlds.

A copy-on-modify strategy substantially reduces the memory requirements; the frame is copied into a context only when it is to be modified in that context. However, this strategy can involve lengthy searches in large, complex context trees to find the proper version of the frame for the current context, because if it has not been copied to that context, the version existing in the closest ancestor context must be determined.

SUMMARY OF THE INVENTION

An object of the present invention is to provide a method and apparatus for the efficient managing of one-to-many mapping from the user's handle (i.e. ID or pointer) for a frame to the particular version of the frame (i.e. representing that frame) in a particular context.

In carrying out the above object and other objects of the present invention, a method is provided in a frame-based semantic network for storing information about a frame in a plurality of contexts. A given version of the frame represents the frame in a given context. The method includes the steps of creating a frame and creating a first plurality of

contexts including a root context and at least one leaf context to form a context tree having depth. The root context has the lowest depth. The method further includes the steps of locally modifying the frame in a second plurality of contexts of the first plurality of contexts, creating a token for each context of the second plurality of contexts where the frame was modified, storing information about the version of the frame in each of the second plurality of contexts and linking the tokens to form a series of tokens for the frame.

Also provided are apparatus for carrying out the method steps described above.

Preferably, a context resolution algorithm resolves one-to-many mapping and a "copy-up" strategy avoids having to redo the context resolution algorithm after a version of the frame is copied into a context prior to modifying it.

The advantages of the method and apparatus of the present invention are numerous. For example, the resulting "copy-on-modify" strategy is reasonably efficient under substantially all circumstances while reducing the memory required to represent alternative worlds.

The above advantages and other advantages and features of the present invention are readily apparent from the following detailed description of the invention when taken in connection with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIGURE 1 is a schematic block diagram view illustrating a context tree under the method and apparatus of the present invention;

FIGURE 2 is a schematic block diagram view also illustrating a context tree and a frame (i.e. FRAME1) which has been modified in several contexts under the method and apparatus of the present invention; and

FIGURE 3 is a schematic block diagram view illustrating a series of context tokens for FRAME1 in accordance with the method and apparatus of the present invention.

BEST MODE FOR CARRYING OUT THE INVENTION

Referring now to the drawing figures, FIGURES

1 through 3 generally illustrate the method and system of the present invention. In general, the invention efficiently manages one-to-many mapping from a user's handle (i.e. ID or pointer) for a frame to the particular frame version which represents that frame in a particular context.

Copy-on-Modify Strategy

The copy-on-modify strategy minimizes the memory required to represent a context. In the preferred implementation, although the entire knowledge base conceptually exists in each context, a frame is actually copied into a context only when it is modified in that context. This "copy-on-modify" strategy minimizes the time spent copying frames from one context

to another and minimizes the memory required to represent an alternative world.

When a new context is created, it is a "virtual copy" of its parent context, but it contains no frames locally. Starting from one top context (the Root Context) , subcontexts can be created recursively, generating context-trees as shown in FIGURE 1. A context can have at most one parent context, but a parent context can have any number of subcontexts.

FIGURE 2 illustrates the "context representation for a frame" which has been modified in several subcontexts. The AGE slot of FRAMEl has been set to a different value in contexts C3, C4, C5, C6 and the Root Context. The remaining contexts (CI, C2 and C7) refer to the copy of FRAMEl which is local to the "closest" ancestor context. For example, if context C7 is the current context and the AGE slot of FRAMEl is accessed, a value of 40 is returned. This is the value or information stored in the AGE slot of FRAMEl in C7's parent context, C4.

Context-Resolution Algorithm

In general, a "context-resolution" algorithm resolves the one-to-many mapping, (i.e. retrieving the specific version of a frame which corresponds to a frame in a particular context) . The algorithm emphasizes quick access to objects in leaf contexts (i.e. any context that doesn't have a child context).

Each frame in the knowledge base potentially corresponds to a number of different versions of the frame, one version for each context in which the frame has been locally modified. A frame is thus a one-to-

many mapping, and each time a frame is accessed in the "current context", the correct version of the frame must be found.

In order to minimize the processing required to find the correct version of the object, each frame has associated with it a series of ordered tokens, one token for each context in which the frame exists locally. Each token consists of three pieces of information: a pointer to a context identifier; a pointer to the object which represents the frame in that context; and a pointer to the next token.

The tokens are ordered by decreasing depth in the context tree. That is, objects in leaf contexts (the ones most typically accessed) will be found toward the front of the series. If a frame has not been explicitly modified in a context, no object or token is created for that context, so frames that are not modified often will have few tokens in the series, and hence be faster to access.

The series of tokens used to represent FRAMEl is illustrated in FIGURE 3. When CI is the current context and the AGE slot is accessed as in the above example, the algorithm works as follows:

Beginning at the header of FRAMEl, the depth of each context associated with each token is compared to the depth of context CI, which is at a depth of 1. Each token whose depth is greater than 1 is ignored.

If a context is encountered which has a depth of exactly 1, a test for an exact match against Cl is performed. In this case, there are no tokens associated with a context at 5 depth = 1.

In this case, Cl is not found, and the algorithm terminates when a token with a depth of 0 is reached. Since the context at level 0 (Root Context) is the immediate parent of

10 Cl, the algorithm terminates and returns a pointer to the object contained in the Root Context token. This is the expected behavior. Since there is no local copy of FRAMEl in context Cl, the algorithm returns a pointer to

15 the "virtual" representation of FRAMEl found in the most closest ancestor context of Cl (in this case, the Root Context) . In more complex cases, additional searching may be required to find the version of the

20 frame in the closest ancestor. The search is straightforward: each context identifier contains a pointer to its immediate parent context; once the algorithm determines that there is no token corresponding to the current

25 context, the search continues down the token series for the parent context. If the parent context token is not found, the search continues for the grandparent context, etc. Because of the ordering of the tokens, the

30 correct ancestor object is always further down in the series of tokens. The token list is not retraversed.

"Copy-Up" Strategy

In general, the "copy-up" strategy together with the "copy-on-modify" strategy efficiently copy versions of a frame into a context. The "copy-up" strategy avoids having to redo the context-resolution step after a version of the frame is copied into a context prior to modifying it.

When a frame is modified in a context which does not already contain a local copy of the frame, a two-step process ensues: the correct version of the frame from which to make the local copy must be identified; the correct version of the frame is the one in the closest ancestor context. — the copy must be made, and a new token which points to the copy must be created and inserted into the token series.

A potential inefficiency exists here because higher-level code in the software system is already pointing to the virtual parent copy of the frame as the correct version of the frame to access in the current context. When a new local version of the frame is made, these other pointers will become invalid, and the higher-level code would need to redo the context resolution step.

In order to avoid this extra work, the "copy- up" strategy moves the existing ancestor token (and the object pointer which is contains) "down" in the token series to the location appropriate to the current subcontext. In turn, the new token and its pointer to the newly copied version of the frame are inserted into the token series at the location of the original

ancestor token. It is as if the original version of the frame was moved down into the current context and the new version of the frame is moved "up" to the ancestor context. Thus, the higher-level code need not redo the context resolution step.

Finally, when a frame is deleted in a context, the memory allocated to the local copy of the frame is freed, but the token remains in the token series so that subsequent attempts to modify the frame in that context will not cause the frame to be recopied to the context. Instead, a "frame deleted" error is generated if an attempt is made to access the deleted frame in the context in which it was deleted or in any of its descendent contexts.

While the best mode for carrying out the invention has been described in detail, those familiar with the art to which this invention relates will recognize various alternative designs and embodiments for practicing the invention as defined by the following claims.