Single step mapping in topological order of the queued class and instance frames of a semantic network to a static working memory5276885Abstract 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 What is claimed is: Description TECHNICAL FIELD
______________________________________
rule R1
{
IF
Class1
{
Slot1 < 0;
Slot2 > 0;
}
THEN
--
{
______________________________________
The rule contains tests for Class1, Slot1, and Slot2. Class frame Class1 and all descendant class and instance frames of Class1 are matched against this condition. The semantics of the invention are specified such that only the frames that pass the following tests successfully match the condition: The frame is either Class1, a descendant class of Class1, or an instance of Class1. AND The value for Slot1 in a frame is less-than 0 (i.e., Slot1<0) AND The value for Slot2 in a frame is greater-than 0 (i.e., Slot>0) The value for a slot in a frame which is used in rule tests can either be local or inheritable. Inheritance values are inherited across the system-defined relations (subclassOf and instanceOf). Working-Memory Elements (wmes) Each frame which matches rules has an associated rule language working-memory element (wme). Both class and instance frames match rules. Therefore, both class and instance frames have associated wmes. The wme for a frame is a vector which contains slots and values. The slots in a wme associated with a particular frame are all the slots which are both local to the frame or inheritable across either subclassOf or instanceOf to that frame. For example, Instance1 contains Slot1 locally, and Slot2 and Slot3 by inheritance (Slot2 is inherited from Class2 and Slot3 is inherited from Class3). The wme for Instance1 contains slots Slot1, Slot2 and Slot3. The wme values are the local or inheritable values for each slot in the frame. For example, Instance1 contains -1 for Slot1 locally, and Instance1 inherits 10 for Slot2 from Class2 and 100 for Slot3 from Class3. Therefore, the wme for Instance1, contains values -1 for Slot1, 10 for Slot2, and 100 for Slot3. That is, the wme for Instance1 is:
______________________________________
wme1
{ Slot1: -1;
Slot2: 10;
Slot3: 100;
______________________________________
Matching Frames Against Rules Matching a frame against a rule is implemented by matching the wme associated with the frame against a rule. Since a wme is a mirror copy of a frame, and the wme contains the same local and inheritable slots and values as the frame, matching the wme against a rule gives the same result as matching the frame against a rule. WMEs are matched against rules instead of matching frames directly because wme vectors can be matched much faster than frames. For example, matching Instance1 against rule R1 is implemented by matching wme1 against rule R1 1) wme1 corresponds to an instance frame of Class1 2) wme1 contains -1 for Slot1, which is less than 0 3) wme1 contains 10 for Slot2, which is greater than 0 WME1 passes the tests in the condition for R1 and so it matches R1. Therefore, Instance1 matches R1. Matching System-Inherited Values As previously mentioned, rule language wmes do not support runtime inheritance. That is, values can only be set and accessed locally in a wme. Values in a wme are never inherited during runtime to other wmes. However, values can be inherited during runtime among frames. Since a wme mirrors a frame, and the wme contains both local and inheritable values for a frame, the inheritable values must somehow be propagated down to the wme (that is, the wme is essentially a cache of the frame values). The way in which values that are inheritable to a frame across relations instanceOf and subclassOf are propagated to the wme for rule matching is described hereinbelow. Overview Of Propagating Inheritable Frames Values to WMEs When a frame is modified herein, the frame is placed on a queue. Queue processing involves ordering the frames on the queue. After the queue is ordered, the frames on the queue are traversed in that order, and values are updated in each frame's associated wme. In the example given above, Instance1 contains value -1 in Slot1. If a frame system function is invoked which modifies the value of Slot1 in Instance1, then Instance1 is placed on the queue. When the queue is processed, the value for Slot1 in the wme that mirrors Instance1 is set to the new value. Maintaining the correspondence between frame values and wme values is more difficult when inheritable values are modified. When a class that contains a slot which is inheritable to descendant classes and instances is updated to contain a new value for the slot, the class is placed on the queue. When the queue is processed, the wme for the class and the wmes for any descendant classes and instances that can inherit the updated value for the slot are updated. For example, if the value of Slot3 in Class3 is updated, Class3 is placed on the queue. When the queue is processed, the wmes for Class3, Instance1, and Instance2 must all be updated to contain the new value for Slot3. The queue is processed using an implementation of a topological sorting algorithm with filtering. The topological sorting algorithm applies an ordering to classes on the queue. This ordering is followed when the wmes corresponding to the class frames are updated. An ordering is required because a particular frame may inherit values from multiple updated classes; if there is no ordering, inefficiency (and possibly even incorrectness) will result because the frame's wme will be updated multiple times, once for each inheritable modification. Class frames only are ordered because an ordering only needs to be applied to the frames from which values are inheritable across system-defined relations. An instance frame is updated in the same order as its class. Since values are not inheritable across system-relations from instances, the instances do not need to be ordered. Therefore, two frame queues are maintained, namely a class queue and an instance queue. The instance queue is maintained to have a place to store local changes which are made to the instances. Filtering is used to block the propagation of frame value changes which do not need to be propagated to wmes. If the value for a slot is updated in a class, the wme for any descendant frame of the class that has a local value for the slot does not need to be updated with the value (the local value overrides the inheritable value). Therefore, filtering is applied to block the propagation of the updated value. Implementation Of Propagating Inheritable Frame Values to WMEs An example involving updates to the frames of the hierarchy of FIG. 1 is described hereinbelow. The following calls to kb.sub.-- SetValue are made (the frame system function kb.sub.-- SetValue is used to update a slot value in a frame):
______________________________________
kb.sub.-- SetValue(
Class2, Slot2, -10 );
kb.sub.-- SetValue(
Instance1, Slot1, -5 );
kb.sub.-- SetValue(
Instance4, Slot2, -7 );
kb.sub.-- SetValue(
Class4, Slot1, -1000
);
kb.sub.-- SetValue(
Class1, Slot1, -1 );
kb.sub.-- SetValue(
Instance4, Slot1, -7 );
______________________________________
The frame queues, which contain updated frames and slots whose values were updated, are as follows after these value updates:
______________________________________
Class queue: [Class2, Slot2]
[Class4, Slot1]
[Class1, Slot1]
Instance queue: [Instance1, Slot1]
[Instance4, Slot2, Slot1]
______________________________________
The resulting frame hierarchy is illustrated in FIG. 2. Even though the values in these frames of FIG. 2 have been updated, these frames are still on the frame queue. The updated values are reflected in the frames but not in the wmes. The wmes are updated to reflect these frame changes when the queue is processed. The queue is processed and wmes are updated just before rules are matched. Queue processing involves making two passes across frames on the queue: (1) A marking pass which orders the classes; and (2) An update pass which updates the wmes for the ordered frames. 1. The Marking Pass As illustrated in FIG. 3, the marking pass traverses the frames on the class queue to apply an order to the classes. A counter is kept for each class. The counter is used to maintain the order in which the wmes for the classes on the queue (and their subclasses and instances) are updated. WMEs are updated during the update pass (described below). The order required for wme updates ensures that a frame is updated after every class which contains an updated value that is inheritable to that frame has been updated. Therefore, the counter for a class represents the number of such classes that must be updated before the class itself is updated. As shown in FIG. 3, the marking pass iterates down the classes on the class queue, and for each class executes the following steps: 1. Increment the counter for that class; and 2. If the counter equals 1: for each subclass of that class, repeat step 1. In step 2, the subclassOf link of a class is accessed to gather the subclasses of the class. Instances are not accessed during the marking pass because an instance is updated in the same order as its class. Executing the marking pass on the example class queue would create the following counter changes: Access Class2 from the queue: 1. Increment counter [result: Class2.count =1] 2. Class2.count=1 Access subclass Class3: 1. Increment counter [result: Class3.count =1] 2. Class3.count=1 since Class 3 has no subclasses, return. Access subclass Class4: 1. Increment counter [result: Class4.count =1] 2. Class4.count=1 since Class4 has no subclasses, return. Access Class4 from the queue: 1. Increment counter [result: Class4.count =2] 2. Class4.count=2 so return. Access Class1 from the queue: 1. Increment counter [result: Class1.count =1] 2. Class1.count=1 Access subclass Class3: 1. Increment counter [result: Class3.count=2] 2. Class3.count=2 so return. Access subclass Class4: 1. Increment counter [result: Class4.count=3] 2. Class4.count=3 so return. Final result: Class1.count=1 Class2.count=1 Class3.count=2 Class4.count=3 The Update Pass As illustrated in FIG. 4, the updated pass traverses the classes that were ordered during the marking phase and propagates all value updates to the wmes in the specified order. The order is based on the counters associated with each class. The counter indicates that a class' wme (and the wmes for the class' instances) should only be updated after the counter reaches 0. When a frame's counter reaches zero, it means that wmes for all frames on which that frame depends for slot and value inheritance have been updated; the wme for the frame is then updated. The updated wme reflects all modified local values of a frame and all modified values which were inherited across subclassOf and instanceOf to that frame. As shown in FIG. 4, the basic update process "pops" a class off of the class queue and executes the following steps on that class: 1. Decrement the counter for that class. 2. If the counter=0: a. call UPDATE.sub.-- WME for that class; b. call UPDATE.sub.-- WME for each instance of that class; c. for each subclass of that class, go to step 1. In step 2b immediately above, the instances are gathered by accessing the instanceOf link in the class. In step 2c, the subclasses are gathered by accessing the subclassOf link in the class. Executing the update pass on the example queue above creates the following updates:
______________________________________
Access Class2 from the queue:
1. decrement counter [result: Class2.count
= 0]
2. Class2.count - 0:
a. UPDATE.sub.-- WME (Class2)
[result: Class2.sub.-- wme.Slot2 = -10]
b. Class2 has no instances
c. Access subclass Class3:
1. decrement counter [result:
Class3.count = 1]
2. Class3.count = 1 so return.
Access subclass Class4:
1. decrement counter [result:
Class4.count = 2]
2. Class4.count = 2 so return.
Access Class4 from the queue:
1. decrement counter [result: Class4.count = 1]
2. Class4.count = 1 so return.
Access Class1 from the queue:
1. decrement counter [result: Class1.count = 0]
2. Class1.count = 0:
a. UPDATE.sub.-- WME (Class1)
[result: Class1.sub.-- wme.Slot1 = -1]
b. Class1 has no instances
c. Access subclass Class3:
1. decrement counter
[result: Class3.count = 0]
2. Class3.count = 0:
a. UPDATE.sub.-- WME( Class3 )
[result:
Class3.sub.-- wme.Slot1 = -1]
Class3.sub.-- wme.Slot2 = -10]
b. UPDATE.sub.-- WME (Instance1)
[result:
Instance1.sub.-- wme.Slot1= -5
Instance1.sub.-- wme.Slot2=-10]
UPDATE.sub.-- WME (Instance2)
[result:
Instance2.sub.-- wme.Slot1=-1
Instance2.sub.-- wme.Slot2=-10]
c. Class3 has no subclasses
Access subclass Class4
1. decrement counter
[result: Class4.count =0]
2. Class4.count = 0:
a. UPDATE.sub.-- WME (Class4)
[result:
Class4.sub.-- wme.Slot1= -1000
Class4.sub.-- wme.Slot2= -10]
b. UPDATE.sub.-- WME (Instance3)
[result:
Instance3.sub.-- wme.Slot1 =
-1000
Instance3.sub.-- wme.Slot2 =
-10]
UPDATE.sub. -- WME (Instance4)
[result:
Instance4.sub.-- wme.Slot1 =
-7
Instance4.sub.-- wme.Slot2 =
-7]
c. Class4 has no subclasses
______________________________________
After the updated pass is completed, the wmes reflect the local and inheritable slots and values from the frame-base. The wmes are then matched against the rules, effectively matching both local and inheritable frame values. While the bias algorithm is given above, a few preferred features that are described in the example are highlighted as follows: (1) Some of the UPDATE.sub.-- WME calls update multiple values in a wme. For example, the UPDATE.sub.-- WME call for Instance1 updated Slot1 in the wme to contain value -5, which was set locally in Instance1, and updated Slot2 to contain value -10, which is the value inherited to Instance1 for Slot2 from Class 2. Multiple wme updates which reflect multiple frame updates are supported by building a list or data structure of slots and values to update during the update pass. This list is built incrementally as the subclasses of enqueued classes are traversed during the update pass (whenever a class from which a value is inherited is traversed during the update pass, the slot & value are added to the inheritable-slot-value-list). When UPDATE.sub.-- WME is called, the frame whose wme must be updated and the inheritable-slot-value-list are passed in. The inheritable-slot-value-list is merged with the local value updates to that frame. The wme is updated by setting the local and inheritable values in the wme. (2) Filters are applied to frames to avoid unnecessary updates. A filter recognizes that an inheritable slot should not be updated in the wme for a frame which has a local value for the slot. The local value is used instead of the inheritable value. In the call to UPDATE.sub.-- WME for Instance1, one of the members of the inheritable-slot-and-value-list is [Slot1, -1] which is the inheritable value for Slot1 from the update to Class1. This must be filtered for Instance1 because Instance1 has a local value for Slot1. (3) When a class may inherit a slot value from multiple ancestor classes, it may be difficult for the method and system to do the propagation properly, since a frame system inheritance algorithm (which permits both depth-first and breadth-first searches) would have to be inverted. When it is determined that the value for a slot can be inherited from multiple ancestor classes, the invention utilizes a frame system algorithm to inherit the slot and value from the appropriate class. The invention recognizes these cases in which the search strategy is a factor and calls the frame system function kb.sub.-- GetValue to execute the multiple inheritance. The method and apparatus of the present invention provides numerous advantages. For example, the application of topological sorting allows the runtime inheritance of slots and values across subclassOf and instanceOf, which is not part of working memory in a rule language, to be active when matching rules against frames. This application of topological sorting provides a correctness and performance improvement over the ad hoc approach to inheritance for matching implemented in the prior art. The algorithm is correct because all frames on which a frame depends for inheritance are updated before that frame is updated. Therefore, when a frame is updated, it will get the correct inherited values. The algorithm is efficient because each frame is updated only one time. The correctness and efficiency of topological sorting is described in the technical report "Reducing Computation by Unifying Inference with User Interface" by Mark Perlin. This application of topological sorting is also unique because it utilizes the complexity of inheritance of a frame system, allows for inheritance of multiple slots and values, inheritance from multiple classes, and filter optimizations. 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.
|
Same subclass Same class Consider this |
||||||||||