UPDATES AND SUBJUNCTIVE QUERIES

A subjunctive query of the form phi > psi, means ''if phi were true in the knowledgebase, would psi also necessarily be true?'' We propose t he following semantics for subjunctive queries: phi > psi, will hold i n the current knowledgebase T if psi holds in the result of updating T with phi. This is known as the Ramsey test in philosophy. We adapt th e model checking approach of Halpern and Vardi: A knowledgebase is a f inite set of finite sets of positive facts interpreted in a closed wor ld setting. We then use Winslett's possible models approach to give se mantics to knowledgebase updates, and we introduce a query language wh ich is essentially propositional logic, augmented with a subjunctive c onditional that has an intensional interpretation in our model. We sho w that query answering and update can be performed in time polynomial in the size of the knowledgebase. However, query equivalence is shown to be complete in polynomial space, and this is also the complexity of query answering as a function of query size. We give a sound axiomati zation of query equivalence and show that the update operator satisfie s the postulates for updates adapted by Katsuno and Mendelzon from the Alchourron-Gardenfors-Makinson belief revision postulates. (C) 1995 A cademic Press, Inc.