Abstract
Evolution of Knowledge Bases (KBs) expressed in Description Logics (DLs) has gained a lot of attention lately. Recent studies on the topic have mostly focused on so-called model-based approaches (MBAs), where the evolution of a KB results in a set of models. For KBs expressed in tractable DLs, such as those of the extit{DL-Lite} family, which we consider here, it has been shown that one faces inexpressibility of evolution, i.e., the result of evolution of a extit{DL-Lite} KB in general cannot be expressed in extit{DL-Lite}, in other words, extit{DL-Lite} is not closed under evolution. What is still missing in these studies is a thorough understanding of various important aspects of the evolution problem for extit{DL-Lite} KBs: Which fragments of extit{DL-Lite} are closed under evolution? What causes the inexpressibility? Can one approximate evolution in extit{DL-Lite}, and if yes, how? This work provides some understanding of these issues for an important class of MBAs, which cover the cases of both update and revision. We describe what causes inexpressibility, and we propose techniques (based on what we call prototypes) that help to approximate evolution under the well-known approach by Winslett, which is inexpressible in extit{DL-Lite}. We also identify a fragment of extit{DL-Lite} closed under evolution, and for this fragment we provide polynomial-time algorithms to compute or approximate evolution results for various MBAs.