Report Number: CS-TR-94-1504
Institution: Stanford University, Department of Computer Science
Title: An Algebraic Approach to Rule Analysis in Expert Database Systems
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1504/CS-TR-94-1504.pdf