=Paper=
{{Paper
|id=Vol-1690/paper64
|storemode=property
|title=Structure-guiding Modular Reasoning for Expressive Ontologies
|pdfUrl=https://ceur-ws.org/Vol-1690/paper64.pdf
|volume=Vol-1690
|authors=Changlong Wang,Xiaowang Zhang,Zhiyong Feng
|dblpUrl=https://dblp.org/rec/conf/semweb/WangZF16
}}
==Structure-guiding Modular Reasoning for Expressive Ontologies==
https://ceur-ws.org/Vol-1690/paper64.pdf
Structure-guiding Modular Reasoning for Expressive
Ontologies
Changlong Wang1,3,4 , Xiaowang Zhang1,3 , and Zhiyong Feng2,3,∗
1
School of Computer Science and Technology, Tianjin University, Tianjin, China
2
School of Software, Tianjin University, Tianjin, China
3
Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin, China
4
School of Computer Science and Engineer Technology, NWNU, Lanzhou, China
∗ Corresponding author
Abstract. We propose a technique that combine an OWL 2 EL reasoner with an
OWL 2 reasoner to classify expressive ontologies. We exploit the information im-
plied by the ontology structure to identify a small non-EL ontology that contains
necessary axioms to ensure the completeness. In the process of ontology classifi-
cation, the bulk of workload is delegated to an efficient OWL 2 EL reasoner and
the small part of workload is handled by a less efficient OWL 2 reasoner. Experi-
mental results show that our approach leads to a reasonable task assignment and
offers a substantial speedup in ontology classification.
1 Introduction
In practical applications, many commonly used ontologies are covered by the OWL 2
EL to a large degree, e.g., of the 226038 axioms in the version V14.03e of NCI ontology,
only 67 are outside the OWL 2 EL fragment. The tableau-based OWL 2 reasoners are
able to reasoning such ontologies, but they are not efficient due to the high complexity
of tableau algorithms for expressive ontologies. The profile-specific OWL 2 EL rea-
soners are efficient, but they become incomplete if the ontologies contain axioms that
are outside the OWL 2 EL fragment. Recently, new approaches have been proposed
to improve the reasoning performance for expressive ontologies by combining differ-
ent reasoners [1, 2]. However, the approach [1] needs to represent an ontology in the
decomposed form [3] and the modular reasoner MORe [2] is less efficient because it
delegates much work to the inefficient tableau-based OWL 2 reasoner. In this study, we
exploit the information implied by the ontology structure [3] to identify a small non-EL
subontology that is handled by a less efficient OWL 2 reasoner.
2 Preliminaries
Description Logic Ontology. In this paper, we focus on ontologies expressed in OWL
2 and its profile OWL 2 EL underpinned by description logics (DLs) SROIQ and EL++ ,
respectively [4]. We refer to individuals, atomic concepts, and atomic roles by calling
them terms. A set of terms is called a signature. We use O for a DL ontology, M (M ⊆
O) for a module, and use eα (resp. O
e )for the signature in an axiom α (resp. O)
2 Changlong Wang, Xiaowang Zhang, and Zhiyong Feng
Ontology Structure Induced by Modules. A module is a subset of an ontology that
captures all the knowledge about a specified signature Σ. The ⊥-module is one basic
type of locality-based modules (LBMs) and enjoys the following property that can be
used for optimising classification [5]:
Proposition 1. Let O be a SROIQ ontology, A, B concept names in O, e Σ ⊆ O e with
A ∈ Σ, and M a ⊥-module in O w.r.t. Σ. Then O |= A v B if and only if M |= A v B.
A ⊥-module w.r.t. Σ is denoted by MΣ⊥ . Different axioms might lead to the same
module due to the strong logical interrelation among axioms, such axioms that “cling
together” is formalised by the notion of atom [3]:
Definition 1. Given an ontology O, and an axiom set at={α1 , α2 , ..., αn } ⊆ O, if Mαf
⊥
1
=
Mαf2 =,...,= Mαfn , and for any β ∈ O \ at,Me , Mαei (i=1,2,...,n). then at is called an
⊥ ⊥ ⊥ ⊥
β
⊥-atom, denoted by at⊥ .
For any module, it either contains all axioms in an atom or none of them. The family
of atoms of O is denoted by AD⊥O . For each atom at ∈ AD⊥O , the module Ma⊥et is denoted
by Mat and the dependent relation between atoms is induced as follows:
Definition 2. Let at1 and at2 be two atoms in AD⊥O , at1 is dependent on at2 (written
at1 at2 ) if Mat2 ⊆ Mat1 .
The atomic decomposition (AD) of an ontology O is a pair (AD⊥O , ), denoted by
ADO, , in which AD⊥O is the set of atoms and is a partial order over those atoms. The
⊥
union of all atoms on which a given atom at depends is called principal ideal of at
( denoted by (at] ).
Proposition 2. [3] Let at be an atom in AD⊥O, , the principal ideal (at] is a module.
Proposition 3. [3, Remark 3.10] For each atom at, Mat coincides with (at] and Mat is
the smallest module containing at.
An atom ati is called a top atom if there exists no a distinct atom at j such that
at j ati . Hence an ontology O is the union of several independent modules:
[
O= {(tat] | tat is a top atom} (1)
3 Modular Reasoning
AD represents the modular structure of an ontology, the information implied by this
structure (especially Proposition 2, Proposition 3, and Equation 1) provide us with two
important clues for optimising modular classification: Firstly, for two distinct atoms
at1 and at2 with at1 at2 , (at2 ] is enough to completely classify all the classed in the
module (at2 ]. Secondly, if not each top atom contains non-EL axioms, it is possible to
identify a small non-El module and delegate it to an OWL 2 reasoner for computing
the subsumption relation of the following form: (1) A v B (2) A u B v C (3) A v
Structure-guiding Modular Reasoning for Expressive Ontologies 3
Algorithm 1 modularClassification
Input: an ontology O
Output: HO : the classification of O
1: MEL ← ∅, H MEL ← ∅, HO ← ∅
2: for each α ∈ S na do
3: if α < MEL then
MEL ← MEL Mα // computing the non-EL subontology
S
4:
5: end if
6: end for
7: if MEL = O then
8: HO ←AR.classify(O)
9: else
10: H MEL ←AR.classify(MEL ) //classifying the non-EL subontology
11: HO ← MR.classify(H MEL ∪ O \ MEL )
12: end if
13: return HO
∃R.B (4) ∃R.A v B (5) R v S (6) A u ∃R.B v C (7) ∃R.A u ∃S .B v C
where A, B, and C are atomic concepts or >, and R, S atomic roles. Obviously, these
subsumption relations fall into OWL 2 EL. Hence, the computed subsumption relations
together with the remaining EL part can be handled by an OWL 2 EL reasoner to obtain
complete classification. Let S na be the set of non-EL axioms in an ontology, Algorithm
1 describes the process of classifying OWL 2 ontologies in a modular manner, where
AR (Assistant Reasoner) stands for an OWL 2 reasoner and MR (Main Reasoner) for
an OWL 2 EL reasoner.
4 Experiment and Evaluation
The proposed approach is implemented in a prototype SGMR in which the OWL 2
reasoner and OWL 2 EL reasoner are integrated in a black-box manner. We conduct an
experiment on eight commonly used ontologies available from the NCBO BioPortal on-
tology repository 5 . Table 1 provides statistics of test ontologies and Table 2 shows the
experimental results compared with MORe. In Table 2, M MORe (resp. MEL ) represents
the non-EL subontology that is delegated to the OWL 2 reasoner in MORe (resp. SGM-
R), and T MORe (resp. T S GMR ) represents the time (in seconds) spent in classifying the
whole ontology by MORe (resp. SGMR). In our experiments, ELK 0.4.1 and HermiT
1.3.86 are used as OWL 2 EL reasoner and OWL 2 reasoner, respectively. The experi-
mental results show that SGMR delegates a smaller part of workload to the inefficient
OWL 2 reasoner and obtain a substantial speedup compared with MORe.
5 Conclusion
In this paper, we present approach to classifying SROIQ ontologies by combining an
OWL 2 EL with an OWL 2 reasoner. Compared with our previous work [1], we do
5
http://bioportal.bioontology.org
6
https://www.cs.ox.ac.uk/isg/tools/
4 Changlong Wang, Xiaowang Zhang, and Zhiyong Feng
Table 1. Test ontology metrics: number of classes (C), number of roles (R), number of axioms
(size), number of non-EL axioms (nonEA), and the DL expressivity (DL)
ontology C R size nonEA DL
SYN 14,462 2 15,353 4 ALF
CSEO 20,085 91 26,540 14 ALCH
Galen 23,141 950 37,696 1,149 SHIF
Dermlex 6,106 18 24,452 16 ALCHF(D)
Protein 35,470 9 46,698 16 SH
NCI 93,413 52 219,224 65 SH(D)
UBERON 18,874 189 48,806 1,296 SRIQ
EFO 17,892 35 25,173 32 ALHI
Table 2. Comparison with MORe on classification time and task assignment.
MORe SGMR
Ontology M MORe T MORe MEL T S GMR
SYN 187 (1.2% ) 12.6 27 (0.8%) 5.1
CSEO 8,693 (32.8% ) 20.3 94 (0.4% ) 4.7
Galen 35,976 (95.4% ) 25.4 2,165 (5.7% ) 3.5
Dermlex 18,347 (75.0% ) 17.2 8,219 (33.6% ) 3.7
Protein 3,972 (8.5% ) 12.6 288 (0.6% ) 1.7
NCI 33,760 (15.4% ) 104.6 7,151 (3.3% ) 17.2
UBERON 14,906 (30.5% ) 76.4 12,988 (26.6% ) 31.4
EFO 7,348 (29.2% ) 64.2 897 (3.6% ) 21.3
not need to represent an ontology in the decomposed form. Compared with MORe, our
approach delegates a smaller workload to the less efficient OWL 2 reasoner hence offers
a substantial speedup in ontology classification.
Acknowledgement. This work is supported by the program of the National Key Re-
search and Development Program of China (2016YFB1000603) and the National Nat-
ural Science Foundation of China (NSFC) (61502336, 61373035). Xiaowang Zhang is
supported by Tianjin Thousand Young Talents Program.
References
1. C. Wang & Z. Feng. A Novel Combination of Reasoners for Ontology Classification. In:
Proc. of ICTAI-13, pp.463–468, 2013.
2. A. Armas Romero, B. Cuenca Grau, & I. Horrocks. MORe: Modular Combination of OWL
Reasoners for Ontology Classification. In:Proc. of ISWC-12, pp. 1–16, 2012.
3. C. Del Vescovo, B. Parsia, U.Sattler, & T. Schneider. The Modular Structure of an Ontology:
Atomic decomposition. In: Proc. of IJCAI-11, pp.2232-2237, 2011.
4. Pascal Hitzler, Markus Krötzsch, & Sebastian Rudolph. Foundations of Semantic Web Tech-
nologies. Chapman and Hall/CRC Press, 2010.
5. B. Cuenca Grau, I. Horrocks, Y. Kazakov, & U. Sattler. Modular Reuse of Ontologies: Theory
and Practice. Journal of Artificial Intelligence Research, 31(1): 273-318, 2008.
6. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., & Patel-Schneider, P. The Description
Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press,
2nd edn. (2007)