Skip Navigation


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
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by De Giacomo, G.
Right arrow Articles by Rosati, R.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

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

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

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.

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 Formula may not be expressible by ABoxes in Formula. In particular, we show that this is true for DL-LiteFormula, a tractable DL that is oriented towards data-intensive applications. To deal with this problem, we first introduce DL-LiteFormula, a DL that minimally extends DL-LiteFormula 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 Formula of instance-level update and erasure, and exploit the algorithm for instance-level update for DL-LiteFormula to get polynomial algorithms for approximated instance-level update and erasure for DL-LiteFormula. These results confirm the nice computational properties of DL-LiteFormula for data intensive applications, even where information about instances is not only read, but also written.

Keywords: Description Logic; ontologies; update; erasure



References

  1. Acciarri A, Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Palmieri M, Rosati R. QUONTO: Querying ontologies. (2005) Pittsburgh, Pennsylvania,USA. 1670–1671. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005).
  2. Alchourrón CE, Gärdenfors P, Makinson D. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic (1985) 50:510–530.[CrossRef][Web of Science]
  3. Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider PF, eds. The Description Logic Handbook: Theory, Implementation and Applications (2003) Cambridge, UK: Cambridge University Press.
  4. Baader F, Horrocks I, Sattler U. Description logics as ontology languages for the semantic web. (2005) Saarbrücken, Germany: Springer. 228–248. In Mechanizing Mathematical Reasoning: Essays in Honor of Jrg Siekmann on the Occasion of his 60th Birthday, volume 2605 of Lecture Notes in Artificial Intelligence.
  5. Baader F, Lutz C, Milicic M, Sattler U, Wolter F. Integrating description logics and action formalisms: first results. (2005) Pittsburgh, Pennsylvania, USA. 572–577. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005).
  6. Bancilhon F, Spyratos N. Update semantics of relational views. ACM Transactions on Database Systems (1981) 6:557–575.[CrossRef][Web of Science]
  7. Berners-Lee T, Hendler J, Lassila O. The semantic web. Scientific American (2001) 284:34–43.[Web of Science][Medline]
  8. Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. DL-Lite: tractable description logics for ontologies. (2005) Pittsburgh, Pennsylvania, USA. 602–607. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005).
  9. Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. Data complexity of query answering in description logics. (2006) Lake District, UK. 260–270. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2006).
  10. Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. Tractable reasoning and efficient query answering in description logics: the DL-Lite family. Journal of Automated Reasoning (2007) 39:385–429.[CrossRef][Web of Science]
  11. De Giacomo G, Lenzerini M, Poggi A, Rosati R. On the update of description logic ontologies at the instance level. (2006) Boston, MA, USA. 1272–1276. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI 2006).
  12. De Giacomo G, Lenzerini M, Poggi A, Rosati R. On the approximation of instance level update and erasure in description logics. (2007) Vancouver, Canada. 403–408. In Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI 2007).
  13. Eiter T, Gottlob G. On the complexity of propositional knowledge base revision, updates and counterfactuals. Artificial Intelligence (1992) 57:227–270.[CrossRef][Web of Science]
  14. Flouris G, Plexousakis D, Antoniou G. On applying the AGM theory to DLs and OWL. (2005) Galway, Ireland. 216–231. In Proceedings of the 4th International Semantic Web Conference (ISWC 2005).
  15. Flouris G, Plexousakis D, Antoniou G. Aclassification of ontology change. In: Proceedings of the 3rd Italian Semantic Web Workshop: Semantic Web Applications and Perspectives (SWAP 2006) (2006) Italy: Pisa.
  16. Flouris G, Plexousakis D, Antoniou G. Evolving ontology evolution. (2006) Czech Republic: Merin. 14–29. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2006).
  17. Gutiérrez C, Hurtado C, Vaisman A. The meaning of erasing in RDF under the Katsuno-Mendelzon approach. In: Proceedings of the 9th International Workshop on the Web and Databases (WebDB 2006) (2006) Chicago, Illinois, USA.
  18. Haarslev V, Möller R. RACERsystem description. (2001) Springer, Siena, Italy. 701–705. In Proceedings of the International Joint Conference on Automated Reasoning (IJCAR 2001). Vol. 2083 of Lecture Notes in Artificial Intelligence.
  19. Haase P, Stojanovic L. Consistent evolution of owl ontologies. (2005) Heraklion, Crete, Greece. 182–197. Proceedings of the 2nd European Semantic Web Conference (ESWC 2005).
  20. Halaschek-Wiener C, Parsia B, Sirin E, Kalyanpur A. Description logic reasoning for dynamic aboxes. (2006) Windermere, Lake District, UK. In Proceedings of the 2006 Description Logic Workshop (DL 2006). Vol. 189 of CEUR Electronic Workshop Proceedingshttp://ceur-ws.org/Vol-189/.
  21. Herzig A, Rifi O. Propositional belief update and minimal change. Artificial Intelligence (1999) 115:107–138.[CrossRef][Web of Science]
  22. Horrocks I. The FaCTsystem. (1998) Springer, Oisterwijk, The Netherlands. 307–312. In Proceedings of the 7th International Conference onAutomated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX’98). H. de Swart, ed. Vol. 1397 of Lecture Notes in Artificial Intelligence.
  23. Katsuno H, Mendelzon A. On the difference between updating a knowledge base and revising it. (1991) Cambridge, Massachusetts, USA. 387–394. In Proceedings of the 2nd International Conference on the Principles of Knowledge Representation and Reasoning (KR'91).
  24. Lenzerini M. Data integration: a theoretical perspective. (2002) Madison,Wisconsin, USA. 233–246. In Proceedings of the 21st ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS 2002).
  25. Levesque HJ, Lakemeyer G. The Logic of Knowledge Bases (2001) Cambridge, Massachusetts, USA: The MIT Press.
  26. Liu H, Lutz C, Milicic M, Wolter F. Updating description logic ABoxes. (2006) UK: Lake District. 46–56. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2006).
  27. Meyer T, Lee K, Booth R. Knowledge integration for description logics. (2005) Pittsburgh, Pennsylvania, USA. 645–650. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005).
  28. Poggi A. Structured and Semi-Structured Data Integration (2006) Dipartimento di Informatica e Sistemistica, Università di Roma ‘La Sapienza’. PhD thesis.
  29. Poggi A, Lembo D, Calvanese D, De Giacomo G, Lenzerini M, Rosati R. Linking data to ontologies. Journal on Data Semantics (2008) X:133–173.
  30. Reiter R. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems (2001) New York, NY, USA: The MIT Press.
  31. Schaerf M, Cadoli M. Tractable reasoning via approximation. Artificial Intelligence (1995) 74:249–310.[CrossRef][Web of Science]
  32. Scherl RB, Levesque HJ. Knowledge, action, and the frame problem. Artificial Intelligence (2003) 144:1–39.[CrossRef][Web of Science]
  33. Sirin E, Parsia B. Pellet: an OWL DL reasoner. In: Proceedings of the 2004 Description Logic Workshop (DL 2004). Vol. 104 of CEUR Electronic Workshop Proceedings (2004) Whistler, BC, Canada. http://ceur-ws.org/Vol-104/.
  34. Winslett M. Reasoning about action using a possible models approach. (1988) Saint Paul: Minnesota, USA. 89–93. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI’88).
  35. Winslett M. Updating Logical Databases (1990) New York, NY, USA: Cambridge University Press.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by De Giacomo, G.
Right arrow Articles by Rosati, R.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?