Tech Report CS-93-17

Interacctions: Multidatabase Support for Planning Applications

Marian H. Nodine

May 1993

Abstract:

A planning task's purpose is to determine, given information about the world, how to reach some particular goal in that world. In this thesis, we examine the ways that a planning task interacts with information in different databases. These databases are grouped together into a single logical entity, called a multidatabase.

A planning task lasts from the time the goals are initially decided on to the time the execution of the plan is complete. During this time, which may be very long, the state of the world as represented in the multidatabase may evolve. If this evolution affects the validity of the plan (as developed so far), then the plan itself may need to be modified so that it is valid given the new state of the multidatabase.

We propose a new transaction model, called Interactions, and an architecture to support them. This model and architecture provide the following capabilities to the planner.

1. Define different possibilities for how to accomplish the goal and the relative acceptability of each possibility. 2. Define conditions that are set by specific subtasks and which must be maintained for the plan to remain valid. 3. Detect when a condition is violated, indicating the plan is no longer valid. 4. React to the condition violation by modifying the current plan into one that is valid given the current multidatabase state.

This thesis has two major themes. The first is theoretical: we provide a formal definition for Interactions. Basically, an Interaction is an open nested transaction, i.e., a partial order of atomic multidatabase transactions. It is a flexible model in that different plans cause different sets of global transactions to be executed. It is reactive in that it can automatically replan when some change in the multidatabase invalidates the current plan. We give an underlying theory about correctness for atomic multidatabase transactions (which are the basic building blocks for Interactions), and for Interactions both independently and in situations where it must react to some change in the multidatabase. We provide scheduling and synchronization algorithms that ensure both that Interactions get executed correctly and that changes as little completed work done by the Interaction as possible given the different changes in the multidatabase.

The second theme of this thesis is a system design and implementation of a multidatabase that supports Interactions. We define a language, TaSL, that can be used to specify Interactions. We also describe the basic system design of our multidatabase system, Mongrel. Mongrel has been used to test the feasibility and practicality of Interactions as a multidatabase transaction model. Novel functions of the Mongrel system include an ability to check the multidatabase for specific changes that impact running Interactions. It also provides the ability of each local database in the multidatabase to define its interface to the multidatabase, and to use this interface to automatically generate semantic undo steps in the local database when needed (e.g. in backing out of some invalid plan).

(complete text in pdf or gzipped postscript)