1.3. Knowledge Representation

1.3.1. Production Rules

A Production Rule (aka Rule) in Drools is a two part structure, with a Left Hand Side (LHS) and a Right Hand Side (RHS) which are alternately known as the "Head" and "Tail" respectively. Additionally a Rule may have the following attributes:

  • salience

  • agenda-group

  • auto-focus

  • activation-group

  • no-loop

  • duration

      
        rule "<name>" <attribute> <value>
        when <LHS>
        then <RHS>
        end
      
    

The LHS of a Rule consists of Conditional Elements (CE) and Columns (aka - Patterns); to facilate the encoding of propositional and first order logic. The term Column is used to indicate Field Constraints on a Fact.

Drools currently supports the follows CEs:

  • 'and'

  • 'or',

  • 'not',

  • 'exists'

'forall' and 'accumulate' will be added shortley. The following Field Constraints are allowed:

  • Literal Constraint

  • Bound Variable Constraint

  • Return Value

  • Predicate

The Language Guide chapter provides more indepth information for each of these.

As facts are asserted and modified in the Working Memory, the rules engine matches the facts against the LHS conditions, when all the conditions of a rules LHS are met and true that rule plus those match facts are activated. When a Rule is activated it is placed onto the Agenda for potential execution, where the actions of RHS, called the Consequence, are executed. The LHS and the RHS is analogous to:

      
    if (<LHS>) {
      <RHS>
    }
      
    

However 'if' is considered procedural in that it is one part of a possible execution flow - if this.... else if.... else ..... Rules use 'when' to more semantically recognise that the rule will activate when, and only when, its LHS is matched.

Rules are associated with a namespace via the package keyword; other Rule Engines may call this a Rule Set. A Package declares imports, global variables, functions and rules.


package com.sample

import java.util.List
import com.sample.Cheese

global List cheeses

function void exampleFunction(Cheese cheese) {
    System.out.println( cheese );
}

rule “A Cheesey Rule”
    when
        cheese : Cheese( type == "stilton" )
    then
        exampleFunction( cheese );
        cheeses.add( cheese );
end

    

The following example shows a LHS with a single Column that has a single Literal Field Constraint used with a Cheese Fact:


rule "Cheddar Cheese"
when
    Cheese( type == "cheddar" )
then
    System.out.println( "cheddar" );
end
  
    

The example above is analogous to :


public void cheddarCheese(Cheese cheese) {
  if ( cheese.getType().equals("cheddar") {
      System.out.println( "cheddar" );
  }
}

    

Rules are a complete de-coupling of data from the logic. Rules cannot be called directly as they are not methods or functions instead Rules fire in response to changes in Working Memory's data. Rules are also fully declarative in that they describe "what" not "how" like imperative languages such as Java.

1.3.2. First Order Logic

Rules are written using First Order Logic, or predicate logic, which extends Propositional Logic. Emil Leon Post was the first to develop an inference based system using symbols to express logic - as a consequence of this he was able to prove that any logical system (including mathematics) could be expressed with such a system.

A proposition is a statement that can be classified as true or false. If the truth can be determined from statement alone it is said to be a "closed statement". In programming terms this is an expression that does not reference any variables:

10 == 2 * 5

Expressions that evaluate against one or more variables, the facts, are "open statements", in that we cannot determine whether the statement is true until we have a variable instance to evaluate against:

Person.sex == "male"

With SQL if we look at the conclusion's action as simply returning the matched fact to the user:

select * from People where People.sex == "male"

For any rows, which represent our facts, that are returned we have inferred that those facts are male people. The following diagram shows how the above SQL statement and People table can be represented in terms of an Inference Engine.

SQL as a simplistic Inference Engine

Figure 1.4. SQL as a simplistic Inference Engine


So in Java we can say that a simple proposition is of the form 'variable' 'operator' 'value' - where we often refer to 'value' as being a literal value - a proposition can be thought as a field constraint. Further to this propositions can be combined with conjuntive and disjuntive connectives, which is the logic theorists way of saying '&&' and '||'. The following shows two open propositional statements connected together with a single disjunctive connective.

      
      person.getEyeColor().equals("blue") || person.getEyeColor().equals("green") 
      
    

This can be expressed using a disjunctive Conditional Element connective - which actually results in the generation of two rules, to represent the two possible logic outcomes.

      
      Person( eyeColour == "blue" ) || Person( eyeColor == "green" )
      
    

Disjunctive field constraints connectives could also be used - although they are not currently supported in Drools 3.0 - and would not result in multiple rule generation.

      
      Person( eyeColour == "blue"||"green" )
      
    

Propositional Logic is not Turing complete, limiting the problems you can define, because it cannot express criteria for the structure of data. First Order Logic (FOL), or Predicate Logic, extends Propositional Logic with two new quantifier concepts to allow expressions defining structure - specifically universal and existential quantifiers. Universal quantifiers allow you to check that something is true for everything; normally supported by the 'forall' conditional element, but not yet implemented in Drools 3.0. Existential quantifiers check for the existence of something, in that it occurs at least once - this is supported with 'not' and 'exists' conditional elements.

Imagine we have two classes - Student and Module. Module represents each of the courses the Student attended for that semester, referenced by the List collection. At the end of the semester each Module has a score. If the Student has a Module score below 40 then they will fail that semester - the existential quantifier can be used used with the "less than 40" open proposition to check for the existence of a Module that is true for the specified criteria.

    
    public class Student {
    private String name;
    private List modules;

    ...
    }
       
    
    
    public class Module {
    private String name;
    private String studentName;
    private int score;
    
    

Java is Turing complete in that you can write code, among other things, to iterate data structures to check for existence. The following should return a List of students who have failed the semester.

    
    List failedStudents = new ArrayList();
    
    for ( Iterator studentIter = students.iterator(); studentIter.hasNext() {
        Student student = ( Student ) studentIter.next();
        for ( Iterator it = student.getModules.iterator(); it.hasNext(); ) {
            Module module = ( Module ) it.next();
            if ( module.getScore() < 40  ) {
                failedStudents.add( student ) ;
                break;
            }
        }
    }
    
    

Early SQL implementations were not Turing complete as they did not provide quantifiers to access the structure of data. Modern SQL engines do allow nesting of SQL, which can be combined with keywords like 'exists' and 'in'. The following show SQL and a Rule to return a set of Students who have failed the semester.


      select 
    * 
from 
    Students s 
where exists (  
    select 
        * 
    from 
        Modules m 
    where 
        m.student_name = s.name and 
        m.score < 40 
)

    


    rule "Failed_Students"
    when
        exists( $student : Student() && Module( student == $student, score < 40 ) )