Updating Direct Graph for Incremental Reasoning in OWL 2 QL Ontology

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 a ected paths for incremental classification. We implement the proposed method in a prototype 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

Graph Theory Notions. We use traditional notions in graph theory. A digraph D consists 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 T C(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 concepts(roles), O |= S 1 ⊑ S 2 i ∃(S 1, S 2) ∈ E(T C(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. 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 di erences between concept axiom additions 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), (Q1−, Q2−), (∃Q1, ∃Q2), (∃Q1−, ∃Q2−) need to be removed. (2) If d(Q1) > 1 and d(Q2) = 1, then, the 4 edges (Q1, Q2), (Q1−, Q2−), (∃Q1, ∃Q2), (∃Q1−, ∃Q2−), and the 4 vertices Q2, Q2−, ∃Q2, ∃Q2− need to be removed. (3) If d(Q1) = 1 and d(Q2) > 1, then, the 4 edges (Q1, Q2),(Q1−, Q2−), (∃Q1, ∃Q2),(∃Q1−, ∃Q2−), and 4 vertices Q1, Q1−, ∃Q1,∃Q1− need to be removed. (4) If d(Q1) = 1 and d(Q2) = 1, then, the 4 edges (Q1, Q2),(Q−, Q2−), (∃Q1, ∃Q2),(∃Q1−, ∃Q2−), 1 and the 8 vertices Q1, Q1−, ∃Q1, ∃Q1−,Q2,Q2−, ∃Q2,∃Q2− are removed. 4

Identifying the A ected 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 a ected paths and recompute the transitive closure of such a ected subdigraph.

Definition 1 (a ected 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 a ected 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 Proposition 1. Let i j be an a ected 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 a ected 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 classification 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/ 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 ontology 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 reclassify 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 M x represents maximum value. Column 3 Number o f A.P.(Av/M x) and 4 S ize o f A.P.(Av/M x) indicates the number of a ected 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 a ected paths and time in re-computing the transitive closure of all the a ected 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 exploiting digraph algorithm, which allows us to e ciently identify the small a ected 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 ontologybased 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 .