Report Number: CS-TR-94-1504
Institution: Stanford University, Department of Computer Science
Title: An Algebraic Approach to Rule Analysis in Expert Database
Author: Baralis, Elena
Author: Widom, Jennifer
Date: February 1994
Abstract: Expert database systems extend the functionality of
conventional database systems by providing a facility for
creating and automatically executing Condition-Action rules.
While Condition-Action rules in database systems are very
powerful, they also can be very difficult to program, due to
the unstructured and unpredictable nature of rule processing.
We provide methods for static analysis of Condition-Action
rules; our methods determine whether a given rule set is
guaranteed to terminate, and whether rule execution is
confluent (has a guaranteed unique final state). Our methods
are based on previous methods for analyzing rules in active
database systems. We improve considerably on the previous
methods by providing analysis criteria that are much less
conservative: our methods often determine that a rule set
will terminate or is confluent when previous methods could
not. Our improved analysis is based on a ``propagation''
algorithm, which uses a formal approach based on an extended
relational algebra to accurately determine when the action of
one rule can affect the condition of another. Our algebraic
approach yields methods that are applicable to a broad class
of expert database rule languages.