Research On Parallel Reasoning Techniques Of OWL 2 EL

OWL 2 EL is a tractable fragment of OWL 2. Due to its sufficient expressive power and relatively low computation complexity, EL has gained more and more attention of researchers and the industry. On-tology reasoning techniques play an important role in many EL applications. Classification, which is the task of computing a subsumption hierarchy between concepts, is the most fundamental reasoning task for EL ontologies.Among the state-of-the-art reasoners and reasoning algorithms for EL, the serial reasoner CEL does not perform very well on large ontologies; the ELK reasoner, which is based on Java concurrency, is restricted to the main memories of the utilized machines; the parallel algorithms which are designed based on the MapRe-duce model are practically not efficient due to large amounts of redundant computation and I/O overhead of the concrete computation frameworks. To overcome the deficiencies of the above reasoners and algorithms, we propose parallel algorithms for EL reasoning based on Pregel. Our contributions are as follows:(1) We Propose a method for transforming an EL ontology into a directed and labeled graph, and prove the semantical equivalence of an EL ontology and its corresponding graph representation. A basic algorithm for EL ontology reasoning based on the graph representation is proposed. It is proved that the algorithm terminates in polynomial time, and is sound and complete.(2) Based on the graph representation of EL ontologies and the basic reasoning algorithm, we propose two parallel reasoning algorithms for the classification task using Pregel model, and prove the termination, correctness and completeness of the two algorithms. One algorithm adopts the request-answer method, the other adopts the push method. Both request-answer method and push method can effectively solve the problem of lack of edge information of a vertex.(3) The proposed parallel algorithms are implemented and tested on large-scale ontologies. Experimental results show that our proposed two parallel reasoning algorithms have superior efficiency and favorable speed-up. We also discuss the factors that influence reasoning time by experiments.