Derivation of an Efficient Rule System Pattern Matcher
Abstract
This thesis presents a derivation of an efficient rule system pattern matcher. The matcher efficiently computes all matches between a set of rules and a database. The rules may have multiple patterns. The matcher incrementally updates the set of matches as changes are made to the database. This matcher is modeled on the Rete matcher used in the OPS5 production system. Representation used in the matcher are modeled on the structures used in the model-theoretic semantics of first-order logic. The thesis demonstrates the correspondence between these structures and the data structures used in the Rete matcher. A new structure, the lattice of disjunctive substitutions, is introduced to capture the semantics of the rule-system matching computation. An element of this lattice represents the set of all matches between a rule and the terms in a database. The derivation is implemented using program transformations. The derivation has been implemented using a wide-spectrum language and an interactive program transformation system. This work is presented as a contribution towards the construction of a library of programming knowledge to facilitate software reuse and automatic programming. Program derivation, Theses.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1989
- Accession Number
- ADA216801
Entities
People
- Jeremy Wertheimer
Organizations
- Massachusetts Institute of Technology