Optimization techniques and software architectures for improving scalability of description logic reasoners

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

The proposed research program is mainly concerned with the design and empirical evaluation of optimization techniques and software architectures for description logic (DL) reasoners. Over the last 15 years DL reasoning has gained attention from the semantic web community because the Web Ontology Language (OWL) is based on DL. OWL is a syntactic variant of a 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. From a DL point of view an OWL knowledge base (or ontology) can be divided into terminological and assertional knowledge. The terminological knowledge (Tbox) consists of a finite set of concept and role axioms and assertional knowledge (Abox) of a finite set of assertions about individuals. The concept satisfiability problem for OWL is known to be N2ExpTime-complete. A multitude of optimization techniques are required to speed up inference services for concepts (e.g., satisfiability, subsumption), Tboxes (e.g., axiom transformation, classification), individuals (e.g., instance checking), and Aboxes (e.g., consistency, realization, conjunctive query answering). The first objective is to improve reasoning scalability by adapting parallelization or distribution techniques. These techniques are well suited in cases where reasoning remains expensive. The proposed architectures employ (i) thread-level parallelism for DL reasoning algorithms that can be executed in parallel but usually share common data structures or (ii) distributed approaches applying a divide-and-conquer scheme where reasoning tasks can be partitioned into independent subproblems. Over the last four years we developed a very promising approach for parallelizing OWL ontology classification with a scalability that is linear to the number of available processing units. It is planned to further extend this approach and develop other approaches based on distributed processing. The second objective is to develop novel calculi and optimization techniques for DL language elements such as number restrictions, nominals, and inverse roles. These three elements can impose implicit cardinality constraints on sets of individuals and in this context most known DL reasoning algorithms do not scale. Over the past decade my research group has coined the algebraic DL reasoning approach, which combines traditional reasoning algorithms that are tableau or consequence-based with integer linear programming. Such algebraic reasoning approaches have shown to be superior because implicit cardinality constraints on sets can be encodes as integer linear inequalities and solved efficiently. The scalability of algebraic reasoning has been improved by integrating column generation and branch-and-price techniques. The goal is to extend these techniques further and improve their scalability.