7.10. House of Doom example decisions (backward chaining and recursion)
The House of Doom example decision set demonstrates how the decision engine uses backward chaining and recursion to reach defined goals or subgoals in a hierarchical system.
The following is an overview of the House of Doom example:
-
Name:
backwardchaining
-
Main class:
org.drools.examples.backwardchaining.HouseOfDoomMain
(insrc/main/java
) -
Module:
drools-examples
- Type: Java application
-
Rule file:
org.drools.examples.backwardchaining.BC-Example.drl
(insrc/main/resources
) - Objective: Demonstrates backward chaining and recursion
A backward-chaining rule system is a goal-driven system that starts with a conclusion that the decision engine attempts to satisfy, often using recursion. If the system cannot reach the conclusion or goal, it searches for subgoals, which are conclusions that complete part of the current goal. The system continues this process until either the initial conclusion is satisfied or all subgoals are satisfied.
In contrast, a forward-chaining rule system is a data-driven system that starts with a fact in the working memory of the decision engine and reacts to changes to that fact. When objects are inserted into working memory, any rule conditions that become true as a result of the change are scheduled for execution by the agenda.
The decision engine in Red Hat Decision Manager uses both forward and backward chaining to evaluate rules.
The following diagram illustrates how the decision engine evaluates rules using forward chaining overall with a backward-chaining segment in the logic flow:
図7.27 Rule evaluation logic using forward and backward chaining
The House of Doom example uses rules with various types of queries to find the location of rooms and items within the house. The sample class Location.java
contains the item
and location
elements used in the example. The sample class HouseOfDoomMain.java
inserts the items or rooms in their respective locations in the house and executes the rules.
Items and locations in HouseOfDoomMain.java class
ksession.insert( new Location("Office", "House") ); ksession.insert( new Location("Kitchen", "House") ); ksession.insert( new Location("Knife", "Kitchen") ); ksession.insert( new Location("Cheese", "Kitchen") ); ksession.insert( new Location("Desk", "Office") ); ksession.insert( new Location("Chair", "Office") ); ksession.insert( new Location("Computer", "Desk") ); ksession.insert( new Location("Drawer", "Desk") );
The example rules rely on backward chaining and recursion to determine the location of all items and rooms in the house structure.
The following diagram illustrates the structure of the House of Doom and the items and rooms within it:
図7.28 House of Doom structure
To execute the example, run the org.drools.examples.backwardchaining.HouseOfDoomMain
class as a Java application in your IDE.
After the execution, the following output appears in the IDE console window:
Execution output in the IDE console
go1 Office is in the House --- go2 Drawer is in the House --- go3 --- Key is in the Office --- go4 Chair is in the Office Desk is in the Office Key is in the Office Computer is in the Office Drawer is in the Office --- go5 Chair is in Office Desk is in Office Drawer is in Desk Key is in Drawer Kitchen is in House Cheese is in Kitchen Knife is in Kitchen Computer is in Desk Office is in House Key is in Office Drawer is in House Computer is in House Key is in House Desk is in House Chair is in House Knife is in House Cheese is in House Computer is in Office Drawer is in Office Key is in Desk
All rules in the example have fired to detect the location of all items in the house and to print the location of each in the output.
Recursive query and related rules
A recursive query repeatedly searches through the hierarchy of a data structure for relationships between elements.
In the House of Doom example, the BC-Example.drl
file contains an isContainedIn
query that most of the rules in the example use to recursively evaluate the house data structure for data inserted into the decision engine:
Recursive query in BC-Example.drl
query isContainedIn( String x, String y ) Location( x, y; ) or ( Location( z, y; ) and isContainedIn( x, z; ) ) end
The rule "go"
prints every string inserted into the system to determine how items are implemented, and the rule "go1"
calls the query isContainedIn
:
Rules "go" and "go1"
rule "go" salience 10 when $s : String( ) then System.out.println( $s ); end rule "go1" when String( this == "go1" ) isContainedIn("Office", "House"; ) then System.out.println( "Office is in the House" ); end
The example inserts the "go1"
string into the decision engine and activates the "go1"
rule to detect that item Office
is in the location House
:
Insert string and fire rules
ksession.insert( "go1" ); ksession.fireAllRules();
Rule "go1" output in the IDE console
go1 Office is in the House
Transitive closure rule
Transitive closure is a relationship between an element contained in a parent element that is multiple levels higher in a hierarchical structure.
The rule "go2"
identifies the transitive closure relationship of the Drawer
and the House
: The Drawer
is in the Desk
in the Office
in the House
.
rule "go2" when String( this == "go2" ) isContainedIn("Drawer", "House"; ) then System.out.println( "Drawer is in the House" ); end
The example inserts the "go2"
string into the decision engine and activates the "go2"
rule to detect that item Drawer
is ultimately within the location House
:
Insert string and fire rules
ksession.insert( "go2" ); ksession.fireAllRules();
Rule "go2" output in the IDE console
go2 Drawer is in the House
The decision engine determines this outcome based on the following logic:
-
The query recursively searches through several levels in the house to detect the transitive closure between
Drawer
andHouse
. -
Instead of using
Location( x, y; )
, the query uses the value of(z, y; )
becauseDrawer
is not directly inHouse
. -
The
z
argument is currently unbound, which means it has no value and returns everything that is in the argument. -
The
y
argument is currently bound toHouse
, soz
returnsOffice
andKitchen
. -
The query gathers information from the
Office
and checks recursively if theDrawer
is in theOffice
. The query lineisContainedIn( x, z; )
is called for these parameters. -
No instance of
Drawer
exists directly inOffice
, so no match is found. With
z
unbound, the query returns data within theOffice
and determines that z == Desk.isContainedIn(x==drawer, z==desk)
The
isContainedIn
query recursively searches three times, and on the third time, the query detects an instance ofDrawer
inDesk
.Location(x==drawer, y==desk)
-
After this match on the first location, the query recursively searches back up the structure to determine that the
Drawer
is in theDesk
, theDesk
is in theOffice
, and theOffice
is in theHouse
. Therefore, theDrawer
is in theHouse
and the rule is satisfied.
Reactive query rule
A reactive query searches through the hierarchy of a data structure for relationships between elements and is dynamically updated when elements in the structure are modified.
The rule "go3"
functions as a reactive query that detects if a new item Key
ever becomes present in the Office
by transitive closure: A Key
in the Drawer
in the Office
.
Rule "go3"
rule "go3" when String( this == "go3" ) isContainedIn("Key", "Office"; ) then System.out.println( "Key is in the Office" ); end
The example inserts the "go3"
string into the decision engine and activates the "go3"
rule. Initially, this rule is not satisfied because no item Key
exists in the house structure, so the rule produces no output.
Insert string and fire rules
ksession.insert( "go3" ); ksession.fireAllRules();
Rule "go3" output in the IDE console (unsatisfied)
go3
The example then inserts a new item Key
in the location Drawer
, which is in Office
. This change satisfies the transitive closure in the "go3"
rule and the output is populated accordingly.
Insert new item location and fire rules
ksession.insert( new Location("Key", "Drawer") ); ksession.fireAllRules();
Rule "go3" output in the IDE console (satisfied)
Key is in the Office
This change also adds another level in the structure that the query includes in subsequent recursive searches.
Queries with unbound arguments in rules
A query with one or more unbound arguments returns all undefined (unbound) items within a defined (bound) argument of the query. If all arguments in a query are unbound, then the query returns all items within the scope of the query.
The rule "go4"
uses an unbound argument thing
to search for all items within the bound argument Office
, instead of using a bound argument to search for a specific item in the Office
:
Rule "go4"
rule "go4" when String( this == "go4" ) isContainedIn(thing, "Office"; ) then System.out.println( thing + "is in the Office" ); end
The example inserts the "go4"
string into the decision engine and activates the "go4"
rule to return all items in the Office
:
Insert string and fire rules
ksession.insert( "go4" ); ksession.fireAllRules();
Rule "go4" output in the IDE console
go4 Chair is in the Office Desk is in the Office Key is in the Office Computer is in the Office Drawer is in the Office
The rule "go5"
uses both unbound arguments thing
and location
to search for all items and their locations in the entire House
data structure:
Rule "go5"
rule "go5" when String( this == "go5" ) isContainedIn(thing, location; ) then System.out.println(thing + " is in " + location ); end
The example inserts the "go5"
string into the decision engine and activates the "go5"
rule to return all items and their locations in the House
data structure:
Insert string and fire rules
ksession.insert( "go5" ); ksession.fireAllRules();
Rule "go5" output in the IDE console
go5 Chair is in Office Desk is in Office Drawer is in Desk Key is in Drawer Kitchen is in House Cheese is in Kitchen Knife is in Kitchen Computer is in Desk Office is in House Key is in Office Drawer is in House Computer is in House Key is in House Desk is in House Chair is in House Knife is in House Cheese is in House Computer is in Office Drawer is in Office Key is in Desk