ComR: a combined OWL reasoner for ontology classification

Abstract

Ontology classification, the problem of computing the subsumption hierarchies for classes (atomic concepts), is a core reasoning service provided by Web Ontology Language (OWL) reasoners. Although general-purpose OWL 2 reasoners employ sophisticated optimizations for classification, they are still not efficient owing to the high complexity of tableau algorithms for expressive ontologies. Profile-specific OWL 2 EL reasoners are efficient; however, they become incomplete even if the ontology contains only a small number of axioms that are outside the OWL 2 EL fragment. In this paper, we present a technique that combines an OWL 2 EL reasoner with an OWL 2 reasoner for ontology classification of expressive SROIQ. To optimize the workload, we propose a task decomposition strategy for identifying the minimal non-EL subontology that contains only necessary axioms to ensure completeness. During the ontology classification, the bulk of the workload is delegated to an efficient OWL 2 EL reasoner and only the minimal non- EL subontology is handled by a less efficient OWL 2 reasoner. The proposed approach is implemented in a prototype ComR and experimental results show that our approach offers a substantial speedup in ontology classification. For the wellknown ontology NCI, the classification time is reduced by 96.9% (resp. 83.7%) compared against the standard reasoner Pellet (resp. the modular reasoner MORe).

Keywords

OWL / ontology / classification / reasoner

References

[1] Horrocks I, Patel-Schneider P F, van Harmelen F. From SHIQ and RDF to OWL: the making of a web ontology language. Journal of Web Semantics, 2003, 1(1): 7–26

[2] Patel-Schneider P, Hayes P, Horrocks I. Web ontology language OWL abstract ayntax and aemantics. W3C Recommendation, 2004

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

[4] Motik B, Patel-Schneider P F, Cuenca Grau B. OWL 2 Web ontology language direct semantics. W3C Recommendation, 2009

[5] Berners-Lee T, Hendler J, Lassila O. The semantic Web. Scientific American, 2001, 284(5): 28–37

[6] Sidhu A, Dillon T, Chang E, Sidhu B S. Protein ontology development using OWL. In: Proceedings of the 1st Workshops on OWL: Experiences and Directions. 2005

[7] Golbreich C, Zhang S, Bodenreider O. The foundational model of anatomy in OWL: experience and perspectives. Journal of Web Semantics, 2006, 4(3): 181–195

[8] Rector A, Rogers J. Ontological and practical issues in using a description logic to represent medical concept systems: experience from GALEN. In: Proceedings of the 2nd International Summer School on Reasoning Web. 2006, 197–231

[9] Soergel D, Lauser B, Liang A, Fisseha F, Keizer J, Katz S. Reengineering thesauri for new applications: the AGROVOC example. Journal of Digital Information, 2006, 4(4): 1–23

[10] Derriere S, Richard A, Preite-Martinez A. An ontology of astronomical object types for the virtual observatory. In: Proceedings of the 26th meeting of the IAU on Virtual Observatory in Action: New Science, New Technology, and Next Generation Facilities. 2006

[11] Lacy L, Aviles G, Fraser K, Gerber W, Mulvehill A, Gaskill R. Experiences using OWL in military applications. In: Proceedings of the 1st Workshop on OWL: Experiences and Directions. 2005

[12] Goodwin J. Experiences of using OWL at the ordnance survey. In: Proceedings of the 1st Workshop on OWL: Experiences and Directions. 2005

[13] Lécué F, Schumann A, Sbodio M L. Applying semantic web technologies for diagnosing road traffic congestions. In: Proceedings of the 11th International Semantic Web Conference. 2012, 114–130

[14] Lécué F, Tucker R, Bicer V, Tommasi P, Tallevi-Diotallevi S, Sbodio M. Predicting severity of road traffic congestion using semantic Web technologies. In: Proceedings of the 11th Extended Semantic Web Conference. 2014, 611–627

[15] Kazakov Y, Krötzsch M, Simancík F. Concurrent classification of EL ontologies. In: Proceedings of the 10th International Semantic Web Conference. 2011, 305–320

