Logics for belief base updating

Herzig, Andreas


In the domain of knowledge bases, it is usually considered that a database comes equiped with two functions, a query-answering function `ASK' and an update function `TELL'. Questions such as `ASK(light-on)' are answered ``yes'' or ``no'', according to whether `light-on' logically from the base or not. `TELL(light-on)' means that `light-on' is a new piece of information which the database should take into account. This is a much fuzzier requirement than that for ASK, which is far more difficult to implement both from a logical and a computational point of view.

A somewhat easier case is when `light-on' is already in the database (or follows from it) and there is no need to act. The picture gets more complex if light-on does not follow from the current database, or worse if it contradicts the database. In early approaches it had been considered that the new information is systematically rejected in this case. This is clearly unsatisfactory. Other approaches such as the introduction of so-called `null values' in relational databases turned out to be problematic as well.

Several authors coming from the database field such as Winslett, Katsuno, Mendelzon, Satoh and Grahne have linked the problematics of updating to that of belief change as studied by philosophers in the field of formal epistemology. In that field, Alchourròn, Gärdenfors and Makinson (AGM) had given in the 80ies a set of rationality postulates that every reasonable belief revision operation should satisfy, and had proved characterization theorems.

It has been brought to the fore that there is a fundamental semantical difference between update operations and AGM-revision operations. In particular updates are markedly more liberal in the case where the new information is contingent (neither contradicts nor follows from the current database). Moreover, updates fit better with counterfactual conditionals, as pointed out by Grahne and recently Ryan and Schobbens. Katsuno and Mendelzon (KM) have paralleled AGM and have characterized what we shall call KM-updates by a set of postulates. As well, such interdisciplinary activity has stimulated research on theoretical complexity and the practical implementability of change operations.

In this chapter we mainly concentreate on such interdisciplinary interactions. We shall give formal accounts of update operations in terms of logical systems that have been proposed for conditionals. In particular we recast KM-updates as a particular logic of update and conditional operators.

These systems give us the abstract properties of update operations w.r.t. the logical and metalogical operators of classical logic. Such abstract update operations being satisfactory from the philosophical point of view, they do not give us explicit constructions such as algorithms or procedures, which is what people in database theory and artificial intelligence are interested in. Worse, the class of update operations authorized by these logical systems is much too broad from a database practitioner's point of view. It contains e.g. the trivial update operation which as soon as the new information does not follow from the database only keeps the former and destroys the latter.

Ideally there should be only one update operation: the right one. Does such an operation exist? Sometimes it is argued that the choice of the update operation depends on the application we have in mind. Nevertheless, there might be a unique basic update operation which could be extended and adapted to particular applications. Anyway, this makes us turn to concrete update operations: we start from Winslett's so-called Possible Models Approach (PMA), which is the best example of a concrete update operation (which is moreover unique). We construct the corresponding conditional logic and study its properties. We review critiques of the approach that have been made in the literature, and discuss solutions that have been proposed.

Get Postscript (gzipped)

Get pdf


  author = 	 "Herzig, Andreas",
  title = 	 "Logics for belief base updating",
  booktitle = 	 "Handbook of defeasible reasoning and uncertainty management",
  publisher = 	 "Kluwer Academic Publishers",
  year = 	 1998,
  editor = 	 "Dubois, Didier and Gabbay, Dov and Prade, Henri and Smets, Philippe",
  volume = 	 "3 - Belief Change",
  pages = 	 "189--231"