Geeks With Blogs

News
Charles Young

‘Negation’ refers to any mechanism by which we change the truth value of a statement to the opposite of its current value.   We use negation extensively in speech.   Consider the following two statements:

“I am called Charles Young”

“I am not called Charles Young”

By introducing ‘not, the second statement is a negation of the first.   The truth value of the first statement is ‘True’ (it really is my name).   It is ‘False’ for the second statement.

Negation can be a surprisingly problematic issue in the world of rules.   This article looks at one type of negation, generally referred to  as ‘negation as failure’ (NaF), and discusses  the implications for the Microsoft Business Rules Engine (MS BRE).   In summary, we shall see that MS BRE fails to provide direct support for this type of negation, and as a consequence, the Microsoft Business Rule Language (MS BRL) is less expressive than it might otherwise be.   We will also discuss a general approach to working around this lack of expressivity.

A little logic

A rule contains one or more conditions.   In MS BRE, and similar engines, these conditions are matched against ‘facts’ asserted to the working memory of the engine.   Each condition represents a proposition which can be tested.   Each proposition, when tested, may be found to be either true or false.

A condition can be either true or false.   This ‘bivalent’ approach is simplistic when compared to testing propositions in the real world.   Consider the following proposition:

“The stock market will rise tomorrow.”

Clearly, at whatever time we evaluate this proposition, we will always be unable to determine with certainty if it is true or false.   We simply don’t have the information available to use to know if this is true or not.   The stock market may rise, or it may fall.   We may be able to determine a probability as to the truth or falsehood of the proposition, but we cannot know for certain what the truth is (or, in this case, will be).

Not all propositions are bivalent.   There is often uncertainty and unknowing in the real world.   Unfortunately, engines like the MS BRE are not that good at handling uncertainties.   When an engine tests a condition in a rule, it must evaluate to either ‘true’ or ‘false’.   We are therefore forced to resort to indirect methods to handle any uncertainty.   For example, we could calculate the probability of the stock market rising, assert this as a fact and then test propositions such as:

“The probability of the stock market rising tomorrow is greater than 50%”

Probabilities are reasonably easy to handle.   However, consider the following proposition:

“Last night was hot”

I’m writing this from a hotel room in Kuwait in the summer time.   Last night, the temperature fell to a balmy 31oC, compared to daytime temperatures in the region of 45oC.   So, was last night hot, warm or cool?   In the UK, if the temperature reaches 31oC during the daytime, we complain that it is too hot (we always complain about the weather in the UK, regardless of the temperature).    Over here in the desert, 31oC offers pleasant relief from weather that, at this time of year, can top 50oC.

The ability to deal with a spectrum of possibilities when evaluating the truth of propositions which are uncertain is sometime termed ‘fuzzy logic’.   MS BRE has no direct support for fuzzy logic, and again, you must implement your own additional logic to handle this type of  requirement.   In this case, you would have to impose some overall determination of what it means to be hot, warm or cold, based perhaps on geographical location as well as temperature.   In addition, fuzzy logic often requires the combination of multiple truth values, where each truth value is taken from a range of possible values.

Back to negation.   MS BRE conditions are bivalent.   They can have just two possible values .   However,  there is a complication.   Conditions are patterns which are matched to the available facts in the working memory of the engine.   What about scenarios where there are no matching facts available.   In this case, the engine fails to evaluate the condition because there is nothing to match it to.   We cannot determine if the proposition represented by the condition is either true or false.

Sometimes, it is desirable to treat the failure to evaluate the truth value of a proposition as a negation of the proposition being tested.    We interpret the failure to mean that the proposition is false.   This is what the term ‘Negation as Failure’ means.

Consider the following business rule:

“If a departmental employee has a corporate pension then send a pension statement to that employee”

Lets imagine a scenario where we assert employee facts for people working in a specific department together with pension account facts for everyone in the company.   We will assert these facts as .NET objects.   We can represent our rule in pseudo code as follows:

IF
  PensionAccount.EmployeeId is equal to Employee.Id
THEN
  PensionHelper.SendStatement(Employee)

So far, so good.   The engine will execute instances of this rule wherever it finds a combination of a PensionAccount fact and an Employee fact that match.   Let’s now implement a second business rule:

“If a departmental employee does not have a corporate pension then send a pension brochure”

This seems like a straightforward rule.   Our first attempt to express this rule in MS BRE might be:

IF
  NOT
    PensionAccount.EmployeeId is  equal to Employee.Id
THEN
  PensionHelper.SendBrochure(Employee)

