TechTalk: Scott Woodgate Talks About BizTalk Server 2004 & 2006

And so these messaging based systems were good for getting customers started with connecting applications together, but they were really looking to add some more value into what they were doing by putting a business process on top of it. So, it’s not just Seibel talking to SAP, but it’s a conversation where Seibel and SAP talk because I receive a purchase order from trading partner that goes into my Seibel application, does a lookup on some employee information, comes back to my SAP system, does a lookup on some price and so on. So that business process functionality is something that everybody was really keen for us to improve on in BizTalk Server 2004. That was the number one investment we made in 2004.

And the first thing I want to say is, if you're a developer, architect or customer and you’ve been considering enterprise service bus because you have been talking to one of key analysts like Gartner or one of our competitors, then Microsoft can absolutely offer enterprise service bus capabilities. The combination of BizTalk Server and web services stack today offers that and then BizTalk Server and Indigo in 2006 timeframe really compete the web services stack.

Of course, it needs to be economical relative to other rules engines and I think our low-end edition, Partner Edition, which includes the rules engine and only costs a thousand US dollars is incredibly economical relative to competitive offering in the rules engine space.

A challenge to Microsoft

And now, you can put those inside a forward chaining RETE based rules engine and that rules engine then goes ahead and executes the rules and there is a user interface that you can use, or you can create your own as a developer to go ahead and make that easy for people to create rules out of your own web pages to ASP.NET or through a designer that we provide.

A challenge to Microsoft

So Detective ...

So Detective ...

So you're saying that there is no way they could be telling the truth about RETE and BizTalk? There is no scenario that would lead to the kind of performance degradation you describe? I would think that such conclusions would require a detailed knowledge of the BizTalk implementation. Do you have that knowledge?Or are you saying that because other rules engines that you do consider to be RETE "compliant" perform as you expect, all such engines must perform similarly? There’s no possibility, none, that other features that span the implementation might cause the performance characteristics to be different?I personally find your conclusions just a bit of a jump. But maybe you have much better evidence than you've exposed here.

if
  obj1.attr1 == 1, obj1.attr3 == "hello" (pattern 1)
  obj3.attr3 bound to var myvar0, obj3.attr1 == 100 (pattern 2)
  obj2.attr2 bound to var myvar1 (pattern 3)
  myvar0 == myvar1 (pattern 4)
then
  do something

here is the link

Conclusion

you're right

What I'm trying to point out is, even if there's some doubt that BizTalk is fully RETE, to say that it definitively is not, simply from circumstantial evidence, is a little presumptuous.

Rather, if there is some question, let's try to get Microsoft to answer instead of calling them a bunch of liars. It may be that you're right. It may also be that there is anther good reason for the seeming disparity of facts.I'm not saying you can always believe Microsoft market droids, but their technical people usually shoot straight (in my experience, anyway--maybe your experience is different).

oops typo

Therefore, the ethical thing to do is to simply claim BRE is a forward chaining rule engine and claim something that is clearly questionable.peter

More evidence

Other odd behavior

Does no comment from Microsoft mean it's not RETE?

The match algorithm used in the first implementation of Foops takes every rule and compares it to all the frame instances on each cycle. In particular, both of the example rules above would be compared against working storage on each cycle. Not only is redundant matching being done on each cycle, within each cycle the same frame patterns are being matched twice, once for each rule. Since working memory generally has few changes on each cycle, and since many of the rules have redundant patterns, this approach is very inefficient.

With the Rete algorithm, the status of the match information from one cycle is remembered for the next. The indexing allows the algorithm to update only that match information which is changed due to working memory changes.

The rules are compiled into a network structure where the nodes correspond to the frame patterns in the LHS of the rules. There are three basic types of node which serve as: the entry to the network; the internals of the network; and the exit from the network. These are called root nodes, two-input nodes, and rule nodes respectively.

Yes it is Rete!!

Are you sure?

PeterI've been meaning to weigh into this argument for several months or at least get round to blogging on the Rules Engine in some depth. I don't particularly want to start some 'war' on this subject, but your comments cannot remain unchallenged any longer.First to state my 'credentials'. I'm not, and never have been, a Microsoft employee. I do, however, work for a Microsoft Gold Partner company that specialises principally in BizTalk development, and I have personally been using BizTalk Server 2004 continually for almost two years (since beta). I also arguably have the best knowledge of the Rules Engine amongst my immediate colleagues, though I don't pretend to rival your experience of implementing Rete-based engines. I am not speaking on behalf of Microsoft, either officially or unofficially. Indeed, I have not discussed this reply with anyone in my own company, let alone Microsoft.

