Journal of Logic and Computation Advance Access originally published online on August 6, 2008
Journal of Logic and Computation 2009 19(5):745-770; doi:10.1093/logcom/exn051
| ||||||||||||||||||||||||||||||||||||||||||||||||||
This article appears in the following Journal of Logic and Computation issue: Special Issue: Recent Advances in Ontology Dynamics [View the issue table of contents]
Original Articles |
On Instance-level Update and Erasure in Description Logic Ontologies
Dipartimento di Informatica e Sistemistica ‘Antonio Ruberti’, Sapienza Università di Roma, Via Ariosto 25, 00185 Roma, Italy.
E-mail: lastname{at}dis.uniroma1.it
Received 11 November 2007.
 |
Abstract |
|---|
A Description Logic (DL) 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 DL 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, DLs 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 DL 
may not be expressible by ABoxes in . In particular, we show that this is true for DL-Lite
, a tractable DL that is oriented towards data-intensive applications. To deal with this problem, we first introduce DL-Lite
, a DL that minimally extends DL-Lite 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 of instance-level update and erasure, and exploit the algorithm for instance-level update for DL-Lite to get polynomial algorithms for approximated instance-level update and erasure for DL-Lite. These results confirm the nice computational properties of DL-Lite for data intensive applications, even where information about instances is not only read, but also written.
Keywords: Description Logic; ontologies; update; erasure