[16] Glimm B, Horrocks I, Motik B, Shearer R, Stoilos G. A novel approach to ontology classification. Journal of Web Semantics, 2011, 14(1): 84–101

[17] Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider P. The description logic handbook: theory, implementation, and applications. Cambridge: Cambridge University Press, 2007

[18] Kazakov Y. RIQ and SROIQ are harder than SHOIQ. In: Proceedings of the 11th International Conference on Knowledge Representation and Reasoning. 2008, 274–284

[19] Horrocks I, Sattler U. A tableau decision procedure for SHOIQ. Journal of Automated Reasoning, 2007, 39(3): 249–276

[20] Motik B, Shearer R, Horrocks I. Hypertableau reasoning for description logics. Journal of Artificial Intelligence Research, 2009, 36: 165–228

[21] Glimm B, Horrocks I, Motik B, Stoilos G, Wang Z. HermiT: an OWL 2 reasoner. Journal of Automated Reasoning, 2014, 53(3): 245–269

[22] Tsarkov D, Horrocks I. FaCT++ description logic reasoner: system description. In: Proceedings of the 3rd International Joint Conference on Automated Reasoning. 2006, 292–297

[23] Haarslev V, Möller R. Racer System description. In: Proceedings of the 1st International Joint Conference on Automated Reasoning. 2001, 701–705

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

[25] Goncalves R S, Parsia B, Sattler U. Performance heterogeneity and approximate reasoning in description logic ontologies. In: Proceedings of the 11th International Semantic Web Conference. 2012, 82–98

[26] Krözsch M. OWL 2 profiles: an introduction to lightweight ontology languages. In: Proceedings of the 8th Reasoning Web Summer School. 2012, 112–183

[27] Baader F, Brandt S, Lutz C. Pushing the EL envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. 2005, 364–369

[28] Harris M A, Clark J, Ireland A. Gene ontology consortium: the gene ontology (GO) database and informatics resource. Nucleic Acids Research, 2004, 32: 258–261

[29] Spackman K A. Rates of change in a large clinical terminology: three years experience with snomed clinical terms. In: Proceedings of the AMIA Annual Symposium. 2005, 714–718

[30] Mendez J, Suntisrivaraporn B. Reintroducing CEL as an OWL 2 EL reasoner. In: Proceedings of the 22nd International Workshop on Description Logics. 2009

[31] Mendez J. JCel: a modular rule-based reasoner. In: Proceedings of the 1st International Workshop on OWL Reasoner Evaluation. 2012, 858

[32] Kazakov Y, Krözsch M, Simani¨ck F. The incredible ELK. Journal of Automated Reasoning, 2014, 53(1): 1–61

[33] Smith B, Ashburner M, Rosse C, Bard J, Bug W, Ceusters W, Goldberg L J, Eilbeck K, Ireland A, Mungall C J, OBI Consortium, Leontis N, Rocca-Serra P, Ruttenberg A, Sanson e S A, Scheuermann R H, Shah N, Whetzel L, Lewis S. The OBO foundry: coordinated evolution of ontologies to support biomedical data integration. Nature Biotechnology, 2007, 25(11): 1251–1255

[34] Sioutos N, De Coronado S, Haber M W, Hartel F W, Shaiu W L, Wright L W. NCI thesaurus: a semantic model integrating cancerrelated clinical and molecular information. Journal of Biomedical Informatics, 2007, 40: 30–43

[35] Armas Romero A, Cuenca Grau B, Horrocks I. MORe: modular combination of OWL Reasoners for ontology classification. In: Proceedings of the 11th International Semantic Web Conference. 2012, 1–16

[36] Tsarkov D, Palmisano I. Divide Et Impera: metareasoning for large ontologies. In: Proceedings of the 9th Internation Workshop on OWL: Experiences and Directions. 2012

[37] Song W, Spencer B, Du W. Complete classification of complex ALCHO ontologies using a hybrid reasoning approach. In: Proceedings of the 26th International Workshop on Description Logics. 2013, 942–961

