language: en

How to Progress a Database (and Why) I. Logical Foundations

Fangzhen Lin and Ray Reiter
Department of Computer Science University of Toronto
Toronto, Canada M5S 1A4
email: fl@ai.toronto.edu reiter@ai.toronto.edu

Abstract One way to think about STRIPS is as a mapping from databases to databases, in the following sense: Suppose we want to know what the world would be like if an action, represented by the STRIPS operator ff, were done in some world, represented by the STRIPS database D 0 . To find out, simply perform the operator ff on D 0 (by applying ff's elementary add and delete revision operators to D 0 ). We describe this process as progressing the database D 0 in response to the action ff. In this paper, we consider the general problem of progressing an initial database in response to a given sequence of actions. We appeal to the situation calculus and an axiomatization of actions which addresses the frame problem (Reiter [13], Lin and Reiter [8]). This setting is considerably more general than STRIPS. Our results concerning progression are mixed. The (surprising) bad news is that, in general, to characterize a progressed database we must appeal to second order logic. The good news is that there are many useful special cases for which we can compute the progressed database in first order logic; not only that, we can do so efficiently.

1 INTRODUCTION