Update operations: a review

Herzig, Andreas and Rifi, Omar

Abstract:

In this paper we review several knowledge base update operations that have recently been proposed in order to handle disjunctive updates and updates under integrity constraints. Updating with disjunctive information is problematic for minimal change semantics, in particular for Winslett's Possible Models Approach (PMA). Zhang and Foo have recently defined the MCD semantics to overcome this drawback. In this paper we show that the MCD is still problematic, and propose a correction. Then we address a second important problem plaguing the PMA and its variations, viz. the handling of integrity constraints. We investigate a dependence-based semantics, which Liberatore has shown to be coNP-complete. We give a simple automated deduction method, and show that integrity constraints as well as disjunctive updates are treated correctly in that semantics, and discuss the Katsuno-Mendelzon postulates.

PostScript

Bibtex-entry:



@InProceedings{HeRi-ECAI98,
  author = 	 "Herzig, Andreas and Rifi, Omar", 
  title = 	 "Update operations: a review",
  booktitle = 	 "Proc. Eur. Conf. on Artificial Intelligence (ECAI'98)",
  month = 	 aug, 
  pages = 	 "13--17",
  publisher = 	 "Wiley",
  year =  	 "1998"
}

http://www.irit.fr/~Andreas.Herzig