Asking About Possibilities - Revision and Update Semantics for Subjunctive Queries, Extended Version

Wolfgang Nejdl and Markus Banagl

Abstract

The AGM rationality postulates for belief revision play an important role in the formalization of subjunctive queries over knowledge bases. However, the well known triviality results by Gärdenfors in connection with the Ramsey Test make defining a query semantics corresponding to these rationality postulates a difficult task. While existing approaches avoid the triviality results by restricting the postulates in certain ways, we show that an exact translation into a query semantics is possible. The resulting semantics allows for the first time the integration of subjunctive queries evaluated according to a revision semantics corresponding to the AGM rationality postulates with an update operator corresponding to the update semantics formalized by Katsuno, Mendelzon and Grahne. The query semantics extends usual conditional implication by defining the concepts of possibility and necessity relative to a knowledge base. Additionally, based on this semantics, we present a formal account of splitting a knowledge base into two parts. We propose a specific revision function and show that this function is optimal in the sense, that after revision as few conditional consequences as possible are changed.

Keywords: Logics of revision and update, Gärdenfors triviality results, AGM postulates, iterated revision

The full paper is available as a postscript file .