Project Award Information:
Award No.: IRI-9410993
Title: A Development Environment for Active Database Systems: Testing and Analysis of Active Database Rules
Duration: 1 June 1995 - 30 June 1998

Project Summary: Active database systems transform passive database processing into active environments by using rules as alerters and triggers. This research is investigating two complementary aspects of active database development environments: the analysis of rules for termination and confluence properties and the run-time testing and debugging of active rules. The research is addressed in the context of an active, deductive, and object-oriented database. The rule analysis process is a static approach, applying termination/confluence analysis techniques from conditional term rewriting to identify rule problems before execution. The run-time environment is a dynamic approach allowing users to step through the rule triggering process, observing rule behavior and testing different rule triggering sequences. The execution model includes a propagation algorithm for monitoring changes to derived data. The integration of rule analysis with rule generation and transaction development to support specification and analysis of rules prior to rule execution is also being investigated. The significance of this work is found in the integration of active, deductive, and object-oriented concepts as well as the supportive environment provided to address the correctness and predictability of active rules in the development of complex database applications.

Goals, Objectives, and Targeted Activities:
As part of this research, we have been investigating the development of an active rule development environment that supports the analysis, testing, and debugging of active rules using an active, deductive, object-oriented language known as CDOL (Comprehensive, Declarative Object Language) [Urban97]. The major accomplishments of our work include 1) the development of an initial prototype for active rule debugging, 2) the definition of CDOL, 3) the development of a static rule analysis tool, 4) the development of testing techniques for active rules, 5) the definition of an object delta structure for capturing evolving database states in CDOL, 6) the use of the object delta structure for condition monitoring in condition-action rules, and 7) the use of the object delta structure in the construction of a run- time environment for event-condition-action rules in CDOL. By the end of the funding period, we also expect to produce results describing the manner in which our debugging environment can be used to support the refinement of transaction design in active database applications.

Our research activities were initiated with the development of an active rule debugging prototype to investigate useful features that should be developed as part of any active rule debugging tool, as well as implementation issues that must be considered for the development of rule debugging environments [Jaehne96]. Our initial prototype, known as PEARD for Prototype Environment for Active Rule Debugging, was implemented using Smalltalk and was not based on the use of a specific database environment. We are now using the ideas that we investigated in the construction of PEARD to develop a more sophisticated environment for CDOL based on our developments with object deltas, paying particular attention to the architectural design issues that are important in the construction of a flexible, active database environment.

As an active, deductive, object-oriented language, CDOL provides sub-languages for the expression of derived data, constraints, updates, and active rules. The rule-based query language of CDOL extends the set of stored attributes for a particular class with a set of virtual attributes that are defined using CDOL passive (i.e., deductive) rules. The update rule language is an augmentation of the rule-based query language, where the rule body specifies the objects to be updated and the rule head specifies the update operation. The active rule sub-language provides active, user-transparent agents that support reactive behavior within CDOL applications. As part of our research, we are constructing a run- time environment for CDOL using the SHORE object manager for persistence. This run-time environment requires the evaluation of the CDOL language, which is a non-trivial task for an expressive language such as CDOL. This part of the work is being completed as Siddabathuni's research (see theses in progress below), utilizing our established expertise on the evaluation of declarative languages and investigating the operations provided by the AQUA object algebra.

The static rule analyzer was developed to implement the refined triggering graph (RTG) method of rule analysis [Tschudi97], which was developed by A. Karadimce and S. Urban as part of a previous NSF research project conducted at Arizona State University. Using CDOL rules, the static rule analyzer builds a triggering graph and applies the semantic methods of the RTG method to demonstrate that a conservative triggering graph can be significantly reduced through the use of satisfiability methods applied to the conditions of the rules in the graph. In support of the work, we developed a testbed to demonstrate the use of the analysis process. We also performed an evaluation of the RTG method to determine how well the different analysis tools within the method perform under different rule conditions.

Our research has also focused on the investigation of testing techniques for active rules [Chan97]. The development of testing techniques is a unique aspect of our work that has not been studied in other active database research projects. In particular, we have investigated the application of structural and functional testing to active rules. A prototype of a test case generation tool for active rules is expected to be completed in the Spring of 1998. Our approach is based on the concept that a suite of complementary techniques for testing is an effective means of active rule verification. The prototype tool implements testing techniques based on structural testing techniques, such as control flow and data flow, and functional testing techniques, such as input domain and boundary value tests. The prototype illustrates the applicability of the developed testing techniques for active rules and provides a sample architecture for an active rule testing environment.

