Institute for Systems Research Technical Reports

For the Update Dependency Language, we formally define the language and define safety requirements for its conditions and procedures. We analyze the lacking requirements for two different execution strategies: one that uses a depth-first search and one that uses a concurrent search. We show that it is incorrect to release shared locks on failed subpaths before a successful path is found. However, we show that two-phase locking can be relaxed to allow the early release of exclusive locks along failed subpaths.

For the Starburst Rule System, we describe the components that handle recovery in the presence of system- generated and user-requested rollbacks. We investigate the problem of maintaining rule priorities in the Starburst Rule System and others, describing the requirements and implementation of a priority system that combines user-defined priorities and system-generated default priorities. To support an environment in which users can modify rules during normal database operations, we define consistency requirements for rule definition operations and present a solution based on hierarchical locking that maintains these consistency requirement in a multi-user environment.

We present data structures an efficient algorithms for implementing such a priority system. We show how the data structures can be incrementally maintained as user- defined priorities are altered. We also discuss how the proposed scheme can be extended to build a multi-level hierarchical priority system.