Action Theories in Temporal Databases

Reasoning about action and change has been one of the main research themes of the knowledge representation and planning communities of the last 15 years. Action theories providing an axiomatic basis for managing change are applicable to a wide area of disciplines including software engineering, (cognitive) robotics and data/knowledge base systems. In this thesis, we first review action theories proposed for reasoning about the dynamics of database systems. We examine how these theories deal with the three infamous problems associated with this area, namely: (a) the frame problem, which refers to the identification of predicates or functions that remain unchanged as a result of action execution, (b) the ramification problem, which refers to determining the indirect effects of actions, and (c) the qualification problem, which refers to determining the preconditions which must hold prior to the execution of an action. We briefly describe the solutions which have been proposed for these problems and position these problems in a temporal database context. We also introduce an abstract solution for the frame and qualification problems in temporal databases based on the language of situation calculus. In this thesis we concentrate on the ramification problem. The ramification problem is of great importance to database systems. The users and designers may not know exactly all the indirect effects of their transactions and such indirect effects mays violate the integrity constraints. A solution to the ramification problem permits the designers to discover errors in their design and to correct them. All the solutions to the ramification problem in conventional databases are based on the idea of the persistence of fluents. This means that nothing changes until an action takes place. The above solutions cannot produce automatically the non persistent effects. If such effects exists, they have to be described manually. This is very difficult and impractical in the large databases with complex transactions. In temporal databases the predicate and function values can change as time progresses without any action taking place. Thus the above solutions cannot solve the ramification problem in temporal databases. We examine the ramification problem in the following cases: (a) sequential action execution both for instanteous actions and actions with duration when an action may have effects only in the future, (b) concurrent action execution both for instanteous actions and actions with duration when an action may have effects only in the future and (c) sequential action (instanteous) execution when an action may change beliefs about the past. The problem in the last case is very complex with many philosophic aspects. For each case, we propose a solution which permits to the designers to determine the effects of their transaction, to discover the errors and to correct them