[38] Steigmiller A, Glimm B, Liebig T. Coupling tableau algorithms for expressive description logics with completion-based saturation procedures. In: Proceedings of the 7th International Joint Conference on Automated Reasoning. 2014, 449–463

[39] Angeli G, Nayak N, Manning G D. Combining natural logic and shallow reasoning for question answering. Technical Report in The Stanford Natural Language Processing Group, 2016

[40] Del Vescovo C, Parsia B, Sattler U, Schneider T. The modular structure of an ontology: atomic decomposition. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 2232–2237

[41] Del Vescovo C, Parsia B, Sattler U. Topicality in logic-based ontologies. In: Proceedings of the 19th International Conference on Conceptual Structures. 2011, 25–29

[42] Del Vescovo C, Parsia B, Sattler U. Logical relevance in ontologies. In: Proceedings of the International Workshop on Description Logics. 2012

[43] Klinov P, Del Vescovo C, Schneider T. Incrementally updateable and persistent decomposition of OWL ontologies. In: Proceedings of the 9th International Workshop on OWL: Experiences and Directions. 2012

[44] Horridge M, Mortensen J M, Parsia B, Sattler U, Musen M A. A study on the atomic decomposition of ontologies. In: Proceedings of the 13th International Semantic Web Conference. 2014, 65–80

[45] Wang C L, Feng Z Y. A novel combination of reasoners for ontology classification. In: Proceedings of the 25th IEEE International Conference on Tools with Artificial Intelligence. 2013, 463–468

[46] Cuenca Grau B, Horrocks I, Kazakov Y, Sattler U. Modular reuse of ontologies: theory and practice. Journal of Artificial Intelligence Researchvol, 2008, 31(1): 273–318

[47] Cuenca Grau B, Halaschek-Wiener C, Kazakov Y, Suntisrivaraporn B. Incremental classification of description logics ontologies. Journal of Automated Reasoning, 2010, 44(4): 337–369

[48] Del Vescovo C, Gessler D D, Klinov P, Parsia B, Sattler U, Schneider T, Winget A. Decomposition and modular structure of bioportal ontologies. In: Proceedings of the 10th International Semantic Web Conference. 2011, 130–145

[49] Del Vescovo C. The Modular structure of an ontology: atomic decomposition and its applications. Dissertation for the Doctoral Degree. Manchester: The University of Manchester, 2013

[50] Simancik F, Kazakov Y, Horrocks I. Consequence-based reasoning beyond horn ontologies. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 1093–1098

[51] Martín-Recuerda F, Walther D. Fast modularisation and atomic decomposition of ontologies using axiom dependency hypergraphs. In: Proceedings of the 13th International Semantic Web Conference. 2014, 49–64

[52] Groot P, Stuckenschmidt H, Wache H. Approximating description logic classification for semantic Web reasoning. In: Proceedings of the 2nd European Semantic Web Conference. 2005, 318–332

[53] Kazakov Y. Consequence-driven reasoning for horn SHIQ ontologies. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence. 2009, 2040–2045

[54] Lembo D, Santarelli V O, Fabio Savo D. A graph-based approach for classifying OWL 2 QL ontologies. In: Proceedings of the 26th International Workshop on Description Logics. 2013, 747–759

[55] Liu Z H, Feng Z Y, Zhang X W, Wang X, Rao G Z. RORS: enhanced rule-based OWL reasoning on Spark. In: Proceedings of the 18th Asia- Pacific Web Conference on Web Technologies and Applications. 2016, 444–448

[56] Liu Z H, Ge W, Zhang X W, Feng Z Y. Enhancing rule-based OWL reasoning on spark. In: Proceedings of the 15th International Semantic Web Conference (Posters & Demonstrations Track). 2016

[57] Wang C L, Feng Z Y, Rao G Z, Wang X, Zhang X W. From datalog reasoning to modular structure of an ontology. In: Proceedings of the 14th International Semantic Web Conference (Posters & Demonstrations Track). 2015

[58] Armas Romero A, Kaminski M, Cuenca Grau B, Horrocks I. Ontology module extraction via datalog reasoning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 1410–1416

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature