W3C | Semantic Web | Advanced Development | SWAP | Tutorial | Comparing Rule-Based Systems

Comparing Rule-Based Systems

Cwm acts as a rules processor, using information written in N3 rules to guide it in manipulating the RDF/N3 information it has stored. While rules processors are not exactly commonplace, and understanding them is not manditory for the working programmer, they do have a long and solid history. Where does cwm fit into that history?

The field has sometimes been called Knowledge-Based Systems or Expert Systems, but now people often just says something "uses rules."

Four Kinds of Rules

There seem to be four different ways people think about and want to use rules:

  1. Derivation or Deduction Rules. These are cwm's normal rules. Each rule expresses the knowledge that if one set of statements happens to be true, then some other set of statements must also be true. In most cases this is the same as what is sometimes called a logical implication, a material conditional, or a Horn clause.
  2. Transformation Rules. These are what cwm uses with --filter. Each rule relates truth in one knowledge base to truth in another. Transformation rules on n-tuples can be rewritten as derivation rules on (n+1)-tuples, where the additional element specifies the knowledge base.
  3. Integrity Constraints. These are rules of the form "it must be true that ....". Cwm does not have these rules, but they can be emulated with derivation rules like "if it is not true that .... then we-have-an-error" and a check for "we-have-and-error".
  4. Reaction or Event-Condition-Action (ECA) Rules. These involve a notion of action, not just inference, when a rule applies. Reaction rules may be emulated by wrapping a reaction rule system in a procedure which queries for actions to perform.

A Varierty of Engines

Along with the variety in types of rules, there is also a wide variety in types of rules engines and general logic processors or "reasoners".

Automated Theorem Provers

Automated reasoning using first-order became generally feasible in 1965 with Robinson's resolution and hyperresolution algorithms. Today a raft of automated theorem provers continue this tradition, but they see little use in general computing. The strength here is general expressive power: the machine does perform classical logic operations; the weakness is that such systems generally become too practical, real-world application problems.

A focal point for this research is Thousands of Problems for Theorem-Provers (TPTP), which includes links to provers and a conversion utility between logic languages. You can play a little with its web form (try problem ALG001-1).

In the RDF/Semantic Web community, people have used at least OTTER and SNARK.

Logic Programming

In 1970-1972, Prolog introduced Logic Programming, which took a restricted form of first-order logic (Horn clauses) and offered to prove things with them in a deterministic order, very much like running a program. Prolog always chains backward from a query.

(1970-1975 also saw the introduction of C, Pascal, Scheme, Smalltalk, and Microsoft BASIC.)

Tabled Prolog (as in XSB) allows rules to be written without worrying about looping, much like with cwm.

Production Systems

A different approach became popular with OPS5 (which is since continued into CLIPS and JESS), presenting rules as being "triggered" and causing actions.

Unlike Prolog, these are usually (but not always) chaining forward from the givens, like cwm.

Modern Reasoners

Modern reasoners and rule systems often use a complex hybrid of strategies, or are simply developed for a focussed application domain.

Some worth mentioning include:

  1. Euler handles N3 and many of cwm's operations, using a backward chaining approach with loop-avoidance techniques.
  2. JTP is used for web-reasoning in the KSL InferenceWeb project
  3. RACER and FaCT are leading description-logic (ontology) reasoners
  4. OpenCyc

$Id: rule-systems.html,v 1.4 2003/04/15 23:29:56 sandro Exp $