A major result of our research has been the development of object deltas and their use in support of the CDOL development environment [Sundermier97]. Deltas for representing incremental changes in a database state have primarily been investigated in the context of condition monitoring within active, relational environments. We have extended the concept of relational deltas to an object-oriented environment, creating the notion of object deltas. Our notion of object deltas is different from the work of deltas in H2O in that we provide a self-describing, system-supported approach to deltas that is stored together with each object.

We have investigated the use of object deltas for two different uses within the CDOL environment. One use of object deltas is for condition monitoring. Condition monitoring techniques monitor the changes to the database state to efficiently determine when a condition is satisfied, thus triggering condition-action rules in CDOL. It is obviously undesirable to monitor all conditions defined in the database over the entire database instance. Object deltas identify the conditions that need to be monitored and provide bindings for incremental condition evaluation.

Our second use of object deltas is for support of the run-time debugging environment that we are developing for CDOL. Our notion of object deltas is enhanced with delta abstractions that allow the run-time debugging tool to view deltas at different granularity levels. Granularity levels correspond to different language components of CDOL, such as active rules, update rules, transactions, and methods. Delta abstractions therefore provide a means to rollback to previous states, to replay rule execution, or to query information about the evolution of the database state during the rule triggering process. We are currently integrating object deltas and delta abstractions into the CDOL active rule run-time environment to support the development of a debugging tool based on object delta functionality. We are especially interested in how object deltas can be used to enhance run-time analysis of rule termination and confluence and thus support transaction analysis and design for active applications. This work is being completed as the dissertation research of T. Abdellatif (see dissertations in progress below).

Indication of Success:
This research project will reach its termination point by the end of this year (June 1998 plus a 6 months no-cost extension). We feel that all of the objectives of the project will have been fully addressed by that time. Our success can be measured in terms of 1) the publications that we have generated (and will continue to generate throughout the rest of this year), 2) the students that we have produced, and 3) the overall results that we have been able to demonstrate as a result of this work. The development of tools to assist in the use of active database rules is critical to the future development of active database applications. Using active rules can be a difficult experience; they are not easy to write and the interaction between all rules is not easy to understand. We have been able to demonstrate static and dynamic approaches to rule analysis, where static approaches provide compile-time detection of rule problems and dynamic approaches provide run-time support for examining the execution of rules. The two approaches are complimentary, especially considering the computational limitations of static analysis techniques. We would like to have accomplished more in the way of fully integrating all of the different components of our work, but were often limited by resources (lack of funds to support more students). We have, however, addressed all of our original objectives and demonstrated solutions that now provide issues for commercial database vendors to consider in terms of 1) developing tools to assist in the use of triggers and active rules, and 2) designing the internal structure of database systems to better support such tools.

Project Success and Impact :
Theses/Dissertations Produced and In Progress (Advisor):

• Taoufik Ben Abdellatif, Ph.D. (S. D. Urban) "An Architecture for Active Database Systems Supporting Rule Analysis Through Evolving Database States," expected completion date of Fall 1998


• Hon Wai Rene Chan, M.S. (S. W. Dietrich) "Active Rule Testing: A Case Study of Structural and Functional Testing for the Comprehensive and Declarative Object Language (CDOL)," expected completion date of Spring 1998.


• Babu Siddabathuni, M.S. (S. W. Dietrich) "Evaluation of the Comprehensive Declarative Object Language," expected completion date of Summer 1998.


• Amy Sundermier, M.S. (S. W. Dietrich) "Condition Monitoring in an Active, Deductive, Object-Oriented Database," expected completion date of Fall 1998.


• Michael Tschudi, M.S. (S. D. Urban) "Static Analysis of Active Database Rules: Evaluating Tools for Termination Analysis," Spring 1997, currently works at Intertel in Chandler, AZ.

As a result of our research, we have integrated active database concepts into several of our database courses at Arizona State University. Our first level graduate course in database systems now covers the use of triggers in products such as Oracle, as well as the problems associated with the use of such features. Our course on object-oriented database systems covers the issues of active, object-oriented database systems. Active database concepts are taught in more detail in this course, including the issues of termination and confluence. Details related to our results on object deltas will be incorporated in the next offering of the course. We also teach a deductive database course that address active, deductive database systems. The next offering of this course will also address our results on object deltas as well as the use of object deltas in condition monitoring techniques.

We are also now investigating the application of active database concepts to distributed environments as well as the extension of our results on rule analysis, testing, and debugging for distributed rule processing.