On the Approximation of Instance Level Update and Erasure in Description Logics

Giuseppe De Giacomo, Maurizio Lenzerini, Antonella Poggi, Riccardo Rosati

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 L 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_{\cal 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-Lite_{\cal F}$ are retained in dealing with the evolution of the ABox.

Subjects: 11.1 Description Logics; 11. Knowledge Representation

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.