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

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

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.**