Single step mapping in topological order of the queued class and instance frames of a semantic network to a static working memory

• US 5,276,885 A
• Filed: 04/18/1991
• Issued: 01/04/1994
• Est. Priority Date: 04/18/1991
• Status: Expired due to Fees

• Current Assignee: Carnegie Group Five PPG Place Pittsburgh PA 15222
• Original Assignee: CARNEGIE GROUP, LLP
• Inventors: Scarola, David G., Milnes, Brian G.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US07/687,125
• Time in Patent Office: 992 Days
• Field of Search: 395/63, 395/62, 395/575, 395/600, 395/700, 395/500, 364/513, 364/578
• US Class Current: 1/1
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Method and apparatus are provided for mapping information from a dynamic frame-based semantic network to a static working memory by utilizing a topological sorting algorithm which processes at least one queue of frames. Preferably, the algorithm is utilized with filtering to avoid unnecessary updates. The algorithm makes a marking pass and an updating pass across the queued frames. The marking pass orders a queue of class frames. The updating pass updates working memory elements of the working memory corresponding to the ordered class frames and working memory elements which correspond to instances of the class. After the updating pass, the working memory elements reflect local and inheritable slots and values from the semantic network. Such mapping allows the working memory elements to be further processed such as by matching against rules.

Claims

1. A method of operating a processing means to map updated information upon a call to access from a dynamic frame-based semantic network having class frames and instance frames, with each of said instance frames being associated with at least one of said class frames, to a static working memory having a plurality of working memory elements, each said working memory element corresponding to one of said class frames and instance frames, the method comprising the steps of:

(a) utilizing the processing means to create one class queue of the class frames and one instance queue of the instance frames in a memory means to obtain queued class frames and instance frames having the updated information to be mapped;

(b) utilizing the processing means to mark each of the queued class frames of the class queue to order the queued class frames of the class queue to reflect a currently proper sequence of updating the working memory elements;

said step (b) further includes setting a counter corresponding to each of the queued class frames, each said counter having a value based on a topological sort of the queued class frames; and

(c) utilizing the processing means to update the working memory elements of the working memory corresponding to the queued class frames and queued instance frames with the updated information to be mapped based on the order of the queued class frames of the class queue to obtain an updated working memory, said working memory elements corresponding to one of said queued class frames and said queued instance frames associated with said one of said queued class frames being updated in a single step.

2. The method as claimed in claim 1 wherein the queued class frames include a plurality of class frames and wherein at least one of the class frames is a subclass frame having at least two parent class frames having a first part of the information, the at least two parent class frames being marked during step (b), working memory elements corresponding to the at least one subclass frame and at least two parent class frames being updated with the first part of the information during step (c).

3. The method as claimed in claim 2 wherein the instance queue includes at least one instance frame having a second part of the information and wherein a working memory element corresponding to the at least one instance frame is updated with the second part of the information during step (c).

4. The method as claimed in claim 3 wherein the queued class frames including the at least one subclass frame and the at least one instance frame include local and inherited slots and values and wherein the corresponding working memory elements are updated with information based on the local and inherited slots and values.

5. The method as claimed in claim 4 further comprising the steps of:

creating a plurality of inherited slots and values during the step of updating;

linking the plurality of inherited slots and values to create a data structure;

retrieving one of a class frame and an instance frame which inherits multiple slots and values; and

utilizing the data structure during step (c) to allow a working memory element corresponding to the retrieved frame to be updated to reflect the information to be mapped;

wherein the retrieved frame is retrieved only a single time.

6. The method of claim 4 further comprising the step of filtering the class and instance frames so that a working memory element corresponding to a slot of a frame which has a local value will not be updated.

7. In a data processing system including processing means and memory means including a static working memory having a plurality of working memory elements operatively coupled to the processing means, apparatus for mapping updated information upon a call to access from a dynamic frame-based semantic network having class frames and instance frames, with each of said instance frames being associated with at least one of said class frames, to the static working memory having a plurality of working memory elements, each said working memory element corresponding to one of said class frames and instance frames, the apparatus comprising:

(a) means for creating one class queue of the class frames and one instance queue of the instance frames in the memory means to obtain queued class frames and instance frames having the updated information to be mapped;

(b) means for marking each of the queued class frames of the class queue to order the queued class frames of the class queue to reflect a currently proper sequence of updating the working memory elements;

said means (b) further includes means for setting a counter corresponding to each of the queued class frames, each said counter having a value based on a topological sort of the queued class frames; and

(c) means for updating the working memory elements of the working memory corresponding to the queued class frames and queued instance frames with the updated information to be mapped based on the order of the queued class frames of the class queue to obtain an updated working memory, said working memory elements corresponding to one of said queued class frames and said queued instance frames associated with said one of said queued class frames being updated in a single step.

8. The apparatus as claimed in claim 7 wherein the queued class frames include a plurality of class frames and wherein at least one of the class frames is a subclass frame having at least two parent class frames having a first part of the information, the at least two parent class frames being marked, working class memory elements corresponding to the at least one subclass frame and at least two parent class frames being updated with the first part of the information.

9. The apparatus as claimed in claim 8 wherein the step of creating includes the step of creating a second queue including at least one instance frame having a second part of the information and wherein a working memory element corresponding to the at least one instance frame is updated with the second part of the information.

10. The apparatus as claimed in claim 9 wherein the queued class frames including the at least one subclass frame and the at least one instance frame include local and inherited slots and values and wherein the corresponding working memory elements are updated with information based on the local and inherited slots and values.

11. The apparatus as claimed in claim 10 further comprising:

means for creating a plurality of inherited slots and values;

means for retrieving one of a class frame and an instance frame which inherits multiple slots and values; and

means for linking the plurality of inherited slots and values to create a data structure wherein the means for updating utilizes the data structure to update a working memory element corresponding to a retrieved frame.

12. The apparatus as claimed in claim 10 further comprising filtering means for filtering the class and instance frames so that a working memory element corresponding to a frame which has a local value will not be updated.