This, however, will not work.   Remember that MS BRE is a pattern matching engine.   It will execute rule instances for every combination it finds of a PensionAccount object and an Employee object where the two do not match.   This rule would probably result in every departmental employee being sent multiple brochures inviting them to get a corporate pension, whether or not they already have a pension.  This is just about the opposite of what we intended!

Before we go further, notice that we can redefine our business rule as follows:

“If no corporate pension exists for a departmental employee, then send a pension brochure to that employee”

This rule has the same semantics as before, but explicitly displays two characteristics which were implicit in the first version.   First, the proposition relies on ‘existential quantification’.    We check for the existence of any corporate pensions for a given employee.   We are not concerned about how many pensions that employee might have, but only with testing if they have any.   Second, the rule uses negation.   It has a value of ‘True’ if no pension accounts exist for the employee.

In MS BRE, we might like to express this rule along the following lines:

IF
  NOT  EXISTS PensionAccount WHERE
      PensionAccount.EmployeeId is  equal to Employee.Id
THEN
  PensionHelper.SendBrochure (Employee)

Unfortunately, MS BRE has no equivalent to the ‘NOT EXISTS…WHERE’ operator.   If it did, it would execute one instance of this rule for each employee for whom the engine failed to find any matching PensionAccounts.  

Understanding why this represents Negation as Failure can exercise the brain a little.   Consider our redefined business rule statement.   We are trying to prove the proposition that ‘no corporate pension exists for a departmental employee’.    If you think about this carefully, you can see that, in a very real sense, our pseudo MS BRE rule strictly fails to either prove or disprove this proposition.   Consider that the engine can only match conditional patterns to the available facts.   There is, however, no fact that explicitly says that a given employee does not have a corporate pension.   We are interpreting the lack of matches to mean that the employee has no pension.  

This may seem unnecessarily subtle, but consider a scenario where, for some reason, not all PensionAccounts have been asserted to the engine.   In this case the engine would probably send brochures to employees that already have a pension.   Our failure to fully assert all PensionAccount facts leads to incorrect inferences being drawn.   Consider an alternative approach where we add an additional Boolean property to the Employee class and use it to state explicitly if an employee has a corporate pension or not.   Now there could be no ambiguity about the possession of a pension.   We would know the situation explicitly for each employee.  

IF
  NOT

    Employee.HasCorporatePension
THEN
  PensionHelper.SendBrochure (Employee)

Of course, when using an engine designed to apply rules directly to business objects and data, we cannot assume that it will always be possible to introduce changes  to existing data schemas in this fashion.

Our pseudo MS-BRE rule employs a form of ‘weak negation’ through the use of ‘NOT EXISTS…WHERE’.   If the engine is provided with no factual evidence to the contrary, it assumes that an employee has no corporate pension.   If, however, we used a Boolean property on the Employee class to explicitly state the lack of possession of a corporate pension, this is an example of ‘strong negation’.   Weak negation (essentially synonymous with the term ‘Negation as Failure’) is always based on the closed world assumption.    This is the assumption that the engine is operating a closed environment where all relevant facts have been asserted.   If a fact has not been asserted, it is assumed to not exist.

In passing, note how very different this is to the ‘semantic web’.   The semantic web is envisioned by the W3C as a parallel web of meaning, co-existing alongside the hyperlinked world of web pages.   Meaning is expressed though RDF statements which act as statements of fact.    The semantic web can be searched by matching propositions against these statements.   It sounds like we are familiar territory, but consider that the closed world assumption is, in essence, invalid in the semantic web (although that is a matter of some debate).   Just because the semantic web does not contain an assertion saying something is true,  it cannot be assumed that it is false.    That would be a little like saying that, just because you can’t find any web pages describing the manufacture of jelly beans, jelly beans come into existence through spontaneous generation.    Please forgive such an imprecise analogy, especially as there is actually lots of information on the web about the Jelly Bean manufacturing process!      The point is that the semantic web exists in an open-world where we must assume that we never possess all the relevant facts.

Handling Weak Negation in MS BRE

Most pattern matching, forward chaining rules engines provide direct support for Negation as Failure through the use of specialised internal join nodes.   Hence, they support some rule syntax that is the equivalent of our make-believe NOT EXISTS…WHERE operator.   The current version of  MS BRE offers no such support, and hence no equivalent operator.    This can be a problem, as you can see from our simple example.   It represents a lack of expressivity  for which we must find work-arounds.   To be fair, all engines suffer from a lack of expressivity to some degree, and MS BRE has other redeeming features, such as its eminently simple ‘Update’  refraction feature or its automated agenda de-duplication.   These make some rules easier to express than in many other engines.   Nevertheless, the lack of support for NaF is unfortunate, especially considering that the basic approach to implementing it was first described over 25 years ago!

