Abstract

Description Logic has become one of the primary knowledge representation and reasoning methodologies during the last twenty years. A lot of areas are benefiting from description logic based technologies. Description logic reasoning algorithms and a number of optimization techniques for them play an important role and have been intensively researched.

However, few of them have been systematically investigated in a concurrency context in spite of multi-processor computing facilities growing up. Meanwhile, semantic web, an application domain of description logic, is producing vast knowledge data on the Internet, which needs to be dealt with by using scalable solutions. This situation requires description logic reasoners to be endowed with reasoning scalability.

This research introduced concurrent computing in two aspects: classification, and tableau-based description logic reasoning.

Classification is a core description logic reasoning service. Over more than two decades many research efforts have been devoted to optimizing classification. Those classification optimization algorithms have shown their pragmatic effectiveness for sequential processing. However, as concurrent computing becomes widely available, new classification algorithms that are well suited to parallelization need to be developed. This need is further supported by the observation that most available OWL reasoners, which are usually based on tableau reasoning, can only utilize a single processor. Such an inadequacy often leads users working in ontology development to frustration, especially if their ontologies are complex and require long processing times.

Classification service finds out all named concept subsumption relationships entailed in a knowledge base. Each subsumption test enrolls two concepts and is independent of the others. At most n^2 subsumption tests are needed for a knowledge base which contains n concepts. As the first contribution of this research, we developed an algorithm and a corresponding architecture showing that reasoning scalability can be gained by using concurrent computing.

Further, this research investigated how concurrent computing can increase performance of tableau-based description logic reasoning algorithms. Tableau-based description logic reasoning decides a problem by constructing an AND-OR tree. Before this research, some research has shown the effectiveness of parallelizing processing disjunction branches of a tableau expansion tree. Our research has shown how reasoning scalability can be gained by processing conjunction branches of a tableau expansion tree.

In addition, this research developed an algorithm, merge classification, that uses a divide and conquer strategy for parallelizing classification. This method applies concurrent computing to the more efficient classification algorithm, top-search & bottom-search, which has been adopted as a standard procedure for classification. Reasoning scalability can be observed in a number of real world cases by using this algorithm.