Stanford InfoLab Publication Server

An Algebraic Approach to Rule Analysis in Expert Database Systems

Baralis, E. and Widom, J. (1994) An Algebraic Approach to Rule Analysis in Expert Database Systems. In: 20th International Conference on Very Large Data Bases, (VLDB 1994), September 12-15, 1994, Santiago de Chile, Chile.




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 diffcult 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 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.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:active database, static analysis
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:52
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:14 Jan 2009 16:19

Download statistics

Repository Staff Only: item control page