article

Incremental Classification of Description Logics Ontologies

Authors:

Bernardo Cuenca Grau,

Christian Halaschek-Wiener,

Yevgeny Kazakov,

Boontawee SuntisrivarapornAuthors Info & Claims

Journal of Automated Reasoning, Volume 44, Issue 4

Pages 337 - 369

https://doi.org/10.1007/s10817-009-9159-0

Published: 01 April 2010 Publication History

Abstract

The development of ontologies involves continuous but relatively small modifications. However, existing ontology reasoners do not take advantage of the similarities between different versions of an ontology. In this paper, we propose a collection of techniques for incremental reasoning--that is, reasoning that reuses information obtained from previous versions of an ontology. We have applied our results to incremental classification of OWL ontologies and found significant improvement over regular classification time on a set of real-world ontologies.

References

[1]

Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence IJCAI-05. Morgan-Kaufmann, Edinburgh (2005).

[2]

Baader, F., Lutz, C., Suntisrivaraporn, B.: Is tractable reasoning in extensions of the description logic el useful in practice? In: Proceedings of the 2005 International Workshop on Methods for Modalities (M4M-05) (2005).

[3]

Baader, F., Lutz, C., Suntisrivaraporn, B.: CEL--a polynomial-time reasoner for life science ontologies. In: IJCAR 2006, Proceedings of the Third International Joint Conference on Automated Reasoning. Lecture Notes in Computer Science, vol. 4130, pp. 287-291. Springer, New York (2006).

[4]

Baader, F., Lutz, C., Suntisrivaraporn, B.: Efficient reasoning in EL+. In: Proceedings of the 19th International Workshop on Description Logics (DL-06). CEUR Workshop Proceedings, vol. 189 (2006).

[5]

Baader, F., Nutt, W.: Basic description logics. In: Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.) The Description Logic Handbook: Theory, Implementation, and Applications, pp. 43-95. Cambridge University Press, Cambridge (2003).

[6]

Blakeley, J.A., Larson, P.-A., Tompa, F.W.: Efficiently updating materialized views. In: Proc. of SIGMOD '86: ACM SIGMOD International Conference on Management of Data, pp. 61-71 (1986).

[7]

Cuenca Grau, B., Halaschek-Wiener, C., Kazakov, Y.: History matters: incremental ontology reasoning using modules. In: 6th International Semantic Web Conference (ISWC). Lecture Notes in Computer Science, vol. 4825, pp. 183-196. Springer, New York (2007).

[8]

Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Just the right amount: extracting modules from ontologies. In: Proc. of the 16th International World Wide Web Conference (WWW2007) (2007).

[9]

Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: A logical framework for modularity of ontologies. In: Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI- 2007), pp. 298-303. AAAI, Menlo Park (2007).

[10]

Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontologies: theory and practice. J. Artif. Intell. Res. (JAIR) 31, 273-318 (2008).

[11]

Cuenca Grau, B., Horrocks, I., Motik, B., Parsia, B., Patel-Schneider, P., Sattler, U.: OWL 2: the next step for OWL. Journal of Web Semantics 6(4), 309-322 (2008).

Digital Library

[12]

de Kleer, J.: An assumption-based TMS. Artif. Intell. 28(2), 127-162, ISSN 0004-3702 (1986).

Digital Library

[13]

Dong, G., Su, J., Topor, R.W.: Nonrecursive incremental evaluation of datalog queries. Ann. Math. Artif. Intell. 14(2-4) (1995).

[14]

Dong, G., Topor, R.W.: Incremental evaluation of datalog queries. In: Proc. of the 4th Int. Conference on Database Theory (1992).

Digital Library

[15]

Dowling, W., Gallier, J.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 3(1), 267-284 (1984).

[16]

Doyle, J.: A truth maintenance system. In: Readings in Nonmonotonic Reasoning, pp. 259-279 (1987).

Digital Library

[17]

Haarslev, V., Moeller, R.: Racer system description. In: Proceedings of the First International Joint Conference on Automated Reasoning (IJCAR 2001). Lecture Notes in Artificial Intelligence, vol. 2083, pp. 701-705 (2001).

[18]

Haarslev, V., Möller, R.: Incremental query answering for implementing document retrieval services. In: Proc. of DL-2003, pp. 85-94 (2003).

[19]

Halaschek-Wiener, C., Hendler, J.: Toward expressive syndication on the web. In: Proc. of the 16th International World Wide Web Conference (WWW 2007) (2007).

