On the approximation of instance level update and erasure in description logics

A Description Logics knowledge base is constituted by two components, called TBox and ABox, where the former expresses general knowledge about the concepts and their relationships, and the latter describes the properties of instances of concepts. We address the problem of how to deal with changes to a Description Logic knowledge base, when these changes affect only its ABox. We consider two types of changes, namely update and erasure, and we characterize the semantics of these operations on the basis of the approaches proposed by Winslett and by Katsuno and Mendelzon. It is well known that, in general. Description Logics are not closed with respect to updates, in the sense that the set of models corresponding to an update applied to a knowledge base in a Description Logic ℒ may not be expressible by ABoxes in L. We show that this is true also for erasure. To deal with this problem. we introduce the notion of best approximation of an update (erasure) in a DL L, with the goal of characterizing the L ABoxes that capture the update (erasure) at best. We then focus on DL-Lite?F. a tractable Description Logic, and present polynomial algorithms for computing the best approximation of updates and erasures in this logic, which shows that the nice computational properties of DL-LiteF are retained in dealing with the evolution of the ABox. Copyright © 2007. Association for the Advancement of Artificial Intelligence (www.aaai.org), All rights reserved.