There is no single work-around approach, but all work-arounds will exhibit some common characteristics.   First, they will substitute a strong negation in place of a weak negation.   Your rules will test some flag or value that will explicitly state the negation of a proposition.   This is fundamental, because MS BRE does not possess the mechanisms to perform weak negations directly.

Secondly, you will have to use custom logic to infer the strong negation based on a closed world assumption.   Again, this is directly due to the lack of any support for weak negation.   You need to write your own logic to bridge the missing functionality of the engine.   If you consider our pseudo MS BRE rule, you can see that the NOT EXISTS…WHERE operator really does something similar.   It returns a value representing a strong negation based on the absence of matching facts.   In reality, you cannot reason over missing data directly in the MS BRE, so any work around is going to have to add additional logic to infer the strong negation.  

A very simple example would be the use of a Boolean property in a custom helper class with a default value of ‘false’.   You could create a rule that matches certain facts.   For each match, you could set the property to ‘true’.   Then, in a second, lower priority, rule, you could test the value of your custom property.   If it remains at its default value, then this shows that the first rule was never fired.   No matches were found, and hence you infer a strong negation from the value of the property.

In many cases, you might need to implement more complex code.   In one example, I implemented a custom factory class to create instances of a fact type which were then asserted into working memory.   Each time the engine calls the factory class to create an instance, the custom code records the new fact in a Dictionary, keyed on the value of an attribute of the fact.   In another rule, I used a helper method to look for a key value in the Dictionary and return false if the value is not found.   Care needs to be taken when writing code like this to ensure that the Dictionary is always kept accurate and up-to-date.   The code can be quite brittle.   However, this kind of approach often provides a performance advantage compared to what we might expect from typical implementations of NaF features in similar engines.

A third characteristic, which is really an implication of the second, is that you cannot generally use the forward-chaining inferencing features of the engine to infer your strong negation.   This is really just another way of saying that you have to use custom code.

For a simple example of substituting strong negation for weak negation, see the BizTalk documentation for the Rules Engine.   The documentation for the 2006 version contains a page entitled ‘How to Implement Negation as Failure’ at:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/BTS06CoreDocs/html/011ef5cd-716b-44c1-bf47-74b86e07f7bb.asp