[20]

Halaschek-Wiener, C., Parsia, B., Sirin, E.: Description logic reasoning with syntactic updates. In: Proc. of ODBase2006 (2006).

[21]

Horrocks, I., Patel-Schneider, P.F., van Harmelen, F.: From SHIQ and rdf to owl: the making of a web ontology language. Journal ofWeb Semantics 1(1), 7-26 (2003).

[22]

Hustadt, U., Motik, B., Sattler, U.: Deciding expressive description logics in the framework of resolution. Inf. Comput. 206(5), 579-601 (2008).

Digital Library

[23]

Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of owl dl entailments. In: 6th International Semantic Web Conference. Lecture Notes in Computer Science, vol. 4825, pp. 267-280. Springer, New York (2007).

[24]

Kazakov, Y.: RIQ and SROIQ are harder than SHOIQ. In: Proc. of the Eleventh International Conference on the Principles of Knowledge Representation and Reasoning (KR-2008), pp. 274- 284 (2008).

[25]

Kutz, O., Horrocks, I., Sattler, U.: The even more irresistible SROIQ. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2006), pp. 68-78. AAAI, Lake District (2006).

[26]

Lutz, C., Walther, D., Wolter, F.: Conservative extensions in expressive description logics. In: Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007) (2007).

Digital Library

[27]

Lutz, C., Wolter, F.: Conservative extensions in the lightweight description logic EL. In: Pfenning, F. (ed.) Proceedings of the 21th Conference on Automated Deduction (CADE-21). Lecture Notes in Artificial Intelligence, vol. 4603, pp. 84-99. Springer, New York (2007).

[28]

Motik, B., Cuenca Grau, B., Horrocks, I., Wu, Z., Fokoue, A., Lutz, C. (eds.): OWL 2 web ontology language profiles. W3C Recommendation (2009).

[29]

Motik, B., Patel-Schneider, P.F., Parsia, B. (eds.): OWL 2 web ontology language structural specification and functional-style syntax. W3C Recommendation (2009).

[30]

Motik, B., Shearer, R., Horrocks, I.: Optimized reasoning in description logics using hyper-tableaux. In: Proc. of the 21st Conference on Automated Deduction (CADE-21). LNAI, vol. 4603, pp. 67-83. Springer, Bremen (2007).

[31]

Parsia, B., Halaschek-Wiener, C., Sirin, E.: Towards incremental reasoning through updates in OWL-DL. In: Reasoning on the Web Workshop (2006).

[32]

Parsia, B., Sirin, E., Kalyanpur, A.: Debugging OWL ontologies. In: Proceedings of the 14th International World Wide Web Conference (WWW 2005), pp. 633-640 (2005).

[33]

Patel-Schneider, P., Hayes, P., Horrocks, I.: Web ontology language OWL abstract syntax and semantics. W3C Recommendation (2004).

[34]

Sattler, U., Schneider, T., Zakharyaschev, M.: Which kind of module should i extract? In: Proc. of the 22nd International Workshop on Description Logics (DL 2009). CEUR Workshop Proceedings, vol. 477 (2009).

[35]

Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: Proc. of the 18th International Joint Conference on Artificial Intelligence (IJCAI, 2003). Morgan Kaufmann, San Francisco, pp. 355-362 (2003).

[36]

Schlobach, S., Huang, Z., Cornet, R., van Harmelen, F.: Debugging incoherent terminologies. J. Autom. Reason. 39(3), 317-349 (2007).

Digital Library

[37]

Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: a practical OWL-DL reasoner. Journal of Web Semantics 5(2), 51-53 (2007).

Digital Library

[38]

Stonebraker, M.: Implementation of integrity constraints and views by query modification. In: SIGMOD '75: Proc. of the 1975 ACM SIGMOD International Conference on Management of Data, pp. 65-78. ACM, New York (1975).

Digital Library

[39]

Suntisrivaraporn, B.: Module extraction and incremental classification: a pragmatic approach for ontologies. In: 5th European Semantic Web Conference (ESWC). Lecture Notes in Computer Science, vol. 5021, pp. 230-244. Springer, New York (2008).

[40]

Terry, D.B., Goldberg, D., Nichols, D., Oki, B.M.: Continuous queries over append-only databases. In: Proceedings of the International Conference on Management of Data (1992).

[41]

