‘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! 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
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.
First posted at
http://geekswithblogs.net/cyoung/articles/90100.aspx