Article

Evolution of DL-lite knowledge bases

Authors:

Diego Calvanese,

Evgeny Kharlamov,

Dmitriy ZheleznyakovAuthors Info & Claims

ISWC'10: Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I

Pages 112 - 128

Published: 07 November 2010 Publication History

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.

References

[1]

Borgida, A., Brachman, R.J.: Conceptual modeling with description logics. In: {13}, ch.10, pp. 349-372

Digital Library

[2]

Flouris, G., Manakanatas, D., Kondylakis, H., Plexousakis, D., Antoniou, G.: Ontology change: Classification and survey. Knowledge Engineering Review 23(2), 117-152 (2008)

Digital Library

[3]

Abiteboul, S., Grahne, G.: Update semantics for incomplete databases. In: Proc. of VLDB 1985 (1985)

Digital Library

[4]

Katsuno, H., Mendelzon, A.: On the difference between updating a knowledge base and revising it. In: Proc. of KR 1991, pp. 387-394 (1991)

Digital Library

[5]

Eiter, T., Gottlob, G.: On the complexity of propositional knowledge base revision, updates and counterfactuals. Artificial Intelligence 57, 227-270 (1992)

Digital Library

[6]

Winslett, M.: Updating Logical Databases. Cambridge University Press, Cambridge (1990)

Digital Library

[7]

Flouris, G.: On belief change in ontology evolution. AI Communications 19(4) (2006)

Digital Library

[8]

Qi, G., Du, J.: Model-based revision operators for terminologies in description logics. In: Proc. of IJCAI 2009, pp. 891-897 (2009)

Digital Library

[9]

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)

Digital Library

[10]

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)

Digital Library

[11]

Liu, H., Lutz, C., Milicic, M., Wolter, F.: Updating description logic ABoxes. In: Proc. of KR 2006, pp. 46-56 (2006)

[12]

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)

Digital Library

[13]

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)

Digital Library

[14]

Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. of Artificial Intelligence Research 36, 1-69 (2009)

Digital Library

[15]

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)

Digital Library

[16]

Ginsberg, M.L., Smith, D.E.: Reasoning about action I: A possible worlds approach. Technical Report KSL-86-65, Knowledge Systems, AI Laboratory (1987)

[17]

Forbus, K.D.: Introducing actions into qualitative simulation. In: Proc. of IJCAI 1989 (1989)

Digital Library

[18]

Borgida, A.: Language features for flexible handling of exceptions in information systems. ACM Trans. on Database Systems 10(4), 565-603 (1985)

Digital Library

[19]

Dalal, M.: Investigations into a theory of knowledge base revision. In: Proc. of AAAI 1988, pp. 475-479 (1988)

[20]

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

[21]

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)

Digital Library

[22]

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

Cited By

De Giacomo GOriol XRosati RSavo D(2021)Instance-Level Update in DL-Lite Ontologies through First-Order RewritingJournal of Artificial Intelligence Research10.1613/jair.1.1241470(1335-1371)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12414
Zheleznyakov DKharlamov EHorrocks ISingh SMarkovitch S(2017)Trust-sensitive evolution of DL-Lite knowledge basesProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298424(1266-1272)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298239.3298424
Benferhat SBouraoui ZPapini OWürbel E(2017)Prioritized assertional-based removed sets revision of DL-Lite belief basesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9494-279:1-3(45-75)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10472-015-9494-2
Show More Cited By

Index Terms

Evolution of DL-lite knowledge bases
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Logic

Recommendations

Adding DL-Lite TBoxes to Proper Knowledge Bases
The Semantic Web - ISWC 2015
Abstract
Levesque’s proper knowledge bases (proper KBs) correspond to infinite sets of ground positive and negative facts, with the notable property that for FOL formulas in a certain normal form, which includes conjunctive queries and positive queries ...
On expansion and contraction of DL-Lite knowledge bases
Abstract
Knowledge bases (KBs) are not static entities: new information constantly appears and some of the previous knowledge becomes obsolete. In order to reflect this evolution of knowledge, KBs should be expanded with the new knowledge and ...
Capturing instance level ontology evolution for DL-lite
ISWC'11: Proceedings of the 10th international conference on The semantic web - Volume Part I

Evolution of Knowledge Bases (KBs) expressed in Description Logics (DLs) proved its importance. Recent studies of the topic mostly focussed on model-based approaches (MBAs), where an evolution (of a KB) results in a set of models. For KBs expressed in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISWC'10: Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I

November 2010

829 pages

ISBN:364217745X

Editors:
Peter F. Patel-Schneider
Bell Labs Research, Murray Hill, NJ
,
Yue Pan
IBM Research Labs, Beijing, China
,
Pascal Hitzler
Wright State University, Dayton, OH
,
Peter Mika
Yahoo! Research, Barcelona, Spain
,
Lei Zhang
IBM Research Labs, Shanghai, China

Sponsors

Elsevier
Ontotext
Artificial Intelligence Journal
Yahoo!
Saltlux

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 November 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

De Giacomo GOriol XRosati RSavo D(2021)Instance-Level Update in DL-Lite Ontologies through First-Order RewritingJournal of Artificial Intelligence Research10.1613/jair.1.1241470(1335-1371)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12414
Zheleznyakov DKharlamov EHorrocks ISingh SMarkovitch S(2017)Trust-sensitive evolution of DL-Lite knowledge basesProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298424(1266-1272)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298239.3298424
Benferhat SBouraoui ZPapini OWürbel E(2017)Prioritized assertional-based removed sets revision of DL-Lite belief basesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9494-279:1-3(45-75)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10472-015-9494-2
Benferhat SBouraoui ZCroitoru MPapini OTabia K(2016)Non-objection inference for inconsistency-tolerant query answeringProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3061053.3061134(3684-3690)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3061053.3061134
Bienvenu MBourgaux CGoasdoué F(2016)Query-driven repairing of inconsistent DL-Lite knowledge basesProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060754(957-964)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060754
Ahmeti ACalvanese DPolleres ASavenkov V(2016)Handling Inconsistencies Due to Class Disjointness in SPARQL UpdatesProceedings of the 13th International Conference on The Semantic Web. Latest Advances and New Domains - Volume 967810.1007/978-3-319-34129-3_24(387-404)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.1007/978-3-319-34129-3_24
Kaminski TKnorr MLeite J(2015)Efficient paraconsistent reasoning with ontologies and rulesProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832681(3098-3105)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832681
Calvanese DMontali MSantoso A(2015)Verification of generalized inconsistency-aware knowledge and action basesProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832647(2847-2853)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832647
Wang ZWang KTopor R(2015)DL-Lite Ontology Revision Based on An Alternative Semantic CharacterizationACM Transactions on Computational Logic10.1145/278675916:4(1-37)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2786759
Felfernig AReiterer SStettinger MTiihonen JSchmid KHaugen ØMüller J(2015)Towards Understanding Cognitive Aspects of Configuration Knowledge FormalizationProceedings of the 9th International Workshop on Variability Modelling of Software-Intensive Systems10.1145/2701319.2701327(117-123)Online publication date: 21-Jan-2015
https://dl.acm.org/doi/10.1145/2701319.2701327
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents