next up previous contents
Next: Example: FramesAccess Paths, Up: Introduction to Frame Based Previous: Rules Are Implications

Inference in Algernon

There are two basic operations on a knowledge-base -- queries  and assertions . Queries retrieve knowledge from the knowledge-base, applying if-needed rules, while assertions add facts to the knowledge-base and apply if-added rules. Of course, a successful if-needed rule will assert its consequent into the knowledge-base, and the antecedent of an if-added rule may have additional formulas to be queried, so the two operations are not disjoint. The rules in an Algernon knowledge-base are organized into small packets by being associated either with frames representing sets, or with slots.

To understand how this works, consider a knowledge-base of frames and rules representing the following genealogy:



There is also a frame People, representing the set of all people. We assert the relation isa (representing the membership relation between an object and a set containing it) between each frame for a person in the genealogy and the frame People (i.e. (isa Adam People), (isa Beth People), tex2html_wrap_inline1283 ). We may associate the rule:


with the frame People.  Formally this means:


Operationally, this means that any query to the aunt slot of a frame that has an isa relation to the frame People will result in the application of this rule. A rule is applied by first querying its antecedent and then, if the antecedent succeeds, asserting its consequent. Querying the antecedent of a rule finds all consistent sets of bindings to the variables in the antecedent. One instance of the consequent is asserted for each binding set, with variables replaced by values in the binding set. This means that retrieval guided by an access path branches on the values in a slot that provide possible bindings for a variable.

For example, if we query (aunt Janet ?x), then rule (2) will apply, with ?z bound to Janet. The path will immediately branch on the values in the parent slot of Janet: bindings of ?x to Ellen or Frank. If ?x is bound to Ellen, then Algernon will query (sister Ellen ?y), which binds ?y to Donna, so it will conclude and assert (aunt Janet Donna). However, along the branch where x is bound to Frank, retrieval of (sister Frank ?y) will branch on two possibilities, so Algernon will also conclude and assert that (aunt Janet Gertrude) and (aunt Janet Hazel).

Rules may also (less commonly) be associated with slots or sets of slots.  If an if-added rule is associated with a slot r, or with a set of which r is a member, then it is applied whenever a value is added to the r slot of any frame (if-needed rules associated with slots and sets of slots are similar). For example, one might want to put the slot less in the set of partial orders, and thus inherit rules, associated with the set of partial orders, for transitivity, reflexivity, and antisymmetry.

By associating rules with sets of individuals, or with slots representing specific relations, we are imposing a semantically-motivated organization on the knowledge-base, which clarifies the structure of its knowledge. We are also limiting access to those rules, thereby reducing the number of times their antecedents must be tested, and hence gaining efficiency.

next up previous contents
Next: Example: FramesAccess Paths, Up: Introduction to Frame Based Previous: Rules Are Implications

Micheal S. Hewett
Tue Oct 29 10:54:13 CST 1996