Research On Approaches To Large-scale Ontology Reasoning

The ontology languages RDFS and OWL have been widely used in many real applications.The task of reasoning plays an important role in the services built on ontologies and supports other tasks,like query answering,ontology repairing and inconsistency handling.With a rapid growth of semantic data,it is chal-lenging to conduct the reasoning tasks on large-scale ontologies efficiently.Current work proposes parallel algorithms and employs computing platforms of high-performance to make materialization sufficiently efficient and scalable in practice.However,there do exist ontologies,for which the reasoning tasks cannot always be improved by parallelism(an experiment is set to show it in this thesis).On the other hand,some well-known large-scale ontologies,such as YAGO,have been shown to have good performance for parallel reasoning,but they are expressed in ontology languages that are not scaling-tractable in theory,i.e.,the efficiency of reasoning may not be improved on a parallel implementation.Motivated by the above issue,this thesis attempts to study the problem of scalable-tractability of ontology reasoning from a theoretical perspective.That is,this work aims to identify the ontologies for which the corresponding reasoning task is scaling-tractable,i.e.,in Nick's Class(NC)complexity.The results of the scalable-tractability can be further used to optimize reasoning algorithms and to guide ontology engineers in creating scaling-tractable ontologies.To this end,this thesis provides the following solutions.1)This thesis focuses on datalog rewritable ontology languages,and first studies the scalable-tractability of the datalog reasoning task.Two NC algorithms are proposed in this part.Based on the analysis of these NC algorithms,this thesis further identifies two classes of datalog rewritable ontologies(called scaling-tractable classes)such that reasoning over them is scaling-tractable.2)In the main part of this thesis,two important ontology reasoning tasks are studied,materialization and classification.For materialization,this thesis studies two ontology languages,DL-Lite and DHL(De-scription Horn Logic).This thesis shows that materialization over any ontology expressed in DL-Litecore or DL-Lite-is scaling-tractable.For DHL,there exist ontologies where materialization can hardly be parallelized.This thesis proposes to restrict the usage of DHL such that the restricted ontologies are scaling-tractable,and,further extends the results to a DHL extension DHL(o)that also allows complex role inclusion axioms.Based on the above restrictions,this thesis gives an optimized materialization algorithm.3)For classification,this thesis studies the core language of OWL EL,?L+.In this part,a sub-language?LP of?L+ is first defined.The classification of ?LP is proved to be reducible to the materialization of DHL(o)based on a LogSpace reduction.Thus,the restriction of DHL(o)can also guarantee the scalable-tractability of ?L+ classification.Further,the full ?L+ is studied.A new usage restriction is proposed such that the classification of ?L+ can be handled by an NC algorithm;in other words,it is scaling-tractable.Based on the above restriction,this thesis further gives an optimized classification algorithm.4)To verify the practical usability of the above results,several benchmarks and real-world datasets are inves-tigated.This thesis then shows that many ontologies belong to the scaling-tractable classes.Based on the results and techniques of scalable-tractability,this thesis further proposes optimized parallel algorithms for materialization and classification,and compares them to the state-of-the-art reasoners,i.e.,RDFox,CEL and ELK.The experimental results show that the optimization used in the implementation of this thesis results in a better performance on scaling-tractable ontologies compared with the test reasoners.