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 challenging 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 Chapter 6). 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 paper 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 NC complexity. The results of the scalable-tractability can be further used to optimize reasoning algorithms and to guide ontology engineers in creating scalingtractable ontologies. To this end, this paper provides the following solutions.
1) This paper 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 paper 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 paper, two important ontology reasoning tasks are studied, materialization and classification. For materialization, this paper studies two ontology languages, DL-Lite and DHL (Description Horn Logic). This paper shows that materialization over any ontology expressed in DL-Litecore or DL-LiteR is scaling-tractable. For DHL, there exist ontologies where materialization can hardly be parallelized. This paper 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.
3) For classification, this paper studies the core language of OWL EL, EL+. In this part, a sub-language ELP of EL+ is first defined. The classification of ELP is proved to be reducible to the materialization of DHL(o). Thus, the restriction of DHL(o) can also guarantee the scalable-tractability of ELP classification. Further, the full EL+ is studied. A new usage restriction is proposed such that the classification of EL+ can be handled by an NC algorithm; in other words, it is scaling-tractable.
4) To verify the practical usability of the above results, several real-world datasets are investigated. This paper then shows that many ontologies belong to the scaling-tractable classes. Based on the results and techniques of scalable-tractability, this paper further proposed 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 paper results in a better performance on scaling-tractable ontologies compared with the test reasoners.