Updating Direct Graph for Incremental Reasoning in OWL 2 QL Ontology Changlong Wang1,2 , Zhiyong Feng1 , Xin Wang1 ,Guozheng Rao1 ,Xiaowang Zhang1 1 School of Computer Science and Technology, Tianjin University,Tianjin 300072, China, 2 School of Computer Science and Engineer Technology, NWNU,Lanzhou 730070, China, Abstract. We propose an incremental reasoning approach to QL ontologies by mapping an evolving ontology to an updatable digraph and maintaining dynamic transitive closure to obtain incremental classification. We describe the procedure of updating ontology digraph and present an approach to identify the affected paths for incremental classification. We implement the proposed method in a pro- totype incR and evaluated it on widely-used ontologies. The experiments show that our approach can lead to performance gain. Keywords: Ontology; Incremental Reasoning; Direct Digraph 1 Introduction Existing incremental reasoning techniques mainly focused on ontologies in OWL 2 and its profiles OWL 2 EL and OWL 2 RL [1–3]. In recent years, OWL 2 QL ontolo- gies have become increasingly important in Ontology-Based Data Access (OBDA) [4]. However, to the best of our knowledge, there exists no incremental classification ap- proach or implementation tailored to QL ontologies. In this paper, we close this gap by extending the graph-based approach for static QL ontolgoies in [5]. 2 Preliminaries Graph Theory Notions. We use traditional notions in graph theory. A digraph D con- sists of a non-empty finite vertex set V(D) and edge set E(D). The degree of a vertex v is denoted by d(v). A path p is a sequence p=v1 , v2 , ..., vk of distinct vertices in V(D), such that for every vi , vi+1 ∈ p, (vi , vi+1 ) ∈ E(D). A path from u to v is denoted with u v. The size of path p is represented by the number of edges contained in p. The number of distinct paths u v is denoted by Paths(u, v). We use TC(D) to denote the transitive closure of a digraph D. Digraph Representation of QL 2 Ontology. The idea of digraph representation of a QL ontology is that, given an OWL 2 QL ontology O and its digraph DO , each vertex v ∈ V(DO ) represents a basic concept(role). Let S 1 and S 2 be two atomic concept- s(roles), O |= S 1 ⊑ S 2 iff ∃(S 1 , S 2 ) ∈ E(TC(DO )). Please refer to [5] for details. We use L(α) (resp. R(α)) to denote the basic concept or basic role on the left (resp. right) sides of α. we also use d(L(α)) or d(R(α)) to represent degree of the corresponding vertex. For an axiom of the form Q1 ⊑ Q2 , we use d(Q1 ) and d(Q2 ) to represent the degrees of Q1 and Q2 , respectively. 2 C. Wang, Z. Feng, G. Rao, X. Wang, X. Zhang Table 1. Test ontologies Ontology DL ♯A.C. ♯A.R. ♯Ont T QUONT Mouse ALE 2753 1 3463 0.104 Gene SH 26225 4 42655 1.236 EL-Galen ALCH(D) 23136 950 97811 3.528 FMA-OBO ALE 75139 2 119558 4.723 3 Updating Digraph When an axiom is added to an ontology, it is easy to update the corresponding digraph. Let O be an ontology and α+ be an added axiom, if the basic concepts and basic roles in α+ are already contained in O, we only insert edge(s) into DO ; if α+ contains new basic concepts and basic roles, we insert vertex and edge(s) according to Definition 2 in [5]. Axiom deletions are complicated and discussed in details as follows: From Definition 2 in [5], there exist some differences between concept axiom addi- tions and role axiom additions. Let α− be a deleted axiom, we consider two cases : — Case 1: α− is a concept inclusion. (1) If d(L(α− )) > 1 and d(R(α− )) > 1, then, only the edge (L(α− ), R(α− )) is removed. (2) If d(L(α− )) > 1 and d(R(α− )) = 1, then, the edge (L(α− ), R(α− )) and its head are removed. (3) If d(L(α− )) = 1 and d(R(α− )) > 1, then, the edge (L(α− ), R(α− )) and its tail are removed. (4) If d(L(α− ))) = 1 and d(R(α− )) = 1, then, the edge (L(α− ), R(α− )) is removed, both its tail and head are removed. — Case 2: α− is a role inclusion axiom of the form Q1 ⊑ Q2 . (1) If d(Q1 ) > 1 and d(Q2 ) > 1, then, the 4 edges (Q1 , Q2 ), (Q−1 , Q−2 ), (∃Q1 , ∃Q2 ), (∃Q−1 , ∃Q−2 ) need to be removed. (2) If d(Q1 ) > 1 and d(Q2 ) = 1, then, the 4 edges (Q1 , Q2 ), (Q−1 , Q−2 ), (∃Q1 , ∃Q2 ), (∃Q−1 , ∃Q−2 ), and the 4 vertices Q2 , Q−2 , ∃Q2 , ∃Q−2 need to be removed. (3) If d(Q1 ) = 1 and d(Q2 ) > 1, then, the 4 edges (Q1 , Q2 ),(Q−1 , Q−2 ), (∃Q1 , ∃Q2 ),(∃Q−1 , ∃Q−2 ), and 4 vertices Q1 , Q−1 , ∃Q1 ,∃Q−1 need to be removed. (4) If d(Q1 ) = 1 and d(Q2 ) = 1, then, the 4 edges (Q1 , Q2 ),(Q−1 , Q−2 ), (∃Q1 , ∃Q2 ),(∃Q−1 , ∃Q−2 ), and the 8 vertices Q1 , Q−1 , ∃Q1 , ∃Q−1 ,Q2 ,Q−2 , ∃Q2 ,∃Q−2 are removed. 4 Identifying the Affected Path for Incremental Classification An edge addition (deletion) into (from) digraph may change the number of path i j. It is necessary to identify those affected paths and recompute the transitive closure of such affected subdigraph. Definition 1 (affected path). Given a digraph DO containing vertices i, j, u, v, and path i j, if the number of i j changes after an edge (u, v) is inserted (removed) into (from) DO , the path i j is called affected path. When we add (delete) axioms, no cycles is created in the corresponding digraph DO . From Lemma 3.1 in [6], the following proposition holds: Updating Direct Graph for Incremental Reasoning in OWL 2 QL Ontology 3 Table 2. IncR VS.Pellet.Time in seconds Ontology n Number o f A.P.(Av/Mx) S ize o f A.P.(Av/Mx) T IncR(Av/Mx) T Pellet (Av/Mx) mouse 1 96/321 148/431 0.002/0.032 0.021/0.039 mouse 2 164/404 170/518 0.003/0.043 0.044/0.063 mouse 4 225/664 274/673 0.006/0.061 0.068/0.072 mouse 8 452/811 471/831 0.013/0.084 0.082/0.095 Gene 1 23/71 42/79 0.006/0.182 0.029/0.191 Gene 2 58/104 63/119 0.112/0.243 0.357/0.489 Gene 4 76/164 98/294 0.128/0.302 0.432/0.764 Gene 8 149/394 219/438 0.363/0.414 0.927/1.014 EL-Galen 1 213/871 432/968 0.018/0.211 0.698/1.164 EL-Galen 2 486/1004 586/1484 0.024/0.298 0.835/2.718 EL-Galen 4 869/1864 1076/2038 0.217/0.393 1.107/2.973 EL-Galen 8 327/714 1482/3752 0.572/0.819 1.328/3. 219 FMA-OBO 1 45/89 83/174 0.007/0.131 0.012/0.275 FMA-OBO 2 69/127 192/387 0.148/0.573 0.726/0.915 FMA-OBO 4 136/259 293/653 0.152/0.512 0.759/1.416 FMA-OBO 8 283/894 461/934 0.263/0.748 1.663/1.943 Proposition 1. Let i j be an affected path after the edge (u, v) is inserted (or deleted), the number of the paths i j increases (or decreases) by Paths(i, u) ∗ Paths(v, j). In ontology development, a domain engineer often adds (or deletes) a set of axioms related to a certain concept (role). Such modification will lead to a changed set of edges incident to a common vertex and more affected paths in the corresponding digraph. Proposition 2 [6] Let DO be a digraph and Ev be a updating set of edges incident to a common vertex v, let ∆Paths(i, j) be the change to Paths(i, j), ∆Paths(i, j) ← Paths(i, v) ∗ ∆Paths(v, j) + ∆Paths(i, v) ∗ Paths(v, j) + ∆Paths(i, v) ∗ ∆Paths(v, j). From above discussion, it is feasible to design an algorithm for incremental classifi- cation in QL ontologies. Give a digraph D and any two vertices i, j ∈ D, the number of the path i j can be represented by an n × n adjacency matrix Q such that Q(i, j) = 0 if there exists no path from i to j. The transitive closure of a digraph D is presented by an n × n adjacency matrix MD∗ such that MD∗ (i, j)=1 if Q(i, j) , 0, else MD∗ (i, j)=0. While updating the digraph, if Q(i, j) increases from 0, MD∗ (i, j)=1, if Q(i, j) decreases to 0, MD∗ (i, j)=0. 5 Implementation and Evaluation We implement our approach in IncR. We perform experiments to compare IncR with QUONTO [4] and Pellet [1]—QUONT supports the graph-based approach in [5] and Pellet supports module-based incremental classification [1]. We select 4 widely-used ontologies from Bioportal 1 , of which the EL-Galen falls out of OWL 2 QL and need to be approximated by a QL ontology. Table 1 provides 1 http://bioportal.bioontology.org/ 4 C. Wang, Z. Feng, G. Rao, X. Wang, X. Zhang basic information: the DL language , the number of atomic concept and role, the size of ontology. The last column of Table 1 presents the time in seconds taken by QUONTO. In order to compare IncR with Pellet, we use similar experimental methodology in [1]: for various values of n, 1) remove n random axioms; 2) classify the resulting ontol- ogy using IncR and Pellet ; then, we repeat the following steps 30 times: 3) randomly remove an additional n axioms, add back the previously removed n axioms, and reclas- sify the ontology using IncR and Pellet. All the results are gathered during step 3) of the experiment. All tests are performed on a server with Intel Xeon E5620 2.40GHz CPU, running Windows Server 2008 R2 Enterprise and Java 1.7 with 16GB of RAM available to JVM. Table 2 summarizes the results of our experiments for n=1,2,4 and 8, where Av means average value and Mx represents maximum value. Column 3 Number o f A.P.(Av/Mx) and 4 S ize o f A.P.(Av/Mx) indicates the number of affected paths and their total size, respectively. Colomn 5 shows the time spent in maintaining the transitive closure of the updated digraph, the time value includes time spent in identifying affected paths and time in re-computing the transitive closure of all the affected paths. The last column provides the time taken to classify those updated ontologies by Pellet. 6 Conclusion We have proposed an approach to incremental classification in QL ontology by exploit- ing digraph algorithm, which allows us to efficiently identify the small affected paths and to reuse previous computation. We demonstrate the performance gain indicated by the significant reduction of classification time. As a big challenge in the future, we will develop a parallel version of our method to exploit many cores/CPUs available in modern systems. Acknowledgments. This work is supported by the NSFC (61100049,61373165) and the 863 Program of China (2013AA013204). References 1. Grau B. C., Wiener C. H., Kazakov Y.,et al.: Incremental classification of description logics ontologies. J. of Automated Reasoning. 44(4), 337-369, 2010. 2. Kazakov Y., Klinov P.: Incremental reasoning in OWL EL without bookkeeping. In ISWC, 232-247, 2013. 3. Motik B., Nenov Y., Piro R., Horrocks I.: Incremental update of datalog materialisation : the backward/forward algorithm. In AAAI, 1560-1568, 2015. 4. Calvanese D., Giacomo G. D., Lembo D., Lenzerini M.,et al.: The mastro system for ontology- based data access. Semantic Web, 2(1), 43-53, 2011. 5. Domenico L., Santarelli V., Savo D. F.: A graph-based approach for classifying owl 2 QL ontologies. In Description logic, 747-759, 2013. 6. King, Valerie, Garry Sagert: A fully dynamic algorithm for maintaining the transitive closure. In STOC, 492-498, 1999.