Design of optimization techniques and software architectures for description logic reasoners

点击翻译按钮获取中文摘要

The proposed research program is mainly concerned with the design and empirical evaluation of optimization techniques for description logic (DL) reasoners. Over the last decade DL reasoning has gained quite some attention from the semantic web community because the Web Ontology Language, OWL, and its sequel OWL 2 are based on description logics. The DL subset of OWL 2 is a syntactic variant of a well-known and very expressive DL. Roughly speaking DL knowledge is described using concepts, roles, and individuals that can be combined with various constructors. Concepts describe sets of individuals with common properties and roles specify binary relationships between individuals. The concept satisfiability problem for OWL 2 DL is known to be 2-NExpTime-complete. Most reasoners are based on tableau (proof) procedures. The implementation of these calculi requires highly sophisticated optimization techniques due to the structure of the calculi and the inherent time complexity of the inference problems. A large set of tableau optimization techniques needs to be applied to speed up provided inference services and make DL reasoning feasible in practical applications. We propose to continue with our research on the design of optimization techniques and software architectures for DL reasoners with the goal to achieve better scalability even if non-tractable reasoning is required. The major expected outcomes are (i) novel algebraic tableau methods and corresponding optimization techniques that resolve known inefficiencies in standard tableau methods for combinations of OWL 2 DL language features such as qualified cardinality restrictions, nominals, and inverse roles; (ii) new parallel DL reasoning architectures that will support modern multi-processor and multi-core hardware and offer speed improvements that are roughly linear to the number of available cores. The expected outcomes are important for the continued success of ontology development in the semantic web community, especially since the size and complexity of ontologies has often increased in such a way that the time required for (non-tractable) DL reasoning has become a major obstacle.