1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China 2. Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300072, China 3. School of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China
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).
IHorrocks, P F Patel-Schneider, Fvan Harmelen. From SHIQ and RDF to OWL: the making of a web ontology language. Journal of Web Semantics, 2003, 1(1): 7–26 https://doi.org/10.1016/j.websem.2003.07.001
2
PPatel-Schneider, P Hayes, IHorrocks. Web ontology language OWL abstract ayntax and aemantics. W3C Recommendation, 2004
3
BCuenca Grau, I Horrocks, BMotik, BParsia, P F Patel-Schneider, USattler. OWL 2: the next step for OWL. Journal of Web Semantics, 2008, 6(4): 309–322 https://doi.org/10.1016/j.websem.2008.05.001
4
BMotik, P F Patel-Schneider, BCuenca Grau. OWL 2 Web ontology language direct semantics. W3C Recommendation, 2009
ASidhu, TDillon, EChang, B S Sidhu. Protein ontology development using OWL. In: Proceedings of the 1st Workshops on OWL: Experiences and Directions. 2005
7
CGolbreich, SZhang, OBodenreider. The foundational model of anatomy in OWL: experience and perspectives. Journal of Web Semantics, 2006, 4(3): 181–195 https://doi.org/10.1016/j.websem.2006.05.007
8
ARector, JRogers. 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 https://doi.org/10.1007/11837787_9
9
DSoergel, BLauser, ALiang, F Fisseha, JKeizer, SKatz. Reengineering thesauri for new applications: the AGROVOC example. Journal of Digital Information, 2006, 4(4): 1–23
10
SDerriere, A Richard, APreite-Martinez. 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
LLacy, GAviles, KFraser, W Gerber, AMulvehill, RGaskill . Experiences using OWL in military applications. In: Proceedings of the 1st Workshop on OWL: Experiences and Directions. 2005
12
JGoodwin. Experiences of using OWL at the ordnance survey. In: Proceedings of the 1st Workshop on OWL: Experiences and Directions. 2005
13
FLécué, A Schumann, M LSbodio. Applying semantic web technologies for diagnosing road traffic congestions. In: Proceedings of the 11th International Semantic Web Conference. 2012, 114–130 https://doi.org/10.1007/978-3-642-35173-0_8
14
FLécué, R Tucker, VBicer, PTommasi, S Tallevi-Diotallevi, MSbodio. Predicting severity of road traffic congestion using semantic Web technologies. In: Proceedings of the 11th Extended Semantic Web Conference. 2014, 611–627 https://doi.org/10.1007/978-3-319-07443-6_41
15
YKazakov, M Krötzsch, FSimancík. Concurrent classification of EL ontologies. In: Proceedings of the 10th International Semantic Web Conference. 2011, 305–320
16
BGlimm, I Horrocks, BMotik, RShearer, G Stoilos. A novel approach to ontology classification. Journal of Web Semantics, 2011, 14(1): 84–101
17
FBaader, D Calvanese, DMcGuinness, DNardi, P Patel-Schneider. The description logic handbook: theory, implementation, and applications. Cambridge: Cambridge University Press, 2007 https://doi.org/10.1017/CBO9780511711787
18
YKazakov. RIQ and SROIQ are harder than SHOIQ. In: Proceedings of the 11th International Conference on Knowledge Representation and Reasoning. 2008, 274–284
BMotik, R Shearer, IHorrocks. Hypertableau reasoning for description logics. Journal of Artificial Intelligence Research, 2009, 36: 165–228
21
BGlimm, I Horrocks, BMotik, GStoilos, ZWang. HermiT: an OWL 2 reasoner. Journal of Automated Reasoning, 2014, 53(3): 245–269 https://doi.org/10.1007/s10817-014-9305-1
22
DTsarkov, I Horrocks. FaCT++ description logic reasoner: system description. In: Proceedings of the 3rd International Joint Conference on Automated Reasoning. 2006, 292–297
23
VHaarslev, R Möller. Racer System description. In: Proceedings of the 1st International Joint Conference on Automated Reasoning. 2001, 701–705 https://doi.org/10.1007/3-540-45744-5_59
R SGoncalves, BParsia, USattler. Performance heterogeneity and approximate reasoning in description logic ontologies. In: Proceedings of the 11th International Semantic Web Conference. 2012, 82–98 https://doi.org/10.1007/978-3-642-35176-1_6
26
MKrözsch. OWL 2 profiles: an introduction to lightweight ontology languages. In: Proceedings of the 8th Reasoning Web Summer School. 2012, 112–183 https://doi.org/10.1007/978-3-642-33158-9_4
27
FBaader, SBrandt, CLutz. Pushing the EL envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. 2005, 364–369
28
M AHarris, JClark, AIreland. Gene ontology consortium: the gene ontology (GO) database and informatics resource. Nucleic Acids Research, 2004, 32: 258–261 https://doi.org/10.1093/nar/gkh036
29
K ASpackman. 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
JMendez, B Suntisrivaraporn. Reintroducing CEL as an OWL 2 EL reasoner. In: Proceedings of the 22nd International Workshop on Description Logics. 2009
31
JMendez. JCel: a modular rule-based reasoner. In: Proceedings of the 1st International Workshop on OWL Reasoner Evaluation. 2012, 858
BSmith, M Ashburner, CRosse, JBard, WBug, WCeusters, L J Goldberg, KEilbeck, AIreland, C J Mungall, ConsortiumOBI, NLeontis, P Rocca-Serra, ARuttenberg, e S ASanson, R H Scheuermann, NShah, LWhetzel, SLewis. The OBO foundry: coordinated evolution of ontologies to support biomedical data integration. Nature Biotechnology, 2007, 25(11): 1251–1255 https://doi.org/10.1038/nbt1346
34
NSioutos, S De Coronado, M WHaber, F WHartel, W LShaiu, L WWright. NCI thesaurus: a semantic model integrating cancerrelated clinical and molecular information. Journal of Biomedical Informatics, 2007, 40: 30–43 https://doi.org/10.1016/j.jbi.2006.02.013
35
AArmas Romero, B Cuenca Grau, IHorrocks. MORe: modular combination of OWL Reasoners for ontology classification. In: Proceedings of the 11th International Semantic Web Conference. 2012, 1–16 https://doi.org/10.1007/978-3-642-35176-1_1
36
DTsarkov, I Palmisano. Divide Et Impera: metareasoning for large ontologies. In: Proceedings of the 9th Internation Workshop on OWL: Experiences and Directions. 2012
37
WSong, B Spencer, WDu. 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
ASteigmiller, BGlimm, TLiebig. 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 https://doi.org/10.1007/978-3-319-08587-6_35
39
GAngeli, NNayak, G DManning. Combining natural logic and shallow reasoning for question answering. Technical Report in The Stanford Natural Language Processing Group, 2016
40
CDel Vescovo, BParsia, USattler, T Schneider. The modular structure of an ontology: atomic decomposition. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 2232–2237
41
CDel Vescovo, BParsia, USattler. Topicality in logic-based ontologies. In: Proceedings of the 19th International Conference on Conceptual Structures. 2011, 25–29 https://doi.org/10.1007/978-3-642-22688-5_14
42
CDel Vescovo, BParsia, USattler. Logical relevance in ontologies. In: Proceedings of the International Workshop on Description Logics. 2012
43
PKlinov, C Del Vescovo, TSchneider. Incrementally updateable and persistent decomposition of OWL ontologies. In: Proceedings of the 9th International Workshop on OWL: Experiences and Directions. 2012
44
MHorridge, J M Mortensen, BParsia, USattler, M AMusen. A study on the atomic decomposition of ontologies. In: Proceedings of the 13th International Semantic Web Conference. 2014, 65–80 https://doi.org/10.1007/978-3-319-11915-1_5
45
C LWang, Z YFeng. A novel combination of reasoners for ontology classification. In: Proceedings of the 25th IEEE International Conference on Tools with Artificial Intelligence. 2013, 463–468 https://doi.org/10.1109/ICTAI.2013.75
46
BCuenca Grau, I Horrocks, YKazakov, USattler. Modular reuse of ontologies: theory and practice. Journal of Artificial Intelligence Researchvol, 2008, 31(1): 273–318
47
BCuenca Grau, C Halaschek-Wiener, YKazakov, BSuntisrivaraporn. Incremental classification of description logics ontologies. Journal of Automated Reasoning, 2010, 44(4): 337–369 https://doi.org/10.1007/s10817-009-9159-0
48
CDel Vescovo, D D Gessler, PKlinov, BParsia, U Sattler, TSchneider, AWinget. Decomposition and modular structure of bioportal ontologies. In: Proceedings of the 10th International Semantic Web Conference. 2011, 130–145 https://doi.org/10.1007/978-3-642-25073-6_9
49
CDel Vescovo. The Modular structure of an ontology: atomic decomposition and its applications. Dissertation for the Doctoral Degree. Manchester: The University of Manchester, 2013
50
FSimancik, Y Kazakov, IHorrocks. Consequence-based reasoning beyond horn ontologies. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 2011, 1093–1098
51
FMartín-Recuerda, DWalther. Fast modularisation and atomic decomposition of ontologies using axiom dependency hypergraphs. In: Proceedings of the 13th International Semantic Web Conference. 2014, 49–64 https://doi.org/10.1007/978-3-319-11915-1_4
52
PGroot, H Stuckenschmidt, HWache. Approximating description logic classification for semantic Web reasoning. In: Proceedings of the 2nd European Semantic Web Conference. 2005, 318–332 https://doi.org/10.1007/11431053_22
53
YKazakov. Consequence-driven reasoning for horn SHIQ ontologies. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence. 2009, 2040–2045
54
DLembo, V O Santarelli, DFabio Savo. A graph-based approach for classifying OWL 2 QL ontologies. In: Proceedings of the 26th International Workshop on Description Logics. 2013, 747–759
55
Z HLiu, Z YFeng, X WZhang, X Wang, G ZRao. 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 https://doi.org/10.1007/978-3-319-45817-5_43
56
Z HLiu, WGe, X WZhang, Z Y Feng. Enhancing rule-based OWL reasoning on spark. In: Proceedings of the 15th International Semantic Web Conference (Posters & Demonstrations Track). 2016
57
C LWang, Z YFeng, G ZRao, X Wang, X WZhang. From datalog reasoning to modular structure of an ontology. In: Proceedings of the 14th International Semantic Web Conference (Posters & Demonstrations Track). 2015
58
AArmas Romero, M Kaminski, BCuenca Grau, IHorrocks. Ontology module extraction via datalog reasoning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 1410–1416