Unfortunately, at the time of writing, this page is still awaiting a promised fix.  It fails to display the example rules!  [UPDATE:  The page has been fixed, and was relocated to http://msdn2.microsoft.com/en-us/library/aa546749.aspx. However, at the same time, although the page is available on-line it appears to have been orphaned from the rest of the BizTalk Server documentation!  Oh well.]      There is, however, an earlier (2004) version of the same page entitled ‘Implementing Negation as Failure’ at:

http://msdn.microsoft.com/library/en-us/sdk/htm/ebiz_prog_rules_emmz.asp

[UPDATE:  This page was relocated to http://msdn2.microsoft.com/en-us/library/ms964672.aspx]

I have a small complaint about these pages.   I think the titles are misleading.   You cannot implement  true Negation As Failure directly in Microsoft’s  engine.   You can simply infer a substitute strong negation using custom code.   I complained bitterly about this to the BizTalk documentation guys a couple of months back, but on reflection, I can see that you could argue that your custom code provides the implementation of NaF internally.   After all, as I pointed out above, the make-believe NOT EXISTS…WHERE operator in my sample rule operates in a similar way.

What about the ‘exists’ predicate

I have deliberately avoided discussing the MS BRE ‘exists’ predicate until the end, partly because I get a perverse kick from imagining BizTalk developers getting this far, and all the  time muttering to themselves “doesn’t this guy know about the ‘exists’ predicate”.   Yes, I know about it, and no, it isn’t a true engine-level existential quantifier.

The ‘exists’ predicate is limited in its scope.  Unlike any other pre-defined predicate, it applies only to XML facts.  You cannot use it in conjunction with .NET objects, ADO.NET data tables and rows or live data connections.   This is because it does not check for existence of matches directly in the working memory.   Instead, it performs a ‘selectNodes()’ call over XML content using an XPath.   If it fails to find any matching XML nodes, it returns false.   Otherwise, it returns true.

The ‘exists’ predicate is a built-in example of a work-around for the lack of support for NaF.  It has all the characteristics I described.   It substitutes a strong negation in place of a weak negation using ‘custom’ code (i.e., the XPath engine in the .NET framework).   It infers the strong negation by performing a selectNodes() search internally on XML content.   The nodes that the ‘exists’ predicate searches for may, or may not, correspond to facts asserted to working memory.    If they do, the ‘exists’ approximates a little more closely to a the NaF features we might wish were built into the engine.   Unfortunately, there are other reasons, specific to the use of XML facts, which means that ‘exists’ is often not very useful.   I have blogged on this elsewhere.   You will find the article at http://geekswithblogs.net/cyoung/articles/90102.aspx.

Conclusion

This article has attempted to explain the notion of Negation as Failure, and to show why direct support for it in a rules engine is welcome.   Unfortunately, the current version of MS BRE does not support NaF directly.   We have discussed, at a high level, how you might work around this  lack of functionality, and the major characteristics of such work-arounds.

Posted on Saturday, September 2, 2006 4:23 PM | Back to top


Comments on this post: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
You could do this in something like Blaze Advisor for .NET more easily. For instance:

if at most 0 PensionAccount satisfy it.EmployeeId = Employee.Id

then PensionHelp.SendBrochure(Employee).

Where PensionAccount is a class name and Employee is a pattern.

Essentially Blaze Advisor provides direct support for Negation as Failure. If a value is unknown, the condition will be assumed false unless there is some other rule that helps find the unknown value (in which case additional rules will fire to determine it and the original rule will then be re-evaluated). Blaze Advisor also has the quantified conditions of at most, at least, and every to be able to do the equivalent of the NOT EXISTS…WHERE construct.

If your rules problems start to exceed the capabilities of the MS BRE, perhaps you should consider moving to one of the pureplays rather than tinkering around the edges?
Left by James Taylor on Sep 06, 2006 3:02 PM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
I guess you get what you pay for ;-)

Seriously, though, most modern engines either have, or an in the process of being equipped with, forms of existential and universal quantifiaction. I do hope MS will follow the lead give by others.
Left by Charles Young on Sep 06, 2006 5:11 PM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
Considering that exist and NOT "arent' that hard to implement" it "shouldn't" take long for MS to implement it. There a danger with faking Neg when a rule engine doesn't support it. The first one is that it doesn't really do what the user expects and the second is the performance for work arounds is horrible. Just ask the Drools guys how the NOT work around for drools2 was. With just 16 guests and a hack work around for NOT, it took over 10 minutes. Not to mention it also took several months to get the hack NOT working correctly. If I remember correctly, the first several attempts at simulating NOT in drools2 were horrible and weren't really doing a full cross product NOT join. This in part explains why the first couple attempts to port Manners in drools2 showed it was faster than JESS. It wasn't until I dug deep into the port for drools2 that we figured out exactly what was wrong.

When a rule engine implements NOT correctly, it should take less than 1 minute for 16 guests. If the rule engine implements additional indexing for the join and not nodes, it should finish 16 guests within 1 second. JESS completes 16 guests in 250ms with a 3ghz sempron system and heap setting of 128/512Mb. Sumatra finishes in the same amount of time and drools takes longer than JESS.

Existential quantifier is also straight forward to implement, though there's 2 ways to do it. The approach taken by CLIPS is to use (not (not (blah...) ) ). It is also the approach taken by JESS and Drools3. The primary difference between NOT and Exists is that NOT on right activation only results in retracting facts from nodes lower in the network. A retract right on NOT join results in fact propogation down the network. A proper NOT implementation should calculate all cross products, maintain memories for each and propogate when the match count between the right and left is zero.

that's probably more information than most people care about.
Left by Peter Lin on Sep 06, 2006 7:28 PM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
Thanks Peter

Workarounds can be faster, in my experience. A good example is the Miss Manners variant which we created for MS BRE. It's taking such a long time to get the paper we wrote on this published, but when we do, we'll publish the code with it. The main issue we had was the lack of support for negated conjunction. We implemented custom code, very much along the lines I described in the article, using a 'Hashtable of hashtables' approach in that case to provide, in effect, our own alternative to indexed working memories (alpha memories) for Path and Chosen facts. Horrible hack, but it had much the same effect as smart indexing in Jess (MS BRE has a fairly similar indexing feature built in, by the way). And it only took a couple of hours to implement. As a result, MS BRE's performance of our variant actually out-performed Jess running a 'pure' implementation of the benchmark. I really am stealing my own thunder here, but the thing to understand about Miss Manners is that, as you increase the number of guests, the benchmark rapidly become totally dominated by evaluations at the second-to-last beta node before the 'find_seating' pNode, which is, of course, a NotCE node. This is where almost all the match cost is, and any optimisation that affects this node will effectively dictate the results you get from the benchmark. Looks like our custom code was slightly more optimal than Jess's excellent smart indexing feature (as I say, MS BRE has much the same feature). More importantly, the work we did suggest that Miss Manners does little more than measure negated conjunction at a single node, which is one more reason why it is a poor choice as a general purpose comparative benchmark.

The paper we wrote has a more complete description of what we did, and the characteristics. I'll get it out of the door as soon as I can.

I do agree that existential and universal quantifications are fairly straightforward to implement. Existential quantification, in particular, has been regularly discussed in the literature for the last quarter of a century or more. Maybe the next version of MS BRE will be upgraded to support these useful features.
Left by Charles Young on Sep 07, 2006 1:03 AM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
I wasn't able to the comment here, since it was way too long. So I made a new entry here http://woolfel.blogspot.com/2006/09/what-affects-manners-performance.html.
Left by Peter Lin on Sep 07, 2006 11:21 PM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
Thanks Peter. An excellent response. I don't consider that, in writing it, you are a trouble maker. In fact, I agree with just about everything you write, and especially your conclusions in the second-to-last paragraph about the creation of a better suite of benchmarks.

I am, personally, more with the Drools guys, than you, about my overall stance on Manners. This, however, seems to be one of those arguments that could generate more heat than light. No one is arguing about the facts, but about some of the overall conclusions we should draw from those facts. I think we probably are in agreement on this; the naive (and, sometimes, even disingenuous) use of benchmarking in performance comparisons of different engines does more harm than good, and serves only to obfuscate the facts. Miss Manners has been particularly abused in this respect over the years.

As you suggest, I learned a great deal about MS BRE (and Jess and CLIPS) from the implementation of our variant. Some of this is good, and some is bad. On the negative side, MS BRE has no support for existential or universal quantifications, and has a rather simplistic approach to conflict resolution which I find questionable. On the positive side, it provides automatic Rete optimisation (actually, can be viewed as a negative as well, as it reduces the ability to implement manual optimisation in a few cases), and has a particularly strong story to tell around refraction (I blogged previously on one aspect of this concerning the use of ‘OR’ connectives).

I do think that Miss Manners is a lot of hard work if you just want to know how well a NotCE node, or equivalent, works under stress! I'm sure it is possible to come up with a much simpler, clearer test that will provide the same information (you probably already have such a test in mind). Without a lot of hard work, it is not obvious what you are really measuring with Miss Manners. As well as the huge dominance of evaluations performed by just one node, there are other issues, such as the test's dependence on undocumented, and sometimes arbitrary and co-incidental, features of engines and the ease with which it can be ‘cheated’ (actually, a direct consequence of the dominance of that one node again).

Like others, I think the time has come to bid Miss Manners a fond farewell. I've come to find her dinner parties a little tedious, in any case. I never get a seat. I only have one hobby in life, which is hobby 7, and which I don’t share with any other guest. In any case, I am more than a number, I am a man....(sorry, showing my age, there).
Left by Charles Young on Sep 08, 2006 3:17 AM

# re: MS BRE: Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...
I totally understand the feeling about manners. At times I hate manners because it points out weaknesses in my own engine, but at the same time I can't think of a benchmark which measures so many aspects better. My list of benchmarks measure specific low level aspects, and more realistic business scenarios. I can say none of them would stress a rule engine as much as manners or waltz. Though I usually tell developers "avoid cross product mathcing" as much as possible. If someone really has a great reason for doing cross products, it can't be avoided.

I think it's important to have a difference of opinion. I wouldn't want to live in a world where everyone thinks the same.

Benchmarks will always be abused, but I doubt that will ever change. We humans are not rational and proned to idiotic behavior. I'm sure people will abuse the benchmark suite I've written up.
Left by Peter Lin on Sep 08, 2006 1:26 PM

# Using XPath to handling XML in the Microsoft Business Rules Engine
Requesting Gravatar...
A couple of days ago I found myself, yet again, introducing another BizTalk developer to the delights...
Left by Charles Young on Oct 16, 2006 4:17 AM

# Negation-as-Failure and the Microsoft Business Rules Engine
Requesting Gravatar...

‘Negation’ refers to any mechanism by which we change the truth value of a statement to the opposite...
Left by Charles Young on Oct 16, 2006 4:24 AM

# excellent description of MS BRE problems
Requesting Gravatar...
Thank you for detailed description of MS BRE problems.
1. Weak negation
2. Fuzzy logic
3. Lack of suitable predicates supported
-----------------

Hope new versions of MS BRE solved this....
Left by Ljubica on Jan 27, 2009 11:19 AM

Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net