Raymond Pendergraph's List: Rules Engine Research

• The Rete network is comprise of two types of nodes:

    
   
  • 1-input/1-output nodes 
     
    • The 1/1 nodes are constrictive nodes that only allow matching tuples to flow through. Any tuples that do not match are discarded by the node.
     
     
   
     
   
  • 2-input/1-output nodes 
     
    • The 2/1 nodes simply connect the output arcs from two other nodes (either 1/1 nodes or 2/1 nodes) merging tuples from both the left and right incoming arcs into a single tuple on the outgoing arc. Maintains a memory of tuples for matching against future facts.
     
     
   
     

  A forest of 1/1 nodes acts as the entry-point into the entire Rete network for any incoming tuple. The network-entry nodes filter tuples purely by their type. Tuples about dogs and tuples about cats may each have a different type and may be differentiated from each other by the 1/1 network-entry nodes.

  • This was documented as part of the JBoss Drools project
• Whenever a fact is asserted, retracted or modified within the Working Memory, many rules may become candidates for firing, or may have become invalidated. A simplistic approach is to reevaluate all rules against the entirety of the working memory. This method is guaranteed to be correct but will also certainly be sub-optimal. Any individual fact modification only affects a small number of conditions in a small number of rules.

• The Rete algorithm keeps up to date the information associated with the nodes in the graph. When a fact is added or removed from working  memory, a token representing that fact and operation is entered at the  root of the graph and propagated to its leaves modifying as appropriate the information associated with the nodes.  When a fact is modified, say,  the age of John is changed from 20 to 21, this is expressed as a deletion  of the old fact (the age of John is 20) and the addition of a new fact (the age of John is 21).

• The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper (see References). Rete has become the basis for many popular expert systems, including CLIPS, Jess, JBoss Rules, and Soar.

• The Rete algorithm (usually pronounced either 'REET', 'REE-tee' or, in Europe, 're-tay' after the Latin pronunciation, from the Latin 'rete' for net, or network) provides the basis for a more efficient implementation of an expert system. A Rete-based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left-hand-side of a rule. The path from the root node to a leaf node defines a complete rule left-hand-side. Each node has a memory of facts which satisfy that pattern. This structure is essentially a generalized Trie.

   

  As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered.

• Drools is an Object-Oriented Rule Engine for Java. Drools is an augmented implementation of Forgy's Rete algorithm tailored for the Java language. Adapting Rete to an object-oriented interface allows for more natural expression of business rules with regards to business objects.  More importantly, Drools provides for declarative logic programming and is flexible enough to match the semantics of your problem domain. The various parts that compose a rule may be extended to lend domain-specific sense to the rule.
• SweetRules is a uniquely powerful integrated set of tools for semantic web rules and ontologies, revolving around the RuleML (Rule Markup/Modeling Language) emerging standard for semantic web rules, and supporting also the closely related SWRL (Semantic Web Rule Language), along with the OWL standard for semantic web ontologies, which in turn use XML and, optionally, RDF. (SWRL rules are essentially an expressive subset of RuleML rules.)   SweetRules supports the powerful Situated Courteous Logic Programs extension of RuleML, including prioritized conflict handling and procedural attachments for actions and tests. SweetRules' capabilities include semantics-preserving translation and interoperability between a variety of rule and ontology languages (including XSB Prolog, Jess production rules, HP Jena-2, and IBM CommonRules), highly scaleable backward and forward inferencing, and merging of rulebases/ontologies. Procedural attachments can even be WSDL Web Services.   SweetRules' pluggability and composition capabilities enable new components to be added relatively quickly. Implemented in Java, SweetRules has a compact codebase (~40K lines of code total for several dozen tools).   The SweetRules project is an international, multi-institutional effort, originated and coordinated by the SweetRules group at MIT Sloan led by Benjamin Grosof, and its creation was funded largely by the DAML (DARPA Agent Markup Language) research program which co-pioneered the Semantic Web.   SWEET ("Semantic WEb Enabling Technology") is an overall set of tools that Benjamin Grosof's group (with collaborators) has been developing since 2001.
• • Needs more research
• OpenRules is a full-scale open source Business Rules Management Framework. It efficiently uses the power of MS Excel, Eclipse IDE and open source Java libraries to create, deploy, execute, and maintain different rule engines with complex business logic controlled by business analysts.
• Zilonis provides a Multithreaded Rules Engine platform and a scripting environment for Java based applications.  The core of the Zilonis platform is based on a variation of the forward chainning Rete algorithm described in "Rete: A Fast Algorithm for the Many Pattern/ Many Object Pattern Match Problem", Charles L. Forgy, Artificial Intelligence 19(1982), 17-37.).  The implementations follows the optimizations and the structure used in the Soar system, and the ones well described in the paper: "Production Matching for Large Learning Systems", Robert B. Doorenbos. 1995   Multithreaded Capabilities  A nice feature and contribution from Zilonis, is that it is multithreaded. Because of that, it is easy to reuse a set of rules across several concurrent users in a safe way, without creating copies of the rules and the engine, as you would have to do if you were to use other engines.
• TermWare is a rule processing engine intended for embedding into Java applications. TermWare implements terminal systems concept.
• JLisa is a powerful framework for building business rules accessible to Java and it is compatible with JSR94 V, the JavaTM Rule Engine API
• Hammurapi Rules is JSR-94 compliant rules engine. With Hammurapi Rules Java developers don't need to learn a new rules language - rules are written in Java. Hammurapi Rules leverages Java language type system and naming conventions to plug rules into its inference engine.
• Take (aka Mandarax Compiler) consists of a scripting language that can be used to define derivation rules, and a compiler that creates executable Java code and deploys it into running systems. Take is inspired by Mandarax, has a similar API but does not use a separate interpreter "inference engine". The deployment process is very similar to how web servers treat server pages. The result is optimized, reflective and easy to maintain code.
• JEOPS is a Java based forward chaining RULE ENGINE. This Rule Engine is used to power up the business process by rules in Java Application Servers, client applications, and Servlets.
• JRuleEngine is a java rule engine, based on Java Specification Request 94, release 1.1, i.e.   Rules can be loaded by an XML file or by means of JRuleEngine APIs, so rules can be stored externally into a database, too.  The distribution consists of a library that can be embedded into a java application, so it can be used in any kind of application (web based or not).
• Prova (from Prolog+Java) is a rule-based system for Java and agent scripting and information integration extending the Mandarax engine with a proper language syntax and enhanced semantics. The language breaks new ground in combining expressive and declarative programming. It combines natural syntax and typing of Java with Prolog-style rules and database wrappers. Java calls may include both constructor and method calls as wellas access to public variables in classes. Distributed and agent programming transported via JMS or JADE protocols is based on reaction rules specified in a natural syntax. The language makes it easy for agents to engage in concurrent conversations without starting new threads by using reaction and novel inline reaction rules in a very natural and ecoonomic syntax, directly capturing conversations as state machines.

10 more annotations...