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

用于提高描述逻辑推理器可扩展性的优化技术和软件架构

• 批准号: RGPIN-2019-05526
• 负责人: Haarslev, Volker
• 金额: $ 2.48万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715591
• 关键词: Optimization; techniques; software; architectures; improving

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.

提出的研究计划主要关注描述逻辑（DL）推理器的优化技术和软件架构的设计和经验评估。在过去的15年中，由于web本体语言（OWL）是基于深度学习的，深度学习推理受到了语义web社区的关注。OWL是表达能力很强的DL的语法变体。粗略地说，深度学习知识是用概念、角色和个体来描述的，这些概念、角色和个体可以与各种构造器组合在一起。概念描述具有共同属性的个体集合，角色指定个体之间的二元关系。从DL的角度来看，OWL知识库（或本体）可以分为术语知识和断言知识。术语知识（Tbox）由概念和角色公理的有限集合和关于个体的有限断言集合的断言知识（Abox）组成。OWL的概念可满足性问题是已知的N2ExpTime-complete。需要大量的优化技术来加速概念（例如，可满足性，包容），Tboxes（例如，公理转换，分类），个体（例如，实例检查）和abox（例如，一致性，实现，连接查询回答）的推理服务。