Friday, February 29, 2008

OpenRules Rule Compressor

The people over at OpenRules have developed some very cool technology with their Rule Compressor. Given any decision table the compressor looks for redundant rule combinations and removes them.

If I have two rows in the decision table that look like this:
if age > 50 then decrease price by 10%
if age > 65 then decrease price by 10%

We have redundancy there and it can be combined into a single rule:
if age > 50 then decrease price by 10%

This is obviously a very simple case and the Rule Compressor can do much more complex combinations. I've taken the liberty of taking a screen shot from a section showing an example from their Rule Compressor explanation page:

Tuesday, February 26, 2008

Zementis Drools Case Study

Here at Zementis we have developed a decision engine called ADAPA – Adaptive Decision and Predictive Analytics (http://zementis.com/products.htm) that offers at its core batch and real-time scoring of predictive models as well as fast execution of business rules. As you readers might have guessed, the rules engine is Drools.

I will briefly sketch the core philosophy behind the our decision engine and then detail the successful implementation of Drools in ADAPA and how Drools has been an integral part of helping us gain a strong foothold in the analytics market.

The key idea behind our decision engine has always been to integrate two philosophies: Rules-based systems (explicit knowledge) and predictive models (implicit, data-driven algorithms). We believe that in order to have a complete, “intelligent” decision engine, it should not be limited to either rules or predictive models. Hence in ADAPA, rules and predictive models can be combined with great ease to create a complex decision model.

The resulting ADAPA decision engine has been used successfully to deliver intelligent systems to the financial industry. Typically, the financial industry relies heavily on rules-based systems for making decisions on credit applications. We, on the other hand, have implemented systems that not only use conventional business rules but also calculate a custom risk score as part of the decision process. The process in a nutshell: Upon matching of appropriate facts, a rule would fire which would in turn call the appropriate predictive model, and after the predictive model returns a risk score, that number would further be used in other rules to get the correct decision.

The key points about the Drools rule engine that we want to emphasize are:

  • Drools is extremely reliable: Over the past years, we have successfully used multiple versions of Drools for complex, mission-critical deployments.

  • Drools is scalable: The rules aspect of our system has supported several thousand rules and hundreds of users while delivering sub-second response times for AJAX-based user interfaces and web services.

  • Drools is fast: The great thing about Drools that the clients immediately noticed was the speed of execution. The Drools rule engine would return a decision on complex loan applications so fast that we had clients ask: “How can it be so fast?”

  • Usability: We authored all rules using the Excel based decision table approach. This approach worked better for our user base over writing drl files since it enabled, e.g., a mortgage lender to make changes to rules on a regular basis without needing dedicated IT staff. We would initially create all appropriate Excel files and then let them enter data to reflect their mortgage guidelines. Hence having the ability to generate rules through Excel, versus only being able to write ‘drl’ files gave us a strategic advantage in usability.

Thank you Drools team!

Sunday, February 24, 2008

RETE Nodes indexing in Drools

Michal Bali has written a short explanation on alpha and beta node indexing:
RETE Nodes indexing in Drools

Friday, February 22, 2008

Solving the Examination problem part 1: Domain diagram

The examination problem is one of the examples in drools-solver. It has a number of exams, students, periods and rooms. A student is enrolled into multiple exams. Each exam needs to be scheduled into a period and into a room. Multiple exams can share the same room during the same period.

There are a number of hard constraints that cannot be broken:
  • Exam conflict: 2 exams that share students should not occur in the same period.

  • Room capacity: A room's seating capacity should suffice at all times.

  • Period duration: A period's duration should suffice for all of its exams.

  • Period related hard constraints should be fulfilled:

    • Coincidence: 2 exams should use the same period (but possibly another room).

    • Exclusion: 2 exams should not use the same period.

    • After: 1 exam should occur in a period after another exam's period.


  • Room related hard constraints should be fulfilled:

    • Exclusive: 1 exam should not have to share its room with any other exam.

There are also a number of soft constraints that should be minimized (each of which has parameterized penalty's):
  • 2 exams in a row.

  • 2 exams in a day.

  • Period spread: 2 exams that share students should have a number of periods between them.

  • Mixed durations: 2 exams that share a room should not have different durations.

  • Front load: Large exams should be scheduled earlier in the schedule.

  • Period penalty: Some periods have a penalty when used.

  • Room penalty: Some rooms have a penalty when used.

It uses large test data sets of real-life universities. You can find more information here.

So let's take a look at the domain diagram:



The first dataset has 7883 students, 607 exams, 54 periods and 7 rooms. That makes over 10 to the power 1052 possible solutions. Another dataset even has 10^5761 possible solutions. This means that a brute force algorithm is not an option, unless you can wait over 10^5700 years.

In upcoming blogs, I 'll take a deeper look into the implementation and how to deal which such a massive search space. Continue with the next part of this blog series.

Thursday, February 21, 2008

“Program, Enhance Thyself!” – Demand-Driven Pattern-Oriented Program Enhancement

Godmar Back has been relentless in the mailing list recently diving deep into Drools and shining a bright light on obscure bugs. Good work Godmar, keep it up - that which does not kill us, can only make us stronger :)

I'd also like to bring this paper written in collaboration by Dr. Eli Tilevich and Dr. Godmar Back to everyone's attention. It's a very interesting read on how Drools can be used to dynamically enhance classes using rules and aop (aspectj). I've taken the liberty of pasting the abstract and a section with some examples in it. enjoy.

“Program, Enhance Thyself!” – Demand-Driven Pattern-Oriented Program Enhancement

Program enhancement refers to adding new functionality to an existing program. We argue that repetitive program enhancement tasks can be expressed as patterns, and that the application of such enhancement patterns can be automated. This paper presents a novel approach to pattern-oriented automated enhancement of object-oriented programs. Our approach augments the capabilities of an aspect compiler to capture the programmer’s intent to enhance a program. In response to the programmer referencing a piece of functionality that is non-existent, our approach automatically synthesizes aspect code to supply the required functionality transparently. To improve flexibility and facilitate reuse, the synthesis and application of the new functionality is guided by declarative whenthen rules, concisely expressed using a rule base. Our extensible automated program enhancement system, called DRIVEL, extends the AspectJ compiler with aspect generating capabilities. The generation is controlled using the DROOLS rules engine. To validate our approach and automated tool, we have created a collection of enhancement libraries and used DRIVEL to apply them to the LibX Edition Builder, a large-scale, widely-used Web application. DRIVEL automatically enhanced the LibX Edition Builder’s XML processing modules with structural navigation capabilities and caching, eliminating the need to implement this functionality by hand.
...
...
Below, the variable ’m’ is bound to any encountered ’InvalidMethod’ facts meeting the condition that the name of the missing method is “toStringLong.” AddToStringLong(m) returns an enhancement object, and the insert method adds it as a new fact into the working memory.

rule "Provide a toStringLong() aspect"
when
m : InvalidMethod ( methodName == "toStringLong" )
then
insert (Enhancements.AddToStringLong(m));
end
A second example shows how rules can be triggered even in the absence of compile time errors using annotations. The annotation @NaturalOrdering triggers an enhancement that adds a natural ordering to a class, allowing it to be used in java.util.* containers without requiring the use of a comparator.

rule "Provide a natural ordering"
when
t : Clazz ( annotations[’NaturalOrdering’] != null )
not ( Enhancements.HaveNaturalOrdering ( clazz == t ) )
then
insert (Enhancements.AddNaturalOrdering(t));
end

The ’not HaveNaturalOrdering’ construct prevents the application
of this rule if the class already defines a natural ordering. Applying
the enhancement will assert a “HaveNaturalOrdering” fact for the
class that is being enhanced. If the class already provides a natural
ordering via a compareTo method, a rule can add this fact as
follows:

rule "Disallow natural ordering annotation if compareTo() is present."
salience 10
when
m : Method (name == "compareTo",
signature == "(Ljava/lang/Object;)I")
then
insert(new Enhancements.HaveNaturalOrdering (m.getClazz()));
end
The ’salience 10’ argument gives this rule higher priority than the “Provide a natural ordering” rule, thereby ensuring that its antecedent is falsified before it fires, preventing the accidental application of the enhancement (which would result in a compile error).

Wednesday, February 20, 2008

Shadow Facts - What you always wanted to know, but was afraid to ask

Shadow Facts are (a necessary) evil. I'm sorry to tell you that. Their purposes in life are to increase memory usage, add method call indirections and cause all types of hassle for us poor rule engine users.

Well, having said that, I must also say that they have a side effect of keeping the Rule Engine Session (a.k.a. Working Memory) in a consistent state in the presence of non-tracked fact attribute changes. But that is minor of course. Did I mentioned I hate Shadow Facts?

This post is a follow up on a discussion we were having in the Drools mail list and tries to bring some light to the shadow (facts).

What problem are Shadow Facts trying to address?

Rules Engines usually reason over facts (in the form of data structures) that are defined, created and managed by their own API. This is what happens with the regular Jess/CLIPS templates, just to mention one example.

Such facts do not require any form of "shadow facts", because all the handling is done through the engine API and as so, it is completely traceable and controlled by the engine. There is no "unsafe" change.

Well, that was beautiful, but someone realized that it is a pain to integrate such engines with the common Java programs out there. It would be much simpler to directly use the application POJOs as facts in the rules engine. That would avoid a lot of bridging and copy operations between the application and the engine "worlds".

I'm sorry to say I don't know who first introduced the concept, or the whole history behind it. I'm just mentioning Jess as an example, but many other engines support that.

The idea of using POJOs as facts without the need to explicitly copy attribute values from POJOs to templates and vice-versa is wonderful, but it raises a problem: a POJO attribute may be changed by a simple method call. There is no need to use a traceable engine API to do the job and so, the engine would completely lose control over the reasoning process. Even worse, since the application may have references to the objects asserted as facts, the application may change the fact attributes while they are in the working memory and the engine would not know about it, causing all types of inconsistencies.

In Drools syntax, imagine a rule like:
rule "my simple rule"
when
Person( likes == "cheese" )
then
// give cheese to the person
end

Pretend that in a stateful session, after asserting a Person fact that likes "cheese" into the working memory (and consequently activating the rule above, but before firing it), the Person changes his mind and now it likes "chocolate". The application changes the likes attribute value, but the engine don't know about it, since it has no way to trace such changes. Consequently the engine would fire the rule anyway, what is clearly inconsistent. And this is just one simple example of the wide range of inconsistencies that may happen in such scenario.

Shadow Facts to the rescue

So, how can we allow the engines to reason over POJOs without incurring in the above described problems? This is critical for Drools that uses POJOs as its primary fact type, but is also a problem other engines (like Jess) have do deal with.

Shadow Facts are the most common way of solving this problem.

Shadow Facts are a "copy" of the fact attributes. As simple as that. So when you insert a POJO fact into the working memory, the engine will transparently copy the fact attributes to an internal structure and will reason over that structure instead of reasoning over the POJO directly. This way, if any non-traceable change happens to the POJO's attributes, the engine will be shielded by it and remain consistent. If the application wants the change to become "visible" to the engine, it just needs to notify the engine by calling the update() action. The engine will make sure the attribute changes will become visible only at a safe point.

This is the mechanism used by most engines I'm aware about, including Jess and Drools, although the implementation are certainly different.

How Drools implements Shadow Facts?

As mentioned before, the primary fact type for Drools is POJO. It means we not only reason over POJOs, but we use POJOs internally to represent the facts. To not break this paradigm and to allow the engine to transparently work with facts that have shadow facts enable and facts that have shadow facts disabled, we implemented Shadow Facts as lazy proxies.

So, when an application asserts a Person instance to the working memory, the engine will dynamically bytecode generate a PersonShadowProxy class that extends the Person class and keeps a lazy proxy of the required attributes. It also keeps a "delegate" attribute to the actual asserted fact (instance). The engine only sees PersonShadowProxy, but anywhere we expose the fact to the user, only the Person instance is exposed. This keeps the working memory consistent and safe from external changes. Although, it obviously creates overheads and eventual problems with final mutable classes, that can't be extended, but have mutable attributes. It is also not simple to deal with the Collections Framework, because Maps and Collections do not follow the Javabean Spec, but must also be shadowed.

Is there a way to disable Shadow Facts and still keep the working memory consistent?

The good news is: yes. It is possible to do that if you follow a set of best practices.

1. Immutable classes are safe: if you have immutable classes that you use as facts you don't need to do anything for them.

2. In your rules, only change fact attributes inside modify() blocks: both Drools supported dialects (MVEL and Java) have the modify block construct. Make sure all fact attribute changes are made inside modify() blocks and you are safe. You can find more info on the Java modify block syntax here. MVEL example is here.

3. In your application, use modifyRetract() and modifyInsert() around any attribute changes for your facts: this way, the engine becomes aware that attributes will be changed and can prepare itself for them.

// create session
StatefulSession session = ruleBase.newStatefulSession();

// get facts
Person person = new Person( "Bob", 30 );
person.setLikes( "cheese" );

// insert facts
FactHandle handle = session.insert( person );

// do application stuff and/or fire rules
session.fireAllRules();

// wants to change attributes?
session.modifyRetract( handle ); // call modifyRetract() before doing changes
person.setAge( 31 );
person.setLikes( "chocolate" );
session.modifyInsert( handle, person ); // call modifyInsert() after the changes

If you can make sure that all changes made to fact attributes happens in the ways described above, you can go ahead and completely disable Shadow Facts. You can do that by setting a system property:

java -Ddrools.shadowproxy=false ...

Or by using the API:

RuleBaseConfiguration conf = new RuleBaseConfiguration();
conf.setShadowProxy( false );
RuleBase rulebase = RuleBaseFactory.newRuleBase( conf );

Is Drools team thinking about improving that?

Yes. Mark is working on a new implementation for the next major release that completely removes the need for Shadow Facts in common use cases. Since this blog post is already huge, we will talk about this subject in another blog post.

Any questions, just talk to us in the mail list or in the IRC channel.

Happy Drooling,
Edson

Tuesday, February 19, 2008

Looking under Drools' skirt

As most users know, during rule compilation, Drools generates several classes in Java to represent rule consequences and semantic blocks of code. Although, for performance reasons, this whole process occur in memory and no content is dumped to the filesystem.

We had a few requests in the past to expose the generated code in some way, so that the users can look at it and eventually understand what is happening behind the scenes. Since this is a useful feature for debug sessions too, I just added a configuration parameter to allow users to dump the generated Java code to disk.

In order to do that, just set the "drools.dump.dir" property with the root directory where you want files dumped:

java -Ddrools.dump.dir="some/root/dir" ...

Or use the PackageBuilderConfiguration API:

PackageBuilderConfiguration conf = new PackageBuilderConfiguration();
conf.setDumpDir( new File( "some/root/dir" ) );
PackageBuilder builder = new PackageBuilder( conf ) ;

It is important to remember that depending on your rules, Drools may generate several files. It will use the provided root directory as the base directory and will create subdirectories as needed and defined by the usual Java package directory structure.

This is available both in 4.0.x branch (to be released in version 4.0.5) and trunk (to be released in 5.0.0).

Enjoy.
Edson

Drools BRMS Guide (Business Rules Management System)

Shortcut to Drools BRMS end user guide (preview)

The aim of Drools (or any other Business Rules Engine) is to get knowledge out of business user's heads and into a format where it can be copied , edited and peer reviewed , then run 24/7. Ideally, business users should be able to write these rules directly (a) to save time and (b) to reduce errors caused by a 3rd party having to to 'translate' these rules into code. And it saves you (as a technical person) from having to code them yourself.

Drools Brms Screenshot

Drools BRMS (Business Rules Management System) is such a tool. Easily deployed into almost any Java Web or App server, it allows users to write and validate business rules that you can then pull into your Enterprise Java Application.

Because it uses the Google Web Toolkit (GWT) , even though it is a web application (i.e. zero install on client machines) it behaves and performs as fast as a desktop one. And unlike some other (Commercial) Rules Engines, it's free to Download and use (under the Apache licence) from the JBoss site.

And now there is a guide for business users available online. Shortly to be integrated into the existing Drools (technical) documentation a preview of the JBoss Drools BRMS guide is now available.

More Information

Sunday, February 17, 2008

Drools Clips

I've done some more work on Drools Clips in the last few weeks and it's starting to take shape now and the basic shell is working and we should have something useful as part of the next Drools milestone release in a few weeks. You can see the unit tests here:
http://anonsvn.labs.jboss.com/labs/jbossrules/trunk/drools-clips/src/test/java/org/drools/clips/ShellTest.java

Below you can see two of the unit tests demonstrating deffunctions and rules:

public void testRuleCallDeftemplate() {
String function = "(deffunction max (?a ?b) (if (> ?a ?b) then (return ?a) else (return ?b) ) )";
this.shell.eval( function );

this.shell.eval( "(import org.drools.*)" );
this.shell.eval( "(defrule testRule (Person (age ?age) ) => (printout t hello)
(printout t \" \" (max 3 ?age) ) )" );
this.shell.eval( "(assert (Person (name mark) (age 32) ) )" );
this.shell.eval( "(run)" );
assertEquals( "hello 32",
new String( this.baos.toByteArray() ) );
}

public void testTwoSimpleRulesWithModify() {
this.shell.eval( "(import org.drools.*)" );
this.shell.eval( "(defrule testRule ?p <- (Person (name ?name&mark) ) =>
(printout t hello) (printout t \" \" ?name) (modify ?p (name bob) ) )" );
this.shell.eval( "(defrule testRule (Person (name ?name&bob) ) => (printout t
hello) (printout t \" \" ?name))" );
this.shell.eval( "(assert (Person (name mark) ) )" );
this.shell.eval( "(run)" );
assertEquals( "hello markhello bob",
new String( this.baos.toByteArray() ) );
}
We have support for a large set of the Clips LHS rule syntax and functions are easy to add. As Drools DRL also has support for the Jess 7.0 style infix notation we will add support for that too. The goal is to support the full LHS syntax for Jess and Clips. For now we will be missing out logical assertions, Jess slot specific and Clips COOL. Our logical assertion approaches are slightly different, so it's easier to leave that out, and we currently have no way to support slot specific which is also the behaviour of Clips COOL. As we have full support for Java pojos and their approach to OO we have less need for COOL at this stage. It would be nice to add slot specific support soon and I hope to do it some time this year.

We do not yet support deftemplates but the rules will reason directly over pojo classes, as our DRL already does. I will add support for those soon.

One of the cool things about this is that it doesn't just allow you to execute Jess and Clips rules but that it also provides you with a migration path. Using DrlDumper you can now load Jess/Clips rules via drools-clips and have the DrlDumper dump them to the more modern Drools DRL syntax.

I've actually changed my design approach for this. Originally I was building my own Lisp execution engine and then realised that I was creating much of the infrastructure that we already had put into MVEL. As Lisp really is just an abstract syntax tree you can actually take any Lisp statement and dump it to MVEL for execution. So I gave up on my own Lisp execution engine and instead did a Lisp to MVEL converter. This is only a stop gap though as Mike Brock has promised to eventually do a direct S-Expression lexer and parser for MVEL. It's trivial to add new built-in functions to drools-clips by simply creating an MVEL language dumper. You can look at the existing functions like the 'if' function in the link below to see how simple this is:
http://anonsvn.labs.jboss.com/labs/jbossrules/trunk/drools-clips/src/main/java/org/drools/clips/functions/IfFunction.java

Tuesday, February 05, 2008

Drools 2.x Migration Script

Arina He has create an XSLT migration script from Drools 2.x to Drools 4.x. He has uploaded the script with instructions to the wiki:
http://wiki.jboss.org/wiki/Wiki.jsp?page=Drools2Migration

If anyone uses this, please give us feedback on your success or failures :)

Friday, February 01, 2008

Sandia's Jess 7.1a3 rule engine selected by Lockheed Martin for Navy's DDG 1000 destroyer ship

It's great to see public announcements like this, as it helps demonstrate that there is real value to using and deploying expert systems - far too many interesting projects are kept secret. Congratulations Ernest.

Sandia's Jess 7.1a3 rule engine selected by Lockheed Martin for Navy's DDG 1000 destroyer ship

"Sandia is a National Nuclear Security Administration laboratory.

The Navy’s DDG 1000 is a multi-mission, maritime fleet of destroyer ships. It includes a number of advanced technologies and features, including an integrated power system, dual band radar, integrated undersea warfare system, and advanced gun system. Among other intended uses, Jess will help the DDG 1000 ship domain controller with its alarm management function and reasoning about ship system states for safe operation."

JavaOne turns down Drools presentations

Edson submitted two Drools presentations to JavaOne this year and I submitted one, entitled "Declarative programming with rules, processes and cep" - all where refused. So yet again JavaOne will be littered with talks on various web frameworks of the month, but nothing on a really interesting, innovative and increasingly important area of technology in the Enterprise. Oh well better luck next year :(