Tsarkov, D., Horrocks, I.: FaCT++ description logic reasoner: system description. In: Proc. of the Third International Joint Conference on Automated Reasoning (IJCAR 2006). Lecture Notes in Artificial Intelligence, vol. 4130, pp. 292-297. Springer, New York (2006).

Cited By

Zhao HParsia BSattler U(2021)ReAD: AD-Based Modular Ontology ClassificationLogics in Artificial Intelligence10.1007/978-3-030-75775-5_15(210-224)Online publication date: 17-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75775-5_15
Ye YCui XOuyang D(2020)Extracting a justification for OWL ontologies by critical axiomsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-7267-514:4Online publication date: 3-Jan-2020
https://dl.acm.org/doi/10.1007/s11704-019-7267-5
Wang CFeng ZZhang XWang XRao GFu D(2019)ComRFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6397-213:1(139-156)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11704-016-6397-2
Show More Cited By

Incremental Classification of Description Logics Ontologies
1. Computing methodologies
  1. Artificial intelligence
2. Theory of computation

Recommendations

Modularisation of domain ontologies implemented in description logics and related formalisms including OWL
K-CAP '03: Proceedings of the 2nd international conference on Knowledge capture

Modularity is a key requirement for large ontologies in order to achieve re-use, maintainability, and evolution. Mechanisms for 'normalisation' to achieve analogous aims are standard for databases. However, no similar notion of normalisation has yet ...
A semantic metrics suite for evaluating modular ontologies

Ontologies, which are formal representations of knowledge within a domain, can be used for designing and sharing conceptual models of enterprises information for the purpose of enhancing understanding, communication and interoperability. For ...
(Non-)Succinctness of uniform interpolants of general terminologies in the description logic EL

EL is a popular description logic, used as a core formalism in large existing knowledge bases. Uniform interpolants of knowledge bases are of high interest, e.g. in scenarios where a knowledge base is supposed to be partially reused. However, to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Automated Reasoning

Journal of Automated Reasoning Volume 44, Issue 4

April 2010

120 pages

ISSN:0168-7433

Issue’s Table of Contents

Copyright © Copyright © 2010 Springer Science+Business Media B.V.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao HParsia BSattler U(2021)ReAD: AD-Based Modular Ontology ClassificationLogics in Artificial Intelligence10.1007/978-3-030-75775-5_15(210-224)Online publication date: 17-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75775-5_15
Ye YCui XOuyang D(2020)Extracting a justification for OWL ontologies by critical axiomsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-7267-514:4Online publication date: 3-Jan-2020
https://dl.acm.org/doi/10.1007/s11704-019-7267-5
Wang CFeng ZZhang XWang XRao GFu D(2019)ComRFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6397-213:1(139-156)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11704-016-6397-2
Romero AKaminski MGrau BHorrocks I(2016)Module extraction in expressive ontology languages via datalog reasoningJournal of Artificial Intelligence Research10.5555/3013558.301357355:1(499-564)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.5555/3013558.3013573
Romero AKaminski MGrau BHorrocks I(2015)Ontology module extraction via datalog reasoningProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence10.5555/2887007.2887202(1410-1416)Online publication date: 25-Jan-2015
https://dl.acm.org/doi/10.5555/2887007.2887202
Kazakov YKrötzsch MSimančík F(2014)The Incredible ELKJournal of Automated Reasoning10.1007/s10817-013-9296-353:1(1-61)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10817-013-9296-3
Kazakov YKlinov P(2013)The benefits of incremental reasoning in OWL ELProceedings of the 12th International Semantic Web Conference (Posters & Demonstrations Track) - Volume 103510.5555/2874399.2874414(57-60)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.5555/2874399.2874414
Kazakov YKlinov P(2013)Incremental Reasoning in OWL EL without BookkeepingProceedings of the 12th International Semantic Web Conference - Part I10.1007/978-3-642-41335-3_15(232-247)Online publication date: 21-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41335-3_15
Chen JWang PHuang YYen H(2012)Applying Ontology Techniques to Develop a Medication History Search and Alert System in Department of Nuclear MedicineJournal of Medical Systems10.1007/s10916-010-9541-936:2(737-746)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1007/s10916-010-9541-9
Romero AGrau BHorrocks I(2012)MOReProceedings of the 11th international conference on The Semantic Web - Volume Part I10.1007/978-3-642-35176-1_1(1-16)Online publication date: 11-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-35176-1_1
Show More Cited By

View Options

View options

Get Access

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 Issue’s Table of Contents