Rete algorithm I think it should be noted that Scott Woodgate, who is the programme manager for BizTalk, stated very clearly, some months ago in this same forum, that the BizTalk engine implements the Rete algorithm. The Business Rules Framework team is quite separate to the BizTalk team, and Scott is not really a techie, but nevertheless, Microsoft has responded previously to your questions and claims.

For my part, I can assure you, with all the authority I can muster on this subject, and without any equivocation, that the Microsoft Rules Engine is 100% based on the Rete algorithm. It represents a particularly straight-forward 'text-book' implementation of the algorithm, without any notable elaboration or deviation (Scott's comments about some optimisations are all very straightforward, and do not affect the core implementation of the algorithm in any way). The implementation includes everything you would expect, including alpha and beta memory, root, condition, join and terminal nodes, an agenda, conflict resolution and working memory. The engine is rather un-adventurous, in that it supports only a single, salience-based, conflict resolution policy. How do I know all this - well...a techie's fascination with how things work coupled with a bit too much time spent with a reflector tool.Side effectsI was particularly concerned to read your beliefs on how the engine is implemented. This is not accurate in any respect, although you do raise one significant issue with regard to 'side effects'. Unfortunately, your conclusion that "This means [the engine] does not support "truth maintenance" and requires developers manually keep track of modifications." is very incorrect. However, as the documentation on side effects is partial, minimal and fairly impenetrable, I can understand the confusion.

Before explaining, let me get one issue out of the way. I have seen no evidence of a non-monotonic CF approach, and am quite certain that this is not used by the engine. On the contrary. The engine uses the classic Rete approach, storing partial match results in beta memory.As you have surmised, the side-effects feature could potentially 'compromise' truth maintenance to a degree. However, Microsoft has adopted other strategies within their technology which mitigate or remove this risk in most scenarios, and by default, they only allow the risk in a limited set of scenarios for some very good and practical reasons. I would certainly want to criticise Microsoft for their failure to properly document this, and I have a few minor concerns about some of the exact mechanics of how they have implemented their side-effects feature, but broadly, their approach is sensible and reasonable. Microsoft supports three different 'media' for representing and asserting facts to the engine. Facts can be asserted as .NET objects, XML documents or ADO.NET datasets (a dataset is essentially an in-memory relational data cache).

Internally, the engine further abstracts facts in two ways. Firstly, it wraps XML documents and dataset objects in specialised 'wrapper' classes (rather like shadow facts). Secondly, and more importantly for the purposes of this discussion, it abstracts all facts within the working memory using instances of a class called 'WorkingMemoryElement' (they couldn't have been any more 'text-book' than this). All the stuff you wrote about XPath and leaf nodes is entirely wrong in relation to the engine. In effect, WorkingMemoryElement lies at the centre of a typical head/slot representation of facts.

The 'side effects' feature refers to a simple read-only cache feature associated with WorkingMemoryElement. This cache is optionally used during slot evaluation. The 'sideeffects' flag which controls this is set (via Microsoft XML rule language) on each slot evaluation within conditions and actions. If switched on, the cache is not used - i.e., WorkingMemoryElement goes back to the underlying fact object to get the datum. If switched off, the WorkingMemoryElement caches the value on the first read, and uses the cache thereafter.

By default, 'side effects' is only switched on for slots backed by .NET object facts. It is switched off for XML and dataset facts. There is a very good reason for this. In order to support its generic abstraction of facts internally, the engine uses reflection to invoke members of underlying 'fact' objects (remember the engine uses wrapper classes for XML and datasets).

For facts asserted as .NET objects, the engine invokes methods and properties (.NET's higher-level abstraction of accessor methods) using this single mechanism. This means that the engine can evaluate members that execute code. If side effects is switched off, code will only be invoked the first time the slot (which maps to the object member) is evaluated. By adopting the default of switching side effects on, Microsoft ensures that the code in the underlying .NET object is invoked on each evaluation.

For XML and dataset facts, side effects is switch off. More than that, the flag appears always to be ignored when evaluating an XML or dataset-backed slot within a condition (this is entirely undocumented!). Hence, issues only arise when asserting .NET objects as facts. You could debate Microsoft's default approach endlessly, but for my part, I think their decision to switch side effects on for .NET objects is sensible and defensible. Novice users would be very confused by the alternative approach, and experienced users can always switch the side-effects feature off. Microsoft has reduced the risk further through another mechanism whereby, generally, asserts, updates and retracts (I won't explain the finer points of an 'update' here, but Microsoft's implementation is quite interesting) are only performed once all other actions in a rule have been completed (including any evaluations of slots within the action list). It does this regardless of where asserts, etc., appear in the action list. This makes sense in the vast majority of scenarios, although a knowledgeable developer can invoke asserts, etc., (and hence enter a new match-resolve-act cycle) midway through the action list if they really want to.

This is a documented feature (just), and helps to reduce the risks associated with using the side effects feature.The real issue here is that there is an impedance between the OO model represented by .NET objects and the head/slot model typically used in Rete-based engines. Microsoft allows developers to exploit the rich OO model directly within their rules without any particular restriction, but this means that they map 'slots' not only to accessor methods, but also to other methods including voids and static members. I love this feature, but also recognise that it can (and often does) lead to a somewhat 'impure' approach where business logic is deeply integrated with asserted facts.

This is very practical and flexible when dealing with business rules, but maybe not designed to appeal to the AI purists amongst us. It's worth mentioning something about shadow facts here. I've only come across the term 'shadow facts' in Jess. In this case, shadow facts essentially wrap Java Bean components (a bit like Microsoft wrapping XML DOM document and ADO.NET dataset objects) and can optionally use PropertyChangeListeners to update working memory with changes to bean state.

Because the .NET object approach is not targeted to a specific component model, there is no equivalent of Jess' PropertyChangeListener approach, but there again, this feature is not needed if side effects is switched on. Performance
This must, of necessity, be the weakest part of my reply because I do not have comparative facts and figures to prove/disprove your assertions about performance. I did implement the Miss Manners benchmark (traditional 8-rule version) a little while back, and I have run some entirely informal and non-trustworthy tests against a very similar implementation for an open-source Java-based Rete engine. The Microsoft engine 'won' in this case, but given the way benchmarks are treated, I am not willing at this time to publish my 'results', or even to say which engine I ran the tests against. Suffice to say that my informal testing suggested that the Microsoft engine is really quite efficient.

Your specific issue is with some figures published in a Microsoft whitepaper. If I get time in the next few weeks, I might see if I can shed further light on the alleged performance degradation when increasing the number of rules. The whitepaper does not provide any great detail on exactly how the measure was made. The paper was, I presume, written by members of the BizTalk team. this team was not responsible for the rules engine, and wouldn't necessary be aware of the finer points of Rete performance (the author may never even have heard of Rete). They are measuring enormous rulesets containing between 1,000 and 10,000 rules. There is plenty of scope here for significant misinterpretation of what the figures are telling us, and to base such a sustained attack on Microsoft's engine on the basis of a couple of graphs is really not, in my opinion, very wise.

Still, I understand the concern. If I get time I will look into this issue further.If you are interested in getting your hands on the rules engine, you could always download the 120-day evaluation copy of BizTalk from the Microsoft web site at:http://www.microsoft.com/biztalk/evaluation/trial/default.mspx)

from Forgy's paper

1.2. Work on production system efficiency
Since execution speed has always been a major issue for production systems. several researchers have worked on the problem of efficiency. The most common approach has been to combine a process called indexing with direct interpretation of the LHSs. In the simplest form of indexing, the interpreter begins the match process by extracting one or more features from each working memory element, and uses those features to hash into the collection of productions. This produces a set of productions that might have satisfied LHSs.
The interpreter examines each LHS in this set individually to determine whether it is in fact satisfied. A more efficient form of indexing adds memory to the process. A typical scheme involves storing a count with each pattern. The counts are all zero when execution of the system begins. When an element enters working memory, the indexing function is executed with the new element as its only input, and all the patterns that are reached have their counts increased by one. When an element leaves working memory, the index is again executed, and the patterns that are reached have their counts decreased by one. The interpreter performs the direct interpretation step only on those LHSs that have non-zero counts for all their patterns. Interpreters using this scheme—in some cases combined with other efficiency measures—have been described by McCracken [8], McDermott, Newell, and Moore [9), and Rychener [10].

The Rete algorithm was first described in 1974 [3]. A 1977 paper (4] described some rather complex interpreters for the networks of feature recognizers, including parallel interpreters and interpreters which delayed evaluation of patterns as long as possible. (Delaying evaluation is useful because it makes it less likely that patterns will be evaluated unnecessarily.) A 1979 paper [5] discussed simple but very fast interpreters for the networks. This article is based in large part on the
1979 paper.

The box receives information about the changes that are made to working memory, and it determines the changes that must be made in the conflict set to keep it consistent. For example, the black box might be told that the element
   (Goal T Type Simplify T Object Exprl9)
has been added to working memory, and it might respond that production TimexN has just become instantiated.

Clarification

The real issue here is that there is an impedance between the OO model represented by .NET objects and the head/slot model typically used in Rete-based engines.

Microsoft allows developers to exploit the rich OO model directly within their rules without any particular restriction, but this means that they map 'slots' not only to accessor methods, but also to other methods including voids and static members.

As explained above, the black box must maintain state information because it must know what is in working memory. In simple Rete networks all such state is stored by the two-input nodes. Each two-input node contains two lists called It’s left and right memories. The left memory holds copies of the tokens that arrived at its left input, and the right memory holds copies of the tokens that arrived at its right input. The tokens are stored as long as they are useful. The next section explains how the nodes determine when the tokens are no longer useful.

Both kinds of one-input nodes could be represented as single words that are divided into three fields. The first field would hold the type of the node. The second field would hold the index of the value to test. The third field would
hold either a constant or a second index. The bits in a word could be allocated as follows A sixteen-bit field is required to represent an integer or an atom using the
format of Section 3.1. Since a floating point number cannot be represented in sixteen bits, in nodes that test floating point numbers, this field would hold not the number, but the address of the number.

Yes I am.

Good points

My view on the side effects issue is that Microsoft has implemented a straight-forward trade-off for practical purposes. When using XML documents and datasets, the engine works in a classic fashion, creating shadows, caching the data and thereby preventing data from being changed in working memory by another process. When using .NET objects, the cache is switched off by default. I agree that this can reasonably be characterised as 'impure', but I think that it is quite wrong to state that the engine is therefore not Rete-based. I just don't get it. Rete is an algorithm for maximising matching performance by using node sharing and state retention (alpha and beta memory). Truth maintenance is an important aspect in any deductive system, but surely the fact that Microsoft has given us some limited control over this does not in any way change or invalidate the core matching algorithm. My view is that this 'impurity' is entirely reasonable and practical. I entirely understand that you may disagree with that statement, but I find the claim that the engine in not therefore Rete-based to be extreme!

Given your stance on this, would you then accept that, if side-effects are switched off for .NET objects (which is easily done), the engine magically becomes Rete-based? How exactly does the side effects feature change the matching algorithm? I knew my head/slot statement would cause trouble, which is why I adopted the slightly strange terminology of describing WorkingMemoryElement as being 'at the centre of' this model. WorkingMemoryElement is simply what the name suggests (as per fairly common terminology in text-book descriptions of Rete).

I was trying to stress the fact that the engine really does have a genuine working memory, and that the physical representation of facts is abstracted using much the same conceptual model employed in other Rete-based engines. This remains the case when using .Net objects, and hence, although I accept that the default 'side effects' feature is 'impure', it does not, as you suggested, mean that the engine has no genuine working memory.

Driving home this evening, I started thinking more deeply about Microsoft's performance figures, and it occurred to me that we may both be missing the blindingly obvious. If you look again at the whitepaper, you will see that Microsoft provides an illustration of the type of rule they implemented, as follows:

If ( ClassN.Attribute >= constant ) Then {Do something}

The example rule will surely result in the Rete containing condition nodes only, and no join nodes. If there are no join nodes, there is no use of beta memory. I think we would both agree that the performance characteristics of Rete are primarily influenced by partial match retention in beta memory.

However, it looks like the simple rules used in the test only result in the use of alpha memory, and I also suspect that Microsoft’s test ruleset did not really get any noticeable benefit from node sharing. I would expect that for such simple rules, the performance of Rete would be linearly dependant on the number of rules - exactly what the graphs show!

The trouble here is that the BizTalk team appear to have implemented their test using rules that are so extremely simple, they really don't benefit, in terms of performance, from being represented as a Rete.

The test therefore surely proves nothing about the use, or otherwise, of the Rete algorithm. Put another way, I can't see that a given implementation of the Rete algorithm would ever guarantee a particular ruleset-size/activations-per-second ratio. The performance of the Rete will depend on the benefit gained principally from partial match retention (beta nodes), secondarily from minimisation of condition/constant filtering (alpha nodes), and thirdly from node sharing. This, in turn, is driven by the complexity of the rules in the ruleset. Lots of simple rules get little benefit. Lots of complex rules get a lot.

As I said in my earlier post, the BizTalk team were not responsible for implementing the rules engine, and the people who did the performance tests probably did not have enough knowledge to understand that their tests are actually failing to show the true performance benefits of the Rete approach when using large rulesets with at least a degree of complexity within those rules. I am considering publishing the Miss Manners implementation at some point, but will need to jump through some commercial hoops first. In the meantime, I would prefer to decline saying which engine I tested against. I have a healthy suspicion of all benchmarking figures, including my own, and especially of comparative benchmarking. I just don't want to get into the position of appearing to claim that one engine is faster than another based on some quick and dirty tests done, as I recall, on a virtual PC image running on a memory-starved notebook!! There are other issues as well. Miss Manners is, in my opinion, not a good benchmark for comparative tests (Waltz is, I suspect, better, but I haven't got round to implementing this yet). For example, it is, I think, too highly sensitive to the exact behaviour of the conflict resolver.

I also remain unimpressed by the argument that Miss Manners shows how the engine behaves when stressed. Yes, it does stress the engine, but only by the artificial device of adopting a really inefficient approach to solving the seating problem. You would never implement a real-life solution in this fashion, so can we really say it is a trustworthy guide to the likely performance in live systems.

Another (minor) issue is that the original implementation assumes that you can perform existence checks on working memory ('if fact x does not exist...'). Many engines, including Microsoft's, do not support this, although Microsoft does implement an XPath-based 'exists' predicate for use with XML-based facts only. And also, as we all know, a lot of vendors have 'cheated' in their implementations of Miss Manners, so you never really quite know what you are comparing!I have only implemented Miss Manners using .NET object facts.

I always intended to create three implementations for the three different fact representation types. Perhaps I should do this and then publish (if I am allowed) the code and results (obtained on a 'proper' platform!!).

corrections to my post

If the alpha nodes do not store an index for each fact, doing a retract would require traversing all alpha (1-input) nodes.

What I think happened...and other matters

What I think happened...and other matters

Hence, it is likely that the Rete contained no beta nodes, and that no forward chaining occurred. Indeed, the Rete would have consisted of a rather 'flat' structure of alpha nodes taking input from the input nodes (Microsoft calls these 'class' nodes) and outputting directly to terminal nodes. We are told that "different .NET classes were used for the rules in the policy", which indicates that Microsoft probably asserted a number of facts of different types. I suspect (it is a guess on my behalf) that they created a certain number of almost identical classes, created a number of instances of these classes and asserted them as facts, and had rules which simply tested some value on each fact.

Given that the test involved the use of rulesets containing between 1,000 and 10,000 rules, Microsoft must have generated their rules either in-memory using the API or by generating XML. Let's speculate that they had five different fact types, and hence five input nodes. We will further assume that they created their rules to test fact types in a round-robin fashion (i.e., rule 1 tests type A, rule 2 tests type B, etc., with rule n1 going back to testing type A and starting a round 'round'). For the 1,000 rule test they would end up with 200 alpha nodes per input node. Let’s say they asserted 5 instances of each fact type. There would have to be 5 * 200 (1,000) alpha traversals. Now, if Microsoft then generated a 2,000-rule ruleset using the same round-robin approach, and using unique constants in their conditions, each of the five input nodes would now have 400 alpha nodes. Assert the same 25 facts, and there would now be 2,000 alpha traversals, taking approximately twice as long. With no beta nodes, and no forward chaining, the test as a whole would take approximately twice as long to complete, and you would get exactly the kind of graph Microsoft shows.

I realise this speculation and guesswork proves nothing about the implementation of the Microsoft Rules Engine. However, it does suggest that a perfectly reasonable explanation can be given, based on the partial information provided, which would lead to the results. There is no need to assume that the engine is not using Rete. Rather, we might speculate that some BizTalk guys, who did not have a good understanding of the Rete algorithm, came up with a very simple test that they thought showed a really nice classic linear scale, without realising that in fact they are showing the engine behaving at its least efficient!

You'll be amused to know that I spent time this weekend writing a test for Drools using rulesets of the sort I suspect Microsoft used in their test (as described above), and got an identical result to Microsoft's (2x linear scale). However, I am not particularly familiar with Drools, and am uncertain about its status re. Rete.

The web site appears to claim to be implemented on Rete (Rete-OO), but I understand, from what you have said elsewhere, that this is not correct, and that you have written an implementation of the algorithm (or at least the alpha memory part of the algorithm) which the Drools team are currently integrating into their engine in order to make it truly Rete-compliant. If this is the case, I guess my Drools test proves nothing, unless, perhaps, Drools is currently capable of performing Rete-like node sharing.

Do please let me know the current status. Is there a beta version of Drools available with a true Rete implementation? We might ask if there is any evidence in the Microsoft performance paper that actively supports the claim that the engine is using Rete? Well, yes there is actually. I think maybe you would not have picked up on this, as not having experience of this particular engine, you may not have realised the implications of one of the tests. On pages 72 and 73, Microsoft reports the result of a test under the title “Increasing the Number of Conditions”. This is one of a series of tests investigating performance in relation to the use of facts asserted as ADO.NET datasets where a connection to the underlying data source is exploited. Microsoft explains the test as follows:

"This test used a policy that contained 100 rules, and changed the number of unique conditions in the rules. Rule N

If (Table1.Column1 = (N Mod NumberofUniqueConditions) Then Class1.Property1 = Table1.Column1

The purpose of the test was to show how the data connection binding becomes much more efficient when the rule set uses shared conditions/queries."

The resulting graph shows a very significant increase in performance as the number of ‘unique queries’ contained in the conditions of the rules is reduced to 1. If the engine is using Rete, then with NumberofUniqueConditions set to 1, there would be just one alpha node for the condition of Table1.Column1 = 0. While I accept that this does not prove a correct implementation of Rete, it is, nevertheless, clear evidence that the engine is behaving in a Rete-like fashion.

The performance characteristic is exactly what would be expected as a result of alpha node sharing. In fact, I have looked pretty hard at the code, and can confirm that this is exactly what would happen in this case.

Implementation Details

I can help with the details of how the engine is implemented. While it is true that I don't have access to the source code, Microsoft has not obfuscated their compiled code, and there are some good reflection tools out there for .NET. I hope Microsoft won't mind me providing a high-level description of their implementation and the names of some of their internal classes. My point is that, as you will see, the Microsoft developers clearly believed they were implementing Rete.Microsoft implements their Rete engine in a namespace (similar to a Java package) called Microsoft.RuleEngine.Rete. The 'executor' is represented by a top-level class called Rete. The executor is initialised by a translator class called RuleSetToReteTranslator which creates the Rete directly from a given ruleset. Note that Executors and Translators are just two of several different pluggable components within the Microsoft Business Rules Framework, and the classes I am describing are the implementation provided 'out of the box' by Microsoft.

Microsoft represents different Rete node types using node classes. Here is a class diagram showing the inheritance hierarchy (sorry, it will probably need copying and pasting in a fixed-pitch font to view correctly).

The ClassNode class defines what, elsewhere, might be called input or type nodes. The SelectNode class defines alpha nodes and the JoinNode class defines beta nodes. Note how both these classes are derived from MemoryNode.

The full implementation of alpha and beta memory would take a fair amount of describing, but at its core, Microsoft implements alpha memory using an internal class called 'AlphaMemory'. This maintains a sorted (and partitioned) list of HashTables (HashMaps, in Java-speak). Each HashTable acts as a bucket of tokens, each containing a working memory element represented by the WorkingMemoryElement class. The sorted list is indexed on the 'literals' within a given condition. So, to summarise, alpha memory is a sorted list, sorted by 'literal' value, of buckets of WMEs.

Conditions are represented using instances of a class called 'RelationalTest'. These contain the left and right arguments and a relational operator. Join classes (beta, 2-input nodes) have left- and right-memories. Each memory contains either a 1-input or a 2-input node. As I say, the implementation of alpha and beta memory is fairly involved (I haven't unravelled it totally), but suffice to say that you get your indexing at both alpha and beta nodes.

The agenda is represented by a class called 'PrioritizedAgenda' which is derived from an abstract class called 'Agenda'. PrioritizedAgenda maintains an internal queue (implemented in a class called PriorityQueue) of instances of a class called 'Production'. Production instances represent rules, and maintain a list of actions represented by Action and derived Argument objects. Productions are queued in priority order (the only conflict resolution strategy supported by the engine is a salience approach driven by a rule priority setting). Items are added to the agenda by terminal nodes.

As I say, I think it is fairly clear from the above that it certainly looks and smells like a Rete implementation when you look at the code.  Not the ‘BizTalk’ Rules EngineJust one other small matter. You, naturally enough, have on several occasions referred to the Microsoft Business Rules Engine as the ‘BizTalk’ rules engine. It is true that at the current time, the only way of obtaining the engine is with a copy of BizTalk. This is a licensing thing, only, and we can be fairly certain that this will change over time as Microsoft releases new products and product versions to market.

The engine is, as I began to describe above, a pluggable component (one of several) within an overall Business Rules Framework. As well as ‘executors’ and ‘translators’, Microsoft supports an entire framework for managing the capture and storage of rules and semantics. They supply a SQL Server repository and associated ‘Rules Composer’ tool, but the framework also comes with pre-built support for any OLE-DB rule repositories and also XML files. There is also an entire rule publishing framework (centred on a Windows service) that is decoupled from both rules stores and rule executors. If the truth be told, some of the tools are a little basic at present, but no doubt this will improve, and the framework is wide open to third-party plug-in, repository and tool development or integration with existing engines and frameworks. I mention this for information and clarity about the nature of the product, and also to draw a clear distinction between BizTalk, which is an enterprise level message routing and business process orchestration tool, and the rules engine. BizTalk is quite separate to, and not in any way dependant on the rules engine, although there is some very lightweight integration with the framework in order to allow rules and rules engines to be exploited within automated business processes.

link to screen capture

An interesting paper...

An interesting paper...

I happened across an interesting paper at http://reports-archive.adm.cs.cmu.edu/anon/usr/ftp/home/ftp/1992/CMU-CS-92-158.ps. The paper has some relevance to this discussion. It looks at the 'clash of views' on how alpha and beta match time tends to increase as rulesets are increased. Essentially, it contrasts the worlds of parallel production systems and EBL (Explanation Based Learning).

The Microsoft test results provide an example of what the authors call 'Average Growth Effect', or AGE. For parallel production systems, the expectation, we are told, is that adding large numbers of rules leads to little or no AGE. In EBL systems, the expectation, apparently, is exactly the opposite, and the paper even has an 'AGE Prediction' graph looking just like the Microsoft results.

The authors of the paper analysed this conflict of expectations using test production systems implemented using SOAR, and they specifically state that they used the Rete algorithm. They implemented three very different production systems. Two of them exhibited little or no AGE, and the third exhibited some AGE (a 2x slowdown for each 6-fold increase in the rules).

They conclude that "the presence or absence of AGE appears related to particular tasks (or domains) and encoding styles". They state that "...an acknowledgement that the existing match algorithms (the specifically appear to have Rete in mind here) cannot alleviate the AGE...could be considered as a key outcome of our investigation".

Please note that I mention this as a point of interest only, and not as some kind of counter argument to anything you have said. Your position, I believe, is that rules engines built on the Rete algorithm can and often do exhibit a degree of AGE (I love discovering new acronyms!), but not, as a general observation, to the degree that the Microsoft figures exhibit. I totally agree with this, although I think we may have a reasonable explanation for the MS figures.

Looks like global bindings

more food for thought

Its a rule 'term', not an engine function

Jess, Drools and MS-BRE comparison

Typo alert...

Further results

thanks to Mr Young

DSLs and language interop

VS 2008 Resources

VB code downloads home

XAML Learning Guide

Company uses VSTS DB edition to tame workflow

Book: Intro to DSL Tools

I See the Silverlight Shining!

A look at .NET 3.5

Venkat Subramaniam on AJAX

Building a Claims-Based Security Model in WCF - Part 2

Introducing the Entity Framework

WCF Security Learning Guide

Brad Abrams: Patterns for successful ASP.NET AJAX development

Building a Claims-Based Security Model in WCF

Authoring workflow using XAML