A Modal Temporal Logic for Reasoning about Change

A Modal Temporal Logic for Reasoning about Change Eric Mays Department of Computer and Information Science Moore School of Electrical Engineerlng/D2 University of Pennsylvania Philadelphia, PA 19104 ABSTRACT We examine several behaviors for query systems that become possible with the ability to represent and reason about change in data bases: queries about possible futures, queries about alternative histories, and offers of monitors as responses to queries. A modal temporal logic is developed for this purpose. A completion axiom for history is given and modelling strategies are given by example. I INTRODUCTION In this paper we present a modal temporal logic that has been developed for reasoning about change in data bases. The basic motivation is as follows. A data base contains information about the world: as the world changes, so does the data base -- probably maintaining some description of what the world was like before the change took place. Moreover, if the world is constrained In the ways it can change, so is the dat~ base. We are motivated by the benefits to be gained by being able to represent those constraints and use them to reason about the possible states of a data base. It is generally accepted that a natural language query system often needs to provide more than just the literal answer to a question. For example, [Kaplan 82I presents methods for correcting a questionerls misconceptions (as reflected in a query) about the contents of a data base, as well as providing additional information in suvport of the literal answer to a query, By enriching the data base model, Kaplan's work on correcting misconceptions was extended in [Mays 801 to distinquish between misconceptions about data base structure and data base contents. In either case, however, the model was a static one. By incorporating a model of the data base in which a dynamic view is allowed, answers to questions can include an offer to monitor for some condition which might possibly occur in the future. The following is an example: U: "Is the Kitty Hawk in Norfolk?" S: "No, shall I let you know when she is?" IThJs work is partially supported by a grant from the Natlonal Science Foundation, NSF-MCS 81-07290. But just having a dynamic view is not adequate, it is necessary--r-y--~at the dynamic view correspond to the possible evolution of the world that is modelled. Otherwise, behaviors such as the following might arise: U: "Is New York less than 50 miles from Philadelphia?" S: "No, shall I let you know when it is?" An offer of a monitor is said to be competent only if the conditlon to be monitored can possibly occur. Thus, in the latter example the offer is not competent, while in the former it is. This paper is concerned with developing a lo~ic for reasoning about change in data bases, and assessing the impact of that capability on the behavior of question answering systems. The general area of extended interaction in data base systems is discussed in [WJMM 831. …

Content truncated to 500 words