On rules and relations

Having designed and built a number of rules engines over the years, I’ve come to realize that rules and relational databases just don’t get along. I thought I might explore why that is, and, given the shotgun wedding of the two demanded by Oracle’s dominion and the emerging demand for business rule automation, suggest some ways of working around it.

Rules are sentences. Remember the other name for the propositional calculus is the sentential calculus.

So rules are a kind of language. And one of the defining features of language is that its structure is recursive: bigger units are built up by combining similar smaller units, which themselves may be combinations of even smaller similar units, and so on.

The first problem with putting rules in databases is that databases don’t like recursive data. They especially don’t like recursion (think self-join) to an unknown-ahead-of-time or varying depth.

The second problem is that our rules’ literals, the ‘variables’ which are bound at evaluation, usually come from the database. So there is a dependency between our rule structure and the database structure. There is a modeling-level problem here: a rule stored as data has a structural dependency on the level of structure that contains the data.

So storing rules in a relational database makes them difficult to work with, and difficult to maintain. (I confess I have not looked at how other people’s rules engines such as Drools have addressed this problem. I am inspired to do so now, and will add to this thread with what I find out.) [see comment below - Max.]

There are a couple of practical things that will help.

The first is something called disjunctive normal form. This is something well known in the realm of automated theorem proving. In disjunctive normal form, or DNF, a formula is expressed as a disjunction of conjunctions. ‘Not’ is only allowed to bind to literals. So these are valid formulas in DNF, assuming ‘A’, ‘B’, and ‘C’ are literals. I’ll use a v for ‘or’, a ‘^’ for and, and a ‘!’ ‘not’:

• A
• !A
• A ^ B
• (A ^ B) v C
• (A ^ !B ^ C) v (!B ^ A)

And so on.

DNF has some interesting and useful features.

The first is that it lends itself to conditional evaluation. You can determine the truth value of the entire formula very efficiently by simply starting at the leftmost literal and evaluating to the right. The first false literal you reach in a conjunction makes the whole conjunction false, so you can skip to the next conjunction. And the first disjunction that is true makes the whole formula true.

The second useful feature of DNF is that it consists of only a few elements in a very regular structure, making it relatively easy to model.

The third useful feature of DNF is the ‘resolution principle’: (p ^ q) v (!p ^ r) –> q v r is a tautology, so we can replace the left side with the right before we evaluate the rule. There are other similar simplifications that can be applied to make evaluation more efficient (these are only two examples):

• p v ( p ^ q) –> p
• ( p ^ q) v ( p ^ r) –> p ^ ( q v r )

The fourth useful feature of DNF, and the most suprising, is that it has all the expressive power of the full propositional calculus. Any WFF of the propositional calculus can be mechanically translated into DNF. If we combine this with the substitution strategy we just visited, we come up with a proof strategy:convert to DNF, then substitute until you reach a tautology. In a rules engine we can follow the same path until we run out of substitutions, then we bind our literals to our domain and evalute. (One caution – if you start with something in the inverse form, Conjunctive Normal, and convert it, you can end up with an extremely large – think exponentially large – DNF formula.)

So rules (or just their antecedents if our model is logical antecedent->consequent action) can be stored and evaluated efficiently in DNF. Translating from the full PC can be a challenge. In practice, business users don’t use material implication in business rules, so constraining the UI to DNF is not particularly onerous. UI designers and builders will appreciate the simplicity and regularity of the form.

So lets say you’ve followed my advice, and have a database for storing DNF, with relational expressions (like schema.table.column >= scalar value) as the logical literals. (I will flesh this out sometime with a pseudocode example.)

How do you query a rule from the database, when you don’t know how deeply nested it is?

The answer is to use Oracle’s ability to do hierarchical queries. Hierarchial queries appeared in Oracle 8i (don’t quote me) and have been improved in subsequent versions. Hierarchical queries permit querying n-deep self joins efficiently in a single SELECT, where parent->child rows (and->grandchild rows, etc, to whatever level of nesting is present) are returned as consecutive rows.

Getting our rules out of the database is reduced to executing a hierarchical query, then iterating over the result set to build up the rule from its parts.

Addressing the structural dependency problem requires bridging the modeling level gap. One effective approach to managing this is to have the schema name, table name, column name, data type and size part of the record of the literal. Then it is a simple matter to query the data dictionary to determine if the schema->table->column->type->size is valid and raise an exception if a database structure change has broken rules.

This will all be a lot more clear with some explicit examples. I’ll try to add them soon.