Abstract
We study the problem of evolution for Knowledge Bases (KBs) expressed in Description Logics (DLs) of the DL − Lite family. DL − Lite is at the basis of OWL 2 QL, one of the tractable fragments of OWL 2, the recently proposed revision of the Web Ontology Language. We propose some fundamental principles that KB evolution should respect. We review known model and formula-based approaches for evolution of propositional theories. We exhibit limitations of a number of model-based approaches: besides the fact that they are either not expressible in DL − Lite or hard to compute, they intrinsically ignore the structural properties of KBs, which leads to undesired properties of KBs resulting from such an evolution. We also examine proposals on update and revision of DL KBs that adopt the model-based approaches and discuss their drawbacks. We show that known formula-based approaches are also not appropriate for DL − Lite evolution, either due to high complexity of computation, or because the result of such an action of evolution is not expressible in DL − Lite. Building upon the insights gained, we propose two novel formula-based approaches that respect our principles and for which evolution is expressible in DL − Lite. For our approaches we also developed polynomial time algorithms to compute evolution of DL − Lite KBs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Borgida, A., Brachman, R.J.: Conceptual modeling with description logics. In: [13], ch.10, pp. 349–372
Flouris, G., Manakanatas, D., Kondylakis, H., Plexousakis, D., Antoniou, G.: Ontology change: Classification and survey. Knowledge Engineering Review 23(2), 117–152 (2008)
Abiteboul, S., Grahne, G.: Update semantics for incomplete databases. In: Proc. of VLDB 1985 (1985)
Katsuno, H., Mendelzon, A.: On the difference between updating a knowledge base and revising it. In: Proc. of KR 1991, pp. 387–394 (1991)
Eiter, T., Gottlob, G.: On the complexity of propositional knowledge base revision, updates and counterfactuals. Artificial Intelligence 57, 227–270 (1992)
Winslett, M.: Updating Logical Databases. Cambridge University Press, Cambridge (1990)
Flouris, G.: On belief change in ontology evolution. AI Communications 19(4) (2006)
Qi, G., Du, J.: Model-based revision operators for terminologies in description logics. In: Proc. of IJCAI 2009, pp. 891–897 (2009)
Peters, R.J., Özsu, M.T.: An axiomatic model of dynamic schema evolution in objectbase systems. ACM Trans. on Database Systems 22(1), 75–114 (1997)
De Giacomo, G., Lenzerini, M., Poggi, A., Rosati, R.: On instance-level update and erasure in description logic ontologies. J. of Logic and Computation, Special Issue on Ontology Dynamics 19(5), 745–770 (2009)
Liu, H., Lutz, C., Milicic, M., Wolter, F.: Updating description logic ABoxes. In: Proc. of KR 2006, pp. 46–56 (2006)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3), 385–429 (2007)
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge (2003)
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. of Artificial Intelligence Research 36, 1–69 (2009)
Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. on Data Semantics X, 133–173 (2008)
Ginsberg, M.L., Smith, D.E.: Reasoning about action I: A possible worlds approach. Technical Report KSL-86-65, Knowledge Systems, AI Laboratory (1987)
Forbus, K.D.: Introducing actions into qualitative simulation. In: Proc. of IJCAI 1989 (1989)
Borgida, A.: Language features for flexible handling of exceptions in information systems. ACM Trans. on Database Systems 10(4), 565–603 (1985)
Dalal, M.: Investigations into a theory of knowledge base revision. In: Proc. of AAAI 1988, pp. 475–479 (1988)
Calvanese, D., Kharlamov, E., Nutt, W.: A proof theory for DL-Lite. In: Proc. of DL 2007. CEUR, vol. 250, pp. 235–242 (2007), ceur-ws.org
De Giacomo, G., Lenzerini, M., Poggi, A., Rosati, R.: On the update of description logic ontologies at the instance level. In: Proc. of AAAI 2006, pp. 1271–1276 (2006)
Zheleznyakov, D., Calvanese, D., Kharlamov, E., Nutt, W.: Updating TBoxes in DL-Lite. In: Proc. of DL 2010. CEUR, vol. 573, pp. 102–113 (2010), ceur-ws.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calvanese, D., Kharlamov, E., Nutt, W., Zheleznyakov, D. (2010). Evolution of DL − Lite Knowledge Bases. In: Patel-Schneider, P.F., et al. The Semantic Web – ISWC 2010. ISWC 2010. Lecture Notes in Computer Science, vol 6496. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17746-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-17746-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17745-3
Online ISBN: 978-3-642-17746-0
eBook Packages: Computer ScienceComputer Science (R0)