On Instance-Level Update and Erasure in Description Logic Ontologies

Giuseppe De Giacomo, Maurizio Lenzerini, Antonella Poggi, Riccardo Rosati.
Journal of Logic and Computation, volume 19, number 5, pages 745-770, 2009.

 

Abstract:

A Description Logic ontology is constituted by two components, a TBox that expresses general knowledge about the concepts and their relationships, and an ABox that describes the properties of individuals that are instances of concepts. We address the problem of how to deal with changes to a Description Logic ontology, when these changes affect only the ABox, i.e., when the TBox is considered invariant. We consider two basic changes, namely instance-level update and instance-level erasure, roughly corresponding to the addition and the deletion of a set of facts involving individuals. We characterize the semantics of instance-level update and erasure on the basis of the approaches proposed by Winslett and by Katsuno and Mendelzon. Interestingly, Description Logics are typically not closed with respect to instance-level update and erasure, in the sense that the set of models corresponding to the application of any of these operations to a knowledge base in a Description Logic L may not be expressible by ABoxes in L. In particular, we show that this is true for DL-Lite_F, a tractable DL that is oriented towards data intensive applications. To deal with this problem, we first introduce DL-Lite_FS, a DL that minimally extends DL-Lite_F and is closed with respect to instance-level update, and present a polynomial algorithm for computing instance-level update in this logic. Then, we provide a principled notion of best approximation with respect to a fixed language L of instance-level update and erasure, and exploit the algorithm for instance-level update for DL-Lite_FS, to get polynomial algorithms for approximated instance-level update and erasure for DL-Lite_F. These results confirm the nice computational properties of DL-Lite_F for data intensive applications, even where information about instances is not only read, but also written.

Bibtex entry:

@String{JLC = "Journal of Logic and Computation"}

@Article{DLPR09,
author = "De Giacomo, Giuseppe and Maurizio Lenzerini and Antonella Poggi and Riccardo Rosati",
title = "On Instance-Level Update and Erasure in Description Logic Ontologies",
journal = JLC,
volume = 19,
number = 5,
pages = "745--770",
year = 2009,
}

Link to electronic version of published paper