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

建议的研究计划主要关注的设计和经验评估的优化技术和软件架构的描述逻辑（DL）推理机。在过去的15年里，深度学习推理得到了语义Web社区的关注，因为Web本体语言（OWL）是基于深度学习的。OWL是一个表达能力很强的DL的语法变体。粗略地说，深度学习知识是使用概念、角色和个体来描述的，这些概念、角色和个体可以与各种构造器相结合。概念描述具有共同属性的个体集合，角色指定个体之间的二元关系。从深度学习的角度来看，OWL知识库（或本体）可以分为术语知识和断言知识。术语知识（Tbox）由概念和角色公理的有限集合和关于个体的断言的有限集合的断言知识（Abox）组成。OWL的概念可满足性问题被称为N2 ExpTime-complete。需要多种优化技术来加速概念的推理服务（例如，可满足性、包容性）、Tboxes（例如，公理变换、分类），个体（例如，实例检查），和Aboxes（例如，一致性、实现、合取查询应答）。 第一个目标是通过适应并行化或分布式技术来提高推理的可扩展性。这些技术非常适合推理仍然昂贵的情况。所提出的架构采用（i）线程级并行DL推理算法，可以并行执行，但通常共享共同的数据结构，或（ii）分布式方法应用分而治之的方案，推理任务可以划分为独立的子问题。在过去的四年中，我们开发了一个非常有前途的方法，并行OWL本体分类的可扩展性，是线性的可用处理单元的数量。计划进一步扩展这一方法，并开发基于分布式处理的其他方法。 第二个目标是开发新的演算和优化技术DL语言元素，如数量限制，名词和逆角色。这三个元素可以对个体集合施加隐式基数约束，并且在这种情况下，大多数已知的DL推理算法不具有可扩展性。在过去的十年里，我的研究小组创造了代数DL推理方法，它将基于表或结果的传统推理算法与整数线性规划相结合。这种代数推理方法已被证明是上级，因为集合上的隐式基数约束可以被编码为整数线性不等式并有效地求解。代数推理的可扩展性已通过集成列生成和分支和价格技术得到改善。我们的目标是进一步扩展这些技术并提高其可扩展性。

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.